Document Open Access Logo

A Framework of Quantum Strong Exponential-Time Hypotheses

Authors Harry Buhrman, Subhasree Patro, Florian Speelman

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.19.pdf
  • Filesize: 0.8 MB
  • 19 pages

Document Identifiers

Author Details

Harry Buhrman
  • QuSoft, CWI, Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands
Subhasree Patro
  • QuSoft, CWI, Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands
Florian Speelman
  • QuSoft, CWI, Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands

Funding

SP is supported by the Robert Bosch Stiftung. HB, SP, and FS are additionally supported by NWO Gravitation grants NETWORKS and QSC, and EU grant QuantAlgo.

Acknowledgements

We would like to thank Andris Ambainis, Gilles Brassard, Frédéric Magniez, Miklos Santha, Mario Szegedy, and Ronald de Wolf for helpful discussions.

Cite AsGet BibTex

Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.19

Abstract

The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It essentially states that determining whether a CNF formula is satisfiable can not be done faster than exhaustive search over all possible assignments. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are very likely beyond current techniques. In this work, we introduce an extensive framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to what SETH is for classical computation. Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in P. As an example, we provide a conditional quantum time lower bound of Ω(n^1.5) for the Longest Common Subsequence and Edit Distance problems. We also show that the n² SETH-based lower bound for a recent scheme for Proofs of Useful Work carries over to the quantum setting using our framework, maintaining a quadratic gap between verifier and prover. Lastly, we show that the assumptions in our framework can not be simplified further with relativizing proof techniques, as they are false in relativized worlds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Quantum complexity theory
Keywords
  • complexity theory
  • fine-grained complexity
  • longest common subsequence
  • edit distance
  • quantum query complexity
  • strong exponential-time hypothesis

Metrics

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

Related Versions

References

  1. Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang. On the quantum complexity of closest pair and related problems. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.01973.
  2. Scott Aaronson, Daniel Grier, and Luke Schaeffer. A Quantum Query Complexity Trichotomy for Regular Languages. Electronic Colloquium on Computational Complexity (ECCC), 26:61, 2019. URL: https://eccc.weizmann.ac.il/report/2019/061.
  3. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Quadratic-time hardness of LCS and other sequence similarity measures. CoRR, abs/1501.07053, 2015. URL: http://arxiv.org/abs/1501.07053.
  4. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pages 59-78, Washington, DC, USA, 2015. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2015.14.
  5. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating Branching Programs with Edit Distance and Friends Or: a Polylog Shaved is a Lower Bound Made. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 375-388, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2897518.2897653.
  6. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In ICALP, 2014. Google Scholar
  7. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 41-50, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2746539.2746594.
  8. Andris Ambainis. Quantum lower bounds by quantum arguments. In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC '00, pages 636-643, New York, NY, USA, 2000. ACM. URL: https://doi.org/10.1145/335305.335394.
  9. Andris Ambainis, Kaspars Balodis, Janis Iraids, Kamil Khadiev, Vladislavs Klevickis, Krisjanis Prusis, Yixin Shen, Juris Smotrovs, and Jevgenijs Vihrovs. Quantum lower and upper bounds for 2d-grid and dyck language. In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 8:1-8:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.8.
  10. Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, and Shigeru Yamashita. Quantum identification of boolean oracles. In Volker Diekert and Michel Habib, editors, STACS 2004, pages 105-116, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  11. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). STOC, 2015. Google Scholar
  12. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM Journal on computing, 4(4):431-442, 1975. Google Scholar
  13. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Proofs of useful work. Cryptology ePrint Archive, Report 2017/203, 2017. URL: https://eprint.iacr.org/2017/203.
  14. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (im) possibility of obfuscating programs. Journal of the ACM (JACM), 59(2):1-48, 2012. Google Scholar
  15. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48(4):778-797, July 2001. URL: https://doi.org/10.1145/502090.502097.
  16. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510-1523, October 1997. URL: https://doi.org/10.1137/S0097539796300933.
  17. E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411-1473, 1997. URL: https://doi.org/10.1137/S0097539796300921.
  18. Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: Quantum and mapreduce. CoRR, abs/1804.04178, 2018. URL: http://arxiv.org/abs/1804.04178.
  19. 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
  20. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS '14, pages 661-670, Washington, DC, USA, 2014. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2014.76.
  21. Karl Bringmann and Marvin Kunnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pages 79-97, Washington, DC, USA, 2015. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2015.15.
  22. Harry Buhrman, Subhasree Patro, and Florian Speelman. A framework of quantum strong exponential-time hypotheses, 2019. URL: http://arxiv.org/abs/1911.05686.
  23. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity, CCC '06, pages 252-260, Washington, DC, USA, 2006. IEEE Computer Society. URL: https://doi.org/10.1109/CCC.2006.6.
  24. Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, and Michael E. Saks. Approximating edit distance within constant factor in truly sub-quadratic time. CoRR, abs/1810.03664, 2018. URL: http://arxiv.org/abs/1810.03664.
  25. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41:1-41:24, May 2016. URL: https://doi.org/10.1145/2925416.
  26. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. Exponential time complexity of the permanent and the tutte polynomial. ACM Transactions on Algorithms (TALG), 10(4):21, 2014. Google Scholar
  27. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Limit on the speed of quantum computation in determining parity. Phys. Rev. Lett., 81:5442-5444, December 1998. URL: https://doi.org/10.1103/PhysRevLett.81.5442.
  28. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC '96, pages 212-219, New York, NY, USA, 1996. ACM. URL: https://doi.org/10.1145/237814.237866.
  29. Cupjin Huang, Michael Newman, and Mario Szegedy. Explicit lower bounds on strong quantum simulation. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.10368.
  30. Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani. Does looking inside a circuit help? In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  31. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  32. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  33. Robin Kothari. An optimal quantum algorithm for the oracle identification problem. In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 482-493, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.482.
  34. William J. Masek and Michael S. Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980. URL: https://doi.org/10.1016/0022-0000(80)90002-1.
  35. Tomoyuki Morimae and Suguru Tamaki. Fine-grained quantum computational supremacy. Quantum Information & Computation, 19(13&14):1089-1115, 2019. URL: http://www.rintonpress.com/xxqic19/qic-19-1314/1089-1115.pdf.
  36. Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An improved exponential-time algorithm for k-SAT. J. ACM, 52(3):337-364, May 2005. URL: https://doi.org/10.1145/1066100.1066101.
  37. Jorg Van Renterghem. The implications of breaking the strong exponential time hypothesis on a quantum computer. Master’s thesis, Ghent University, 2019. URL: https://lib.ugent.be/fulltxt/RUG01/002/787/416/RUG01-002787416_2019_0001_AC.pdf.
  38. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis. IPEC, 2015. Google Scholar
  39. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, 2018. To appear. Google Scholar
  40. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2):357-365, December 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
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