Document Open Access Logo

Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)

Authors Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.58.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Sevag Gharibian
  • University of Paderborn, Paderborn, North Rhine-Westphalia, Germany, and Virginia Commonwealth University, Richmond, Virginia, USA
Miklos Santha
  • CNRS, IRIF, Université Paris Diderot, Paris, France and Centre for Quantum Technologies, National University of Singapore, Singapore
Jamie Sikora
  • Perimeter Institute for Theoretical Physics, Waterloo, Ontario, Canada
Aarthi Sundaram
  • Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, Maryland, USA
Justin Yirka
  • Virginia Commonwealth University, Richmond, Virginia, USA

Cite AsGet BibTex

Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka. Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.58

Abstract

The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH does not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, QCPH, uses classical proofs, and the second, QPH, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, Q Sigma_3, into NEXP using the Ellipsoid Method for efficiently solving semidefinite programs. These results yield two implications for QMA(2), the variant of Quantum Merlin-Arthur (QMA) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs "equivalent"), then QMA(2) is in the Counting Hierarchy (specifically, in P^{PP^{PP}}). Second, unless QMA(2)= Q Sigma_3 (i.e., alternating quantifiers do not help in the presence of "unentanglement"), QMA(2) is strictly contained in NEXP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
  • Theory of computation → Complexity classes
  • Theory of computation → Semidefinite programming
Keywords
  • Complexity Theory
  • Quantum Computing
  • Polynomial Hierarchy
  • Semidefinite Programming
  • QMA(2)
  • Quantum Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor. The power of unentanglement. Theory of Computing, 5:1-42, 2009. URL: http://dx.doi.org/10.4086/toc.2009.v005a001.
  2. S. Aaronson, A. Cojocaru, A. Gheorghiu, and E. Kashefi. On the implausibility of classical client blind quantum computing. Available at arXiv.org e-Print quant-ph/1704.08482, 2017. Google Scholar
  3. S. Aaronson and A. Drucker. A full characterization of quantum advice. SIAM Journal on Computing, 43(3):1131-1183, 2014. Google Scholar
  4. D. Aharonov. A simple proof that Toffoli and Hadamard are quantum universal. Available at arXiv.org e-Print quant-ph/0301040, jan 2003. URL: http://arxiv.org/abs/quant-ph/0301040.
  5. D. Aharonov, M. Ben-Or, F. Brandão, and O. Sattath. The pursuit for uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings. Available at arXiv.org e-Print quant-ph/0810.4840v1, 2008. Google Scholar
  6. D. Aharonov and T. Naveh. Quantum NP - A survey. Available at arXiv.org e-Print quant-ph/0210077v1, 2002. Google Scholar
  7. E. W. Allender and K. W. Wagner. Counting hierarchies: Polynomial time and constant depth circuits, pages 469-483. World Scientific, 1993. URL: http://dx.doi.org/10.1142/9789812794499_0035.
  8. A. Ambainis. On physical problems that are slightly more difficult than QMA. In Proceedings of 29th IEEE Conference on Computational Complexity (CCC 2014), pages 32-43, 2014. Google Scholar
  9. S. Beigi. NP vs QMA_log(2). Quantum Information and Computation, 10:0141-0151, 2010. Google Scholar
  10. H. Blier and A. Tapp. All languages in NP have very short quantum proofs. In Proceedings of the 3rd International Conference on Quantum, Nano and Micro Technologies, pages 34-37, 2009. Google Scholar
  11. S. Fenner, L. Fortnow, S. A. Kurtz, and L. Li. An oracle builder’s toolkit. Information and Computation, 182(2):95-136, 2003. URL: http://dx.doi.org/10.1016/S0890-5401(03)00018-X.
  12. L. Fortnow. The role of relativization in complexity theory. Bulletin of the European Association for Theoretical Computer Science, 52:52-229, 1994. Google Scholar
  13. L. Fortnow and J. Rogers. Complexity limitations on quantum computation. Journal of Computer and System Sciences, 59(2):240-252, 1999. Google Scholar
  14. S. Gharibian and J. Kempe. Hardness of approximation for quantum problems. In Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), pages 387-398, 2012. Google Scholar
  15. S. Gharibian and J. Yirka. The complexity of simulating local measurements on quantum systems. In Mark M. Wilde, editor, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), volume 73 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1-2:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.TQC.2017.2.
  16. O. Goldreich. On promise problems: A survey. Theoretical Computer Science, 3895:254-290, 2006. Google Scholar
  17. M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1993. Google Scholar
  18. R. A. Horn and C. H. Johnson. Matrix Analysis. Cambridge University Press, 1990. Google Scholar
  19. R. Jain, Z. Ji, S. Upadhyay, and J. Watrous. QIP = PSPACE. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pages 573-581, 2010. Google Scholar
  20. S. P. Jordan, H. Kobayashi, D. Nagaj, and H. Nishimura. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information &Computation, 12(5 & 6):461-471, 2012. Google Scholar
  21. R. M. Karp and R. J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC '80, pages 302-309, New York, NY, USA, 1980. ACM. URL: http://dx.doi.org/10.1145/800141.804678.
  22. A. Kitaev, A. Shen, and M. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002. Google Scholar
  23. A. Kitaev and J. Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC 2000), pages 608-617, 2000. Google Scholar
  24. Y.-K. Liu, M. Christandl, and F. Verstraete. Quantum computational complexity of the N-representability problem: QMA complete. Physical Review Letters, 98:110503, 2007. Google Scholar
  25. J. Lockhart and C. E. González-Guillén. Quantum state isomorphism. arXiv preprint arXiv:1709.09622, 2017. Google Scholar
  26. C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, 1992. URL: http://dx.doi.org/10.1145/146585.146605.
  27. C. Marriott and J. Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14(2):122-152, 2005. Google Scholar
  28. A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential time. In Proceedings of the 13th Symposium on Foundations of Computer Science, pages 125-129, 1972. Google Scholar
  29. A. Pereszlényi. Multi-prover quantum Merlin-Arthur proof systems with small gap. Available at arXiv.org e-Print quant-ph/1205.2761, 2012. Google Scholar
  30. S. Toda. PP is as hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing, 20:865-877, 1991. Google Scholar
  31. L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85-93, 1986. Google Scholar
  32. N. V. Vinodchandran. A note on the circuit complexity of pp. TCS, 347(1-2):415-418, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2005.07.032.
  33. M. Vyalyi. QMA=PP implies that PP contains PH. Electronic Colloquium on Computational Complexity, 2003. Google Scholar
  34. J. Watrous. Semidefinite programs for completely bounded norms. Theory of Computing, 5:217-238, 2009. Google Scholar
  35. C. Wrathall. Complete sets and the Polynomial-Time Hierarchy. Theoretical Computer Science, 3(1):23-33, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90062-1.
  36. T. Yamakami. Quantum NP and a quantum hierarchy. In Proceedings of the 2nd IFIP International Conference on Theoretical Computer Science, pages 323-336. Kluwer Academic Publishers, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact