Cover Image

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Buhrman, Harry, Helsen, Jonas, Weggemans, Jordi
Format:	Preprint
Published:	2024
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
by: Weggemans, Jordi, et al.
Published: (2023)

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
by: Cade, Chris, et al.
Published: (2022)

Finding quantum partial assignments by search-to-decision reductions
by: Weggemans, Jordi
Published: (2024)

Lower Bounds for Unitary Property Testing with Proofs and Advice
by: Weggemans, Jordi
Published: (2024)

Formal Framework for Quantum Advantage
by: Buhrman, Harry, et al.
Published: (2025)

Improved Hardness Results for the Guided Local Hamiltonian Problem
by: Cade, Chris, et al.
Published: (2022)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

Provable and Verifiable Quantum Advantage in Sample Complexity
by: Benedetti, Marcello, et al.
Published: (2025)

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

Single-copy stabilizer testing
by: Hinsche, Marcel, et al.
Published: (2024)

Beating the natural Grover bound for low-energy estimation and state preparation
by: Buhrman, Harry, et al.
Published: (2024)

Multi-Prover Interactive Proof Systems with Leakage
by: Asadi, Vahid R., et al.
Published: (2026)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
by: Waite, Gabriel
Published: (2025)

Permutation tests for quantum state identity
by: Buhrman, Harry, et al.
Published: (2024)

Commuting Local Hamiltonians Beyond 2D
by: Bostanci, John, et al.
Published: (2024)

On the Complexity of the Succinct State Local Hamiltonian Problem
by: Waite, Gabriel, et al.
Published: (2025)

Physically-Motivated Guiding States for Local Hamiltonians
by: Waite, Gabriel, et al.
Published: (2025)

Complexity Classification of Product State Problems for Local Hamiltonians
by: Kallaugher, John, et al.
Published: (2024)

The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
by: Waite, Gabriel, et al.
Published: (2025)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
by: Grewal, Sabee, et al.
Published: (2025)

On the Complexity of Pure-State Consistency of Local Density Matrices
by: Kamminga, Jonas, et al.
Published: (2024)

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
by: Mataraarachchi, Ranitha, et al.
Published: (2026)

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control
by: Krovi, Hari
Published: (2024)

Quantum advantage from random geometrically-two-local Hamiltonian dynamics
by: Quek, Yihui
Published: (2025)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
by: Aggarwal, Divesh, et al.
Published: (2025)

Modifications of Quantum Computation and Adaptive Queries to PP
by: Miloschewsky, David, et al.
Published: (2025)

Unconditional and exponentially large violation of classicality
by: Benedetti, Marcello, et al.
Published: (2025)

The Complexity of Stoquastic Sparse Hamiltonians
by: Grilo, Alex B., et al.
Published: (2026)

On classical advice, sampling advice and complexity assumptions for learning separations
by: Pérez-Guijarro, Jordi
Published: (2024)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
by: Delavenne, Hugo, et al.
Published: (2024)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
by: He, Kun, et al.
Published: (2018)

SAT, Gadgets, Max2XOR, and Quantum Annealers
by: Ansótegui, Carlos, et al.
Published: (2024)

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
by: Hiromasa, Ryo, et al.
Published: (2022)

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
by: Chen, Kean, et al.
Published: (2024)

Entanglement-Dependent Error Bounds for Hamiltonian Simulation
by: Kulkarni, Prateek P.
Published: (2026)

Ideals, Macaulay Bases, and PCPs
by: Amireddy, Prashanth, et al.
Published: (2025)

Hamiltonian Locality Testing via Trotterized Postselection
by: Kallaugher, John, et al.
Published: (2025)

Circuit-to-Hamiltonian from tensor networks and fault tolerance
by: Anshu, Anurag, et al.
Published: (2023)