Double-bracket Quantum Algorithms For Diagonalization

Republished By Plato

Followers: 0

School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, 637371 Singapore, Republic of Singapore

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

Abstract

This work proposes double-bracket iterations as a framework for obtaining diagonalizing quantum circuits. Their implementation on a quantum computer consists of interlacing evolutions generated by the input Hamiltonian with diagonal evolutions which can be chosen variationally. No qubit overheads or controlled-unitary operations are needed but the method is recursive which makes the circuit depth grow exponentially with the number of recursion steps. To make near-term implementations viable, the proposal includes optimization of diagonal evolution generators and of recursion step durations. Indeed, thanks to this numerical examples show that the expressive power of double-bracket iterations suffices to approximate eigenstates of relevant quantum models with few recursion steps. Compared to brute-force optimization of unstructured circuits double-bracket iterations do not suffer from the same trainability limitations. Moreover, with an implementation cost lower than required for quantum phase estimation they are more suitable for near-term quantum computing experiments. More broadly, this work opens a pathway for constructing purposeful quantum algorithms based on so-called double-bracket flows also for tasks different from diagonalization and thus enlarges the quantum computing toolkit geared towards practical physics problems.

Featured image: Pseudo-code of the diagonalization equations which give rise to circuits that allow to approximate eigenstates.

Popular summary

A method for preparing on a quantum computer states of complicated materials.

► BibTeX data

@article{Gluza2024doublebracket, doi = {10.22331/q-2024-04-09-1316}, url = {https://doi.org/10.22331/q-2024-04-09-1316}, title = {Double-bracket quantum algorithms for diagonalization}, author = {Gluza, Marek}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1316}, month = apr, year = {2024} }

► References

[1] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik. “Noisy intermediate-scale quantum algorithms”. Rev. Mod. Phys. 94, 015004 (2022).
https://doi.org/10.1103/RevModPhys.94.015004

[2] Lennart Bittel and Martin Kliesch. “Training variational quantum algorithms is np-hard”. Phys. Rev. Lett. 127, 120502 (2021).
https://doi.org/10.1103/PhysRevLett.127.120502

[3] Daniel Stilck Franca and Raul Garcia-Patron. “Limitations of optimization algorithms on noisy quantum devices”. Nature Physics 17, 1221–1227 (2021).
https://doi.org/10.1038/s41567-021-01356-3

[4] Cornelius Lanczos. “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators”. Journal of Research of the National Bureau of Standards 45 (1950).
https://doi.org/10.6028/jres.045.026

[5] Mario Motta, Chong Sun, Adrian TK Tan, Matthew J O’Rourke, Erika Ye, Austin J Minnich, Fernando GSL Brandao, and Garnet Kin Chan. “Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution”. Nature Physics 16, 205–210 (2020).
https://doi.org/10.1038/s41567-019-0704-4

[6] Christian Kokail, Christine Maier, Rick van Bijnen, Tiff Brydges, Manoj K Joshi, Petar Jurcevic, Christine A Muschik, Pietro Silvi, Rainer Blatt, Christian F Roos, et al. “Self-verifying variational quantum simulation of lattice models”. Nature 569, 355–360 (2019).
https://doi.org/10.1038/s41586-019-1177-4

[7] Stanisław D. Głazek and Kenneth G. Wilson. “Renormalization of hamiltonians”. Phys. Rev. D 48, 5863–5872 (1993).
https://doi.org/10.1103/PhysRevD.48.5863

[8] Stanislaw D. Glazek and Kenneth G. Wilson. “Perturbative renormalization group for hamiltonians”. Phys. Rev. D 49, 4214–4218 (1994).
https://doi.org/10.1103/PhysRevD.49.4214

[9] Franz Wegner. “Flow-equations for hamiltonians”. Annalen der physik 506, 77–91 (1994).
https://doi.org/10.1002/andp.19945060203

[10] S Kehrein. “The flow equation approach to many-particle systems”. Springer Tracts Mod. Phys. 217, 1–170 (2006).
https://doi.org/10.1007/3-540-34068-8

[11] Franz Wegner. “Flow equations and normal ordering: a survey”. Journal of Physics A: Mathematical and General 39, 8221 (2006).
https://doi.org/10.1088/0305-4470/39/25/s29

[12] Percy Deift, Tara Nanda, and Carlos Tomei. “Ordinary differential equations and the symmetric eigenvalue problem”. SIAM Journal on Numerical Analysis 20, 1–22 (1983).
https://doi.org/10.1137/0720001

[13] R.W. Brockett. “Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems”. Linear Algebra and its Applications 146, 79–91 (1991).

[14] Moody T. Chu. “On the continuous realization of iterative processes”. SIAM Review 30, 375–387 (1988). url: http://www.jstor.org/stable/2030697.
http://www.jstor.org/stable/2030697

[15] Uwe Helmke and John B. Moore. “Optimization and dynamical systems”. Springer London. (1994).
https://doi.org/10.1007/978-1-4471-3467-1

[16] Andrew M. Childs and Yuan Su. “Nearly optimal lattice simulation by product formulas”. Phys. Rev. Lett. 123, 050503 (2019).
https://doi.org/10.1103/PhysRevLett.123.050503

[17] Esteban A Martinez, Christine A Muschik, Philipp Schindler, Daniel Nigg, Alexander Erhard, Markus Heyl, Philipp Hauke, Marcello Dalmonte, Thomas Monz, Peter Zoller, et al. “Real-time dynamics of lattice gauge theories with a few-qubit quantum computer”. Nature 534, 516–519 (2016).
https://doi.org/10.1038/nature18318

[18] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B Buckley, et al. “Hartree-fock on a superconducting qubit quantum computer”. Science 369, 1084–1089 (2020).
https://doi.org/10.1126/science.abb9811

[19] Frank HB Somhorst, Reinier van der Meer, Malaquias Correa Anguita, Riko Schadow, Henk J Snijders, Michiel de Goede, Ben Kassenberg, Pim Venderbosch, Caterina Taballione, JP Epping, et al. “Quantum simulation of thermodynamics in an integrated quantum photonic processor”. Nature communications 14, 3895 (2023).
https://doi.org/10.1038/s41467-023-38413-9

[20] Jeongrak Son, Marek Gluza, Ryuji Takagi, and Nelly HY Ng. “Quantum dynamic programming” (2024). arXiv:2403.09187.
arXiv:2403.09187

[21] Alexander Streltsov, Gerardo Adesso, and Martin B. Plenio. “Colloquium: Quantum coherence as a resource”. Rev. Mod. Phys. 89, 041003 (2017).
https://doi.org/10.1103/RevModPhys.89.041003

[22] Stavros Efthymiou, Sergi Ramos-Calderer, Carlos Bravo-Prieto, Adrián Pérez-Salinas, Diego García-Martín, Artur Garcia-Saez, José Ignacio Latorre, and Stefano Carrazza. “Qibo: a framework for quantum simulation with hardware acceleration”. Quantum Science and Technology 7, 015018 (2021).
https://doi.org/10.1088/2058-9565/ac39f5

[23] Michael A Nielsen and Isaac L Chuang. “Quantum computation and quantum information”. Cambridge University Press. (2010).

[24] JB Moore, RE Mahony, and U Helmke. “Numerical gradient algorithms for eigenvalue and singular value calculations”. SIAM Journal on Matrix Analysis and Applications 15, 881–902 (1994).
https://doi.org/10.1137/S0036141092229732

[25] R Brockett. “Dynamical systems that sort lists, solve linear programming problems and diagonalize symmetric matrices”. In Proc. 1988 IEEE Conference on Decision and Control, Linear Algebra Appl. Volume 146, pages 79–91. (1991).

[26] R Brockett. “Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems”. Linear Algebra and its applications 146, 79–91 (1991).
https://doi.org/10.1016/0024-3795(91)90021-N

[27] Steven Thomas Smith. “Geometric optimization methods for adaptive filtering”. Harvard University. (1993).
https://doi.org/10.48550/arXiv.1305.1886

[28] Christopher M Dawson and Michael A Nielsen. “The solovay-kitaev algorithm”. Quantum Information & Computation 6, 81–95 (2006).
https://doi.org/10.48550/arXiv.quant-ph/0505030
arXiv:quant-ph/0505030

[29] Yu-An Chen, Andrew M. Childs, Mohammad Hafezi, Zhang Jiang, Hwanmun Kim, and Yijia Xu. “Efficient product formulas for commutators and applications to quantum simulation”. Phys. Rev. Res. 4, 013191 (2022).
https://doi.org/10.1103/PhysRevResearch.4.013191

[30] Dave Wecker, Bela Bauer, Bryan K. Clark, Matthew B. Hastings, and Matthias Troyer. “Gate-count estimates for performing quantum chemistry on small quantum computers”. Phys. Rev. A 90, 022305 (2014).
https://doi.org/10.1103/PhysRevA.90.022305

[31] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu. “Theory of trotter error with commutator scaling”. Phys. Rev. X 11, 011020 (2021).
https://doi.org/10.1103/PhysRevX.11.011020

[32] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. “Simulating hamiltonian dynamics with a truncated taylor series”. Phys. Rev. Lett. 114, 090502 (2015).
https://doi.org/10.1103/PhysRevLett.114.090502

[33] Guang Hao Low and Isaac L. Chuang. “Hamiltonian Simulation by Qubitization”. Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163

[34] John Watrous. “The theory of quantum information”. Cambridge University Press. (2018).
https://doi.org/10.1017/9781316848142

[35] Pierre Pfeuty. “The one-dimensional ising model with a transverse field”. Ann. Phys. 57, 79 – 90 (1970).
https://doi.org/10.1016/0003-4916(70)90270-8

[36] Lin Lin and Yu Tong. “Near-optimal ground state preparation”. Quantum 4, 372 (2020).
https://doi.org/10.22331/q-2020-12-14-372

[37] Andrew M Childs and Robin Kothari. “Limitations on the simulation of non-sparse hamiltonians”. Quantum Information & Computation 10, 669–684 (2010).
https://doi.org/10.26421/QIC10.7-8

[38] Matthew B Hastings. “On Lieb-Robinson bounds for the double bracket flow” (2022). arXiv:2201.07141.
arXiv:2201.07141

[39] Yichen Huang. “Universal eigenstate entanglement of chaotic local hamiltonians”. Nuclear Physics B 938, 594–604 (2019).
https://doi.org/10.1016/j.nuclphysb.2018.09.013

[40] Elliott H Lieb and Derek W Robinson. “The finite group velocity of quantum spin systems”. In Statistical Mechanics. Pages 425–431. Springer (1972).

[41] Bruno Nachtergaele, Robert Sims, and Amanda Young. “Quasi-locality bounds for quantum lattice systems. i. lieb-robinson bounds, quasi-local maps, and spectral flow automorphisms”. Journal of Mathematical Physics 60, 061101 (2019).
https://doi.org/10.1063/1.5095769

[42] Tomotaka Kuwahara and Keiji Saito. “Eigenstate thermalization from the clustering property of correlation”. Phys. Rev. Lett. 124, 200604 (2020).
https://doi.org/10.1103/PhysRevLett.124.200604

[43] Fernando GSL Brandao, Elizabeth Crosson, M Burak Sahinoglu, and John Bowen. “Quantum error correcting codes in eigenstates of translation-invariant spin chains”. Phys. Rev. Lett. 123, 110502 (2019).
https://doi.org/10.1103/PhysRevLett.123.110502

[44] Álvaro M. Alhambra, Jonathon Riddell, and Luis Pedro García-Pintos. “Time evolution of correlation functions in quantum many-body systems”. Phys. Rev. Lett. 124, 110605 (2020).
https://doi.org/10.1103/PhysRevLett.124.110605

[45] Michael M. Wolf, Frank Verstraete, Matthew B. Hastings, and J. Ignacio Cirac. “Area laws in quantum systems: Mutual information and correlations”. Phys. Rev. Lett. 100, 070502 (2008).
https://doi.org/10.1103/PhysRevLett.100.070502

[46] David Pekker, Bryan K. Clark, Vadim Oganesyan, and Gil Refael. “Fixed points of wegner-wilson flows and many-body localization”. Phys. Rev. Lett. 119, 075701 (2017).
https://doi.org/10.1103/PhysRevLett.119.075701

[47] Steven J. Thomson and Marco Schirò. “Local integrals of motion in quasiperiodic many-body localized systems”. SciPost Phys. 14, 125 (2023).
https://doi.org/10.21468/SciPostPhys.14.5.125

[48] Ryan LaRose, Arkin Tikku, Étude O’Neel-Judy, Lukasz Cincio, and Patrick J Coles. “Variational quantum state diagonalization”. npj Quantum Information 5, 1–10 (2019).
https://doi.org/10.1038/s41534-019-0167-6

[49] Jinfeng Zeng, Chenfeng Cao, Chao Zhang, Pengxiang Xu, and Bei Zeng. “A variational quantum algorithm for hamiltonian diagonalization”. Quantum Science and Technology 6, 045009 (2021).
https://doi.org/10.1088/2058-9565/ac11a7

[50] Benjamin Commeau, Marco Cerezo, Zoë Holmes, Lukasz Cincio, Patrick J Coles, and Andrew Sornborger. “Variational hamiltonian diagonalization for dynamical quantum simulation” (2020). arXiv:2009.02559.
arXiv:2009.02559

[51] Cristina Cirstoiu, Zoe 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, 82 (2020).
https://doi.org/10.1038/s41534-020-00302-0

[52] Joe Gibbs, Kaitlin Gili, Zoë Holmes, Benjamin Commeau, Andrew Arrasmith, Lukasz Cincio, Patrick J Coles, and Andrew Sornborger. “Long-time simulations for fixed input states on quantum hardware”. npj Quantum Information 8, 135 (2022).
https://doi.org/10.1038/s41534-022-00625-0

[53] Roeland Wiersema and Nathan Killoran. “Optimizing quantum circuits with riemannian gradient flow”. Phys. Rev. A 107, 062421 (2023).
https://doi.org/10.1103/PhysRevA.107.062421

[54] Emanuel Knill, Gerardo Ortiz, and Rolando D. Somma. “Optimal quantum measurements of expectation values of observables”. Phys. Rev. A 75, 012328 (2007).
https://doi.org/10.1103/PhysRevA.75.012328

[55] David Poulin and Pawel Wocjan. “Sampling from the thermal quantum gibbs state and evaluating partition functions with a quantum computer”. Phys. Rev. Lett. 103, 220502 (2009).
https://doi.org/10.1103/PhysRevLett.103.220502

[56] Kristan Temme, Tobias J Osborne, Karl G Vollbrecht, David Poulin, and Frank Verstraete. “Quantum metropolis sampling”. Nature 471, 87–90 (2011).
https://doi.org/10.1038/nature09770

[57] Yimin Ge, Jordi Tura, and J Ignacio Cirac. “Faster ground state preparation and high-precision ground energy estimation with fewer qubits”. Journal of Mathematical Physics 60, 022202 (2019).
https://doi.org/10.1063/1.5027484

[58] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. “Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics”. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 193–204. (2019).
https://doi.org/10.1145/3313276.3316366

[59] Kok Chuan Tan, Dhiman Bowmick, and Pinaki Sengupta. “Quantum stochastic series expansion methods” (2020). arXiv:2010.00949.
arXiv:2010.00949

[60] Yulong Dong, Lin Lin, and Yu Tong. “Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices” (2022). arXiv:2204.05955.
arXiv:2204.0595

[61] Lin Lin and Yu Tong. “Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers”. PRX Quantum 3, 010318 (2022).
https://doi.org/10.1103/PRXQuantum.3.010318

[62] Ethan N Epperly, Lin Lin, and Yuji Nakatsukasa. “A theory of quantum subspace diagonalization” (2021). arXiv:2110.07492.
https://doi.org/10.1088/1361-6455/ac44e0
arXiv:2110.07492

[63] A Yu Kitaev. “Quantum measurements and the abelian stabilizer problem” (1995). arXiv:quant-ph/9511026.
arXiv:quant-ph/9511026

[64] Lin Lin. “Lecture notes on quantum algorithms for scientific computation” (2022). arXiv:2201.08309.
arXiv:2201.08309

[65] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. “Quantum amplitude amplification and estimation”. Contemporary Mathematics 305, 53–74 (2002).
https://doi.org/10.1090/conm/305/05215

[66] Robert M Parrish and Peter L McMahon. “Quantum filter diagonalization: Quantum eigendecomposition without full quantum phase estimation” (2019). arXiv:1909.08925.
arXiv:1909.08925

[67] Nicholas H Stair, Renke Huang, and Francesco A Evangelista. “A multireference quantum krylov algorithm for strongly correlated electrons”. Journal of chemical theory and computation 16, 2236–2245 (2020).
https://doi.org/10.1021/acs.jctc.9b01125

[68] Gene Golub and William Kahan. “Calculating the singular values and pseudo-inverse of a matrix”. Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis 2, 205–224 (1965).
https://doi.org/10.1137/0702016

[69] R.W. Brockett. “Least squares matching problems”. Linear Algebra and its Applications 122-124, 761–777 (1989).
https://doi.org/10.1016/0024-3795(89)90675-7

[70] Roger W Brockett. “Smooth dynamical systems which realize arithmetical and logical operations”. Three Decades of Mathematical System Theory: A Collection of Surveys at the Occasion of the 50th Birthday of Jan C. WillemsPages 19–30 (2005).
https://doi.org/10.1007/BFb0008457

[71] Anthony M Bloch. “A completely integrable hamiltonian system associated with line fitting in complex vector spaces”. Bull. Amer. Math. Soc. (1985).

[72] Anthony Bloch. “Estimation, principal components and hamiltonian systems”. Systems & Control Letters 6, 103–108 (1985).

[73] Anthony M Bloch. “Steepest descent, linear programming and hamiltonian flows”. Contemp. Math. AMS 114, 77–88 (1990).
https://doi.org/10.1090/conm/114

[74] Anthony M Bloch, Roger W Brockett, and Tudor S Ratiu. “Completely integrable gradient flows”. Communications in Mathematical Physics 147, 57–74 (1992).
https://doi.org/10.1007/BF02099528

[75] Nic Ezzell, Bibek Pokharel, Lina Tewala, Gregory Quiroz, and Daniel A Lidar. “Dynamical decoupling for superconducting qubits: a performance survey” (2022). arXiv:2207.03670.
https://doi.org/10.1103/PhysRevApplied.20.064027
arXiv:2207.03670

[76] Rajendra Bhatia. “Matrix analysis”. Volume 169. Springer Science & Business Media. (1996).
https://doi.org/10.1007/978-1-4612-0653-8

[77] Steven T. Flammia and Yi-Kai Liu. “Direct fidelity estimation from few pauli measurements”. Phys. Rev. Lett. 106, 230501 (2011).
https://doi.org/10.1103/PhysRevLett.106.230501

[78] Marek Gluza. url: github.com/marekgluza/double_bracket_flow_as_a_diagonalization_quantum_algorithm.
https://github.com/marekgluza/double_bracket_flow_as_a_diagonalization_quantum_algorithm

[79] “Scientific co2nduct”. url: scientific-conduct.github.io.
https://scientific-conduct.github.io

[80] Morris W Hirsch, Stephen Smale, and Robert L Devaney. “Differential equations, dynamical systems, and an introduction to chaos”. Academic press. (2012).

Cited by

[1] Jeongrak Son, Marek Gluza, Ryuji Takagi, and Nelly H. Y. Ng, “Quantum Dynamic Programming”, arXiv:2403.09187, (2024).

[2] Michael Kreshchuk, James P. Vary, and Peter J. Love, “Simulating Scattering of Composite Particles”, arXiv:2310.13742, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2024-04-09 13:35:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2024-04-09 13:35:14: Could not fetch cited-by data for 10.22331/q-2024-04-09-1316 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.