加入
QMA(2) versus QMA: do unentangled proofs help?
Decide whether two unentangled quantum proofs let an efficient quantum verifier check more problems than one proof: is QMA(2) = QMA?
shoal 2周前提交
0 个父提交
提交 34245e1a9313d70834fef34cac2a0f507063d15b
+50 −0 README.md 新增 查看文件
| @@ -0,0 +1,50 @@ | ||
| 1 | +# QMA(2) versus QMA: do unentangled proofs help? | |
| 2 | + | |
| 3 | +In QMA, the quantum analogue of NP, an efficient quantum verifier checks a quantum state sent by an untrusted prover. QMA(2) gives the verifier two quantum proofs that are promised to be unentangled with each other. Nobody knows whether this promise adds any power: perhaps every such protocol can be simulated with one proof, or perhaps two proofs can verify problems far beyond QMA. | |
| 4 | + | |
| 5 | +## Problem | |
| 6 | + | |
| 7 | +A promise problem $L=(L_{\mathrm{yes}},L_{\mathrm{no}})$ is in $\mathsf{QMA}(2)$ if there is a polynomial-time quantum verifier $V$ that receives an input $x$ of length $n$ and two registers of $\mathrm{poly}(n)$ qubits each, such that | |
| 8 | + | |
| 9 | +- if $x\in L_{\mathrm{yes}}$, some product state $\lvert\psi_1\rangle\otimes\lvert\psi_2\rangle$ makes $V$ accept with probability at least $2/3$; | |
| 10 | +- if $x\in L_{\mathrm{no}}$, every product state $\lvert\phi_1\rangle\otimes\lvert\phi_2\rangle$ makes $V$ accept with probability at most $1/3$. | |
| 11 | + | |
| 12 | +$\mathsf{QMA}$ is the same with a single proof register and no restriction on the proof. A verifier may ignore one of the two proofs, and a nondeterministic exponential-time machine can guess classical descriptions of both proofs and compute the acceptance probability, so | |
| 13 | + | |
| 14 | +$$\mathsf{QMA}\subseteq\mathsf{QMA}(2)\subseteq\mathsf{NEXP}.$$ | |
| 15 | + | |
| 16 | +**Question.** Is $\mathsf{QMA}(2)=\mathsf{QMA}$? Or is the first inclusion strict, perhaps with $\mathsf{QMA}(2)=\mathsf{NEXP}$? | |
| 17 | + | |
| 18 | +## Background | |
| 19 | + | |
| 20 | +Kobayashi, Matsumoto and Yamakami defined $\mathsf{QMA}(k)$, verification with $k$ unentangled quantum proofs, in 2001 to compare one quantum certificate with several [1]. The promise matters because a single prover could entangle the two registers to fool tests that are sound only against product states. Harrow and Montanaro proved $\mathsf{QMA}(k)=\mathsf{QMA}(2)$ for every $k\ge2$, so two proofs are the whole question, and related $\mathsf{QMA}(2)$ with logarithmic-size proofs to testing separability of mixed states and to injective norms of tensors [2]. The question thus links quantum complexity, entanglement theory and polynomial optimization. After 25 years, essentially only the two inclusions above are known [6]. | |
| 21 | + | |
| 22 | +## What is known | |
| 23 | + | |
| 24 | +- Harrow and Montanaro also gave efficient soundness amplification for $\mathsf{QMA}(2)$ and, building on Aaronson et al., a protocol that verifies 3-SAT on $n$ variables with constant soundness from two unentangled proofs of $O(\sqrt n\,\mathrm{polylog}\,n)$ qubits [2]. | |
| 25 | +- If both proofs must have non-negative amplitudes, the class equals $\mathsf{NEXP}$ (Jeronimo and Wu). They also showed that such a protocol for $\mathsf{NEXP}$ with completeness–soundness gap at least $3/4+1/\mathrm{poly}(n)$ would give $\mathsf{QMA}(2)=\mathsf{NEXP}$ [3]. In August 2026 Miyamoto reported protocols of this kind with completeness $1-1/\mathrm{poly}(n)$ and soundness $1/4+1/\mathrm{poly}(n)$, just short of that gap (unrefereed preprint) [8]. | |
| 26 | +- Bassirian, Fefferman, Leigh, Marwaha and Wu found a modified class, with an "internally separable" proof, in which one proof is strictly weaker than two unentangled proofs, assuming $\mathsf{EXP}\ne\mathsf{NEXP}$ [4]. | |
| 27 | +- Buhrman, Helsen and Weggemans showed that a quantum PCP for $\mathsf{QMA}(k)$, for any $k\le\mathrm{poly}(n)$, would imply $\mathsf{QMA}(2)=\mathsf{QMA}$ [5]. | |
| 28 | +- In September 2026, Bostanci, Grewal, Haferkamp, Huang, Hwang, Natarajan and Nirkhe gave the first quantum (unitary) oracle relative to which $\mathsf{QMA}\ne\mathsf{QMA}(2)$, resolving Watrous's no-disentanglers conjecture. Because in-place amplification for $\mathsf{QMA}(2)$ would imply $\mathsf{QMA}(2)\subseteq\mathsf{QMA}$ even relative to oracles, any such amplification must be non-relativizing [6]. | |
| 29 | +- In October 2026, Grewal, Mutreja and Tomer claimed a classical oracle relative to which $\mathsf{QMA}\ne\mathsf{QMA}(2)$, built from a separable Hamiltonian problem on graphs; it is an unrefereed preprint [7]. Oracle separations do not settle the unrelativized question. | |
| 30 | + | |
| 31 | +## What would count as progress | |
| 32 | + | |
| 33 | +- A better inclusion on either side, such as $\mathsf{QMA}(2)\subseteq\mathsf{EXP}$ or $\mathsf{NEXP}\subseteq\mathsf{QMA}(2)$; the latter would follow from a non-negative-amplitude protocol for $\mathsf{NEXP}$ with gap at least $3/4+1/\mathrm{poly}(n)$ [3]. | |
| 34 | +- An independent check, or a simpler proof, of the classical-oracle separation claimed in [7]. | |
| 35 | +- A proof that $\mathsf{QMA}(2)=\mathsf{QMA}$; by [6] it must use techniques that fail relative to quantum oracles, and by [7], if it holds, relative to classical oracles too. | |
| 36 | + | |
| 37 | +## References | |
| 38 | + | |
| 39 | +1. H. Kobayashi, K. Matsumoto and T. Yamakami, "Quantum certificate verification: single versus multiple quantum certificates", preprint (2001). [arXiv:quant-ph/0110006](https://arxiv.org/abs/quant-ph/0110006) | |
| 40 | +2. A. W. Harrow and A. Montanaro, "Testing product states, quantum Merlin-Arthur games and tensor optimization", *Journal of the ACM* 60(1), 3 (2013). [doi:10.1145/2432622.2432625](https://doi.org/10.1145/2432622.2432625) | |
| 41 | +3. F. G. Jeronimo and P. Wu, "The power of unentangled quantum proofs with non-negative amplitudes", preprint (2024). [arXiv:2402.18790](https://arxiv.org/abs/2402.18790) | |
| 42 | +4. R. Bassirian, B. Fefferman, I. Leigh, K. Marwaha and P. Wu, "Quantum Merlin-Arthur with an internally separable proof", preprint (2024). [arXiv:2410.19152](https://arxiv.org/abs/2410.19152) | |
| 43 | +5. H. Buhrman, J. Helsen and J. Weggemans, "Quantum PCPs: on adaptivity, multiple provers and reductions to local Hamiltonians", *Quantum* 9, 1791 (2025). [doi:10.22331/q-2025-07-11-1791](https://doi.org/10.22331/q-2025-07-11-1791) | |
| 44 | +6. J. Bostanci, S. Grewal, J. Haferkamp, A. Huang, Y. Hwang, A. Natarajan and C. Nirkhe, "A quantum oracle separation between QMA(2) and QMA", preprint (2026). [arXiv:2609.02865](https://arxiv.org/abs/2609.02865) | |
| 45 | +7. S. Grewal, S. Mutreja and K. Tomer, "A classical oracle separation between QMA and QMA(2)", preprint (2026). [arXiv:2610.06760](https://arxiv.org/abs/2610.06760) | |
| 46 | +8. M. Miyamoto, "Near-optimal gap amplification for nonnegative unentangled quantum proofs", preprint (2026). [arXiv:2608.07986](https://arxiv.org/abs/2608.07986) | |
| 47 | + | |
| 48 | +## Source | |
| 49 | + | |
| 50 | +Imported from [QIQCOP Zoo op_61cc0e261b3889c6](https://qiqc-op.com/problem/op_61cc0e261b3889c6/), curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion. | |