Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2411.00946

Classical versus quantum queries in quantum PCPs with classical proofs

Harry Buhrman, François Le Gall, Jordi R. Weggemans

Published Nov 1, 2024• 0 citations
arXivHTMLPDF

Abstract

We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for $q$ quantum queries to a polynomially-sized classical proof ($\mathsf{QCPCP}_{Q,c,s}[q]$). Exploiting a connection with the polynomial method, we prove that for any constant $q$, promise gap $c-s = Ω(1/\text{poly}(n))$ and $δ>0$, we have $\mathsf{QCPCP}_{Q,c,s}[q] \subseteq \mathsf{QCPCP}_{1-δ,1/2+δ}[3] \subseteq \mathsf{BQ} \cdot \mathsf{NP}$, where $\mathsf{BQ} \cdot \mathsf{NP}$ is the class of promise problems with quantum reductions to an $\mathsf{NP}$-complete problem. Surprisingly, this shows that we can amplify the promise gap from inverse polynomial to constant for constant query quantum-classical PCPs, and that any quantum-classical PCP making any constant number of quantum queries can be simulated by one that makes only three classical queries. Nevertheless, even though we can achieve promise gap amplification, our result also gives strong evidence that there exists no constant query quantum-classical PCP for $\mathsf{QCMA}$, as it is unlikely that $\mathsf{QCMA} \subseteq \mathsf{BQ} \cdot \mathsf{NP}$, which we support by giving oracular evidence. In the (poly-)logarithmic query regime, we show for any positive integer $c$, there exists an oracle relative to which $\mathsf{QCPCP}[\mathcal{O}(\log^c n)] \subsetneq \mathsf{QCPCP}_Q[\mathcal{O}(\log^c n)]$, contrasting the constant query case where the equivalence of both query models holds relative to any oracle. Finally, we connect our results to more general quantum-classical interactive proof systems.

DOI
10.48550/arxiv.2411.00946

Related papers

A Relativizing MIP for BQP

Scott Aaronson, Anand Natarajan, Avishay Tal +1 more

Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\mathsf{IP}$ for $\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.

quant-pharXiv:2604.11952•Apr 15, 2026•0 citations

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

Harry Buhrman, Jonas Helsen, Jordi R. Weggemans

We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Hamiltonian with a constant promise gap. The reduction turns out to be a versatile subroutine to prove properties of quantum PCPs, allowing us to show: (i) Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. In fact, this can even be shown to hold when the non-adaptive quantum PCP picks the proof indices simply uniformly at random from a subset of all possible index combinations, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). (ii) If the q -local Hamiltonian problem with constant promise gap can be solved in QCMA , then QPCP[q]⊆QCMA for any q∈O(1) . (iii) If QMA(k) has a quantum PCP for any k≤poly(n) , then QMA(2)=QMA , connecting two of the longest-standing open problems in quantum complexity theory. Moreover, we also show that there exist (quantum) oracles relative to which certain quantum PCP statements are false. Hence, any attempt to prove the quantum PCP conjecture requires, just as was the case for the classical PCP theorem, (quantumly) non-relativizing techniques.

arXiv:2403.04841•Quantum•Jul 11, 2025•1 citation

Quantum Interactive Oracle Proofs

Baocheng Sun, Thomas Vidick

We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs. In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture. We show the following two main constructions of qIOPs, both of which are unconditional: - We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages. - We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist. As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.

cs.CCCross-listedarXiv:2601.12874•Jan 20, 2026•0 citations

Gap Amplification for Local Hamiltonians with Combinatorial Soundness

Mitali Bafna, Quynh T. Nguyen, Tina Zhang

The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of many known strategies for proving the classical PCP theorem. In this work, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies the combinatorial gap of local Hamiltonians. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central ingredients in classical PCPs into the quantum setting. In particular, we build upon ideas from the recent classical PCP of Bafna--Minzer--Vyas based on high-dimensional expanders, and the circuit-to-Hamiltonian construction of Anshu--Breuckmann--Nguyen, in addition to several recent advances in quantum coding theory.

quant-pharXiv:2610.04952•Oct 6, 2026•0 citations

Quantum versus classical resources in computational complexity

Jordi R. Weggemans

This dissertation studies the interplay between quantum and classical computational resources through the lens of computational complexity theory. Part I considers low-energy states of quantum systems. We study the complexity of estimating ground- and excited-state energies of local Hamiltonians, given access to a guiding state promised to have non-negligible overlap with the relevant eigenspace. We formalise access models for such guiding states, examine their properties and relations, and study the problem for physically motivated Hamiltonians. We also study the task of obtaining approximate descriptions of ground states, given QMA-oracle access, in the setting of low-locality reduced density matrices. Part II focuses on quantum probabilistically checkable proof systems (QPCPs). We define a general class of QPCPs that allows adaptivity and multiple unentangled provers, and study its relationship to constant-gap local Hamiltonian problems via quantum reductions. Additionally, we investigate quantum–classical PCPs (QCPCPs), where a quantum verifier has either classical or quantum query access to a classical proof. Part III explores alternative complexity measures: unitary query complexity and sample complexity. For unitary query complexity, we develop a lower-bound technique based on unitary channel discrimination. In the context of sample complexity, we introduce and analyse a new sample-to-sample task, called complement sampling, and study the power of quantum computation with quantum samples over their classical counterparts.

•Jan 1, 2025•0 citations

Promises should be taken seriously: On relativization with promise problems

David Miloschewsky, Supartha Podder, Dorian Rudolph

Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries. Our first result separates the language and promise settings. Namely, we construct an oracle $O$ such that $\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^O$, but $\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}$. In particular, $\mathsf{BPP}^O = \mathsf{BQP}^O$, but $\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^O$, showing that results for languages need not transfer to promises. Next, we use loose queries to strengthen the upper bound on the Quantum-Classical Polynomial Hierarchy from $\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}$ to $\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}$. The same proof also shows $\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}$. Additionally, we show that $\mathsf{PromiseBQP}$, even when given quantum advice, is self-low under robust queries. Finally, we exhibit an obstruction to transferring language-level counting results to promise classes. Although $\mathsf{AWPP}$ and $\mathsf{APP}$ are low for $\mathsf{PP}$, a corresponding promise analogue would collapse the counting hierarchy as $\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}$. This motivates the introduction of $\mathsf{PromisePostBQP^*}$, which restricts $\mathsf{PostBQP}$ to input-indepencent postselection. By showing that it is low for \PP, we obtain $\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}$.

cs.CCCross-listedarXiv:2609.07945•Sep 9, 2026•0 citations
We generalize quantum-classical PCPs, first introduced by Weggemans, Folkertsma and Cade (TQC 2024), to allow for qqq quantum queries to a polynomially-sized classical proof (QCPCPQ,c,s[q]\mathsf{QCPCP}_{Q,c,s}[q]QCPCPQ,c,s​[q]). Exploiting a connection with the polynomial method, we prove that for any constant qqq, promise gap c−s=Ω(1/poly(n))c-s = Ω(1/\text{poly}(n))c−s=Ω(1/poly(n)) and δ>0δ>0δ>0, we have QCPCPQ,c,s[q]⊆QCPCP1−δ,1/2+δ[3]⊆BQ⋅NP\mathsf{QCPCP}_{Q,c,s}[q] \subseteq \mathsf{QCPCP}_{1-δ,1/2+δ}[3] \subseteq \mathsf{BQ} \cdot \mathsf{NP}QCPCPQ,c,s​[q]⊆QCPCP1−δ,1/2+δ​[3]⊆BQ⋅NP, where BQ⋅NP\mathsf{BQ} \cdot \mathsf{NP}BQ⋅NP is the class of promise problems with quantum reductions to an NP\mathsf{NP}NP-complete problem. Surprisingly, this shows that we can amplify the promise gap from inverse polynomial to constant for constant query quantum-classical PCPs, and that any quantum-classical PCP making any constant number of quantum queries can be simulated by one that makes only three classical queries. Nevertheless, even though we can achieve promise gap amplification, our result also gives strong evidence that there exists no constant query quantum-classical PCP for QCMA\mathsf{QCMA}QCMA, as it is unlikely that QCMA⊆BQ⋅NP\mathsf{QCMA} \subseteq \mathsf{BQ} \cdot \mathsf{NP}QCMA⊆BQ⋅NP, which we support by giving oracular evidence. In the (poly-)logarithmic query regime, we show for any positive integer ccc, there exists an oracle relative to which QCPCP[O(log⁡cn)]⊊QCPCPQ[O(log⁡cn)]\mathsf{QCPCP}[\mathcal{O}(\log^c n)] \subsetneq \mathsf{QCPCP}_Q[\mathcal{O}(\log^c n)]QCPCP[O(logcn)]⊊QCPCPQ​[O(logcn)], contrasting the constant query case where the equivalence of both query models holds relative to any oracle. Finally, we connect our results to more general quantum-classical interactive proof systems.
Complexity class containments involving interactive proof classes are famously nonrelativizing: although IP=PSPACE\mathsf{IP} = \mathsf{PSPACE}IP=PSPACE, Fortnow and Sipser showed that that there exists an oracle relative to which coNP⊈IP\mathsf{coNP} \not\subseteq \mathsf{IP}coNP⊆IP. In contrast, the question of whether the containment BQP⊆IP\mathsf{BQP} \subseteq \mathsf{IP}BQP⊆IP is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment BQP⊆MIP\mathsf{BQP} \subseteq \mathsf{MIP}BQP⊆MIP holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle OOO, a PCP\mathsf{PCP}PCP proof system for BQPO\mathsf{BQP}^{O}BQPO where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle OOO. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an IP\mathsf{IP}IP for BQP\mathsf{BQP}BQP in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.
We define a general formulation of quantum PCPs, which captures adaptivity and multiple unentangled provers, and give a detailed construction of the quantum reduction to a local Hamiltonian with a constant promise gap. The reduction turns out to be a versatile subroutine to prove properties of quantum PCPs, allowing us to show: (i) Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number of proof queries is constant. In fact, this can even be shown to hold when the non-adaptive quantum PCP picks the proof indices simply uniformly at random from a subset of all possible index combinations, answering an open question by Aharonov, Arad, Landau and Vazirani (STOC '09). (ii) If the q -local Hamiltonian problem with constant promise gap can be solved in QCMA , then QPCP[q]⊆QCMA for any q∈O(1) . (iii) If QMA(k) has a quantum PCP for any k≤poly(n) , then QMA(2)=QMA , connecting two of the longest-standing open problems in quantum complexity theory. Moreover, we also show that there exist (quantum) oracles relative to which certain quantum PCP statements are false. Hence, any attempt to prove the quantum PCP conjecture requires, just as was the case for the classical PCP theorem, (quantumly) non-relativizing techniques.
We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs. In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture. We show the following two main constructions of qIOPs, both of which are unconditional: - We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages. - We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist. As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.
The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical PCP theorem, such as locality-preserving gap amplification and alphabet reduction, have no obvious quantum analogues due to quantum no-cloning. Locality-preserving gap amplification is a procedure that takes as input a local Hamiltonian problem instance and produces a new instance with a larger promise gap, without increasing the locality of the Hamiltonian, and instead moderately increasing its local qudit dimension. Obtaining this kind of control over the locality during gap amplification is critical to the success of many known strategies for proving the classical PCP theorem. In this work, we put forth the first known viable template for quantum locality-preserving gap amplification, and we prove that our procedure amplifies the combinatorial gap of local Hamiltonians. Our work introduces a new framework for reasoning about quantum gap amplification in terms of fault-tolerant computation, and illuminates a route toward importing one of the central ingredients in classical PCPs into the quantum setting. In particular, we build upon ideas from the recent classical PCP of Bafna--Minzer--Vyas based on high-dimensional expanders, and the circuit-to-Hamiltonian construction of Anshu--Breuckmann--Nguyen, in addition to several recent advances in quantum coding theory.
This dissertation studies the interplay between quantum and classical computational resources through the lens of computational complexity theory. Part I considers low-energy states of quantum systems. We study the complexity of estimating ground- and excited-state energies of local Hamiltonians, given access to a guiding state promised to have non-negligible overlap with the relevant eigenspace. We formalise access models for such guiding states, examine their properties and relations, and study the problem for physically motivated Hamiltonians. We also study the task of obtaining approximate descriptions of ground states, given QMA-oracle access, in the setting of low-locality reduced density matrices. Part II focuses on quantum probabilistically checkable proof systems (QPCPs). We define a general class of QPCPs that allows adaptivity and multiple unentangled provers, and study its relationship to constant-gap local Hamiltonian problems via quantum reductions. Additionally, we investigate quantum–classical PCPs (QCPCPs), where a quantum verifier has either classical or quantum query access to a classical proof. Part III explores alternative complexity measures: unitary query complexity and sample complexity. For unitary query complexity, we develop a lower-bound technique based on unitary channel discrimination. In the context of sample complexity, we introduce and analyse a new sample-to-sample task, called complement sampling, and study the power of quantum computation with quantum samples over their classical counterparts.
Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries. Our first result separates the language and promise settings. Namely, we construct an oracle OOO such that PO=BQPO=AWPPO\mathsf{P}^O = \mathsf{BQP}^O = \mathsf{AWPP}^OPO=BQPO=AWPPO, but PromiseBQPO⊈PromiseP/polyO\mathsf{PromiseBQP}^O\not\subseteq\mathsf{PromiseP}^O_{\mathsf{/poly}}PromiseBQPO⊆PromiseP/polyO​. In particular, BPPO=BQPO\mathsf{BPP}^O = \mathsf{BQP}^OBPPO=BQPO, but PromiseBQPO≠PromiseBPPO\mathsf{PromiseBQP}^O \neq \mathsf{PromiseBPP}^OPromiseBQPO=PromiseBPPO, showing that results for languages need not transfer to promises. Next, we use loose queries to strengthen the upper bound on the Quantum-Classical Polynomial Hierarchy from PPPPP\mathsf{P}^{\mathsf{PP}^{\mathsf{PP}}}PPPPP to QCPH⊆BP⋅PP⊆PromiseBPPPP\mathsf{QCPH} \subseteq \mathsf{BP\cdot PP} \subseteq \mathsf{PromiseBPP}^{\mathsf{PP}}QCPH⊆BP⋅PP⊆PromiseBPPPP. The same proof also shows PPPromiseBQP=PP\mathsf{PP}^\mathsf{PromiseBQP} = \mathsf{PP}PPPromiseBQP=PP. Additionally, we show that PromiseBQP\mathsf{PromiseBQP}PromiseBQP, even when given quantum advice, is self-low under robust queries. Finally, we exhibit an obstruction to transferring language-level counting results to promise classes. Although AWPP\mathsf{AWPP}AWPP and APP\mathsf{APP}APP are low for PP\mathsf{PP}PP, a corresponding promise analogue would collapse the counting hierarchy as GapP⊆FPPromiseAWPP\mathsf{GapP} \subseteq \mathsf{FP}^{\mathsf{PromiseAWPP}}GapP⊆FPPromiseAWPP. This motivates the introduction of PromisePostBQP∗\mathsf{PromisePostBQP^*}PromisePostBQP∗, which restricts PostBQP\mathsf{PostBQP}PostBQP to input-indepencent postselection. By showing that it is low for \PP, we obtain PPPromiseYQP∗=PP\mathsf{PP}^{\mathsf{PromiseYQP^*}} = \mathsf{PP}PPPromiseYQP∗=PP.