Built on

Andrew M. Childs and Yuan Su, Nearly optimal lattice simulation by product formulas , Physical Review Letters 123
Original
1901
Earlier work this paper cites.
Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization , Quantum 3
Original
1902
Earlier work this paper cites.
Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush, Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via Trotterization , Quantum 4
Original
1902
Earlier work this paper cites.
Bryan O’Gorman, William J. Huggins, Eleanor G. Rieffel, and K. Birgitta Whaley, Generalized swap networks for near-term quantum computing , 2019, arXiv:1905.05118
Original
1905
Earlier work this paper cites.
Guang Hao Low, Vadym Kliuchnikov, and Nathan Wiebe, Well-conditioned multiproduct Hamiltonian simulation , 2019, arXiv:1907.11679
Original
1907
Earlier work this paper cites.
Xavier Bonet-Monroig, Ryan Babbush, and Thomas E. O’Brien, Nearly optimal measurement scheduling for partial tomography of quantum states , Physical Review X 10
Original
1908
Earlier work this paper cites.
Dong An and Lin Lin, Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm , ACM Transactions on Quantum Computing 3
Original
1909
Earlier work this paper cites.
Lin Lin and Yu Tong, Low-rank representation of tensor network operators with long-range pairwise interactions , SIAM Journal on Scientific Computing 43
Original
1909
Earlier work this paper cites.
Mark Steudtner and Stephanie Wehner, Estimating exact energies in quantum simulation without Toffoli gates , Physical Review A 101
Original
1911
Earlier work this paper cites.
Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, Theory of Trotter error with commutator scaling , Physical Review X 11
Original
1912
Earlier work this paper cites.
Xiaolong Deng, Guido Masella, Guido Pupillo, and Luis Santos, Universal algebraic growth of entanglement entropy in many-body localized systems with power-law interactions , Physical Review Letters 125
Original
1912
Earlier work this paper cites.
Yuri Manin, Vychislimoe i nevychislimoe (computable and noncomputable), Moscow: Sov , 1980
1980
Earlier work this paper cites.
Richard P. Feynman, Simulating physics with computers , International Journal of Theoretical Physics 21
1982
Earlier work this paper cites.
L Greengard and V Rokhlin, A fast algorithm for particle simulations , Journal of Computational Physics 73
1987
Earlier work this paper cites.
Christopher R. Myers, Cyrus J. Umrigar, James P. Sethna, and John D. Morgan, Fock’s expansion, Kato’s cusp conditions, and the exponential ansatz , Physical Review A 44
1991
Earlier work this paper cites.
E. Knill, Approximation by quantum circuits , 1995, arXiv:quant-ph/9508006
1995
Earlier work this paper cites.
Seth Lloyd, Universal quantum simulators , Science 273
1996
Earlier work this paper cites.
A Yu Kitaev, Quantum computations: algorithms and error correction , Russian Mathematical Surveys 52
1997
Earlier work this paper cites.
Richard Courant, Fritz John, Albert A. Blank, and Alan Solomon, Introduction to calculus and analysis: Volume II , Springer New York, 1999
1999
Earlier work this paper cites.
W. Hackbusch, A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices , Computing 62
1999
Earlier work this paper cites.
Lin Lin and Yu Tong, Near-optimal ground state preparation , Quantum 4
Original
2002
Earlier work this paper cites.
Alexander F. Shaw, Pavel Lougovski, Jesse R. Stryker, and Nathan Wiebe, Quantum algorithms for simulating the lattice Schwinger model , Quantum 4
Original
2002
Earlier work this paper cites.
Lars Grasedyck and Wolfgang Hackbusch, Construction and arithmetics of H-matrices , Computing 70
2003
Earlier work this paper cites.
Anurag Anshu, Aram W. Harrow, and Mehdi Soleimanifar, Entanglement spread area law in gapped ground states , Nature Physics 18
Original
2004
Earlier work this paper cites.
Stephen S. Bullock and Igor L. Markov, Asymptotically optimal circuits for arbitrary n n -qubit diagonal computations , Quantum Information & Computation 4
2004
Earlier work this paper cites.
F Verstraete and J I Cirac, Mapping local Hamiltonians of fermions to local Hamiltonians of spins , Journal of Statistical Mechanics: Theory and Experiment 2005
2005
Earlier work this paper cites.
Burak Şahinoğlu and Rolando D. Somma, Hamiltonian simulation in the low-energy subspace , npj Quantum Information 7
Original
2006
Earlier work this paper cites.
V.V. Shende, S.S. Bullock, and I.L. Markov, Synthesis of quantum-logic circuits , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25
2006
Earlier work this paper cites.
Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians , Communications in Mathematical Physics 270
2007
Earlier work this paper cites.
H. P. Büchler, E. Demler, M. Lukin, A. Micheli, N. Prokof’ev, G. Pupillo, and P. Zoller, Strongly correlated 2D quantum phases with cold polar molecules: Controlling the shape of the interaction potential , Physical Review Letters 98
2007
Earlier work this paper cites.
Tomotaka Kuwahara, Álvaro M Alhambra, and Anurag Anshu, Improved thermal area law and quasilinear time algorithm for quantum Gibbs states , Physical Review X 11
Original
2007
Earlier work this paper cites.
Richard Meister, Simon C. Benjamin, and Earl T. Campbell, Tailoring term truncations for electronic structure calculations using a Linear Combination of Unitaries , Quantum 6
Original
2007
Earlier work this paper cites.
A. Micheli, G. Pupillo, H. P. Büchler, and P. Zoller, Cold polar molecules in two-dimensional traps: Tailoring interactions with external fields for novel quantum phases , Physical Review A 76
2007
Earlier work this paper cites.
Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, Quantum computing enhanced computational catalysis , Physical Review Research 3
Original
2007
Earlier work this paper cites.
Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp, Concentration for random product formulas , PRX Quantum 2
Original
2008
Earlier work this paper cites.
A. V. Gorshkov, P. Rabl, G. Pupillo, A. Micheli, P. Zoller, M. D. Lukin, and H. P. Büchler, Suppression of inelastic collisions between polar molecules with a repulsive shield , Physical Review Letters 101
2008
Earlier work this paper cites.
Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán Aspuru-Guzik, Polynomial-time quantum algorithm for the simulation of chemical dynamics , Proceedings of the National Academy of Sciences 105
Original
2008
Earlier work this paper cites.
Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle, A sparse model of quantum holography , 2020, arXiv:2008.02303
Original
2008
Earlier work this paper cites.
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, Quantum algorithm for linear systems of equations , Physical Review Letters 103
Original
2009
Earlier work this paper cites.
David Poulin and Pawel Wocjan, Preparing ground states of quantum many-body systems on a quantum computer , Physical Review Letters 102
Original
2009
Earlier work this paper cites.
M. Dalmonte, G. Pupillo, and P. Zoller, One-dimensional quantum liquids with power-law interactions: The luttinger staircase , Physical Review Letters 105
Original
2010
Earlier work this paper cites.
Mariano Giaquinta and Giuseppe Modica, Mathematical analysis: An introduction to functions of several variables , Springer Science & Business Media, 2010
2010
Earlier work this paper cites.

Similar

M. Saffman, T. G. Walker, and K. Mølmer, Quantum information with Rydberg atoms , Reviews of Modern Physics 82
Original
2010
Cited alongside, same era.
Mariano Giaquinta and Giuseppe Modica, Mathematical analysis: Foundations and advanced techniques for functions of several variables , Springer Science & Business Media, 2011
2011
Cited alongside, same era.
K. Kim, S. Korenblit, R. Islam, E. E. Edwards, M.-S. Chang, C. Noh, H. Carmichael, G.-D. Lin, L.-M. Duan, C. C. Joseph Wang, J. K. Freericks, and C. Monroe, Quantum simulation of the transverse Ising model with trapped ions , New Journal of Physics 13
2011
Cited alongside, same era.
Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, Even more efficient quantum computations of chemistry through tensor hypercontraction , PRX Quantum 2
Original
2011
Cited alongside, same era.

Then

Guang Hao Low, Hamiltonian simulation with nearly optimal dependence on spectral norm , Proceedings of the 51th ACM Symposium on Theory of Computing, pp. 491–502, ACM, 2019, arXiv:1807.03967
Original
2019
Later among the works it cites.
Guang Hao Low and Isaac L. Chuang, Hamiltonian simulation by qubitization , Quantum 3
Original
2019
Later among the works it cites.
Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov, Locality and digital quantum simulation of power-law interactions , Physical Review X 9
Original
2019
Later among the works it cites.
Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, Quantum computational chemistry , Reviews of Modern Physics 92
Original
2020
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2022

On the complexity of implementing Trotter steps

Low, Guang Hao, Su, Yuan, Tong, Yu et al.

Understand

Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner.

However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques.
We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms.
We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law.

Built on

Andrew M. Childs and Yuan Su, Nearly optimal lattice simulation by product formulas , Physical Review Letters 123
Original
1901
Earlier work this paper cites.
Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization , Quantum 3
Original
1902
Earlier work this paper cites.
Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush, Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via Trotterization , Quantum 4
Original
1902
Earlier work this paper cites.
Bryan O’Gorman, William J. Huggins, Eleanor G. Rieffel, and K. Birgitta Whaley, Generalized swap networks for near-term quantum computing , 2019, arXiv:1905.05118
Original
1905
Earlier work this paper cites.
Guang Hao Low, Vadym Kliuchnikov, and Nathan Wiebe, Well-conditioned multiproduct Hamiltonian simulation , 2019, arXiv:1907.11679
Original
1907
Earlier work this paper cites.
Xavier Bonet-Monroig, Ryan Babbush, and Thomas E. O’Brien, Nearly optimal measurement scheduling for partial tomography of quantum states , Physical Review X 10
Original
1908
Earlier work this paper cites.
Dong An and Lin Lin, Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm , ACM Transactions on Quantum Computing 3
Original
1909
Earlier work this paper cites.
Lin Lin and Yu Tong, Low-rank representation of tensor network operators with long-range pairwise interactions , SIAM Journal on Scientific Computing 43
Original
1909
Earlier work this paper cites.
Mark Steudtner and Stephanie Wehner, Estimating exact energies in quantum simulation without Toffoli gates , Physical Review A 101
Original
1911
Earlier work this paper cites.
Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, Theory of Trotter error with commutator scaling , Physical Review X 11
Original
1912
Earlier work this paper cites.
Xiaolong Deng, Guido Masella, Guido Pupillo, and Luis Santos, Universal algebraic growth of entanglement entropy in many-body localized systems with power-law interactions , Physical Review Letters 125
Original
1912
Earlier work this paper cites.
Yuri Manin, Vychislimoe i nevychislimoe (computable and noncomputable), Moscow: Sov , 1980
1980
Earlier work this paper cites.
Richard P. Feynman, Simulating physics with computers , International Journal of Theoretical Physics 21
1982
Earlier work this paper cites.
L Greengard and V Rokhlin, A fast algorithm for particle simulations , Journal of Computational Physics 73
1987
Earlier work this paper cites.
Christopher R. Myers, Cyrus J. Umrigar, James P. Sethna, and John D. Morgan, Fock’s expansion, Kato’s cusp conditions, and the exponential ansatz , Physical Review A 44
1991
Earlier work this paper cites.
E. Knill, Approximation by quantum circuits , 1995, arXiv:quant-ph/9508006
1995
Earlier work this paper cites.
Seth Lloyd, Universal quantum simulators , Science 273
1996
Earlier work this paper cites.
A Yu Kitaev, Quantum computations: algorithms and error correction , Russian Mathematical Surveys 52
1997
Earlier work this paper cites.
Richard Courant, Fritz John, Albert A. Blank, and Alan Solomon, Introduction to calculus and analysis: Volume II , Springer New York, 1999
1999
Earlier work this paper cites.
W. Hackbusch, A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices , Computing 62
1999
Earlier work this paper cites.
Lin Lin and Yu Tong, Near-optimal ground state preparation , Quantum 4
Original
2002
Earlier work this paper cites.
Alexander F. Shaw, Pavel Lougovski, Jesse R. Stryker, and Nathan Wiebe, Quantum algorithms for simulating the lattice Schwinger model , Quantum 4
Original
2002
Earlier work this paper cites.
Lars Grasedyck and Wolfgang Hackbusch, Construction and arithmetics of H-matrices , Computing 70
2003
Earlier work this paper cites.
Anurag Anshu, Aram W. Harrow, and Mehdi Soleimanifar, Entanglement spread area law in gapped ground states , Nature Physics 18
Original
2004
Earlier work this paper cites.
Stephen S. Bullock and Igor L. Markov, Asymptotically optimal circuits for arbitrary n n -qubit diagonal computations , Quantum Information & Computation 4
2004
Earlier work this paper cites.
F Verstraete and J I Cirac, Mapping local Hamiltonians of fermions to local Hamiltonians of spins , Journal of Statistical Mechanics: Theory and Experiment 2005
2005
Earlier work this paper cites.
Burak Şahinoğlu and Rolando D. Somma, Hamiltonian simulation in the low-energy subspace , npj Quantum Information 7
Original
2006
Earlier work this paper cites.
V.V. Shende, S.S. Bullock, and I.L. Markov, Synthesis of quantum-logic circuits , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25
2006
Earlier work this paper cites.
Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians , Communications in Mathematical Physics 270
2007
Earlier work this paper cites.
H. P. Büchler, E. Demler, M. Lukin, A. Micheli, N. Prokof’ev, G. Pupillo, and P. Zoller, Strongly correlated 2D quantum phases with cold polar molecules: Controlling the shape of the interaction potential , Physical Review Letters 98
2007
Earlier work this paper cites.
Tomotaka Kuwahara, Álvaro M Alhambra, and Anurag Anshu, Improved thermal area law and quasilinear time algorithm for quantum Gibbs states , Physical Review X 11
Original
2007
Earlier work this paper cites.
Richard Meister, Simon C. Benjamin, and Earl T. Campbell, Tailoring term truncations for electronic structure calculations using a Linear Combination of Unitaries , Quantum 6
Original
2007
Earlier work this paper cites.
A. Micheli, G. Pupillo, H. P. Büchler, and P. Zoller, Cold polar molecules in two-dimensional traps: Tailoring interactions with external fields for novel quantum phases , Physical Review A 76
2007
Earlier work this paper cites.
Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, Quantum computing enhanced computational catalysis , Physical Review Research 3
Original
2007
Earlier work this paper cites.
Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp, Concentration for random product formulas , PRX Quantum 2
Original
2008
Earlier work this paper cites.
A. V. Gorshkov, P. Rabl, G. Pupillo, A. Micheli, P. Zoller, M. D. Lukin, and H. P. Büchler, Suppression of inelastic collisions between polar molecules with a repulsive shield , Physical Review Letters 101
2008
Earlier work this paper cites.
Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán Aspuru-Guzik, Polynomial-time quantum algorithm for the simulation of chemical dynamics , Proceedings of the National Academy of Sciences 105
Original
2008
Earlier work this paper cites.
Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle, A sparse model of quantum holography , 2020, arXiv:2008.02303
Original
2008
Earlier work this paper cites.
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, Quantum algorithm for linear systems of equations , Physical Review Letters 103
Original
2009
Earlier work this paper cites.
David Poulin and Pawel Wocjan, Preparing ground states of quantum many-body systems on a quantum computer , Physical Review Letters 102
Original
2009
Earlier work this paper cites.
M. Dalmonte, G. Pupillo, and P. Zoller, One-dimensional quantum liquids with power-law interactions: The luttinger staircase , Physical Review Letters 105
Original
2010
Earlier work this paper cites.
Mariano Giaquinta and Giuseppe Modica, Mathematical analysis: An introduction to functions of several variables , Springer Science & Business Media, 2010
2010
Earlier work this paper cites.

Similar

M. Saffman, T. G. Walker, and K. Mølmer, Quantum information with Rydberg atoms , Reviews of Modern Physics 82
Original
2010
Cited alongside, same era.
Mariano Giaquinta and Giuseppe Modica, Mathematical analysis: Foundations and advanced techniques for functions of several variables , Springer Science & Business Media, 2011
2011
Cited alongside, same era.
K. Kim, S. Korenblit, R. Islam, E. E. Edwards, M.-S. Chang, C. Noh, H. Carmichael, G.-D. Lin, L.-M. Duan, C. C. Joseph Wang, J. K. Freericks, and C. Monroe, Quantum simulation of the transverse Ising model with trapped ions , New Journal of Physics 13
2011
Cited alongside, same era.
Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, Even more efficient quantum computations of chemistry through tensor hypercontraction , PRX Quantum 2
Original
2011
Cited alongside, same era.

Then

Guang Hao Low, Hamiltonian simulation with nearly optimal dependence on spectral norm , Proceedings of the 51th ACM Symposium on Theory of Computing, pp. 491–502, ACM, 2019, arXiv:1807.03967
Original
2019
Later among the works it cites.
Guang Hao Low and Isaac L. Chuang, Hamiltonian simulation by qubitization , Quantum 3
Original
2019
Later among the works it cites.
Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov, Locality and digital quantum simulation of power-law interactions , Physical Review X 9
Original
2019
Later among the works it cites.
Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan, Quantum computational chemistry , Reviews of Modern Physics 92
Original
2020
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Dong An, Di Fang, and Lin Lin, Time-dependent unbounded Hamiltonian simulation with vector norm scaling , Quantum 5

Original

2012

Cited alongside, same era.

Joseph W. Britton, Brian C. Sawyer, Adam C. Keith, C. C Joseph Wang, James K. Freericks, Hermann Uys, Michael J. Biercuk, and John J. Bollinger, Engineered two-dimensional Ising interactions in a trapped-ion quantum simulator with hundreds of spins , Nature 484

Original

2012

Cited alongside, same era.

Roger A. Horn and Charles R. Johnson, Matrix analysis , Cambridge university press, 2012

2012

Cited alongside, same era.

N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, and Yoshihisa Yamamoto, Faster quantum chemistry simulation on fault-tolerant quantum computers , New Journal of Physics 14

Original

2012

Cited alongside, same era.

Thomas Koffel, M. Lewenstein, and Luca Tagliacozzo, Entanglement entropy for the long-range Ising chain in a transverse field , Physical Review Letters 109

Original

2012

Cited alongside, same era.

Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, Nearly tight Trotterization of interacting electrons , Quantum 5

Original

2012

Cited alongside, same era.

Trygve Helgaker, Poul Jørgensen, and Jeppe Olsen, Molecular electronic-structure theory , John Wiley & Sons, 2013

2013

Cited alongside, same era.

Bo Yan, Steven A. Moses, Bryce Gadway, Jacob P. Covey, Kaden R. A. Hazzard, Ana Maria Rey, Deborah S. Jin, and Jun Ye, Observation of dipolar spin-exchange interactions with lattice-confined polar molecules , Nature 501

2013

Cited alongside, same era.

Chi-Fang Chen and Fernando G.S.L. Brandão, Concentration for Trotter error , 2021, arXiv:2111.05324

Original

2021