The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
Open accessAbstract
An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325
Quantum principal component analysis
Lloyd, S., Mohseni, M., & Rebentrost, P. (2014) · Nature Physics · doi:10.1038/nphys3029 · Cited by 1,385
Hamiltonian Simulation by Qubitization
Low, G. H., & Chuang, I. L. (2019) · Quantum · doi:10.22331/q-2019-07-12-163 · Cited by 854
Self-citationOptimal Hamiltonian Simulation by Quantum Signal Processing
Low, G. H., & Chuang, I. L. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.010501 · Cited by 769
Self-citationSimulating Hamiltonian Dynamics with a Truncated Taylor Series
Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.090502 · Cited by 742 · cited 3×
“The methodology we describe is a distilled version of the results of a series of works on quantum algorithms [6, 11, 16, 17, 30, 41].”
MethodEfficient Quantum Algorithms for Simulating Sparse Hamiltonians
Berry, D. W., Ahokas, G., Cleve, R., & Sanders, B. C. (2007) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0150-x · Cited by 692
Childs, A. M., Kothari, R., & Somma, R. D. (2017) · SIAM Journal on Computing · doi:10.1137/16m1087072 · Cited by 646 · cited 4×
“The methodology we describe is a distilled version of the results of a series of works on quantum algorithms [6, 11, 16, 17, 30, 41].”
BackgroundMethodInfluentialQuantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001) · Journal of the ACM · doi:10.1145/502090.502097 · Cited by 639
(2004) · doi:10.1109/focs.2004.53 · Cited by 599
Toward the first quantum simulation with quantum speedup
Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., & Su, Y. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801723115 · Cited by 551
Self-citationQuantum Algorithm for Data Fitting
Wiebe, N., Braun, D., & Lloyd, S. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.050505 · Cited by 528
Self-citationAmin, M. H., Andriyash, E., Rolfe, J., Kulchytskyy, B., & Melko, R. (2018) · Physical Review X · doi:10.1103/physrevx.8.021050 · Cited by 520
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters
Berry, D. W., Childs, A. M., & Kothari, R. (2015) · 2015 IEEE 56th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.54 · Cited by 372
Exponential improvement in precision for simulating sparse Hamiltonians
Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D. (2014) · Proceedings of the forty-sixth annual ACM symposium on Theory of computing · doi:10.1145/2591796.2591854 · Cited by 324
Magniez, F., Nayak, A., Roland, J., & Santha, M. (2011) · SIAM Journal on Computing · doi:10.1137/090745854 · Cited by 294
Quantum Recommendation Systems
Kerenidis, I., & Prakash, A. (2016) · arXiv · doi:10.48550/arxiv.1603.08675 · Cited by 270
Marriott, C., & Watrous, J. (2005) · computational complexity · doi:10.1007/s00037-005-0194-x · Cited by 241
Fixed-Point Quantum Search with an Optimal Number of Queries
Yoder, T. J., Low, G. H., & Chuang, I. L. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.210501 · Cited by 223
Self-citationQuantum algorithms for Gibbs sampling and hitting-time estimation
Chowdhury, A. C. N., & Somma, R. D. (2017) · Quantum Information and Computation · doi:10.26421/qic17.1-2-3 · Cited by 219
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2004) · 45th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.54 · Cited by 216
Essai sur la géométrie à $n$ dimensions
Jordan, C. (1875) · Bulletin de la Société mathématique de France · doi:10.24033/bsmf.90 · Cited by 212
Grover, L. K. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.150501 · Cited by 210
Poulin, D., & Wocjan, P. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.220502 · Cited by 207
Product Decomposition of Periodic Functions in Quantum Signal Processing
Haah, J. (2019) · Quantum · doi:10.22331/q-2019-10-07-190 · Cited by 183
Proceedings 44th IEEE Symposium on Foundations of Computer Science - FOCS 2003
(2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238173 · Cited by 161
Arbitrary phases in quantum amplitude amplification
Høyer, P. (2000) · Physical Review A · doi:10.1103/physreva.62.052304 · Cited by 160
Methodology of Resonant Equiangular Composite Quantum Gates
Low, G. H., Yoder, T. J., & Chuang, I. L. (2016) · Physical Review X · doi:10.1103/physrevx.6.041067 · Cited by 159 · cited 10×
“(Flexible) Quantum Signal Processing [44] [43] [41] [42] Quantum Singular Value Transf.”
BackgroundMethodResultInfluentialSelf-citationQuantum Speed-Ups for Solving Semidefinite Programs
Brandao, F. G. S. L., & Svore, K. M. (2017) · 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) · doi:10.1109/focs.2017.45 · Cited by 142 · cited 2×
“These techniques played a crucial role in improving the complexity of quantum semi-definite program solvers, where the scaling with accuracy was improved from the initial O(1/ε32) [14] to O(1/ε4) [4].”
BackgroundDecompositions of n-qubit Toffoli Gates with Linear Circuit Complexity
He, Y., Luo, M.-X., Zhang, E., Wang, H.-K., & Wang, X. (2017) · International Journal of Theoretical Physics · doi:10.1007/s10773-017-3389-4 · Cited by 133
Chakraborty, S., Gilyén, A., & Jeffery, S. (2019) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.icalp.2019.33 · Cited by 127
Self-citationA Combinatorial, Primal-Dual Approach to Semidefinite Programs
Arora, S., & Kale, S. (2016) · Journal of the ACM · doi:10.1145/2837020 · Cited by 120
Faster Algorithms via Approximation Theory
Sachdeva, S., & Vishnoi, N. K. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000065 · Cited by 98
Why haven't more quantum algorithms been found?
Shor, P. W. (2003) · Journal of the ACM · doi:10.1145/602382.602408 · Cited by 97
Hamiltonian simulation with optimal sample complexity
Kimmel, S., Lin, C. Y.-Y., Low, G. H., Ozols, M., & Yoder, T. J. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0013-7 · Cited by 85
Self-citationApproximating fractional time quantum evolution
Sheridan, L., Maslov, D. A., & Mosca, M. (2009) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/42/18/185302 · Cited by 38
On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma
Gilyén, A., & Sattath, O. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.47 · Cited by 25
Self-citation
Cited by
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560
Hamiltonian Simulation by Qubitization
Low, G. H., & Chuang, I. L. (2019) · Quantum · doi:10.22331/q-2019-07-12-163 · Cited by 854
Self-citationA review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 408
Herman, D., Googin, C., Liu, X., Sun, Y., Galda, A., Safro, I., Pistoia, M., & Alexeev, Y. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00603-1 · Cited by 284
Variational Quantum Simulation of General Processes
Endo, S., Sun, J., Li, Y., Benjamin, S. C., & Yuan, X. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.010501 · Cited by 237
Metadata
- Authors
- Gilyén, A., Su, Y., Low, G. H., & Wiebe, N.
- Venue
- Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
- Publisher
- ACM
- Published
- 2019-06-23
- Pages
- 193-204
- OpenAlex
- W2805612073
- Cited by
- 542
- References
- 39
- FWCI
- 9.02
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.