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 · 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 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].”
BackgroundMethodInfluential
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
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145
Tang, E. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.060503 · Cited by 140
Drug design on quantum computers
(2024) · doi:10.1038/s41567-024-02411-5 · Cited by 132
The Python’s Lunch: geometric obstructions to decoding Hawking radiation
Brown, A. R., Gharibyan, H., Penington, G., & Susskind, L. (2020) · Journal of High Energy Physics · doi:10.1007/jhep08(2020)121 · Cited by 124
“(9)There are also other known lower bounds for more general classes of algorithms that perform amplitude amplification [20, 21, 22] and which are closely related to our state-independent protocol from Appendix A.”
BackgroundA Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
Niu, S., Suau, A., Staffelbach, G., & Todri-Sanial, A. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3026544 · Cited by 103
“It promises to solve classically intractable computational problems such as integer factorisation [36], quantum chemistry [9], linear algebra [7, 18, 21, 22, 35, 43], or optimisation [15, 24, 25].”
BackgroundProspects and challenges of quantum finance
Bouland, A., van Dam, W., Joorati, H., Kerenidis, I., & Prakash, A. (2020) · arXiv · doi:10.48550/arxiv.2011.06492 · Cited by 46
Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
Dong, Y., & Lin, L. (2021) · Physical Review A · doi:10.1103/physreva.103.062412 · Cited by 34
Artificial neural network encoding of molecular wavefunctions for quantum computing
Hagai, M., Sugiyama, M., Tsuda, K., & Yanai, T. (2023) · Digital Discovery · doi:10.1039/d2dd00093h · Cited by 5
Quantum algorithm for metabolic network analysis
Joshi, A., & Koyama, T. (2026) · Machine Learning with Applications · doi:10.1016/j.mlwa.2026.100913
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.