The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings

Dorit Aharonov; Michael Ben-Or; Fernando G.S.L. Brandão; Or Sattath

doi:10.22331/q-2022-03-17-668

The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings

Dorit Aharonov¹, Michael Ben-Or¹, Fernando G.S.L. Brandão^2,3, and Or Sattath⁴

¹School of Computer Science and Engineering, The Hebrew University, Jerusalem, Israel.
²AWS Center for Quantum Computing, Pasadena, CA 91125, USA
³IQIM, California Institute of Technology, Pasadena, CA 91125, USA.
⁴Computer Science Department, Ben-Gurion University of the Negev, Beer-Sheva, Israel.

Published:	2022-03-17, volume 6, page 668
Eprint:	arXiv:0810.4840v3
Doi:	https://doi.org/10.22331/q-2022-03-17-668
Citation:	Quantum 6, 668 (2022).

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

Abstract

Valiant-Vazirani showed in 1985 [45] that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions).
We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA [7]. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an $\textit{inverse polynomial}$ spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard, under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [24]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values.
Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.

► BibTeX data

@article{Aharonov2022pursuitof,
  doi = {10.22331/q-2022-03-17-668},
  url = {https://doi.org/10.22331/q-2022-03-17-668},
  title = {The {P}ursuit of {U}niqueness: {E}xtending {V}aliant-{V}azirani {T}heorem to the {P}robabilistic and {Q}uantum {S}ettings},
  author = {Aharonov, Dorit and Ben-Or, Michael and Brand{\~{a}}o, Fernando G.S.L. and Sattath, Or},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {668},
  month = mar,
  year = {2022}
}

► References

[1] S. Arora and B. Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009.

[2] D. Aharonov, M. Ben-Or, F. G. S. L. Brandao, and O. Sattath. The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings, 2008, arXiv: 0810.4840.
arXiv:0810.4840

[3] A. Ambainis and J. Emerson. Quantum t-designs: t-wise Independence in the Quantum World. In 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA, pages 129–140. IEEE Computer Society, 2007, arXiv: quant-ph/0701126.
https://doi.org/10.1109/CCC.2007.26
arXiv:quant-ph/0701126

[4] D. Aharonov, D. Gottesman, S. Irani, and J. Kempe. The Power of Quantum Systems on a Line. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 373–383. IEEE Computer Society, 2007, arXiv: 0705.4077.
https://doi.org/10.1109/FOCS.2007.46
arXiv:0705.4077

[5] I. Arad, Z. Landau, U. Vazirani, and T. Vidick. Rigorous RG Algorithms and Area Laws for Low Energy Eigenstates in 1D. Communications in Mathematical Physics, 356(1):65–105, August 2017, arXiv: 1602.08828.
https://doi.org/10.1007/s00220-017-2973-z
arXiv:1602.08828

[6] A. Ambainis. On Physical Problems that are Slightly More Difficult than QMA. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 32–43. IEEE Computer Society, 2014, arXiv: 1312.4758.
https://doi.org/10.1109/CCC.2014.12
arXiv:1312.4758

[7] D. Aharonov and T. Naveh. Quantum NP - A Survey, 2002, arXiv: quant-ph/0210077.
arXiv:quant-ph/0210077

[8] S. Anders, M. B. Plenio, W. Dür, F. Verstraete, and H.-J. Briegel. Ground-State Approximation for Strongly Interacting Spin Systems in Arbitrary Spatial Dimension. Physical Review Letters, 97(10), September 2006, arXiv: quant-ph/0602230.
https://doi.org/10.1103/physrevlett.97.107206
arXiv:quant-ph/0602230

[9] L. Babai. Trading Group Theory for Randomness. In R. Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 421–429. ACM, 1985.
https://doi.org/10.1145/22145.22192

[10] J. Bausch, T. S. Cubitt, A. Lucia, and D. Perez-Garcia. Undecidability of the Spectral Gap in One Dimension. Phys. Rev. X, 10:031038, Aug 2020, arXiv: 1810.01858.
https://doi.org/10.1103/PhysRevX.10.031038
arXiv:1810.01858

[11] R. Bhatia. Matrix Analysis. Springer New York, 1997.

[12] S. A. Cook. The Complexity of Theorem-Proving Procedures. In M. A. Harrison, R. B. Banerji, and J. D. Ullman, editors, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, pages 151–158. ACM, 1971.
https://doi.org/10.1145/800157.805047

[13] T. S. Cubitt, D. Pérez-García, and M. M. Wolf. Undecidability of the spectral gap. Nature, 528(7581):207–211, December 2015, arXiv: 1502.04573.
https://doi.org/10.1038/nature16059
arXiv:1502.04573

[14] T. M. Cover and J. A. Thomas. Elements of information theory (2. ed.). Wiley, 2006.

[15] L. Carter and M. N. Wegman. Universal Classes of Hash Functions. J. Comput. Syst. Sci., 18(2):143–154, 1979.
https://doi.org/10.1016/0022-0000(79)90044-8

[16] A. Deshpande, A. V. Gorshkov, and B. Fefferman. The Importance of the Spectral Gap in Estimating Ground-State Energies. In M. Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 54:1–54:6. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, arXiv: 2007.11582.
https://doi.org/10.4230/LIPIcs.ITCS.2022.54
arXiv:2007.11582

[17] W. Fulton and J. Harris. Representation Theory. Springer New York, 2004.

[18] B. Fefferman and C. Lin. Quantum Merlin Arthur with Exponentially Small Gap, 2016, arXiv: 1601.01975.
arXiv:1601.01975

[19] C. E. González-Guillén and T. S. Cubitt. History-state Hamiltonians are critical, 2018, arXiv: 1810.06528.
arXiv:1810.06528

[20] S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin. Quantum Hamiltonian Complexity. Found. Trends Theor. Comput. Sci., 10(3):159–282, 2015, arXiv: 1401.3916.
https://doi.org/10.1561/0400000066
arXiv:1401.3916

[21] J. Gill. Computational Complexity of Probabilistic Turing Machines. SIAM J. Comput., 6(4):675–695, 1977.
https://doi.org/10.1137/0206049

[22] A. P. Gilyén and O. Sattath. On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma. In C. Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 439–450. IEEE Computer Society, 2017, arXiv: 1611.08571.
https://doi.org/10.1109/FOCS.2017.47
arXiv:1611.08571

[23] S. Gharibian and J. Yirka. The complexity of simulating local measurements on quantum systems. Quantum, 3:189, September 2019.
https://doi.org/10.22331/q-2019-09-30-189

[24] M. B. Hastings. An area law for one-dimensional quantum systems. Journal of Statistical Mechanics: Theory and Experiment, 2007(08):P08024–P08024, August 2007, arXiv: 0705.2024.
https://doi.org/10.1088/1742-5468/2007/08/p08024
arXiv:0705.2024

[25] R. Hübener, C. Kruszynska, L. Hartmann, W. Dür, F. Verstraete, J. Eisert, and M. B. Plenio. Renormalization algorithm with graph enhancement. Physical Review A, 79(2), February 2009, arXiv: 0802.1211.
https://doi.org/10.1103/physreva.79.022317
arXiv:0802.1211

[26] S. Hallgren, D. Nagaj, and S. Narayanaswami. The local Hamiltonian problem on a line with eight states is QMA-complete. Quantum Inf. Comput., 13(9-10):721–750, 2013, arXiv: 1312.1469.
https://doi.org/10.26421/QIC13.9-10-1
arXiv:1312.1469

[27] R. Impagliazzo and A. Wigderson. P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In F. T. Leighton and P. W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 220–229. ACM, 1997.
https://doi.org/10.1145/258533.258590

[28] R. Jain, I. Kerenidis, G. Kuperberg, M. Santha, O. Sattath, and S. Zhang. On the Power of a Unique Quantum Witness. Theory Comput., 8(1):375–400, 2012.
https://doi.org/10.4086/toc.2012.v008a017

[29] S. P. Jordan, H. Kobayashi, D. Nagaj, and H. Nishimura. Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems. Quantum Inf. Comput., 12(5-6):461–471, 2012, arXiv: 1111.5306.
arXiv:1111.5306
http://www.rintonpress.com/xxqic12/qic-12-56/0461-0471.pdf

[30] A. Kitaev. Quantum NP. A lecture given in the Second Workshop on Algorithms in Quantum Information Processing, January 18-22, 1999 DePaul University, 1999.

[31] J. Kempe, A. Y. Kitaev, and O. Regev. The Complexity of the Local Hamiltonian Problem. SIAM J. Comput., 35(5):1070–1097, 2006, arXiv: quant-ph/0406180.
https://doi.org/10.1137/S0097539704445226
arXiv:quant-ph/0406180

[32] J. Kempe and O. Regev. 3-local Hamiltonian is QMA-complete. Quantum Inf. Comput., 3(3):258–264, 2003, arXiv: quant-ph/0302079.
arXiv:quant-ph/0302079
http://portal.acm.org/citation.cfm?id=2011541

[33] A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate studies in mathematics. American Mathematical Society, 2002.

[34] Z. Landau, U. Vazirani, and T. Vidick. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians. Nature Physics, 11(7):566–569, June 2015, arXiv: 1307.5143.
https://doi.org/10.1038/nphys3345
arXiv:1307.5143

[35] C. Marriott and J. Watrous. Quantum Arthur-Merlin games. Comput. Complex., 14(2):122–152, 2005, arXiv: cs/0506068.
https://doi.org/10.1007/s00037-005-0194-x
arXiv:cs/0506068

[36] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press, 2010.

[37] R. Oliveira and B. M. Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Inf. Comput., 8(10):900–924, 2008, arXiv: quant-ph/0504050.
arXiv:quant-ph/0504050
http://www.rintonpress.com/xxqic8/qic-8-10/0900-0924.pdf

[38] D. Pérez-García, F. Verstraete, M. M. Wolf, and J. I. Cirac. Matrix product state representations. Quantum Inf. Comput., 7(5):401–430, 2007, arXiv: quant-ph/0608197.
arXiv:quant-ph/0608197
http://www.rintonpress.com/xqic7/qic-7-56/401-430.pdf

[39] J. Radhakrishnan, M. Rötteler, and P. Sen. On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, editors, Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 1399–1411. Springer, 2005, arXiv: quant-ph/0503114.
https://doi.org/10.1007/11523468_113
arXiv:quant-ph/0503114

[40] N. Schuch, I. Cirac, and F. Verstraete. Computational Difficulty of Finding Matrix Product Ground States. Physical Review Letters, 100(25), June 2008, arXiv: 0802.3351.
https://doi.org/10.1103/physrevlett.100.250501
arXiv:0802.3351

[41] P. Sen. Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 274–287. IEEE Computer Society, 2006, arXiv: quant-ph/0512085.
https://doi.org/10.1109/CCC.2006.37
arXiv:quant-ph/0512085

[42] S. Vadhan. A study of statistical zero-knowledge proofs. Springer-Verlag Berlin Heidelberg, 1999.

[43] L. G. Valiant. Relative Complexity of Checking and Evaluating. Inf. Process. Lett., 5(1):20–23, 1976.
https://doi.org/10.1016/0020-0190(76)90097-1

[44] G. Vidal. Entanglement Renormalization. Physical Review Letters, 99(22), November 2007, arXiv: cond-mat/0512165.
https://doi.org/10.1103/physrevlett.99.220405
arXiv:cond-mat/0512165

[45] L. G. Valiant and V. V. Vazirani. NP Is as Easy as Detecting Unique Solutions. In R. Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 458–463. ACM, 1985.
https://doi.org/10.1145/22145.22196

[46] J. Watrous. The Theory of Quantum Information. Cambridge University Press, 2018.

[47] P. Wocjan and S. Zhang. Several natural BQP-Complete problems, 2006, arXiv: quant-ph/0606179.
arXiv:quant-ph/0606179

[48] S. Zachos and M. Fürer. Probabalistic Quantifiers vs. Distrustful Adversaries. In K. V. Nori, editor, Foundations of Software Technology and Theoretical Computer Science, Seventh Conference, Pune, India, December 17-19, 1987, Proceedings, volume 287 of Lecture Notes in Computer Science, pages 443–455. Springer, 1987.
https://doi.org/10.1007/3-540-18625-5_67

Cited by

[1] Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman, "Importance of the Spectral gap in Estimating Ground-State Energies", PRX Quantum 3 4, 040327 (2022).

[2] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka, "Quantum generalizations of the polynomial hierarchy with applications to QMA(2)", computational complexity 31 2, 13 (2022).

[3] Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan, "Quantum Hamiltonian complexity in thermal equilibrium", Nature Physics 18 11, 1367 (2022).

[4] Tamara Kohler, Stephen Piddock, Johannes Bausch, and Toby Cubitt, "General Conditions for Universality of Quantum Hamiltonians", PRX Quantum 3 1, 010307 (2022).

[5] Dorit Aharonov, Itai Arad, and Thomas Vidick, "The Quantum PCP Conjecture", arXiv:1309.7495, (2013).

[6] Jordi Weggemans, Marten Folkertsma, and Chris Cade, "Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture", arXiv:2302.11578, (2023).

[7] Brielin Brown, Steven T. Flammia, and Norbert Schuch, "Computational Difficulty of Computing the Density of States", Physical Review Letters 107 4, 040501 (2011).

[8] Thomas Vidick and John Watrous, "Quantum Proofs", arXiv:1610.01664, (2016).

[9] Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman, "Importance of the spectral gap in estimating ground-state energies", arXiv:2007.11582, (2020).

[10] Sevag Gharibian, "Approximation, Proof Systems, and Correlations in a Quantum World", Ph.D. Thesis (2013).

[11] Andris Ambainis, "On physical problems that are slightly more difficult than QMA", arXiv:1312.4758, (2013).

[12] Sevag Gharibian, Jamie Sikora, and Sarvagya Upadhyay, "QMA variants with polynomially many provers", arXiv:1108.0617, (2011).

[13] Serge Massar and Miklos Santha, "Characterising the intersection of QMA and coQMA", Quantum Information Processing 20 12, 396 (2021).

[14] Sevag Gharibian and Justin Yirka, "The complexity of simulating local measurements on quantum systems", Quantum 3, 189 (2019).

[15] Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang, "On the power of a unique quantum witness", arXiv:0906.4425, (2009).

[16] Sevag Gharibian and Justin Yirka, "The complexity of simulating local measurements on quantum systems", arXiv:1606.05626, (2016).

[17] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka, "Quantum generalizations of the polynomial hierarchy with applications to QMA(2)", arXiv:1805.11139, (2018).

[18] Serge Massar and Miklos Santha, "Total functions in QMA", Quantum Information Processing 20 1, 35 (2021).

[19] Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandão, and Or Sattath, "The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings", Quantum 6, 668 (2022).

[20] Tamara Kohler, Stephen Piddock, Johannes Bausch, and Toby Cubitt, "General Conditions for Universality of Quantum Hamiltonians", PRX Quantum 3 1, 010308 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-28 17:35:40) and SAO/NASA ADS (last updated successfully 2023-11-28 17:35:41). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.