The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Quantum Algorithm for Linear Systems of Equations
Open accessAbstract
Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix $A$ and a vector $\stackrel{\ensuremath{\rightarrow}}{b}$, find a vector $\stackrel{\ensuremath{\rightarrow}}{x}$ such that $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$. We consider the case where one does not need to know the solution $\stackrel{\ensuremath{\rightarrow}}{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\stackrel{\ensuremath{\rightarrow}}{x}$, e.g., ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ for some matrix $M$. In this case, when $A$ is sparse, $N\ifmmode\times\else\texttimes\fi{}N$ and has condition number $\ensuremath{\kappa}$, the fastest known classical algorithms can find $\stackrel{\ensuremath{\rightarrow}}{x}$ and estimate ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ in time scaling roughly as $N\sqrt{\ensuremath{\kappa}}$. Here, we exhibit a quantum algorithm for estimating ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ whose runtime is a polynomial of $\mathrm{log}(N)$ and $\ensuremath{\kappa}$. Indeed, for small values of $\ensuremath{\kappa}$ [i.e., $\mathrm{poly}\mathrm{log}(N)$], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“On the specific applications of this algorithm [75], its use is possible in computational biology, where numeric models can be solved, and also in the domain of machine learning techniques.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [75]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“As proposed by Harrow etal. [75], the quantum algorithm is capable enough to give solutions to definite linear systems at exponentially rapid speed compared to any existing algorithm.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [75]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“The classical algorithmic complexity for this task scales polynomially in the dimension N , whereas the now-famous Harrow-Hassidim-Lloyd (HHL) quantum algorithm [3] has a complexity that scales logarithmically in N , with some scaling improvements having been proposed [134-137].”
From Variational quantum algorithms (2021) · cites this paper as [3]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“In particular, the task of matrix inversion admits an exponential quantum speedup, which could have many applications.”
From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [40]
The cited source says what the claim attributes to it.
In the citing paper
“This quantum algorithm runs in time O (log N ) , an exponential speedup relative to classical matrix inversion (for fixed error and for fixed sparsity and condition number of A ).”
From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [40]
The cited source says what the claim attributes to it.
In the citing paper
“Available pieces of literature reveal the application of quantum algorithms to solve linear [75] and differential equations [76-78], where these algorithms play the role of 'subroutines' in algorithms on data processing.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [75]
The cited source says what the claim attributes to it.
In the citing paper
“They proved that even though these traditional sampling ones are quick, any traditional algorithm, in general, needs much more time than their [75] algorithm to complete the identical matrix inversion job.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [75]
The cited source says what the claim attributes to it.
In the citing paper
“This group [75] reported that their algorithm was related to the traditional Monte Carlo ones, which are pretty quick and operate with samples of a statistical distribution involving N objects instead of using all the N constituents of distribution.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [75]
The cited source says what the claim attributes to it.
In the citing paper
“Recent research trends indicate 'data sets' which are used to define these equations, which can be enormous depending on the specific application [75], where data of the order petabytes could be required to process to get a solution.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [75]
The cited source says what the claim attributes to it.
In the citing paper
“However, aside from the caveat that the matrix A must be sparse and well conditioned, note that both the input vector | b 〉 and the output vector | A -1 b 〉 are quantum states.”
From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [40]
The cited source says what the claim attributes to it.
In the citing paper
“Assuming these constraints, x j i can be approximately produced in time polynomial in log N , d and κ . 58,59”
From Quantum algorithms: an overview (2016) · cites this paper as [58]
The cited source says what the claim attributes to it.
In the citing paper
“Indeed, one can even show that achieving a similar runtime classically would imply that classical computers could ef fi ciently simulate any polynomial-time quantum computation. 58”
From Quantum algorithms: an overview (2016) · cites this paper as [58]
The cited source says what the claim attributes to it.
In the citing paper
“The quantum algorithm of Harrow, Hassidim and Lloyd 58 (HHL) for solving systems of linear equations sidesteps this issue by ' solving ' the equations in a peculiarly quantum sense: given the ability to create the quantum state b j i ¼ P N i ¼ 1 bi i j i , and access to A , the algorithm outputs a state approximately proportional to x j i ¼ P N i ¼ 1 xi i j i .”
From Quantum algorithms: an overview (2016) · cites this paper as [58]
In the citing paper
“Second, by considering more favorable schemes for Hamiltonian decomposition 256,257 , most modern-day simulation algorithms scale in terms of τ max = t ‖ H ‖ max instead of τ , where ‖ H ‖ max is the absolute value of the largest entry of H as a matrix in the computational basis.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [257]
In the citing paper
“Childs 257 showed that given oracle access to a Hamiltonian with eigenvalues λ , one can construct a unitary quantum walk operator with eigenvalues e ± i arcsin λ .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [257]
In the citing paper
“Inserting this conditional operation in the quantum phase algorithm and using the improved phaseestimation techniques of ref. 15 yields the eigenvectors and eigenvalues to accuracy by applying the quantum phase algorithm for time t = O( -1 ), and so requires n = O(1/ 3 ) copies of the state ρ.”
From Quantum principal component analysis (2014) · cites this paper as [15]
In the citing paper
“Note that density matrix exponentiation is most effective when some of the eigenvalues of ρ are large.If all of the eigenvalues are of size O(1/d) then we require time t = O(d) to resolve the eigenvalues 15 .”
From Quantum principal component analysis (2014) · cites this paper as [15]
In the citing paper
“The Harrow-Hassidim-Lloyd (HHL) quantum algorithm [16] can solve certain linear systems exponentially faster than any known classical algorithm”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [16]
In the citing paper
“However, the algorithm proposed by Harrow, Hassidim and Lloyd [16] allows the inversion of a matrix in O log N ð Þ within some conditions.”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [16]
In the citing paper
“Reading out the function values from the quantum state |u in general requires exponential sampling, representing a so-called data”
From Solving nonlinear differential equations with differentiable quantum circuits (2021) · cites this paper as [9]
In the citing paper
“The power of HHL-based algorithms relies on amplitude encoding, where a function is represented as a quantum state |u = 2 N k=1 u k |k encoded in complex u k amplitudes of computational basis states |k for N qubits.This allows for compressing large grids into a small qubit register, providing exponential memory advantage.”
From Solving nonlinear differential equations with differentiable quantum circuits (2021) · cites this paper as [9]
In the citing paper
“When two particles for example are sent into a multiport, e.g.multimode waveguide [153,154], multimode fiber [155] or integrated waveguide structures [156], the transmission can be described as a complex bi-partite quantum walk”
From Two-photon interference: the Hong–Ou–Mandel effect (2021) · cites this paper as [154]
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
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
A scheme for efficient quantum computation with linear optics
Knill, E., Laflamme, R., & Milburn, G. J. (2001) · Nature · doi:10.1038/35051009 · Cited by 5,880
The Mathematical Theory of Finite Element Methods
Brenner, S. C., & Scott, L. R. (2007) · Texts in applied mathematics · doi:10.1007/978-0-387-75934-0 · Cited by 4,009
Lloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088 · cited 2×
“[2] S.”
BackgroundSelf-citationIntroduction to the Theory of Computation
Sipser, M. (1996) · ACM SIGACT News · doi:10.1145/230514.571645 · Cited by 2,886
An Introduction to the Conjugate Gradient Method Without the Agonizing Pain
Shewchuk, J. R. (1994) · Cited by 2,193
Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion
Hansen, P. C. (1987) · Medical Entomology and Zoology · Cited by 2,142
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680
Cleve, R., EKERT, A. K., Macchiavello, C., & Mosca, M. (1998) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1998.0164 · Cited by 1,399
Flagged first, then by citations
Research works printed but not linked: 3
- P. W. Shor, 1994, Proc. of the 35th FOCS
- P. Valiant, 2008, Proc. of the 40th Annual STOC
- L. Sheridan, 2009, J. Math Phys. A, 42, 185302
Cited by
Sorted by citations
Items 201–300 of 1,006
Forging the Future: Strategic Approaches to Quantum AI Integration for Industry Transformation
How, M.-L., & Cheah, S.-M. (2024) · AI · doi:10.3390/ai5010015 · Cited by 120
Quantum SDP-Solvers: Better upper and lower bounds
van Apeldoorn, J., Gilyén, A., Gribling, S., & de Wolf, R. (2020) · Quantum · doi:10.22331/q-2020-02-14-230 · Cited by 100
Fermion-to-qubit mappings with varying resource requirements for quantum simulation
Steudtner, M., & Wehner, S. (2018) · New Journal of Physics · doi:10.1088/1367-2630/aac54f · Cited by 113
Recent advances for quantum classifiers
Li, W., & Deng, D.-L. (2021) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-021-1793-6 · Cited by 118
Quantum Machine Learning over Infinite Dimensions
Lau, H.-K., Pooser, R. C., Siopsis, G., & Weedbrook, C. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.080501 · Cited by 104
A 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
Adiabatic Quantum Algorithm for Search Engine Ranking
Garnerone, S., Zanardi, P., & Lidar, D. A. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.230506 · Cited by 102
Quantum computing for smart grid applications
Ullah, M. H., Eskandarpour, R., Zheng, H., & Khodaei, A. (2022) · IET Generation Transmission & Distribution · doi:10.1049/gtd2.12602 · Cited by 107
Chen, S., Cotler, J. S., Huang, H.-Y., & Li, J. Z. (2023) · Nature Communications · doi:10.1038/s41467-023-41217-6 · Cited by 139
A quantum federated learning framework for classical clients
Song, Y., Wu, Y., Wu, S., Li, D., Wen, Q., Qin, S., & Gao, F. (2024) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-023-2337-2 · Cited by 111
Encoding patterns for quantum algorithms
Weigold, M., Barzen, J., Leymann, F., & Salm, M. (2021) · IET Quantum Communication · doi:10.1049/qtc2.12032 · Cited by 112
Quantum machine learning: from physics to software engineering
Melnikov, A. A., Kordzanganeh, M., Alodjants, A. P., & Lee, R. (2023) · Advances in Physics X · doi:10.1080/23746149.2023.2165452 · Cited by 125
Variable time amplitude amplification and quantum algorithms for linear algebra problems
Ambainis, A. (2012) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2012.636 · Cited by 96
Quantum computing for near-term applications in generative chemistry and drug discovery.
Pyrkov, A., Aliper, A., Bezrukov, D., Lin, Y.-C., Polykovskiy, D., Kamya, P., Ren, F., & Zhavoronkov, A. (2023) · Drug Discovery Today · doi:10.1016/j.drudis.2023.103675 · Cited by 100
A two-qubit photonic quantum processor and its application to solving systems of linear equations
Barz, S., Kassal, I., Ringbauer, M., Lipp, Y. O., Dakić, B., Aspuru-Guzik, A., & Walther, P. (2014) · Scientific Reports · doi:10.1038/srep06115 · Cited by 100
Quantum algorithm for the advection–diffusion equation simulated with the lattice Boltzmann method
Budinski, L. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-02996-3 · Cited by 115
Quantum Computational Finance: Quantum Algorithm for Portfolio Optimization
Rebentrost, P., & Lloyd, S. (2024) · Künstliche Intell. · doi:10.1007/s13218-024-00870-9 · Cited by 128
Self-citationA scalable quantum computing platform using symmetric-top molecules
Yu, P., Cheuk, L. W., Kozyryev, I., & Doyle, J. M. (2019) · New Journal of Physics · doi:10.1088/1367-2630/ab428d · Cited by 98
The potential impact of quantum computers on society
de Wolf, R. (2017) · Ethics and Information Technology · doi:10.1007/s10676-017-9439-z · Cited by 105
Nakaji, K., Uno, S., Suzuki, Y., Raymond, R., Onodera, T., Tanaka, T., Tezuka, H., Mitsuda, N., & Yamamoto, N. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.023136 · Cited by 112
Quantum simulation of partial differential equations: Applications and detailed analysis
Jin, S., Liu, N., & Yu, Y. (2023) · Physical Review A · doi:10.1103/physreva.108.032603 · Cited by 154
A comprehensive review of quantum machine learning: from NISQ to fault tolerance
Wang, Y., & Liu, J. (2024) · Reports on Progress in Physics · doi:10.1088/1361-6633/ad7f69 · Cited by 145
Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
Sun, X., Tian, G., Yang, S., Yuan, P., & Zhang, S. (2023) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2023.3244885 · Cited by 144
Huang, H.-L., Xu, X., Guo, C., Tian, G., Wei, S.-J., Sun, X., Bao, W., & Long, G. (2023) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-022-2057-y · Cited by 111
Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model
Gao, X., Wang, S.-T., & Duan, L. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.040502 · Cited by 96
Quantum computation in power systems: An overview of recent advances
Golestan, S., Habibi, M. R., Mousavi, S. Y. M., Guerrero, J. M., & Vásquez, J. C. (2022) · Energy Reports · doi:10.1016/j.egyr.2022.11.185 · Cited by 113
Variational Quantum Algorithms for Computational Fluid Dynamics
Jaksch, D., Givi, P., Daley, A. J., & Rung, T. (2023) · AIAA Journal · doi:10.2514/1.j062426 · Cited by 118
Approximate quantum Fourier transform with O(n log(n)) T gates
Nam, Y., Su, Y., & Maslov, D. A. (2020) · npj Quantum Information · doi:10.1038/s41534-020-0257-5 · Cited by 94
An improved quantum algorithm for ridge regression
Yu, C., Gao, F., & Wen, Q. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2937491 · Cited by 106
A survey on HHL algorithm: From theory to application in quantum machine learning
Duan, B., Yuan, J., Yu, C., Huang, J., & Hsieh, C. (2020) · Physics Letters A · doi:10.1016/j.physleta.2020.126595 · Cited by 99
Quantum estimation, control and learning: Opportunities and challenges
Dong, D., & Petersen, I. R. (2022) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2022.04.011 · Cited by 103
Quantum Methods for Neural Networks and Application to Medical Image Classification
Landman, J., Mathur, N., Li, Y. Y., Strahm, M., Kazdaghli, S., Prakash, A., & Kerenidis, I. (2022) · Quantum · doi:10.22331/q-2022-12-22-881 · Cited by 103
Solving Systems of Linear Equations with a Superconducting Quantum Processor
Zheng, Y., Song, C., Chen, M.-C., Xia, B., Liu, W., Guo, Q., Zhang, L., Xu, D., Deng, H., Huang, K., et al. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.210504 · Cited by 100
Improved quantum algorithms for linear and nonlinear differential equations
Krovi, H. (2023) · Quantum · doi:10.22331/q-2023-02-02-913 · Cited by 148
Quantum computing's potential for drug discovery: Early stage industry dynamics
Zinner, M., Dahlhausen, F., Boehme, P., Ehlers, J. P., Bieske, L., & Fehring, L. (2021) · Drug Discovery Today · doi:10.1016/j.drudis.2021.06.003 · Cited by 102
Quantum machine learning for support vector machine classification
Kavitha, S. S., & Kaulgud, N. (2022) · Evolutionary Intelligence · doi:10.1007/s12065-022-00756-5 · Cited by 97
Quantum computing in power systems
Zhou, Y., Tang, Z., Nikmehr, N., Babahajiani, P., Feng, F., Wei, T.-C., Zheng, H., & Zhang, P. (2022) · iEnergy · doi:10.23919/ien.2022.0021 · Cited by 105
Towards provably efficient quantum algorithms for large-scale machine-learning models
Liu, J., Liu, M., Liu, J.-P., Ye, Z., Wang, Y., Alexeev, Y., Eisert, J., & Jiang, L. (2024) · Nature Communications · doi:10.1038/s41467-023-43957-x · Cited by 121
Quantum algorithm for nonhomogeneous linear partial differential equations
Arrazola, J. M., Kalajdzievski, T. Z., Weedbrook, C., & Lloyd, S. (2019) · Physical Review A · doi:10.1103/physreva.100.032306 · Cited by 98
Self-citationAn introduction to quantum machine learning: from quantum logic to quantum deep learning
Alchieri, L., Badalotti, D., Bonardi, P., & Bianco, S. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-021-00056-8 · Cited by 102
Ranga, D., Rana, A., Prajapat, S., Kumar, P., Kumar, K., & Vasilakos, A. V. (2024) · Mathematics · doi:10.3390/math12213318 · Cited by 113
Decompositions 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 104
Fast-forwarding of Hamiltonians and exponentially precise measurements
Atia, Y., & Aharonov, D. (2017) · Nature Communications · doi:10.1038/s41467-017-01637-7 · Cited by 120
Product Decomposition of Periodic Functions in Quantum Signal Processing
Haah, J. (2019) · Quantum · doi:10.22331/q-2019-10-07-190 · Cited by 85
Quantum Bits with Josephson Junctions
Kockum, A. F., & Nori, F. (2019) · Springer series in materials science · doi:10.1007/978-3-030-20726-7_17 · Cited by 106
Towards Optimal Topology Aware Quantum Circuit Synthesis
Davis, M. G., Smith, E., Tudor, A., Sen, K., Siddiqi, I. A., & Iancu, C. (2020) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00036 · Cited by 89
Alexeev, Y., Amsler, M., Barroca, M. A., Bassini, S., Battelle, T., Camps, D., Casanova, D., Choi, Y. J., Chong, F. T., Chung, C., et al. (2024) · Future Generation Computer Systems · doi:10.1016/j.future.2024.04.060 · Cited by 138
Universal discriminative quantum neural networks
Chen, H., Wossnig, L., Severini, S., Neven, H., & Mohseni, M. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00025-7 · Cited by 89
A Quantum Mechanics-Based Framework for EEG Signal Feature Extraction and Classification
Li, Y., Zhou, R., Xu, R., Luo, J., & Jiang, S.-X. (2020) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2020.3000734 · Cited by 91
Simulating the performance of a distance-3 surface code in a linear ion trap
Trout, C. J., Li, M., Gutiérrez, M., Wu, Y., Wang, S.-T., Duan, L., & Brown, K. R. (2018) · New Journal of Physics · doi:10.1088/1367-2630/aab341 · Cited by 89
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
Quantum implementation of an artificial feed-forward neural network
Tacchino, F., Barkoutsos, P. K., Macchiavello, C., Tavernelli, I., Gerace, D., & Bajoni, D. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/abb8e4 · Cited by 96
Quantum algorithm for solving linear differential equations: Theory and experiment
Xin, T., Wei, S., Cui, J., Xiao, J., Arrazola, Í., Lamata, L., Kong, X., Lu, D., Solano, E., & Long, G. (2020) · Physical Review A · doi:10.1103/physreva.101.032307 · Cited by 90
Quantum data compression by principal component analysis
Yu, C., Gao, F., Lin, S., & Wang, J. B. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2364-9 · Cited by 89
Tong, Y., An, D., Wiebe, N., & Lin, L. (2021) · Physical Review A · doi:10.1103/physreva.104.032422 · Cited by 105
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
A Modular Quantum Compilation Framework for Distributed Quantum Computing
Ferrari, D., Carretta, S., & Amoretti, M. (2023) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2023.3303935 · Cited by 85
Pal, S., Bhattacharya, M., Lee, S.-S., & Chakraborty, C. (2024) · Molecular Biotechnology · doi:10.1007/s12033-023-00765-4 · Cited by 103
“As proposed by Harrow et al. [75], the quantum algorithm is capable enough to give solutions to definite linear systems at exponentially rapid speed compared to any existing algorithm.”
InfluentialHolevo's bound from a general quantum fluctuation theorem
Kafri, D., & Deffner, S. (2012) · Physical Review A · doi:10.1103/physreva.86.044302 · Cited by 77
Trading T gates for dirty qubits in state preparation and unitary synthesis
Low, G. H., Kliuchnikov, V., & Schaeffer, L. (2024) · Quantum · doi:10.22331/q-2024-06-17-1375 · Cited by 138
Quantum analog-digital conversion
Mitarai, K., Kitagawa, M., & Fujii, K. (2019) · Physical Review A · doi:10.1103/physreva.99.012301 · Cited by 86
Lin, L., & Tong, Y. (2020) · eScholarship (California Digital Library) · Cited by 82
Quantum Circuit Designs of Integer Division Optimizing T-Count and T-Depth
Thapliyal, H., Varun, T. S. S., Muñoz‐Coreas, E., Britt, K. A., & Humble, T. S. (2017) · IEEE International Symposium on Nanoelectronic and Information Systems (iNIS) · doi:10.1109/inis.2017.34 · Cited by 81
Bayesian deep learning on a quantum computer
Zhao, Z., Pozas-Kerstjens, A., Rebentrost, P., & Wittek, P. (2019) · Quantum Machine Intelligence · doi:10.1007/s42484-019-00004-7 · Cited by 92
Multipulse Addressing of a Raman Quantum Memory: Configurable Beam Splitting and Efficient Readout
Reim, K. F., Nunn, J., Jin, X., Michelberger, P., Champion, T. F. M., England, D. G., Lee, K. C., Kolthammer, W. S., Langford, N. K., & Walmsley, I. A. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.263602 · Cited by 81
Enhancing quantum control by bootstrapping a quantum processor of 12 qubits
Lu, D., Li, K., Li, J., Katiyar, H., Park, A. J., Feng, G., Xin, T., Li, H., Long, G., Brodutch, A., et al. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0045-z · Cited by 80
“The left one is the spectrum of C7 in the 12-qubit regime, and the right one is obtained by decoupling the (1)H channel via the Waltz-16 sequence [6].”
MethodAn applied quantum Hoare logic
Zhou, L., Yu, N., & Ying, M. (2019) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/3314221.3314584 · Cited by 80
Quantum Machine Learning: A Review and Current Status
Mishra, N., Kapil, M., Rakesh, H. R., Anand, A. K., Mishra, N., Warke, A., Sarkar, S., Dutta, S., Gupta, S., Dash, A. P., et al. (2020) · Advances in intelligent systems and computing · doi:10.1007/978-981-15-5619-7_8 · Cited by 88
A survey on the complexity of learning quantum states
Anshu, A., & Arunachalam, S. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00662-4 · Cited by 126
Gujju, Y., Matsuo, A., & Raymond, R. (2024) · Physical Review Applied · doi:10.1103/physrevapplied.21.067001 · Cited by 104
Enhancing quantum control by bootstrapping a quantum processor of 12 qubits
Lu, D., Li, K., Li, J., Katiyar, H., Park, A., Feng, G., Xin, T., Li, H., Long, G., Brodutch, A., et al. (2017) · MPG.PuRe (Max Planck Society) · Cited by 80
Quantum vs. Classical Algorithms for Solving the Heat Equation
Linden, N., Montanaro, A., & Shao, C. (2022) · Communications in Mathematical Physics · doi:10.1007/s00220-022-04442-6 · Cited by 103
Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience
Lee, Y., Joo, J., & Lee, S. (2019) · Scientific Reports · doi:10.1038/s41598-019-41324-9 · Cited by 77
An Introduction to Quantum Programming in Quipper
Green, A. S., Lumsdaine, P., Ross, N. J., Selinger, P., & Valiron, B. (2013) · International Workshop on Reversible Computation · doi:10.1007/978-3-642-38986-3_10 · Cited by 87
Quantum algorithm for association rules mining
Yu, C., Gao, F., Wang, Q.-L., & Wen, Q. (2016) · Physical Review A · doi:10.1103/physreva.94.042311 · Cited by 77
Minimizing Estimation Runtime on Noisy Quantum Computers
Wang, G., Koh, D. E., Johnson, P. D., & Cao, Y. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.010346 · Cited by 77
Quantum algorithm for the collisionless Boltzmann equation
Todorova, B. N., & Steijl, R. (2020) · Journal of Computational Physics · doi:10.1016/j.jcp.2020.109347 · Cited by 76
Quantum K-nearest neighbor classification algorithm based on Hamming distance
Li, J., Lin, S., Yu, K., & Guo, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03361-0 · Cited by 81
An, D., Liu, J.-P., & Lin, L. (2023) · Physical Review Letters · doi:10.1103/physrevlett.131.150603 · Cited by 132
Can biomass energy curtail environmental pollution? A quantum model approach to Germany
Magazzino, C., Mele, M., Schneider, N., & Shahbaz, M. Q. (2021) · Journal of Environmental Management · doi:10.1016/j.jenvman.2021.112293 · Cited by 76
Quantum computing of fluid dynamics using the hydrodynamic Schrödinger equation
Meng, Z., & Yang, Y. (2023) · Physical Review Research · doi:10.1103/physrevresearch.5.033182 · Cited by 90
Zhan, C., Dai, Z., Yin, S., Carroll, K. C., & Soltanian, M. R. (2024) · Water Research · doi:10.1016/j.watres.2024.121679 · Cited by 77
NISQ Computers: A Path to Quantum Supremacy
AbuGhanem, M., & Eleuch, H. (2024) · IEEE Access · doi:10.1109/access.2024.3432330 · Cited by 94
Parallel evaluation of quantum algorithms for computational fluid dynamics
Steijl, R., & Barakos, G. N. (2018) · Computers & Fluids · doi:10.1016/j.compfluid.2018.03.080 · Cited by 75
Generalized Quantum Signal Processing
Motlagh, D., & Wiebe, N. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.020368 · Cited by 75
Nuclear magnetic resonance for quantum computing: Techniques and recent achievements
Xin, T., Wang, B.-X., Li, K., Kong, X., Wei, S.-J., Wang, T., Ruan, D., & Long, G. (2018) · Chinese Physics B · doi:10.1088/1674-1056/27/2/020308 · Cited by 75
Quantum fast Poisson solver: the algorithm and complete and modular circuit design
Wang, S., Wang, Z., Li, W., Fan, L., Wei, Z., & Gu, Y. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02669-7 · Cited by 83
Efficient Discrete Feature Encoding for Variational Quantum Classifier
Yano, H., Suzuki, Y., Itoh, K. M., Raymond, R., & Yamamoto, N. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/qce49297.2020.00012 · Cited by 81
Forthcoming applications of quantum computing: peeking into the future
Hassija, V., Chamola, V., Goyal, A., Kanhere, S. S., & Guizani, N. (2020) · IET Quantum Communication · doi:10.1049/iet-qtc.2020.0026 · Cited by 75
Prospects of quantum computing for molecular sciences
Liu, H., Low, G. H., Steiger, D. S., Häner, T., Reiher, M., & Troyer, M. (2022) · Materials Theory · doi:10.1186/s41313-021-00039-z · Cited by 73
Scherer, A., Valiron, B., Mau, S.-C., Alexander, S., van den Berg, E., & Chapuran, T. E. (2017) · Quantum Information Processing · doi:10.1007/s11128-016-1495-5 · Cited by 73
Bugs in Quantum computing platforms: an empirical study
Paltenghi, M., & Pradel, M. (2022) · Proceedings of the ACM on Programming Languages · doi:10.1145/3527330 · Cited by 105
Low-depth quantum state preparation
Zhang, X., Yung, M., & Yuan, X. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.043200 · Cited by 84
Best practices for portfolio optimization by quantum computing, experimented on real quantum devices
Buonaiuto, G., Gargiulo, F., Pietro, G. D., Esposito, M., & Pota, M. (2023) · Scientific Reports · doi:10.1038/s41598-023-45392-w · Cited by 87
Quantum Algorithm Design: Techniques and Applications
Shao, C., Yang, L., & Li, H. (2019) · Journal of Systems Science and Complexity · doi:10.1007/s11424-019-9008-0 · Cited by 74
Adiabatic quantum linear regression
Date, P., & Potok, T. E. (2021) · Scientific Reports · doi:10.1038/s41598-021-01445-6 · Cited by 72
Quantum Reservoir Computing Using Arrays of Rydberg Atoms
Bravo, R. A., Najafi, K., Gao, X., & Yelin, S. F. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.030325 · Cited by 87
Low depth algorithms for quantum amplitude estimation
Giurgică-Tiron, T., Kerenidis, I., Labib, F., Prakash, A., & Zeng, W. J. (2022) · Quantum · doi:10.22331/q-2022-06-27-745 · Cited by 71
A hybrid classical-quantum approach for multi-class classification
Chalumuri, A., Kune, R., & Manoj, B. S. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03029-9 · Cited by 77
Quantum Fourier transform in computational basis
Zhou, S. S., Loke, T., Izaac, J., & Wang, J. B. (2017) · Quantum Information Processing · doi:10.1007/s11128-017-1515-0 · Cited by 69
Metadata
- Authors
- Harrow, A. W., Hassidim, A., & Lloyd, S.
- Affiliations
- University of Bristol (GB)
- Massachusetts Institute of Technology (US)
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2009-10-07
- Volume
- 103
- Issue
- 15
- Pages
- 150502-150502
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W1492999010
- Semantic Scholar
- ed562f0c86c80f75a8b9ac7344567e8b44c8d643
- Cited by
- 3,325
- References
- 34
- Citations by year
- 2026: 355 · 2025: 553 · 2024: 478 · 2023: 429 · 2022: 332 · 2021: 337 · 2020: 231 · 2019: 181 · 2018: 98 · 2017: 102 · 2016: 53 · 2015: 35 · 2014: 39 · 2013: 33 · 2012: 40
- FWCI
- 23.75
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Physical Review Letters (publishedVersion)
- arXiv (Cornell University) (publishedVersion)
- PubMed (publishedVersion)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
- arXiv (Cornell University)
- PIRSA
- Bulletin of the American Physical Society
- Funders
- W. M. Keck Foundation
- Engineering and Physical Sciences Research Council (GR/S82169/01)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum algorithms, systems of linear equations, sparse matrices, condition number, expectation value estimation, quantum advantage
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
