Fetching the paper…
Reading the bibliography…
We present a quantum algorithm to solve systems of linear equations of the form $A\mathbf{x}=\mathbf{b}$, where $A$ is a tridiagonal Toeplitz matrix and $\mathbf{b}$ results from discretizing an analytic function, with a circuit complexity of $poly(\log(\kappa), 1/\sqrt{\epsilon}, \log(N))$, where $N$ denotes the number of equations, $\epsilon$ is the accuracy, and $\kappa$ the condition number.
1904
Earlier work this paper cites.
1905
Earlier work this paper cites.
1907
Earlier work this paper cites.
L. F. Richardson, “The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam,” Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character , vol. 210, pp. 307–357, 1911
1911
Earlier work this paper cites.
D. E. Knuth, “Evaluation of polynomials by computer,” Commun. ACM , vol. 5, no. 12, pp. 595–599, Dec. 1962
1962
Earlier work this paper cites.
G. Strang, “On the Construction and Comparison of Difference Schemes,” SIAM Journal on Numerical Analysis , vol. 5, no. 3, pp. 506–517, Sep 1968
1968
Earlier work this paper cites.
H. H. Wang, “A parallel method for tridiagonal equations,” ACM Trans. Math. Softw. , vol. 7, no. 2, pp. 170–183, Jun. 1981
1981
Earlier work this paper cites.
R. P. Feynman, “Simulating physics with computers,” International Journal of Theoretical Physics , vol. 21, no. 6, pp. 467–488, Jun 1982
1982
Earlier work this paper cites.
E. Tadmor, “The exponential accuracy of fourier and chebyshev differencing methods,” SIAM Journal on Numerical Analysis , vol. 23, no. 1, pp. 1–10, 1986
1986
Earlier work this paper cites.
E. B. Saff and V. Totik, “Polynomial approximation of piecewise analytic functions,” Journal of the London Mathematical Society , vol. s2-39, no. 3, pp. 487–498, 1989
1989
Earlier work this paper cites.
M. Suzuki, “General theory of fractal path integrals with applications to many-body theories and statistical physics,” Journal of Mathematical Physics , vol. 32, no. 2, pp. 400–407, 1991
1991
Earlier work this paper cites.
J. Demmel, “The componentwise distance to the nearest singular matrix,” SIAM Journal on Matrix Analysis and Applications , vol. 13, no. 1, pp. 10–19, 1992
1992
Earlier work this paper cites.
J. R. Shewchuk, “An introduction to the conjugate gradient method without the agonizing pain,” Pittsburgh, PA, USA, Tech. Rep., 1994
1994
Earlier work this paper cites.
R. M. Corless, G. H. Gonnet, D. E. G. Hare et al. , “On the Lambert W function,” Advances in Computational Mathematics , vol. 5, no. 4, pp. 329–359, 1996
1996
Earlier work this paper cites.
D. Ventura and T. R. Martinez, “Initializing the amplitude distribution of a quantum state,” Foundations of Physics Letters , vol. 12, pp. 547–559, 1998
1998
Earlier work this paper cites.
G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, “Quantum amplitude amplification and estimation,” arXiv e-prints , 2000, arXiv:quant-ph/0005055
2000
Earlier work this paper cites.
G. L. Long and Y. Sun, “Efficient scheme for initializing a quantum register with an arbitrary superposed state,” Phys. Rev. A - Atomic, Molecular, and Optical Physics , vol. 64, no. 1, p. 4, 2001
2001
Earlier work this paper cites.
L. Grover and T. Rudolph, “Creating superpositions that correspond to efficiently integrable probability distributions,” arXiv e-prints , 2002, arXiv:quant-ph/0208112
2002
Earlier work this paper cites.
B. E. Baaquie, C. Corianò, and M. Srikant, “Quantum Mechanics, Path Integrals and Option Pricing:. Reducing the Complexity of Finance,” in Nonlinear Physics - Theory and Experiment II , Apr 2003, pp. 333–339
2003
Earlier work this paper cites.
A. M. Childs, R. Cleve, E. Deotto et al. , “Exponential algorithmic speedup by a quantum walk,” in Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing , ser. STOC ’03. New York, NY, USA: ACM, 2003, pp. 59–68
2003
Earlier work this paper cites.
D. Aharonov and A. Ta-Shma, “Adiabatic quantum state generation and statistical zero knowledge,” in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing , ser. STOC ’03. New York, NY, USA: Association for Computing Machinery, 2003, pp. 20–29
2003
Earlier work this paper cites.
P. Deuflhard and A. Hohmann, Numerical Analysis in Modern Scientific Computing . Springer New York, 2003
2003
Earlier work this paper cites.
G. Ahokas, “Improved Algorithms for Approximate Quantum Fourier Transmforms and Sparse Hamiltonian Simulations,” 2004
2004
Earlier work this paper cites.
M. Möttönen, J. J. Vartiainen, V. Bergholm, and M. M. Salomaa, “Transformation of quantum states using uniformly controlled rotations,” Quantum Info. Comput. , vol. 5, no. 6, pp. 467–473, Sep. 2005
2005
Earlier work this paper cites.
V. V. Shende, S. S. Bullock, and I. L. Markov, “Synthesis of quantum logic circuits,” in Proceedings of the 2005 Asia and South Pacific Design Automation Conference , ser. ASP-DAC ’05. New York, NY, USA: ACM, 2005, pp. 272–275
2005
Earlier work this paper cites.
2005
Cited alongside, same era.
2005
Cited alongside, same era.
W.-C. Yueh, “Eigenvalues of several tridiagonal matrices,” Applied Mathematics E-Notes [electronic only] , vol. 5, 01 2005
2005
Cited alongside, same era.
2005
Cited alongside, same era.
S. Aaronson, “Read the fine print,” Nature Physics , vol. 11, pp. 291–293, Apr. 2015
2015
Later among the works it cites.
D. W. Berry, A. M. Childs, and R. Kothari, “Hamiltonian simulation with nearly optimal dependence on all parameters,” in Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , ser. FOCS ’15. Washington, DC, USA: IEEE Computer Society, 2015, pp. 792–809
2015
Later among the works it cites.
A. Montanaro and S. Pallister, “Quantum algorithms and the finite element method,” Phys. Rev. A , vol. 93, 12 2015
2015
Later among the works it cites.
D. Berry and L. Novo, “Corrected quantum walk for optimal hamiltonian simulation,” Quantum Info. Comput. , vol. 16, no. 15-16, pp. 1295–1317, Nov. 2016
2016
Later among the works it cites.
J. C. Butcher, Numerical Methods for Ordinary Differential Equations , 3rd ed. Wiley, 7 2016, chapter 33
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2006
Cited alongside, same era.
D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, “Efficient quantum algorithms for simulating sparse hamiltonians,” Communications in Mathematical Physics , vol. 270, no. 2, pp. 359–371, 2007
2007
Cited alongside, same era.
2008
Cited alongside, same era.
A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorithm for linear systems of equations,” Phys. Rev. Lett. , vol. 103, no. 15, pp. 1–15, 2009
2009
Cited alongside, same era.
2010
Cited alongside, same era.
A. M. Childs and R. Kothari, “Limitations on the simulation of non-sparse hamiltonians,” Quantum Info. Comput. , vol. 10, no. 7, pp. 669–684, Jul. 2010
2010
Cited alongside, same era.
A. M. Childs, “On the relationship between continuous- and discrete-time quantum walk,” Communications in Mathematical Physics , vol. 294, no. 2, pp. 581–603, 2010
2010
Cited alongside, same era.
M. A. Nilsen and I. L. Chuang, Quantum Computation and Quantum Information . Cambridge University Press, 2010, chapter 4
2010
Cited alongside, same era.
2016
Later among the works it cites.
R. Iten, R. Colbeck, I. Kukuljan et al. , “Quantum circuits for isometries,” Phys. Rev. A , vol. 93, p. 032318, Mar 2016
2016
Later among the works it cites.
Y.-C. Chen and C.-R. Lee, “Augmented block cimmino distributed algorithm for solving tridiagonal systems on gpu,” Advances in GPU Research and Practice , pp. 233–246, 12 2017
2017
Later among the works it cites.
K. Temme, S. Bravyi, and J. M. Gambetta, “Error Mitigation for Short-Depth Quantum Circuits,” Phys. Rev. Lett. , vol. 119, no. 18, pp. 1–15, 2017
2017
Later among the works it cites.
P. Hawkes and E. Kasper, “The finite-element method (fem),” Principles of Electron Optics (Second Edition) , pp. 185–207, 01 2018
2018
Later among the works it cites.
C. Shao and H. Xiang, “Quantum circulant preconditioner for a linear system of equations,” Phys. Rev. A , vol. 98, p. 062321, Dec 2018
2018
Later among the works it cites.
L. Wossnig, Z. Zhao, and A. Prakash, “Quantum linear system algorithm for dense matrices,” Phys. Rev. Lett. , vol. 120, p. 050502, Jan 2018
2018
Later among the works it cites.
2018
Later among the works it cites.
2018
Later among the works it cites.
2018
Later among the works it cites.
S. Woerner and D. J. Egger, “Quantum Risk Analysis,” npj Quantum Information , no. January, 2018
2018
Later among the works it cites.
2018
Later among the works it cites.
E. F. Dumitrescu, A. J. McCaskey, G. Hagen et al. , “Cloud quantum computing of an atomic nucleus,” Phys. Rev. Lett. , vol. 120, p. 210501, May 2018
2018
Later among the works it cites.
H. Abraham, AduOffei, R. Agarwal et al. , “Qiskit: An open-source framework for quantum computing,” 2019
2019
Later among the works it cites.
Y. b. u. Subaş ı, R. D. Somma, and D. Orsucci, “Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing,” Phys. Rev. Lett. , vol. 122, p. 060504, Feb 2019
2019
Later among the works it cites.
E. Tang, “A quantum-inspired classical algorithm for recommendation systems,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , ser. STOC 2019. New York, NY, USA: Association for Computing Machinery, 2019, pp. 217–228
2019
Later among the works it cites.
C. Zoufal, A. Lucchi, and S. Woerner, “Quantum generative adversarial networks for learning and loading random distributions,” npj Quantum Information , vol. 5, no. 1, Nov 2019
2019
Later among the works it cites.
Z. Zhao, J. K. Fitzsimons, and J. F. Fitzsimons, “Quantum-assisted gaussian process regression,” Phys. Rev. A , vol. 99, p. 052331, May 2019
2019
Later among the works it cites.
A. Kandala, K. Temme, A. D. Córcoles et al. , “Error mitigation extends the computational reach of a noisy quantum processor,” Nature , vol. 567, no. 7749, pp. 491–495, 2019
2019
Later among the works it cites.
N. Stamatopoulos, D. J. Egger, Y. Sun et al. , “Option pricing using quantum computers,” Quantum , vol. 4, p. 291, Jul 2020
2020
Closest in time.