A Distribution Testing Oracle Separation Between QMA And QCMA

Republished By Plato

Followers: 0

Anand Natarajan¹ and Chinmay Nirkhe²

¹Massachusetts Institute of Technology
²IBM Quantum Cambridge

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

Abstract

It is a long-standing open question in quantum complexity theory whether the definition of $non-deterministic$ quantum computation requires quantum witnesses (QMA) or if classical witnesses suffice (QCMA). We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes. Previous separations [3], [13] required a quantum unitary oracle. The separating problem is deciding whether a distribution supported on regular un-directed graphs either consists of multiple connected components (yes instances) or consists of one expanding connected component (no instances) where the graph is given in an adjacency-list format by the oracle. Therefore, the oracle is a distribution over $n$-bit boolean functions.

A distribution testing oracle separation between QMA and QCMA PlatoBlockchain Data Intelligence. Vertical Search. Ai.

► BibTeX data

@article{Natarajan2024distributiontesting, doi = {10.22331/q-2024-06-17-1377}, url = {https://doi.org/10.22331/q-2024-06-17-1377}, title = {A distribution testing oracle separation between {QMA} and {QCMA}}, author = {Natarajan, Anand and Nirkhe, Chinmay}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1377}, month = jun, year = {2024} }

► References

[1] Scott Aaronson. On perfect completeness for QMA. Quantum Info. Comput., 9 (1): 81–89, January 2009. ISSN 1533-7146. 10.26421/qic9.1-2-5.
https://doi.org/10.26421/qic9.1-2-5

[2] Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2 (4), December 2021. ISSN 2643-6809. 10.1145/3488559.
https://doi.org/10.1145/3488559

[3] Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07), pages 115–128, 2007. 10.1109/CCC.2007.27.
https://doi.org/10.1109/CCC.2007.27

[4] Dorit Aharonov and Tomer Naveh. Quantum NP – A survey, 2002.

[5] Andris Ambainis. Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci., 64 (4): 750–767, jun 2002. ISSN 0022-0000. 10.1006/jcss.2002.1826. URL https://doi.org/10.1006/jcss.2002.1826.
https://doi.org/10.1006/jcss.2002.1826

[6] Andris Ambainis, Andrew M. Childs, and Yi-Kai Liu. Quantum property testing for bounded-degree graphs. In Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 365–376, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. ISBN 978-3-642-22935-0. 10.1007/978-3-642-22935-0_31.
https://doi.org/10.1007/978-3-642-22935-0_31

[7] Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe. NLTS hamiltonians from good quantum codes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1090–1096, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9781450399135. 10.1145/3564246.3585114.
https://doi.org/10.1145/3564246.3585114

[8] Atul Singh Arora, Alexandru Gheorghiu, and Uttam Singh. Oracle separations of hybrid quantum-classical circuits. 2022. 10.48550/arXiv.2201.01904.
https://doi.org/10.48550/arXiv.2201.01904

[9] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26 (5): 1510–1523, 1997. 10.1137/S0097539796300933.
https://doi.org/10.1137/S0097539796300933

[10] Adam D. Bookatz. QMA-complete problems. 2012. 10.48550/ARXIV.1212.6312.
https://doi.org/10.48550/ARXIV.1212.6312

[11] Sergey Bravyi and Barbara Terhal. Complexity of stoquastic frustration-free hamiltonians. SIAM J. Comput., 39 (4): 1462–1485, nov 2009. ISSN 0097-5397. 10.1137/08072689x.
https://doi.org/10.1137/08072689x

[12] Sergey Bravyi, David P. Divincenzo, Roberto Oliveira, and Barbara M. Terhal. The complexity of stoquastic local hamiltonian problems. Quantum Info. Comput., 8 (5): 361–385, may 2008. ISSN 1533-7146. 10.26421/qic8.5-1.
https://doi.org/10.26421/qic8.5-1

[13] Bill Fefferman and Shelby Kimmel. Quantum vs. classical proofs and subset verification. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 22:1–22:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. 10.4230/LIPIcs.MFCS.2018.22.
https://doi.org/10.4230/LIPIcs.MFCS.2018.22

[14] Honghao Fu. Personal Communication, Oct 2022.

[15] Alex Bredariol Grilo, Iordanis Kerenidis, and Jamie Sikora. QMA with subset state witnesses. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald T. Sannella, editors, Mathematical Foundations of Computer Science 2015, pages 163–174, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. ISBN 978-3-662-48054-0. 10.1007/978-3-662-48054-0_14.
https://doi.org/10.1007/978-3-662-48054-0_14

[16] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum Search-To-Decision Reductions and the State Synthesis Problem. In Shachar Lovett, editor, 37th Computational Complexity Conference (CCC 2022), volume 234 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:19, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-241-9. 10.4230/LIPIcs.CCC.2022.5.
https://doi.org/10.4230/LIPIcs.CCC.2022.5

[17] Stephen P Jordan, David Gosset, and Peter J Love. Quantum-merlin-arthur-complete problems for stoquastic hamiltonians and markov matrices. 81 (3), 3 2010. ISSN 1050-2947. 10.1103/PHYSREVA.81.032331.
https://doi.org/10.1103/PHYSREVA.81.032331

[18] A.Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2 – 30, 2003. ISSN 0003-4916. https://doi.org/10.1016/S0003-4916(02)00018-0.
https://doi.org/10.1016/S0003-4916(02)00018-0

[19] Hartmut Klauck and Supartha Podder. Two results about quantum messages. In International Symposium on Mathematical Foundations of Computer Science, pages 445–456. Springer, 2014. 10.1007/978-3-662-44465-8_38.
https://doi.org/10.1007/978-3-662-44465-8_38

[20] Dexter Kozen. Lower bounds for natural proof systems. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS ’77, page 254–266, USA, 1977. IEEE Computer Society. 10.1109/SFCS.1977.16.
https://doi.org/10.1109/SFCS.1977.16

[21] William Kretschmer. Personal Communication, Jul 2022.

[22] Andrew Lutomirski. Component mixers and a hardness result for counterfeiting quantum money, 2011.

[23] Michael A Nielsen and Isaac L Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[24] Chinmay Nirkhe. Lower bounds on the complexity of quantum proofs. PhD thesis, EECS Department, University of California, Berkeley, Nov 2022a. URL http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-236.html.
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-236.html

[25] Chinmay Nirkhe. NLTS Hamiltonians from codes, 2022b. URL https://simons.berkeley.edu/events/quantum-colloquium-nlts-hamiltonians-codes. Simons Institute for the Theory of Computing Quantum Colloquium. Panel Umesh Vazirani, Dorit Aharanov, Matthew Hastings, Anand Natarajan, and Chinmay Nirkhe.
https://simons.berkeley.edu/events/quantum-colloquium-nlts-hamiltonians-codes

Cited by

[1] Scott Aaronson, Harry Buhrman, and William Kretschmer, “A Qubit, a Coin, and an Advice String Walk Into a Relational Problem”, arXiv:2302.10332, (2023).

[2] Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha, “On the power of nonstandard quantum oracles”, arXiv:2212.00098, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2024-06-17 15:43:53). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2024-06-17 15:43:51: Could not fetch cited-by data for 10.22331/q-2024-06-17-1377 from Crossref. This is normal if the DOI was registered recently.

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2024-06-17-1377/

Time Stamp: June 17, 2024

Time Stamp: Jul 7, 2022

Republished By Plato

Quantum circuits for toric code and X-cube fracton model

“Proper” Shift Rules for Derivatives of Perturbed-Parametric Quantum Evolutions

Relaxation of Multitime Statistics in Quantum Systems

Hybrid discrete-continuous compilation of trapped-ion quantum circuits with deep reinforcement learning

Quantum Methods for Neural Networks and Application to Medical Image Classification

Covariant operator bases for continuous variables

High-dimensional Encoding in the Round-Robin Differential-Phase-Shift Protocol

Divide-and-conquer verification method for noisy intermediate-scale quantum computation

About Us

Vertical Search & Ai

Platform

Stay Connected

Account