research-article
Authors: Sevag Gharibian and François Le Gall
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
June 2022
Pages 19 - 32
Published: 10 June 2022 Publication History
- 4citation
- 396
- Downloads
Metrics
Total Citations4Total Downloads396Last 12 Months150
Last 6 weeks13
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
Get Access
- Get Access
- References
- Media
- Tables
- Share
Abstract
The Quantum Singular Value Transformation (QSVT) is a recent technique that gives a unified framework to describe most quantum algorithms discovered so far, and may lead to the development of novel quantum algorithms. In this paper we investigate the hardness of classically simulating the QSVT. A recent result by Chia, Gilyén, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can be efficiently “dequantized” for low-rank matrices, and discussed its implication to quantum machine learning. In this work, motivated by establishing the superiority of quantum algorithms for quantum chemistry and making progress on the quantum PCP conjecture, we focus on the other main class of matrices considered in applications of the QSVT, sparse matrices. We first show how to efficiently “dequantize”, with arbitrarily small constant precision, the QSVT associated with a low-degree polynomial. We apply this technique to design classical algorithms that estimate, with constant precision, the singular values of a sparse matrix. We show in particular that a central computational problem considered by quantum algorithms for quantum chemistry (estimating the ground state energy of a local Hamiltonian when given, as an additional input, a state sufficiently close to the ground state) can be solved efficiently with constant precision on a classical computer. As a complementary result, we prove that with inverse-polynomial precision, the same problem becomes BQP-complete. This gives theoretical evidence for the superiority of quantum algorithms for chemistry, and strongly suggests that said superiority stems from the improved precision achievable in the quantum setting. We also discuss how this dequantization technique may help make progress on the central quantum PCP conjecture.
References
[1]
Scott Aaronson. 2009. Why quantum chemistry is hard. Nature Physics, 5 (2009), 707–708. https://doi.org/10.1038/nphys1415
[2]
Scott Aaronson and Alex Arkhipov. 2011. The Computational Complexity of Linear Optics. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (STOC 2011). 333–342. isbn:978-1-4503-0691-1 https://doi.org/10.1145/1993636.1993682
Digital Library
[3]
Daniel S. Abrams and Seth Lloyd. 1999. Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors. Physical Review Letters, 83 (1999), 5162–5165. https://doi.org/10.1103/PhysRevLett.83.5162
[4]
Dorit Aharonov, Itai Arad, and Thomas Vidick. 2013. Guest column: the quantum PCP conjecture. SIGACT News, 44, 2 (2013), 47–79. https://doi.org/10.1145/2491533.2491549 ArXiv: 1309.7495
Digital Library
[5]
Dorit Aharonov and Amnon Ta-Shma. 2003. Adiabatic Quantum State Generation and Statistical Zero Knowledge. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2003). 20–29. isbn:1581136749 https://doi.org/10.1145/780542.780546
Digital Library
[6]
Andris Ambainis. 2014. On physical problems that are slightly more difficult than QMA. In Proceedings of the 29th IEEE Conference on Computational Complexity (CCC 2014). 32–43.
Digital Library
[7]
Frank Arute, Kunal Arya, and Ryan Babbush. 2019. Quantum supremacy using a programmable superconducting processor. Nature, 574 (2019), 505–510.
[8]
Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon. 2005. Simulated Quantum Computation of Molecular Energies. Science, 309, 5741 (2005), 1704–1707. https://doi.org/10.1126/science.1113479
[9]
Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. 2020. Quantum Algorithms for Quantum Chemistry and Quantum Materials Science. Chemical Reviews, 120, 22 (2020), 12685–12717. https://doi.org/10.1021/acs.chemrev.9b00829 arxiv:https://doi.org/10.1021/acs.chemrev.9b00829.
[10]
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. 2014. Exponential Improvement in Precision for Simulating Sparse Hamiltonians. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC 2014). 283–292. isbn:9781450327107 https://doi.org/10.1145/2591796.2591854
Digital Library
[11]
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. 2019. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15 (2019), 159–163.
[12]
Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. 2002. Quantum amplitude amplification and estimation. Contemp. Math., 305 (2002), 53–74.
[13]
Sergey B. Bravyi and Alexei Yu. Kitaev. 2002. Fermionic Quantum Computation. Annals of Physics, 298, 1 (2002), 210–226. issn:0003-4916 https://doi.org/10.1006/aphy.2002.6254
[14]
Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. 2021. Variational quantum algorithms. Nature Reviews Physics, 3 (2021), 625–644. https://doi.org/s42254-021-00348-9
[15]
Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. 2019. The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (LIPIcs, Vol. 132). 33:1–33:14. https://doi.org/10.4230/LIPIcs.ICALP.2019.33
[16]
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. 2020. 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 (STOC 2020). 387–400. https://doi.org/10.1145/3357713.3384314
Digital Library
[17]
Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. 2020. Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020) (LIPIcs, Vol. 181). 47:1–47:17. https://doi.org/10.4230/LIPIcs.ISAAC.2020.47
[18]
Stephen Cook. 1972. The complexity of theorem proving procedures. In Proceedings of the 3rd ACM Symposium on Theory of Computing (STOC 1972). 151–158.
[19]
Charles Derby, Joel Klassen, Johannes Bausch, and Toby Cubitt. 2021. Compact fermion to qubit mappings. Physical Review B, 104 (2021), 035118. https://doi.org/10.1103/PhysRevB.104.035118
[20]
Pablo Echenique and José Luis Alonso. 2007. A mathematical and computational review of Hartree–Fock SCF methods in quantum chemistry. Molecular Physics, 105, 23-24 (2007), 3057–3098. https://doi.org/10.1080/00268970701757875 arxiv:https://doi.org/10.1080/00268970701757875.
[21]
Lior Eldar and Aram W. Harrow. 2017. Local Hamiltonians Whose Ground States Are Hard to Approximate. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017). 427–438. https://doi.org/10.1109/FOCS.2017.46
[22]
Michael H. Freedman and Matthew B. Hastings. 2014. Quantum systems on non-k-hyperfinite complexes: a generalization of classical statistical mechanics on expander graphs. Quantum Information and Computation, 14, 1-2 (2014), 144–180. https://doi.org/10.26421/QIC14.1-2-9
[23]
Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. 2004. Fast Monte-Carlo algorithms for finding low-rank approximations. Journal of the ACM, 51, 6 (2004), 1025–1041. https://doi.org/10.1145/1039488.1039494
Digital Library
[24]
Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. 2015. Quantum Hamiltonian Complexity. Foundations and Trends in Theoretical Computer Science, 10, 3 (2015), 159–282. https://doi.org/10.1561/0400000066
Digital Library
[25]
Sevag Gharibian and Julia Kempe. 2012. Hardness of approximation for quantum problems. arXiv:quant-ph/1209.1055
[26]
Sevag Gharibian and Julia Kempe. 2012. Hardness of approximation for quantum problems. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012). 387–398.
Digital Library
[27]
Sevag Gharibian and Justin Yirka. 2019. The complexity of simulating local measurements on quantum systems. Quantum, 3 (2019), 189. issn:2521-327X https://doi.org/10.22331/q-2019-09-30-189
[28]
András Gilyén, Zhao Song, and Ewin Tang. 2020. An improved quantum-inspired algorithm for linear regression. arXiv:2009.07268. arxiv:2009.07268 ArXiv:2009.07268
[29]
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. 2019. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). 193–204. https://doi.org/10.1145/3313276.3316366
Digital Library
[30]
Alex Bredariol Grilo. 2018. Quantum proofs, the local Hamiltonian problem and applications. (Preuves quantiques, le problème des Hamiltoniens locaux et applications). Ph. D. Dissertation. Sorbonne Paris Cité, France. https://tel.archives-ouvertes.fr/tel-02152364
[31]
Alex B. Grilo, Iordanis Kerenidis, and Jamie Sikora. 2016. QMA with Subset State Witnesses. Chicago Journal of Theoretical Computer Science, 2016 (2016), 4. http://cjtcs.cs.uchicago.edu/articles/2016/4/contents.html
[32]
Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. 212–219. https://doi.org/10.1145/237814.237866
Digital Library
[33]
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum Algorithm for Linear Systems of Equations. Physical Review Letters, 103 (2009), 150502. https://doi.org/10.1103/PhysRevLett.103.150502 Full version available as ArXiv: 0811.3171
[34]
Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. 1986. Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science, 43 (1986), 169–188. https://doi.org/10.1016/0304-3975(86)90174-X
[35]
Dhawal Jethwani, François Le Gall, and Sanjay K. Singh. 2020. Quantum-Inspired Classical Algorithms for Singular Value Transformation. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) (LIPIcs, Vol. 170). 53:1–53:14. https://doi.org/10.4230/LIPIcs.MFCS.2020.53
[36]
Zhang Jiang, Jarrod McClean, Ryan Babbush, and Hartmut Neven. 2019. Majorana Loop Stabilizer Codes for Error Mitigation in Fermionic Quantum Simulations. Physical Review Applied, 12 (2019), 064041. https://doi.org/10.1103/PhysRevApplied.12.064041
[37]
Pascual Jordan and Eugene Wigner. 1928. Über das Paulische Äquivalenzverbot. Zeitschrift für Physik, 47 (1928), 631–651.
[38]
Alexei Yu. Kitaev. 1995. Quantum measurements and the Abelian Stabilizer Problem. arXiv:quant-ph/9511026
[39]
Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. 2002. Classical and Quantum Computation. American Mathematical Society.
Digital Library
[40]
Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush. 2021. Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction. PRX Quantum, 2 (2021), 030305. https://doi.org/10.1103/PRXQuantum.2.030305
[41]
Leonid Levin. 1973. Universal search problems. Problems of Information Transmission, 9, 3 (1973), 265–266.
[42]
Lin Lin and Yu Tong. 2020. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4 (2020), 361. https://doi.org/10.22331/q-2020-11-11-361
[43]
Seth Lloyd. 1996. Universal Quantum Simulators. Science, 273, 5278 (1996), 1073–1078. https://doi.org/10.1126/science.273.5278.1073
[44]
Guang Hao Low and Isaac L. Chuang. 2017. Hamiltonian Simulation by Uniform Spectral Amplification. arxiv:1707.05391. ArXiv: 1707.05391
[45]
Guang Hao Low and Isaac L. Chuang. 2019. Hamiltonian Simulation by Qubitization. Quantum, 3 (2019), 163. issn:2521-327X https://doi.org/10.22331/q-2019-07-12-163
[46]
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. 2011. Search via Quantum Walk. SIAM J. Comput., 40, 1 (2011), 142–164. https://doi.org/10.1137/090745854
Digital Library
[47]
John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. 2021. A Grand Unification of Quantum Algorithms. arxiv:2105.02859. arXiv: 2105.02859
[48]
Jarrod R. McClean, Ryan Babbush, Peter J. Love, and Alán Aspuru-Guzik. 2014. Exploiting Locality in Quantum Computation for Quantum Chemistry. The Journal of Physical Chemistry Letters, 5, 24 (2014), 4368–4380. https://doi.org/10.1021/jz501649m arxiv:https://doi.org/10.1021/jz501649m. 26273989
[49]
Ashley Montanaro. 2015. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471, 2181 (2015), 20150301. https://doi.org/10.1098/rspa.2015.0301 arxiv:https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.2015.0301.
[50]
Tobias J. Osborne. 2012. Hamiltonian complexity. Reports on Progress in Physics, 75, 2 (2012), 022001. http://stacks.iop.org/0034-4885/75/i=2/a=022001
[51]
Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer. 2017. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences, 114, 29 (2017), 7555–7560. issn:0027-8424 https://doi.org/10.1073/pnas.1619152114 arxiv:https://www.pnas.org/content/114/29/7555.full.pdf.
[52]
Alessandro Rudi, Leonard Wossnig, Carlo Ciliberto, Andrea Rocchetto, Massimiliano Pontil, and Simone Severini. 2020. Approximating Hamiltonian dynamics with the Nyström method. Quantum, 4 (2020), 234. issn:2521-327X https://doi.org/10.22331/q-2020-02-20-234
[53]
Norbert Schuch and Frank Verstraete. 2009. Computational complexity of interacting electrons and fundamental limitations of density functional theory. Nature Physics, 5 (2009), 732–735. https://doi.org/10.1038/nphys1370
[54]
Martin Schwarz and Maarten Van den Nest. 2013. Simulating quantum circuits with sparse output distributions. arxiv:1310.6749. arXiv: 1310.6749
[55]
Kanav Setia, Sergey Bravyi, Antonio Mezzacapo, and James D. Whitfield. 2019. Superfast encodings for fermionic quantum simulation. Physical Review Research, 1 (2019), 033033. https://doi.org/10.1103/PhysRevResearch.1.033033
[56]
Mark Steudtner and Stephanie Wehner. 2019. Quantum codes for quantum simulation of fermions on a square lattice of qubits. Physical Review A, 99 (2019), 022308. https://doi.org/10.1103/PhysRevA.99.022308
[57]
Mario Szegedy. 2004. Quantum Speed-Up of Markov Chain Based Algorithms. In Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004). 32–41. https://doi.org/10.1109/FOCS.2004.53
Digital Library
[58]
Ewin Tang. 2019. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). 217–228. https://doi.org/10.1145/3313276.3316310
Digital Library
[59]
Maarten Van Den Nest. 2011. Simulating Quantum Computers with Probabilistic Methods. Quantum Information and Computation, 11, 9–10 (2011), 784–812. issn:1533-7146
[60]
Frank Verstraete and Juan Ignacio Cirac. 2005. Mapping local Hamiltonians of fermions to local Hamiltonians of spins. Journal of Statistical Mechanics: Theory and Experiment, 2005, 09 (2005), P09012–P09012. https://doi.org/10.1088/1742-5468/2005/09/p09012
[61]
James D. Whitfield, Vojtěch Havlíček, and Matthias Troyer. 2016. Local spin operators for fermion simulations. Physical Review A, 94 (2016), 030301. https://doi.org/10.1103/PhysRevA.94.030301
[62]
James Daniel Whitfield, Peter John Love, and Alán Aspuru-Guzik. 2013. Computational complexity in electronic structure. Physical Chemistry Chemical Physics, 15 (2013), 397–411. https://doi.org/10.1039/C2CP42695A
[63]
Pawel Wocjan and Shengyu Zhang. 2006. Several natural BQP-Complete problems. ArXiv: 0606179
Cited By
View all
- Gharibian S(2024)Guest Column: The 7 faces of quantum NPACM SIGACT News10.1145/3639528.363953554:4(54-91)Online publication date: 3-Jan-2024
https://dl.acm.org/doi/10.1145/3639528.3639535
- Chen CHuang HPreskill JZhou LMohar BShinkar IO'Donnell R(2024)Local Minima in Quantum SystemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649675(1323-1330)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649675
- Zhang RWang GJohnson P(2022)Computing Ground State Properties with Early Fault-Tolerant Quantum ComputersQuantum10.22331/q-2022-07-11-7616(761)Online publication date: 11-Jul-2022
- Show More Cited By
Index Terms
Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture
Theory of computation
Models of computation
Quantum computation theory
Quantum complexity theory
Recommendations
- Quantum correlation swapping
Quantum correlations (QCs), including quantum entanglement and those different, are important quantum resources and have attracted much attention recently. Quantum entanglement swapping as a kernel technique has already been applied to quantum repeaters ...
Read More
- Can quantum discord increase in a quantum communication task?
Quantum teleportation of an unknown quantum state is one of the few communication tasks which has no classical counterpart. Usually the aim of teleportation is to send an unknown quantum state to a receiver. But is it possible in some way that the ...
Read More
- Construction of general quantum channel for quantum teleportation
We investigate teleportation and controlled teleportation of an arbitrary $$N$$ -qubit state by using a multipartite entanglement channel. By establishing one-to-one correspondence between an $$N$$ -qubit quantum state and a high-dimension quantum state, we ...
Read More
Comments
Information & Contributors
Information
Published In
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
June 2022
1698 pages
ISBN:9781450392648
DOI:10.1145/3519935
- General Chair:
- Stefano Leonardi
Sapienza University of Rome, Italy
, - Program Chair:
- Anupam Gupta
Carnegie Mellon University, USA
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [emailprotected].
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 10 June 2022
Permissions
Request permissions for this article.
Check for updates
Author Tags
- Quantum singular value transform
- dequantization
- local Hamiltonian
- quantum PCP
- quantum chemistry
Qualifiers
- Research-article
Conference
STOC '22
Sponsor:
- SIGACT
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
4
Total Citations
396
Total Downloads
- Downloads (Last 12 months)150
- Downloads (Last 6 weeks)13
Other Metrics
View Author Metrics
Citations
Cited By
View all
- Gharibian S(2024)Guest Column: The 7 faces of quantum NPACM SIGACT News10.1145/3639528.363953554:4(54-91)Online publication date: 3-Jan-2024
https://dl.acm.org/doi/10.1145/3639528.3639535
- Chen CHuang HPreskill JZhou LMohar BShinkar IO'Donnell R(2024)Local Minima in Quantum SystemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649675(1323-1330)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649675
- Zhang RWang GJohnson P(2022)Computing Ground State Properties with Early Fault-Tolerant Quantum ComputersQuantum10.22331/q-2022-07-11-7616(761)Online publication date: 11-Jul-2022
- Tang E(2022)Dequantizing algorithms to understand quantum advantage in machine learningNature Reviews Physics10.1038/s42254-022-00511-w4:11(692-693)Online publication date: 5-Sep-2022
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderMedia
Figures
Other
Tables
