An efficient quantum algorithm for the time evolution of parameterized circuits

Stefano Barison, Filippo Vicentini, and Giuseppe Carleo

Institute of Physics, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We introduce a novel hybrid algorithm to simulate the real-time evolution of quantum systems using parameterized quantum circuits. The method, named "projected – Variational Quantum Dynamics" (p-VQD) realizes an iterative, global projection of the exact time evolution onto the parameterized manifold. In the small time-step limit, this is equivalent to the McLachlan's variational principle. Our approach is efficient in the sense that it exhibits an optimal linear scaling with the total number of variational parameters. Furthermore, it is global in the sense that it uses the variational principle to optimize all parameters at once. The global nature of our approach then significantly extends the scope of existing efficient variational methods, that instead typically rely on the iterative optimization of a restricted subset of variational parameters. Through numerical experiments, we also show that our approach is particularly advantageous over existing global optimization algorithms based on the time-dependent variational principle that, due to a demanding quadratic scaling with parameter numbers, are unsuitable for large parameterized quantum circuits.

► BibTeX data

► References

[1] Frank Arute ``Quantum supremacy using a programmable superconducting processor'' Nature 574, 505-510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

[2] LeeAnn M. Sager, Scott E. Smart, and David A. Mazziotti, ``Preparation of an exciton condensate of photons on a 53-qubit quantum computer'' Physical Review Research 2 (2020).
https:/​/​doi.org/​10.1103/​physrevresearch.2.043205

[3] P.W. Shor ``Algorithms for quantum computation: discrete logarithms and factoring'' Proceedings 35th Annual Symposium on Foundations of Computer Science (1994).
https:/​/​doi.org/​10.1109/​sfcs.1994.365700

[4] D. Coppersmith ``An approximate Fourier transform useful in quantum factoring'' (1994).

[5] Giuseppe E Santoroand Erio Tosatti ``Optimization using quantum mechanics: quantum annealing through adiabatic evolution'' Journal of Physics A: Mathematical and General 39, R393–R431 (2006).
https:/​/​doi.org/​10.1088/​0305-4470/​39/​36/​r01

[6] 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, 18681–18686 (2008).
https:/​/​doi.org/​10.1073/​pnas.0808245105

[7] I. M. Georgescu, S. Ashhab, and Franco Nori, ``Quantum simulation'' Rev. Mod. Phys. 86, 153–185 (2014).
https:/​/​doi.org/​10.1103/​RevModPhys.86.153

[8] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien, ``A variational eigenvalue solver on a photonic quantum processor'' Nature Communications 5 (2014).
https:/​/​doi.org/​10.1038/​ncomms5213

[9] Ying Liand Simon C. Benjamin ``Efficient Variational Quantum Simulator Incorporating Active Error Minimization'' Phys. Rev. X 7, 021050 (2017).
https:/​/​doi.org/​10.1103/​PhysRevX.7.021050

[10] Pauline J. Ollitrault, Abhinav Kandala, Chun-Fu Chen, Panagiotis Kl. Barkoutsos, Antonio Mezzacapo, Marco Pistoia, Sarah Sheldon, Stefan Woerner, Jay M. Gambetta, and Ivano Tavernelli, ``Quantum equation of motion for computing molecular excitation energies on a noisy quantum processor'' Physical Review Research 2 (2020).
https:/​/​doi.org/​10.1103/​physrevresearch.2.043140

[11] Mario Motta, Chong Sun, Adrian T. K. Tan, Matthew J. O’Rourke, Erika Ye, Austin J. Minnich, Fernando G. S. L. Brandão, and Garnet Kin-Lic Chan, ``Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution'' Nature Physics 16, 205–210 (2019).
https:/​/​doi.org/​10.1038/​s41567-019-0704-4

[12] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles, ``Variational Quantum Algorithms'' (2020).
arXiv:2012.09265

[13] Jacob L. Beckey, M. Cerezo, Akira Sone, and Patrick J. Coles, ``Variational Quantum Algorithm for Estimating the Quantum Fisher Information'' (2020).
arXiv:2010.10488v1

[14] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd, ``Quantum machine learning'' Nature 549, 195–202 (2017).
https:/​/​doi.org/​10.1038/​nature23474

[15] Sima E. Borujeni, Saideep Nannapaneni, Nam H. Nguyen, Elizabeth C. Behrman, and James E. Steck, ``Quantum circuit representation of Bayesian networks'' (2020).
arXiv:2004.14803

[16] Jonathan Romero, Jonathan P Olson, and Alan Aspuru-Guzik, ``Quantum autoencoders for efficient compression of quantum data'' Quantum Science and Technology 2, 045001 (2017).
https:/​/​doi.org/​10.1088/​2058-9565/​aa8072

[17] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash, ``q-means: A quantum algorithm for unsupervised machine learning'' Advances in Neural Information Processing Systems 32, 4134–4144 (2019).

[18] Maria Schuldand Nathan Killoran ``Quantum Machine Learning in Feature Hilbert Spaces'' Phys. Rev. Lett. 122, 040504 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.122.040504

[19] Maria Schuld, Alex Bocharov, Krysta M. Svore, and Nathan Wiebe, ``Circuit-centric quantum classifiers'' Physical Review A 101 (2020).
https:/​/​doi.org/​10.1103/​physreva.101.032308

[20] Vojtěch Havlíček, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta, ``Supervised learning with quantum-enhanced feature spaces'' Nature 567, 209–212 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[21] Mohammad H. Amin, Evgeny Andriyash, Jason Rolfe, Bohdan Kulchytskyy, and Roger Melko, ``Quantum Boltzmann Machine'' Phys. Rev. X 8, 021050 (2018).
https:/​/​doi.org/​10.1103/​PhysRevX.8.021050

[22] Iris Cong, Soonwon Choi, and Mikhail D. Lukin, ``Quantum convolutional neural networks'' Nature Physics 15, 1273–1278 (2019).
https:/​/​doi.org/​10.1038/​s41567-019-0648-8

[23] P. J. J. O'Malley ``Scalable Quantum Simulation of Molecular Energies'' Phys. Rev. X 6, 031007 (2016).
https:/​/​doi.org/​10.1103/​PhysRevX.6.031007

[24] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta, ``Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets'' Nature 549, 242–246 (2017).
https:/​/​doi.org/​10.1038/​nature23879

[25] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan, ``Quantum Algorithms for Quantum Chemistry and Quantum Materials Science'' Chemical Reviews 120, 12685–12717 (2020).
https:/​/​doi.org/​10.1021/​acs.chemrev.9b00829

[26] H. F. Trotter ``On the product of semi-groups of operators'' Proc. Amer. Math. Soc. 10, 545–551 (1959).
https:/​/​doi.org/​10.1090/​S0002-9939-1959-0108732-6

[27] Masuo Suzuki ``General theory of fractal path integrals with applications to many‐body theories and statistical physics'' Journal of Mathematical Physics 32, 400–407 (1991).
https:/​/​doi.org/​10.1063/​1.529425

[28] Daniel S. Abramsand Seth Lloyd ``Simulation of Many-Body Fermi Systems on a Universal Quantum Computer'' Phys. Rev. Lett. 79, 2586–2589 (1997).
https:/​/​doi.org/​10.1103/​PhysRevLett.79.2586

[29] G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme, ``Quantum algorithms for fermionic simulations'' Phys. Rev. A 64, 022319 (2001).
https:/​/​doi.org/​10.1103/​PhysRevA.64.022319

[30] Xiao Yuan, Suguru Endo, Qi Zhao, Ying Li, and Simon C. Benjamin, ``Theory of variational quantum simulation'' Quantum 3, 191 (2019).
https:/​/​doi.org/​10.22331/​q-2019-10-07-191

[31] Cristina Cîrstoiu, Zoë Holmes, Joseph Iosue, Lukasz Cincio, Patrick J. Coles, and Andrew Sornborger, ``Variational fast forwarding for quantum simulation beyond the coherence time'' npj Quantum Information 6 (2020).
https:/​/​doi.org/​10.1038/​s41534-020-00302-0

[32] Benjamin Commeau, M. Cerezo, Zoë Holmes, Lukasz Cincio, Patrick J. Coles, and Andrew Sornborger, ``Variational Hamiltonian Diagonalization for Dynamical Quantum Simulation'' (2020).
arXiv:2009.02559

[33] Kishor Bhartiand Tobias Haug ``Quantum Assisted Simulator'' (2020).
arXiv:2011.06911

[34] P. A. M. Dirac ``Note on Exchange Phenomena in the Thomas Atom'' Mathematical Proceedings of the Cambridge Philosophical Society 26, 376–385 (1930).
https:/​/​doi.org/​10.1017/​S0305004100016108

[35] Jacov Frenkel ``Wave Mechanics: Advanced General Theory'' Oxford University Press (1934).

[36] A.D. McLachlan ``A variational solution of the time-dependent Schrodinger equation'' Molecular Physics 8, 39–44 (1964).
https:/​/​doi.org/​10.1080/​00268976400100041

[37] Jutho Haegeman, J. Ignacio Cirac, Tobias J. Osborne, Iztok Pižorn, Henri Verschelde, and Frank Verstraete, ``Time-Dependent Variational Principle for Quantum Lattices'' Phys. Rev. Lett. 107, 070601 (2011).
https:/​/​doi.org/​10.1103/​PhysRevLett.107.070601

[38] Jutho Haegeman, Christian Lubich, Ivan Oseledets, Bart Vandereycken, and Frank Verstraete, ``Unifying time evolution and optimization with matrix product states'' Phys. Rev. B 94, 165116 (2016).
https:/​/​doi.org/​10.1103/​PhysRevB.94.165116

[39] Giuseppe Carleo, Federico Becca, Marco Schiro, and Michele Fabrizio, ``Localization and Glassy Dynamics Of Many-Body Quantum Systems'' Scientific Reports 2, 243 (2012).
https:/​/​doi.org/​10.1038/​srep00243

[40] Giuseppe Carleo, Federico Becca, Laurent Sanchez-Palencia, Sandro Sorella, and Michele Fabrizio, ``Light-cone effect and supersonic correlations in one- and two-dimensional bosonic superfluids'' Phys. Rev. A 89, 031602 (2014).
https:/​/​doi.org/​10.1103/​PhysRevA.89.031602

[41] Michael Kolodrubetz, Dries Sels, Pankaj Mehta, and Anatoli Polkovnikov, ``Geometry and non-adiabatic response in quantum and classical systems'' Physics Reports 697, 1–87 (2017).
https:/​/​doi.org/​10.1016/​j.physrep.2017.07.001

[42] Marin Bukov, Dries Sels, and Anatoli Polkovnikov, ``Geometric Speed Limit of Accessible Many-Body State Preparation'' Phys. Rev. X 9, 011034 (2019).
https:/​/​doi.org/​10.1103/​PhysRevX.9.011034

[43] Marcello Benedetti, Mattia Fiorentini, and Michael Lubasch, ``Hardware-efficient variational quantum algorithms for time evolution'' (2020).
https:/​/​doi.org/​10.1103/​PhysRevResearch.3.033083
arXiv:2009.12361

[44] Lucas Slattery, Benjamin Villalonga, and Bryan K. Clark, ``Unitary Block Optimization for Variational Quantum Algorithms'' (2021).
arXiv:2102.08403

[45] F. Barratt, James Dborin, Matthias Bal, Vid Stojevic, Frank Pollmann, and A. G. Green, ``Parallel quantum simulation of large systems on small NISQ computers'' npj Quantum Information 7 (2021).
https:/​/​doi.org/​10.1038/​s41534-021-00420-3

[46] Sheng-Hsuan Lin, Rohit Dilip, Andrew G. Green, Adam Smith, and Frank Pollmann, ``Real- and Imaginary-Time Evolution with Compressed Quantum Circuits'' PRX Quantum 2 (2021).
https:/​/​doi.org/​10.1103/​prxquantum.2.010342

[47] Matthew Otten, Cristian L. Cortes, and Stephen K. Gray, ``Noise-Resilient Quantum Dynamics Using Symmetry-Preserving Ansatzes'' (2019).
arXiv:1910.06284

[48] James Stokes, Josh Izaac, Nathan Killoran, and Giuseppe Carleo, ``Quantum Natural Gradient'' Quantum 4, 269 (2020).
https:/​/​doi.org/​10.22331/​q-2020-05-25-269

[49] Daniel Gottesmanand Isaac Chuang ``Quantum Digital Signatures'' (2001).

[50] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf, ``Quantum Fingerprinting'' Physical Review Letters 87 (2001).
https:/​/​doi.org/​10.1103/​physrevlett.87.167902

[51] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran, ``Evaluating analytic gradients on quantum hardware'' Phys. Rev. A 99, 032331 (2019).
https:/​/​doi.org/​10.1103/​PhysRevA.99.032331

[52] J.C. Spall ``Implementation of the simultaneous perturbation algorithm for stochastic optimization'' IEEE Transactions on Aerospace and Electronic Systems 34, 817–823 (1998).
https:/​/​doi.org/​10.1109/​7.705889

[53] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, ``Quantum circuit learning'' Physical Review A 98 (2018).
https:/​/​doi.org/​10.1103/​physreva.98.032309

[54] Robert M. Parrish, Edward G. Hohenstein, Peter L. McMahon, and Todd J. Martinez, ``Hybrid Quantum/​Classical Derivative Theory: Analytical Gradients and Excited-State Dynamics for the Multistate Contracted Variational Quantum Eigensolver'' (2019).
arXiv:1906.08728

[55] Gavin E. Crooks ``Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition'' (2019).
arXiv:1905.13311

[56] Andrea Mari, Thomas R. Bromley, and Nathan Killoran, ``Estimating the gradient and higher-order derivatives on quantum hardware'' Physical Review A 103 (2021).
https:/​/​doi.org/​10.1103/​physreva.103.012405

[57] Leonardo Banchiand Gavin E. Crooks ``Measuring Analytic Gradients of General Quantum Evolution with the Stochastic Parameter Shift Rule'' Quantum 5, 386 (2021).
https:/​/​doi.org/​10.22331/​q-2021-01-25-386

[58] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles, ``Cost function dependent barren plateaus in shallow parametrized quantum circuits'' Nature Communications 12 (2021).
https:/​/​doi.org/​10.1038/​s41467-021-21728-w

[59] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven, ``Barren plateaus in quantum neural network training landscapes'' Nature Communications 9 (2018).
https:/​/​doi.org/​10.1038/​s41467-018-07090-4

[60] Tobias Haugand M. S. Kim ``Optimal training of variational quantum algorithms without barren plateaus'' (2021).
arXiv:2104.14543

[61] Edward Grant, Leonard Wossnig, Mateusz Ostaszewski, and Marcello Benedetti, ``An initialization strategy for addressing barren plateaus in parametrized quantum circuits'' Quantum 3, 214 (2019).
https:/​/​doi.org/​10.22331/​q-2019-12-09-214

[62] Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio, and Patrick J. Coles, ``Variational Quantum Linear Solver'' (2020).
arXiv:1909.05820

[63] Héctor Abraham et al. ``Qiskit: An Open-source Framework for Quantum Computing'' (2019).
https:/​/​doi.org/​10.5281/​zenodo.2562110

[64] J. Demmel ``On condition numbers and the distance to the nearest ill-posed problem'' Numerische Mathematik 51, 251–289 (1987).
https:/​/​doi.org/​10.1007/​BF01400115

[65] Guifré Vidal ``Efficient Simulation of One-Dimensional Quantum Many-Body Systems'' Physical Review Letters 93, 040502 (2004).
https:/​/​doi.org/​10.1103/​PhysRevLett.93.040502

[66] A. J. Daley, C. Kollath, U. Schollwock, and G. Vidal, ``Time-dependent density-matrix renormalization-group using adaptive effective Hilbert spaces'' Journal of Statistical Mechanics-Theory and Experiment P04005 (2004).
https:/​/​doi.org/​10.1088/​1742-5468/​2004/​04/​P04005

[67] Steven R. Whiteand Adrian E. Feiguin ``Real-Time Evolution Using the Density Matrix Renormalization Group'' Physical Review Letters 93, 076401 (2004).
https:/​/​doi.org/​10.1103/​PhysRevLett.93.076401

[68] Giuseppe Carleoand Matthias Troyer ``Solving the quantum many-body problem with artificial neural networks'' Science 355, 602–606 (2017).
https:/​/​doi.org/​10.1126/​science.aag2302

[69] Markus Schmittand Markus Heyl ``Quantum Many-Body Dynamics in Two Dimensions with Artificial Neural Networks'' Physical Review Letters 125, 100503 (2020) Publisher: American Physical Society.
https:/​/​doi.org/​10.1103/​PhysRevLett.125.100503

[70] Stefano Barison ``Github repository'' (2021).
https:/​/​github.com/​StefanoBarison/​p-VQD

Cited by

[1] Michael R. Geller, Zoë Holmes, Patrick J. Coles, and Andrew Sornborger, "Experimental quantum learning of a spectral decomposition", Physical Review Research 3 3, 033200 (2021).

[2] Yong-Xin Yao, Niladri Gomes, Feng Zhang, Cai-Zhuang Wang, Kai-Ming Ho, Thomas Iadecola, and Peter P. Orth, "Adaptive Variational Quantum Dynamics Simulations", PRX Quantum 2 3, 030307 (2021).

[3] Tobias Haug and M. S. Kim, "Optimal training of variational quantum algorithms without barren plateaus", arXiv:2104.14543.

[4] Jonathan Wei Zhong Lau, Tobias Haug, Leong Chuan Kwek, and Kishor Bharti, "NISQ Algorithm for Hamiltonian Simulation via Truncated Taylor Series", arXiv:2103.05500.

[5] Julien Gacon, Christa Zoufal, Giuseppe Carleo, and Stefan Woerner, "Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information", arXiv:2103.09232.

[6] Yongdan Yang, Bing-Nan Lu, and Ying Li, "Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer", arXiv:2106.09880.

[7] Kian Hwee Lim, Tobias Haug, Leong Chuan Kwek, and Kishor Bharti, "Fast-Forwarding with NISQ Processors without Feedback Loop", arXiv:2104.01931.

[8] Kishor Bharti, Tobias Haug, Vlatko Vedral, and Leong-Chuan Kwek, "NISQ Algorithm for Semidefinite Programming", arXiv:2106.03891.

[9] Christa Zoufal, David Sutter, and Stefan Woerner, "Error Bounds for Variational Quantum Time Evolution", arXiv:2108.00022.

[10] Paolo P. Mazza, Dominik Zietlow, Federico Carollo, Sabine Andergassen, Georg Martius, and Igor Lesanovsky, "Machine learning time-local generators of open quantum dynamics", Physical Review Research 3 2, 023084 (2021).

[11] Refik Mansuroglu, Samuel Wilkinson, Ludwig Nützel, and Michael J. Hartmann, "Classical Variational Optimization of Gate Sequences for Time Evolution of Large Quantum Systems", arXiv:2106.03680.

[12] Lucas Slattery, Benjamin Villalonga, and Bryan K. Clark, "Unitary Block Optimization for Variational Quantum Algorithms", arXiv:2102.08403.

[13] Tobias Haug and M. S. Kim, "Natural parameterized quantum circuit", arXiv:2107.14063.

[14] Rouven Koch and Jose L. Lado, "Neural network enhanced hybrid quantum many-body dynamical distributions", Physical Review Research 3 3, 033102 (2021).

[15] Alexander Miessen, Pauline J. Ollitrault, and Ivano Tavernelli, "Quantum algorithms for quantum dynamics: a performance study on the spin-boson model", arXiv:2108.04258.

[16] Michael R. Geller, Andrew Arrasmith, Zoë Holmes, Bin Yan, Patrick J. Coles, and Andrew Sornborger, "Quantum simulation of operator spreading in the chaotic Ising model", arXiv:2106.16170.

The above citations are from Crossref's cited-by service (last updated successfully 2021-09-23 06:06:20) and SAO/NASA ADS (last updated successfully 2021-09-23 06:06:21). The list may be incomplete as not all publishers provide suitable and complete citation data.