Document Open Access Logo

Quantum Meets the Minimum Circuit Size Problem

Authors Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.47.pdf
  • Filesize: 0.66 MB
  • 16 pages

Document Identifiers

Author Details

Nai-Hui Chia
  • Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, IN, USA
Chi-Ning Chou
  • School of Engineering and Applied Sciences, Harvard University, Boston, MA, USA
Jiayu Zhang
  • Department of Computer Science, Boston University, MA, USA
  • Computing and Mathematical Sciences, California Institute and Technology, Pasadena, CA, USA
Ruizhe Zhang
  • Department of Computer Science, The University of Texas at Austin, TX, USA

Funding

  • Chia, Nai-Hui: This work was support by the U.S. Department of Defense and NIST through the Hartree Postdoctoral Fellowship at QuICS and by NSF through IUCRC Planning Grant Indiana University: Center for Quantum Technologies (CQT) under award number 2052730.
  • Chou, Chi-Ning: This work was supported by Boaz Barak’s NSF awards CCF 1565264 and CNS 1618026.
  • Zhang, Jiayu: This work was supported by Adam Smith’s NSF awards 1763786.
  • Zhang, Ruizhe: This work was supported by Dana Moshkovitz’s NSF Grant CCF-1648712 and Scott Aaronson’s Vannevar Bush Faculty Fellowship from the US Department of Defense.

Acknowledgements

We are grateful to Scott Aaronson and Boaz Barak for helpful discussions and valuable comments on our manuscript. We would like to thank Lijie Chen, Kai-Min Chung, Matthew Coudron, Yanyi Liu, and Fang Song for useful discussions.

Cite AsGet BibTex

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.47

Abstract

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory - its hardness is mysterious, and a better understanding of its hardness can have surprising implications to many fields in computer science. We first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for three natural objects: Boolean functions, unitaries, and quantum states. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the relations between the three quantum MCSPs and their variants. We discover that some reductions that are not known for classical MCSP exist for quantum MCSPs for unitaries and states, e.g., search-to-decision reductions and self-reductions. Finally, we systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity) and also find new connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting. Our findings could be of interest for future studies, and we post several open problems for further exploration along this direction.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • Quantum Computation
  • Quantum Complexity
  • Minimum Circuit Size Problem

Metrics

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

Related Versions

References

  1. Scott Aaronson. Oracles are subtle but not malicious. In 21st Annual IEEE Conference on Computational Complexity (CCC'06), pages 15-pp. IEEE, 2006. Google Scholar
  2. Scott Aaronson. The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint, 2016. URL: http://arxiv.org/abs/1607.05256.
  3. Scott Aaronson. Shadow tomography of quantum states. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 325-338, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3188745.3188802.
  4. Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang. On the quantum complexity of closest pair and related problems. In 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  5. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014, pages 25-32, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. Google Scholar
  6. Srinivasan Arunachalam and Ronald de Wolf. Guest column: A survey of quantum learning theory. ACM SIGACT News, 48(2):41-67, 2017. Google Scholar
  7. Srinivasan Arunachalam, Alex B Grilo, Tom Gur, Igor C Oliveira, and Aarthi Sundaram. Quantum learning algorithms imply circuit lower bounds. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.01920.
  8. Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195-202, 2017. Google Scholar
  9. Andrej Bogdanov and Luca Trevisan. On worst‐case to average‐case reductions for np problems. SIAM Journal on Computing, 36(4):1119-1159, 2006. Google Scholar
  10. Adam Bouland, Bill Fefferman, and Umesh Vazirani. Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1-63:2, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.63.
  11. Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses. In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1-19:19, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Google Scholar
  12. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Proceedings of the 31st Conference on Computational Complexity, CCC '16, Dagstuhl, DEU, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  13. Shouvanik Chakrabarti, Chi-Ning Chou, Kai-Min Chung, and Xiaodi Wu. Scalable verification of quantum supremacy based on circuit obfuscation. Manuscript, 2021. Google Scholar
  14. Lijie Chen, Shuichi Hirahara, Igor C Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam. Beyond natural proofs: Hardness magnification and locality. Leibniz International Proceedings in Informatics, 151, 2020. Google Scholar
  15. Nai-Hui Chia, Sean Hallgren, and Fang Song. On Basing One-way Permutations on NP-hard Problems under Quantum Reductions. Quantum, 4:312, August 2020. Google Scholar
  16. Alessandro Cosentino, Robin Kothari, and Adam Paetznick. Dequantizing read-once quantum formulas. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  17. Lisa Hellerstein and Rocco A Servedio. On PAC learning algorithms for rich Boolean function classes. Theoretical Computer Science, 384(1):66-76, 2007. Google Scholar
  18. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within np. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 247-258. IEEE, 2018. Google Scholar
  19. Shuichi Hirahara, Igor C Oliveira, and Rahul Santhanam. Np-hardness of minimum circuit size problem for or-and-mod circuits. In 33rd Computational Complexity Conference (CCC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  20. R. Ilango. AC0[p] lower bounds and np-hardness for variants of mcsp. Electron. Colloquium Comput. Complex., 26:21, 2019. Google Scholar
  21. Rahul Ilango. Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas. In Shubhangi Saraf, editor, 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:35. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  22. Rahul Ilango. Constant depth formula and partial function versions of mcsp are hard. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 424-433. IEEE, 2020. Google Scholar
  23. Rahul Ilango, Bruno Loff, and Igor C. Oliveira. Np-hardness of circuit minimization for multi-output functions. In 35th Computational Complexity Conference (CCC 2020), CCC '20, Dagstuhl, DEU, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.22.
  24. Rahul Ilango, Hanlin Ren, and Rahul Santhanam. Hardness on any samplable distribution suffices: New characterizations of one-way functions by meta-complexity. Electron. Colloquium Comput. Complex., 28:82, 2021. Google Scholar
  25. Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The power of natural properties as oracles. In 33rd Computational Complexity Conference (CCC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  26. Russell Impagliazzo and Avi Wigderson. P= BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 220-229, 1997. Google Scholar
  27. Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology - CRYPTO 2018, pages 126-152, Cham, 2018. Springer International Publishing. Google Scholar
  28. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.04383.
  29. Valentine Kabanets and Jin-Yi Cai. Circuit minimization problem. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 73-79, 2000. Google Scholar
  30. Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), 2017. Google Scholar
  31. William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1-2:20, 2021. Google Scholar
  32. Yanyi Liu and R. Pass. On one-way functions and kolmogorov complexity. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1243-1254, 2020. Google Scholar
  33. Yanyi Liu and Rafael Pass. A note on one-way functions and sparse languages. Electron. Colloquium Comput. Complex., 28:92, 2021. Google Scholar
  34. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631-633, 2014. Google Scholar
  35. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 760-776. SIAM, 2011. Google Scholar
  36. William J Masek. Some np-complete set covering problems. Unpublished Manuscript, 1979. Google Scholar
  37. Cody D Murray and R Ryan Williams. On the (non) np-hardness of computing circuit complexity. Theory of Computing, 13(1):1-22, 2017. Google Scholar
  38. Igor C Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness. arXiv preprint, 2016. URL: http://arxiv.org/abs/1611.01190.
  39. Igor Carboni Oliveira. Advances in hardness magnification. https://www.dcs.warwick.ac.uk/~igorcarb/documents/papers/magnification-note.pdf, 2019.
  40. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. In 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  41. Igor Carboni Oliveira and Rahul Santhanam. Hardness magnification for natural problems. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 65-76. IEEE, 2018. Google Scholar
  42. Alexander A Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 1(55):24-35, 1997. Google Scholar
  43. Hanlin Ren and Rahul Santhanam. A relativization perspective on meta-complexity. Electron. Colloquium Comput. Complex., 28:89, 2021. Google Scholar
  44. Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124-134. Ieee, 1994. Google Scholar
  45. Boris A Trakhtenbrot. A survey of russian approaches to perebor (brute-force searches) algorithms. Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
  46. Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-1142, 1984. Google Scholar
  47. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, volume 3, pages 3431-3472. World Scientific, 2018. Google Scholar
  48. A Chi-Chih Yao. Quantum circuit complexity. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 352-361. IEEE, 1993. 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