Superposition detection and QMA with non-collapsing measurements

Roozbeh Bassirian; Kunal Marwaha

doi:10.22331/q-2025-08-28-1839

Superposition detection and QMA with non-collapsing measurements

Roozbeh Bassirian and Kunal Marwaha

University of Chicago

Published:	2025-08-28, volume 9, page 1839
Editor:	Daniel Grier
Eprint:	arXiv:2403.02532v2
Doi:	https://doi.org/10.22331/q-2025-08-28-1839
Citation:	Quantum 9, 1839 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We prove that $\sf{QMA}$ where the verifier may also make a single $non-collapsing$ measurement [7] is equal to $\sf{NEXP}$, resolving an open question of Aaronson [5]. We show this is a corollary to a modified proof of $\sf{QMA+ = NEXP}$ [15]. At the core of many results inspired by Blier and Tapp [16] is an unphysical property testing problem deciding whether a quantum state is close to an element of a fixed basis.

► BibTeX data

@article{Bassirian2025superposition,
  doi = {10.22331/q-2025-08-28-1839},
  url = {https://doi.org/10.22331/q-2025-08-28-1839},
  title = {Superposition detection and {QMA} with non-collapsing measurements},
  author = {Bassirian, Roozbeh and Marwaha, Kunal},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1839},
  month = aug,
  year = {2025}
}

► References

[1] S. Aaronson. Limitations of quantum advice and one-way communication. Theory of Computing, 1(1):1–28, 2005. arXiv:quant-ph/0402095, doi:10.4086/toc.2005.v001a001.
https://doi.org/10.4086/toc.2005.v001a001
arXiv:quant-ph/0402095

[2] S. Aaronson. Quantum computing and hidden variables. Phys. Rev. A, 71:032325, Mar 2005. doi:10.1103/PhysRevA.71.032325.
https://doi.org/10.1103/PhysRevA.71.032325

[3] S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings: Mathematical, Physical and Engineering Sciences, 461(2063):3473–3482, 2005. arXiv:quant-ph/0412187, doi:10.1098/rspa.2005.1546.
https://doi.org/10.1098/rspa.2005.1546
arXiv:quant-ph/0412187

[4] S. Aaronson. PDQP/qpoly = ALL. arXiv:1805.08577.
arXiv:1805.08577

[5] S. Aaronson. Quantum miscellany — Shtetl-Optimized. URL https://scottaaronson.blog/?p=7516.
https://scottaaronson.blog/?p=7516

[6] S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor. The power of unentanglement. Theory of Computing, 5(1):1–42, 2009. arXiv:0804.0802, doi:10.4086/toc.2009.v005a001.
https://doi.org/10.4086/toc.2009.v005a001
arXiv:0804.0802

[7] S. Aaronson, A. Bouland, J. Fitzsimons, and M. Lee. The space" just above" bqp. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 271–280, 2016, arXiv:1412.6507. doi:10.1145/2840728.2840739.
https://doi.org/10.1145/2840728.2840739
arXiv:1412.6507

[8] S. Aaronson and A. Drucker. A full characterization of quantum advice. SIAM Journal on Computing, 43(3):1131–1183, 2014. arXiv:1004.0377, doi:10.1137/110856939.
https://doi.org/10.1137/110856939
arXiv:1004.0377

[9] S. Aaronson, S. Grewal, V. Iyer, S. C. Marshall, and R. Ramachandran. PDQMA = DQMA = NEXP: QMA with hidden variables and non-collapsing measurements. arXiv:2403.02543.
arXiv:2403.02543

[10] S. Akibue, G. Kato, and S. Tani. On the hardness of conversion from entangled proof into separable one. arXiv:2402.08981.
arXiv:2402.08981

[11] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. doi:10.1145/278298.278306.
https://doi.org/10.1145/278298.278306

[12] D. Aharonov and O. Regev. A Lattice Problem in Quantum NP. In Proceedings of 44th Annual IEEE Symposium on Foundations of Computer Science, pages 210–219. IEEE, 2003, arXiv:quant-ph/0307220. doi:10.1109/SFCS.2003.1238195.
https://doi.org/10.1109/SFCS.2003.1238195
arXiv:quant-ph/0307220

[13] S. Arora and S. Safra. Probabilistic checking of proofs; A new characterization of NP. In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 2–13. IEEE Computer Society, 1992. doi:10.1109/SFCS.1992.267824. URL https://doi.org/10.1109/SFCS.1992.267824.
https://doi.org/10.1109/SFCS.1992.267824

[14] L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, SFCS '90, page 16–25 vol.1, USA, 1990. IEEE Computer Society. doi:10.1109/FSCS.1990.89520.
https://doi.org/10.1109/FSCS.1990.89520

[15] R. Bassirian, B. Fefferman, and K. Marwaha. Quantum merlin-arthur and proofs without relative phase. In 15th Innovations in Theoretical Computer Science Conference, volume 287, pages 9:1–9:19, 2024, arXiv:2306.13247. doi:10.4230/LIPIcs.ITCS.2024.9.
https://doi.org/10.4230/LIPIcs.ITCS.2024.9
arXiv:2306.13247

[16] H. Blier and A. Tapp. A quantum characterization of NP. Computational Complexity, 21(3):499–510, 2012. arXiv:0709.0738, doi:10.1007/s00037-011-0016-2.
https://doi.org/10.1007/s00037-011-0016-2
arXiv:0709.0738

[17] J. Chen and A. Drucker. Short multi-prover quantum proofs for SAT without entangled measurements. arXiv:1011.0716.
arXiv:1011.0716

[18] A. Chiesa and M. A. Forbes. Improved soundness for QMA with multiple provers. arXiv:1108.2098.
https://doi.org/10.4086/cjtcs.2013.001
arXiv:1108.2098

[19] I. Dinur. The PCP theorem by gap amplification. Journal of the ACM (JACM), 54(3):12–es, 2007. doi:10.1145/1236457.1236459.
https://doi.org/10.1145/1236457.1236459

[20] C. A. Fuchs and J. van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory, 45(4):1216–1227, 1999. arXiv:quant-ph/9712042, doi:10.1109/18.761271.
https://doi.org/10.1109/18.761271
arXiv:quant-ph/9712042

[21] S. Gharibian. Guest Column: The 7 faces of quantum NP. ACM SIGACT News, 54(4):54–91, Dec. 2023. doi:10.1145/3639528.3639535.
https://doi.org/10.1145/3639528.3639535

[22] F. L. Gall, S. Nakagawa, and H. Nishimura. On QMA protocols with two short quantum proofs. Quantum Inf. Comput., 12(7-8):589–600, 2012. arXiv:1108.4306, doi:10.26421/QIC12.7-8-4.
https://doi.org/10.26421/QIC12.7-8-4
arXiv:1108.4306

[23] S. Gharibian, M. Santha, J. Sikora, A. Sundaram, and J. Yirka. Quantum generalizations of the polynomial hierarchy with applications to qma(2). arXiv:1805.11139, doi:10.4230/LIPICS.MFCS.2018.58.
https://doi.org/10.4230/LIPICS.MFCS.2018.58
arXiv:1805.11139

[24] P. Harsha. Robust PCPs of proximity and shorter PCPs. PhD thesis, Massachusetts Institute of Technology, 2004. URL https://dspace.mit.edu/bitstream/handle/1721.1/26720/59552830-MIT.pdf.
https://dspace.mit.edu/bitstream/handle/1721.1/26720/59552830-MIT.pdf

[25] A. W. Harrow and A. Montanaro. Testing product states, quantum merlin-arthur games and tensor optimization. Journal of the ACM (JACM), 60(1):1–43, 2013. arXiv:1001.0017, doi:10.1145/2432622.2432625.
https://doi.org/10.1145/2432622.2432625
arXiv:1001.0017

[26] R. Hiromasa, A. Mizutani, Y. Takeuchi, and S. Tani. Rewindable quantum computation and its equivalence to cloning and adaptive postselection. arXiv:2206.05434, doi:10.4230/LIPICS.TQC.2023.9.
https://doi.org/10.4230/LIPICS.TQC.2023.9
arXiv:2206.05434

[27] F. G. Jeronimo and P. Wu. The power of unentangled quantum proofs with non-negative amplitudes. 55th Annual ACM Symposium on Theory of Computing, 2023. arXiv:2402.18790, doi:10.1145/3564246.3585248.
https://doi.org/10.1145/3564246.3585248
arXiv:2402.18790

[28] F. G. Jeronimo and P. Wu. Dimension Independent Disentanglers from Unentanglement and Applications. In 39th Computational Complexity Conference (CCC 2024), volume 300, pages 26:1–26:28, 2024, arXiv:2402.15282. doi:10.4230/LIPIcs.CCC.2024.26.
https://doi.org/10.4230/LIPIcs.CCC.2024.26
arXiv:2402.15282

[29] Y. Kinoshita. QMA(2) with postselection equals to NEXP. arXiv:1806.09732.
arXiv:1806.09732

[30] H. Kobayashi, K. Matsumoto, and T. Yamakami. Quantum merlin-arthur proof systems: Are multiple merlins more helpful to arthur? In Algorithms and Computation, pages 189–198, 2003, arXiv:quant-ph/0306051. doi:10.1007/978-3-540-24587-2_21.
https://doi.org/10.1007/978-3-540-24587-2_21
arXiv:quant-ph/0306051

[31] C. Marriott and J. Watrous. Quantum Arthur-Merlin Games. Computational Complexity, 14:122–152, 2005. arXiv:cs/0506068, doi:10.1007/s00037-005-0194-x.
https://doi.org/10.1007/s00037-005-0194-x
arXiv:cs/0506068

[32] D. Nagaj, P. Wocjan, and Y. Zhang. Fast amplification of qma. Quantum Information and Computation, 9(11):1053–1068, Nov. 2009. arXiv:0904.1549, doi:10.26421/qic9.11-12-8.
https://doi.org/10.26421/qic9.11-12-8
arXiv:0904.1549

[33] A. Pereszlényi. Multi-prover quantum merlin-arthur proof systems with small gap. arXiv:1205.2761.
arXiv:1205.2761

[34] A. She and H. Yuen. Unitary Property Testing Lower Bounds by Polynomials. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, pages 96:1–96:17, 2023, arXiv:2210.05885. doi:10.4230/LIPIcs.ITCS.2023.96.
https://doi.org/10.4230/LIPIcs.ITCS.2023.96
arXiv:2210.05885

Cited by

[1] Fernando Granha Jeronimo, Pei Wu, and Itai Leigh, "The QMA(2) UniverseComplexity, Entanglement, and Optimization", ACM SIGACT News 57 1, 64 (2026).

[2] Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon C. Marshall, and Ronak Ramachandran, "PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements", arXiv:2403.02543, (2024).

[3] David Miloschewsky and Supartha Podder, "New Lower-bounds for Quantum Computation with Non-Collapsing Measurements", arXiv:2411.04085, (2024).

[4] Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu, "Quantum Merlin-Arthur with an internally separable proof", arXiv:2410.19152, (2024).

[5] Sabee Grewal and William Kretschmer, "Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs", arXiv:2509.15319, (2025).

[6] David Miloschewsky and Supartha Podder, "Modifications of Quantum Computation and Adaptive Queries to PP", arXiv:2507.03692, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 10:59:38) and SAO/NASA ADS (last updated successfully 2026-08-09 22:23:50). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-10 10:59:38: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.