Document Open Access Logo

Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers

Authors Abhijit S. Mudigonda , R. Ryan Williams

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2021.50.pdf
  • Filesize: 0.6 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • Time-space tradeoffs
  • lower bounds
  • QMA

Metrics

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

Abstract

A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the SAT problem and related problems within the polynomial-time hierarchy. For example, for the SAT problem, the state-of-the-art is that the problem cannot be solved by random-access machines in n^c time and n^o(1) space simultaneously for c < 2cos(π/7) ≈ 1.801. 
We extend this lower bound approach to the quantum and randomized domains. Combining Grover’s algorithm with components from SAT time-space lower bounds, we show that there are problems verifiable in O(n) time with quantum Merlin-Arthur protocols that cannot be solved in n^c time and n^o(1) space simultaneously for c < (3+√3)/2 ≈ 2.366, a super-quadratic time lower bound. This result and the prior work on SAT can both be viewed as consequences of a more general formula for time lower bounds against small-space algorithms, whose asymptotics we study in full. 
We also show lower bounds against randomized algorithms: there are problems verifiable in O(n) time with (classical) Merlin-Arthur protocols that cannot be solved in n^c randomized time and O(log n) space simultaneously for c < 1.465, improving a result of Diehl. For quantum Merlin-Arthur protocols, the lower bound in this setting can be improved to c < 1.5.

Cite As Get BibTex

Abhijit S. Mudigonda and R. Ryan Williams. Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.50

Author Details

Abhijit S. Mudigonda
  • Portland, OR, USA
R. Ryan Williams
  • EECS and CSAIL, MIT, Cambridge, MA, USA

Funding

  • Williams, R. Ryan: Supported by NSF CCF-1909429 and CCF-1741615.

Acknowledgements

We thank the anonymous reviewers for helpful comments. The first author thanks Ryan Williams for his support and patience throughout this research. The first author also thanks Aram Harrow, Peter Shor, Saeed Mehraban, Ashwin Sah, and Lisa Yang for contributing office space and helpful conversations and Lijie Chen and Shyan Akmal for reading and editing a draft of this manuscript. Lastly, the first author apologizes to the Theory Group at MIT CSAIL eating so many of the chocolate-covered pretzels.

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1), February 2009. URL: https://doi.org/10.1145/1490270.1490272.
  2. Sanjeev Arora and Boaz Barak. Computational complexity: A modern approach. Cambridge University Press, Cambridge, 2009. URL: https://doi.org/10.1017/CBO9780511804090.
  3. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P = ?N P question. SIAM J. Comput., 4(4):431-442, 1975. URL: https://doi.org/10.1137/0204037.
  4. Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In STOC'13 - Proceedings of the 2013 ACM Symposium on Theory of Computing, pages 111-120. ACM, New York, 2013. URL: https://doi.org/10.1145/2488608.2488623.
  5. Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46(4-5):493-505, 1998. Google Scholar
  6. Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308-311, 2018. Google Scholar
  7. Samuel R Buss and Ryan Williams. Limits on alternation trading proofs for time-space lower bounds. computational complexity, 24(3):533-600, 2015. Google Scholar
  8. Scott Diehl. Lower bounds for swapping arthur and merlin. In APPROX-RANDOM, 2007. Google Scholar
  9. Scott Diehl. Lower bounds for swapping arthur and merlin. In Moses Charikar, Klaus Jansen, Omer Reingold, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 449-463, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. Google Scholar
  10. Scott Diehl and Dieter van Melkebeek. Time-space lower bounds for the polynomial-time hierarchy on randomized machines. SIAM J. Comput., 36(3):563-594, 2006. URL: https://doi.org/10.1137/050642228.
  11. Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. J. ACM, 52(6):835-865, 2005. URL: https://doi.org/10.1145/1101821.1101822.
  12. Lov K Grover. A fast quantum mechanical algorithm for database search. arXiv preprint, 1996. URL: http://arxiv.org/abs/quant-ph/9605043.
  13. Yael Tauman Kalai, Omer Paneth, and Lisa Yang. How to delegate computations publicly. In STOC'19 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1115-1124. ACM, New York, 2019. URL: https://doi.org/10.1145/3313276.3316411.
  14. Yael Tauman Kalai, Omer Paneth, and Lisa Yang. Delegation with updatable unambiguous proofs and ppad-hardness. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020, pages 652-673, Cham, 2020. Springer International Publishing. Google Scholar
  15. Ravindran Kannan. Towards separating nondeterminism from determinism. Math. Systems Theory, 17(1):29-45, 1984. URL: https://doi.org/10.1007/BF01744432.
  16. Clemens Lautemann. BPP and the polynomial hierarchy. Inform. Process. Lett., 17(4):215-217, 1983. URL: https://doi.org/10.1016/0020-0190(83)90044-3.
  17. Dylan M. McKay and Richard Ryan Williams. Quadratic time-space lower bounds for computing natural functions with a random oracle. In 10th Innovations in Theoretical Computer Science, volume 124 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 56, 20. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. Google Scholar
  18. V. Nepomnjascii. Rudimentary predicates and turing calculations. Doklady Mathematics, 11:1462-1465, 1970. Google Scholar
  19. Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000. Google Scholar
  20. Noam Nisan. RL ⊆ SC. Comput. Complexity, 4(1):1-11, 1994. URL: https://doi.org/10.1007/BF01205052.
  21. Ran Raz and Avishay Tal. Oracle separation of BQP and PH. In STOC'19 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 13-23. ACM, New York, 2019. URL: https://doi.org/10.1145/3313276.3316315.
  22. Alexander A. Razborov and Steven Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. URL: https://doi.org/10.1006/jcss.1997.1494.
  23. Dieter van Melkebeek and Thomas Watson. Time-space efficient simulations of quantum computations. Theory Comput., 8:1-51, 2012. URL: https://doi.org/10.4086/toc.2012.v008a001.
  24. Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 515-526. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316404.
  25. R. Ryan Williams. Time-space tradeoffs for counting NP solutions modulo integers. In In Proceedings of the 22nd IEEE Conference on Computational Complexity, pages 70-82. IEEE, 2007. Google Scholar
  26. Ryan Williams. Inductive time-space lower bounds for sat and related problems. Journal of Computational Complexity, 15:433-470, 2006. URL: https://doi.org/10.1007/s00037-007-0221-1.
  27. Ryan Williams. Alternation-trading proofs, linear programming, and lower bounds. ACM Trans. Comput. Theory, 5(2):Art. 6, 49, 2013. URL: https://doi.org/10.1145/2493246.2493249.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact