Separating QMA from QCMA with a classical oracle

• URL: http://arxiv.org/abs/2511.09551v1
• Date: Thu, 13 Nov 2025 02:01:43 GMT
• Title: Separating QMA from QCMA with a classical oracle
• Authors: John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, Mark Zhandry,
• Abstract summary: We construct a classical oracle proving that a set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA)<n>We observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons.
• Score: 8.15122567803892
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation -- the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a "Forrelation" matrix between two sets that are accessible through membership queries. Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a "use once" object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons -- a novel "second quantization" perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.

Related papers

• Quantum Interactive Oracle Proofs [2.0482700732041397]
  We introduce the study of quantum Interactive Oracle Proofs (qIOPs)<n>We show two main constructions of qIOPs, both of which are unconditional.<n>We introduce a novel single prover of many-qubits test, which may be of independent interest.
  arXiv  Detail & Related papers  (2026-01-19T09:30:38Z)
• Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity [0.0]
  We give a simple quantum algorithm that uses only a single quantum sample -- a single copy of the uniform superposition over elements of the subset.<n>In a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation.
  arXiv  Detail & Related papers  (2025-02-12T19:00:10Z)
• Toward Separating QMA from QCMA with a Classical Oracle [10.699704508276174]
  QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes.
  arXiv  Detail & Related papers  (2024-11-04T00:18:06Z)
• Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits [15.89518426969296]
  We investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples. On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables. On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed.
  arXiv  Detail & Related papers  (2024-05-21T14:42:39Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Learning unitaries with quantum statistical queries [0.0]
  We propose several algorithms for learning unitary operators from quantum statistical queries.<n>We leverage quantum statistical queries to estimate the Fourier mass of a unitary on a subset of Pauli strings.<n>Our results indicate that quantum statistical queries offer a unified framework for various unitary learning tasks.
  arXiv  Detail & Related papers  (2023-10-03T17:56:07Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Quantum Oracle Separations from Complex but Easily Specified States [1.52292571922932]
  A quantum oracle is a black box unitary callable during quantum computation. We constrain the marked state in ways that make it easy to specify classically while retaining separations in task complexity. Using the fact that classically defined oracle may enable a quantum algorithm to prepare an otherwise hard state in steps, we observe quantum-classical oracle separation in heavy output sampling.
  arXiv  Detail & Related papers  (2021-04-15T05:40:38Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.