Document Open Access Logo

StoqMA Meets Distribution Testing

Author Yupan Liu

PDF
Thumbnail PDF

File

LIPIcs.TQC.2021.4.pdf
  • Filesize: 0.96 MB
  • 22 pages

Document Identifiers

Author Details

Yupan Liu
  • Shenzhen, China

Funding

The author was supported by ISF Grant No. 1721/17 when he was affiliated with the Hebrew University of Jerusalem.

Acknowledgements

The author thanks Alex B. Grilo for his contribution during the early stage of Section 4.1, and the proof of Proposition 19. The author also thanks anonymous reviewers for pointing out an error in the proof of Proposition 16 and valuable suggestions. Additionally, the author thanks Tomoyuki Morimae and Dorit Aharonov for helpful discussion. Circuit diagrams were drawn by the Quantikz package [Kay, 2018].

Cite AsGet BibTex

Yupan Liu. StoqMA Meets Distribution Testing. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.TQC.2021.4

Abstract

StoqMA captures the computational hardness of approximating the ground energy of local Hamiltonians that do not suffer the so-called sign problem. We provide a novel connection between StoqMA and distribution testing via reversible circuits. First, we prove that easy-witness StoqMA (viz. eStoqMA, a sub-class of StoqMA) is contained in MA. Easy witness is a generalization of a subset state such that the associated set’s membership can be efficiently verifiable, and all non-zero coordinates are not necessarily uniform. This sub-class eStoqMA contains StoqMA with perfect completeness (StoqMA₁), which further signifies a simplified proof for StoqMA₁ ⊆ MA [Bravyi et al., 2006; Bravyi and Terhal, 2010]. Second, by showing distinguishing reversible circuits with ancillary random bits is StoqMA-complete (as a comparison, distinguishing quantum circuits is QMA-complete [Janzing et al., 2005]), we construct soundness error reduction of StoqMA. Additionally, we show that both variants of StoqMA that without any ancillary random bit and with perfect soundness are contained in NP. Our results make a step towards collapsing the hierarchy MA ⊆ StoqMA ⊆ SBP [Bravyi et al., 2006], in which all classes are contained in AM and collapse to NP under derandomization assumptions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • StoqMA
  • distribution testing
  • error reduction
  • reversible circuits

Metrics

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

Related Versions

References

  1. Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum lower bounds for approximate counting via laurent polynomials. In Proceedings of the 35th Computational Complexity Conference, pages 1-47, 2020. Google Scholar
  2. Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Symposium on Simplicity in Algorithms, pages 24-32. SIAM, 2020. Google Scholar
  3. Dorit Aharonov and Alex B Grilo. Two combinatorial ma-complete problems. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  4. Dorit Aharonov, Alex B Grilo, and Yupan Liu. StoqMA vs. MA: the power of error reduction. arXiv preprint arXiv:2010.02835, 2020. Google Scholar
  5. László Babai. Trading group theory for randomness. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 421-429, 1985. Google Scholar
  6. Itay Berman, Akshay Degwekar, Ron D Rothblum, and Prashant Nalini Vasudevan. Statistical difference beyond the polarizing regime. In Theory of Cryptography Conference, pages 311-332. Springer, 2019. Google Scholar
  7. Elmar Böhler, Christian Glaßer, and Daniel Meister. Error-bounded probabilistic computations between MA and AM. Journal of Computer and System Sciences, 72(6):1043-1076, 2006. Google Scholar
  8. Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002. Google Scholar
  9. Sergey Bravyi, Arvid J Bessen, and Barbara M Terhal. Merlin-arthur games and stoquastic complexity. arXiv preprint quant-ph/0611021, 2006. Google Scholar
  10. Sergey Bravyi, David P Divincenzo, Roberto Oliveira, and Barbara M Terhal. The complexity of stoquastic local hamiltonian problems. Quantum Information & Computation, 8(5):361-385, 2008. Google Scholar
  11. Sergey Bravyi and Matthew Hastings. On complexity of the quantum ising model. Communications in Mathematical Physics, 349(1):1-45, 2017. Google Scholar
  12. Sergey Bravyi and Barbara Terhal. Complexity of stoquastic frustration-free hamiltonians. SIAM Journal on Computing, 39(4):1462-1485, 2010. Google Scholar
  13. Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. Google Scholar
  14. Clément Canonne and Ronitt Rubinfeld. Testing probability distributions underlying aggregated data. In International Colloquium on Automata, Languages, and Programming, pages 283-295. Springer, 2014. Google Scholar
  15. Clément L Canonne. A survey on distribution testing: Your data is big. but is it blue? Theory of Computing, pages 1-100, 2020. Google Scholar
  16. Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 387-400, 2020. Google Scholar
  17. Toby Cubitt and Ashley Montanaro. Complexity classification of local hamiltonian problems. SIAM Journal on Computing, 45(2):268-316, 2016. Google Scholar
  18. Constantinos Daskalakis, Gautam Kamath, and John Wright. Which distribution distances are sublinearly testable? In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2747-2764. SIAM, 2018. Google Scholar
  19. Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. Space-efficient error reduction for unitary quantum computations. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  20. Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  21. Martin Furer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos. On completeness and soundness in interactive proof systems. Advainces in Computing Research: A Research Annual,, 5:429-442, 1989. Google Scholar
  22. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 59-68, 1986. Google Scholar
  23. Alex B. Grilo. Private communication, 2020. Google Scholar
  24. Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012. Google Scholar
  25. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672-694, 2002. Google Scholar
  26. Dominik Janzing, Pawel Wocjan, and Thomas Beth. "non-identity-check" is QMA-complete. International Journal of Quantum Information, 3(03):463-473, 2005. Google Scholar
  27. Stephen P Jordan. Strong equivalence of reversible circuits is coNP-complete. Quantum Information & Computation, 14(15-16):1302-1307, 2014. Google Scholar
  28. Alastair Kay. Tutorial on the quantikz package. arXiv preprint arXiv:1809.03842, 2018. Google Scholar
  29. Alexei Kitaev. Quantum NP. Talk at AQIP, 99, 1999. Google Scholar
  30. Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. Classical and quantum computation. American Mathematical Soc., 2002. Google Scholar
  31. Adam R Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501-1526, 2002. Google Scholar
  32. Peter Bro Miltersen and N Variyam Vinodchandran. Derandomizing arthur-merlin games using hitting sets. Computational Complexity, 14(3):256-279, 2005. Google Scholar
  33. Tomoyuki Morimae and Harumichi Nishimura. Merlinization of complexity classes above bqp. Quantum Information & Computation, 17(11-12):959-972, 2017. Google Scholar
  34. Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002. Google Scholar
  35. Ronitt Rubinfeld and Rocco A Servedio. Testing monotone high-dimensional distributions. Random Structures & Algorithms, 34(1):24-44, 2009. Google Scholar
  36. Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. Journal of the ACM (JACM), 50(2):196-249, 2003. Google Scholar
  37. Yu Tanaka. Exact non-identity check is NQP-complete. International Journal of Quantum Information, 8(05):807-819, 2010. Google Scholar
  38. Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217-228, 2019. Google Scholar
  39. Ramgopal Venkateswaran and Ryan O'Donnell. Quantum approximate counting with nonadaptive grover iterations. In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 59:1-59:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  40. Ilya Volkovich. The untold story of SBP. In International Computer Science Symposium in Russia, pages 393-405. Springer, 2020. Google Scholar
  41. John Watrous. Succinct quantum proofs for properties of finite groups. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 537-546. IEEE, 2000. Google Scholar
  42. Thomas Watson. The complexity of estimating min-entropy. Computational Complexity, 25(1):153-175, 2016. 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