Quantum algorithm for solving linear differential equations: Theory and experiment
Open accessThe DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Abstract
Solving linear differential equations (LDEs) is a hard problem for classical computers, while quantum algorithms have been proposed to be capable of speeding up the calculation. However, they are yet to be realized in experiment as it cannot be easily converted into an implementable quantum circuit. Here, we present and experimentally realize an implementable gate-based quantum algorithm for efficiently solving the LDE problem: given an $N\ifmmode\times\else\texttimes\fi{}N$ matrix $\mathcal{M}$, an $N$-dimensional vector $\mathbf{b}$, and an initial vector $\mathbf{x}(0)$, we obtain a target vector $\mathbf{x}(t)$ as a function of time $t$ according to the constraint $d\mathbf{x}(t)/dt=\mathcal{M}\mathbf{x}(t)+\mathbf{b}$. We show that our algorithm exhibits an exponential speedup over its classical counterpart in certain circumstances, and a gate-based quantum circuit is produced which is friendly to the experimentalists and implementable in current quantum techniques. In addition, we experimentally solve a $4\ifmmode\times\else\texttimes\fi{}4$ linear differential equation using our quantum algorithm in a four-qubit nuclear magnetic resonance quantum information processor. Our algorithm provides a key technique for solving many important problems which rely on the solutions to linear differential equations.
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
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
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
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
Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
Moler, C., & Van Loan, C. (2003) · SIAM Review · doi:10.1137/s00361445024180 · Cited by 2,357
Khaneja, N., Reiss, T., Kehlet, C., Schulte-Herbrüggen, T., & Glaser, S. J. (2005) · Journal of Magnetic Resonance · doi:10.1016/j.jmr.2004.11.004 · Cited by 1,854
Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., & Chuang, I. L. (2001) · Nature · doi:10.1038/414883a · Cited by 1,738
On the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295
Ensemble quantum computing by NMR spectroscopy
Cory, D. G., Fahmy, A. F., & Havel, T. F. (1997) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.94.5.1634 · Cited by 964
Giovannetti, V., Lloyd, S., & Maccone, L. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.160501 · Cited by 935
Cited by
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
A quantum convolutional neural network on NISQ devices
Wei, S., Chen, Y., Zhou, Z., & Long, G. (2022) · AAPPS Bulletin · doi:10.1007/s43673-021-00030-3 · Cited by 192
Self-citationSolving nonlinear differential equations with differentiable quantum circuits
Kyriienko, O., Paine, A. E., & Elfving, V. E. (2021) · Physical Review A · doi:10.1103/physreva.103.052416 · Cited by 185
Solving nonlinear differential equations with differentiable quantum circuits
Kyriienko, O., Paine, A. E., & Elfving, V. E. (2020) · arXiv · doi:10.48550/arxiv.2011.10395 · Cited by 185
Metadata
- Authors
- Xin, T., Wei, S., Cui, J., Xiao, J., Arrazola, I., Lamata, L., Kong, X., Lu, D., Solano, E., & Long, G.
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2020-03-06
- Volume
- 101
- Issue
- 3
- ISSN
- 0556-2791 (ISSN-L)
- 2469-9926
- 2469-9934
- OpenAlex
- W2846182818
- Cited by
- 86
- References
- 23
- FWCI
- 5.49
- Type
- journal article
- 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.