Quantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations

Juan José García-Ripoll

Institute of Fundamental Physics, Calle Serrano 113b, 28006 Madrid, Spain

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

Abstract

In this work we study the encoding of smooth, differentiable multivariate functions in quantum registers, using quantum computers or tensor-network representations. We show that a large family of distributions can be encoded as low-entanglement states of the quantum register. These states can be efficiently created in a quantum computer, but they are also efficiently stored, manipulated and probed using Matrix-Product States techniques. Inspired by this idea, we present eight quantum-inspired numerical analysis algorithms, that include Fourier sampling, interpolation, differentiation and integration of partial derivative equations. These algorithms combine classical ideas – finite-differences, spectral methods – with the efficient encoding of quantum registers, and well known algorithms, such as the Quantum Fourier Transform. $\textit{When these heuristic methods work}$, they provide an exponential speed-up over other classical algorithms, such as Monte Carlo integration, finite-difference and fast Fourier transforms (FFT). But even when they don't, some of these algorithms can be translated back to a quantum computer to implement a similar task.

Computers have been traditionally an invaluable tool in the solution of complex mathematical problems, in particular in the field of numerical analysis and differential equations. In this work I continue an ongoing exploration of how quantum computers could encode multivariate functions and achieve a similar goal. This exploration reveals that many smooth differentiable functions do not require a lot of entanglement when encoded in a quantum computer. This is good, because it means that such functions can be efficiently recreated in quantum computers with short, shallow circuits. However, it also means that those quantum algorithms have an efficient classical description and can be transformed into new classical and quantum inspired methods to implement Fourier transforms, interpolation, integration or solving differential equations.

► BibTeX data

► References

[1] C. Zalka. Simulating quantum systems on a quantum computer. Proceedings of the Royal Society of London Series A, 454 (1969): 313, January 1998. 10.1098/​rspa.1998.0162.
https:/​/​doi.org/​10.1098/​rspa.1998.0162

[2] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv e-prints, art. quant-ph/​0208112, Aug 2002.
arXiv:quant-ph/0208112

[3] Ashley Montanaro. Quantum speedup of Monte Carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471 (2181): 20150301, 2015. 10.1098/​rspa.2015.0301.
https:/​/​doi.org/​10.1098/​rspa.2015.0301

[4] Stefan Woerner and Daniel J Egger. Quantum risk analysis. npj Quantum Information, 5 (1): 15, 2019. 10.1038/​s41534-019-0130-6.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

[5] Patrick Rebentrost, Brajesh Gupt, and Thomas R. Bromley. Quantum computational finance: Monte Carlo pricing of financial derivatives. Phys. Rev. A, 98: 022321, Aug 2018. 10.1103/​PhysRevA.98.022321.
https:/​/​doi.org/​10.1103/​PhysRevA.98.022321

[6] Nikitas Stamatopoulos, Daniel J. Egger, Yue Sun, Christa Zoufal, Raban Iten, Ning Shen, and Stefan Woerner. Option Pricing using Quantum Computers. arXiv e-prints, art. arXiv:1905.02666, May 2019. 10.22331/​q-2020-07-06-291.
https:/​/​doi.org/​10.22331/​q-2020-07-06-291
arXiv:1905.02666

[7] Daniel J. Egger, Ricardo Gacía Gutiérrez, Jordi Cahué Mestre, and Stefan Woerner. Credit Risk Analysis using Quantum Computers. arXiv e-prints, art. arXiv:1907.03044, Jul 2019.
arXiv:1907.03044

[8] Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub, and Sabre Kais. Quantum algorithm and circuit design solving the Poisson equation. New Journal of Physics, 15 (1): 013021, Jan 2013. 10.1088/​1367-2630/​15/​1/​013021.
https:/​/​doi.org/​10.1088/​1367-2630/​15/​1/​013021

[9] F Fillion-Gourdeau and Emmanuel Lorin. Simple digital quantum algorithm for symmetric first-order linear hyperbolic systems. Numerical Algorithms, pages 1–37, 2018. 10.1007/​s11075-018-0639-3.
https:/​/​doi.org/​10.1007/​s11075-018-0639-3

[10] Pedro C. S. Costa, Stephen Jordan, and Aaron Ostrander. Quantum algorithm for simulating the wave equation. Phys. Rev. A, 99: 012323, Jan 2019. 10.1103/​PhysRevA.99.012323.
https:/​/​doi.org/​10.1103/​PhysRevA.99.012323

[11] Michael Lubasch, Jaewoo Joo, Pierre Moinier, Martin Kiffner, and Dieter Jaksch. Variational quantum algorithms for nonlinear problems. Physical Review A, 101 (1), Jan 2020. ISSN 2469-9934. 10.1103/​physreva.101.010301.
https:/​/​doi.org/​10.1103/​physreva.101.010301

[12] Michael Lubasch, Pierre Moinier, and Dieter Jaksch. Multigrid renormalization. Journal of Computational Physics, 372: 587–602, Nov 2018. ISSN 0021-9991. 10.1016/​j.jcp.2018.06.065.
https:/​/​doi.org/​10.1016/​j.jcp.2018.06.065

[13] Jose I. Latorre. Image compression and entanglement. arXiv e-prints, art. quant-ph/​0510031, Oct 2005.
arXiv:quant-ph/0510031

[14] Lars Grasedyck, Daniel Kressner, and Christine Tobler. A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen, 36 (1): 53–78, 2013. 10.1002/​gamm.201310004.
https:/​/​doi.org/​10.1002/​gamm.201310004

[15] Markus Bachmayr, Reinhold Schneider, and André Uschmajew. Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations. Foundations of Computational Mathematics, 16 (6): 1423–1472, Dec 2016. ISSN 1615-3383. 10.1007/​s10208-016-9317-9.
https:/​/​doi.org/​10.1007/​s10208-016-9317-9

[16] S. Iblisdir, R. Orús, and J. I. Latorre. Matrix product states algorithms and continuous systems. Phys. Rev. B, 75: 104305, Mar 2007. 10.1103/​PhysRevB.75.104305.
https:/​/​doi.org/​10.1103/​PhysRevB.75.104305

[17] L. Hales and S. Hallgren. An improved quantum Fourier transform algorithm and applications. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 515–525, 2000. 10.1109/​SFCS.2000.892139.
https:/​/​doi.org/​10.1109/​SFCS.2000.892139

[18] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes in C. Cambridge Univ. Press, Cambridge, UK, 2nd. edition, 1997.

[19] J. Weideman and B. Herbst. Split-Step Methods for the Solution of the Nonlinear Schrödinger Equation. SIAM Journal on Numerical Analysis, 23 (3): 485–507, 1986. 10.1137/​0723033.
https:/​/​doi.org/​10.1137/​0723033

[20] Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349: 117–158, oct 2014. 10.1016/​j.aop.2014.06.013.
https:/​/​doi.org/​10.1016/​j.aop.2014.06.013

[21] Juan José García-Ripoll. Time evolution of Matrix Product States. New Journal of Physics, 8 (12): 305–305, dec 2006. 10.1088/​1367-2630/​8/​12/​305.
https:/​/​doi.org/​10.1088/​1367-2630/​8/​12/​305

[22] Koenraad M R Audenaert. A sharp continuity estimate for the von neumann entropy. Journal of Physics A: Mathematical and Theoretical, 40 (28): 8127–8136, jun 2007. 10.1088/​1751-8113/​40/​28/​s18.
https:/​/​doi.org/​10.1088/​1751-8113/​40/​28/​s18

[23] Norbert Schuch, Michael M. Wolf, Frank Verstraete, and J. Ignacio Cirac. Entropy scaling and simulability by matrix product states. Physical Review Letters, 100 (3), jan 2008. 10.1103/​physrevlett.100.030504. URL https:/​/​doi.org/​10.1103.
https:/​/​doi.org/​10.1103/​physrevlett.100.030504

[24] C. Schön, E. Solano, F. Verstraete, J. I. Cirac, and M. M. Wolf. Sequential generation of entangled multiqubit states. Phys. Rev. Lett., 95: 110503, Sep 2005. 10.1103/​PhysRevLett.95.110503.
https:/​/​doi.org/​10.1103/​PhysRevLett.95.110503

[25] C. Schön, K. Hammerer, M. M. Wolf, J. I. Cirac, and E. Solano. Sequential generation of matrix-product states in cavity QED. Phys. Rev. A, 75: 032311, Mar 2007. 10.1103/​PhysRevA.75.032311.
https:/​/​doi.org/​10.1103/​PhysRevA.75.032311

[26] Román Orús, Samuel Mugel, and Enrique Lizaso. Quantum computing for finance: Overview and prospects. Reviews in Physics, 4: 100028, 2019. ISSN 2405-4283. https:/​/​doi.org/​10.1016/​j.revip.2019.100028.
https:/​/​doi.org/​10.1016/​j.revip.2019.100028

[27] Juan José García-Ripoll and Burçin Danacı. SeeMPS - Self Explanatory Matrix-Product States library. , 2019. 10.5281/​zenodo.3401566.
https:/​/​doi.org/​10.5281/​zenodo.3401566
https:/​/​github.com/​juanjosegarciaripoll/​seemps

[28] Juan José García-Ripoll. Supplementary material to "Quantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations". , 2020. 10.5281/​zenodo.3969951.
https:/​/​doi.org/​10.5281/​zenodo.3969951
https:/​/​github.com/​juanjosegarciaripoll/​suppl-quantum-inspired-methods.git

[29] F. Verstraete, J. J. García-Ripoll, and J. I. Cirac. Matrix product density operators: Simulation of finite-temperature and dissipative systems. Phys. Rev. Lett., 93: 207204, Nov 2004. 10.1103/​PhysRevLett.93.207204.
https:/​/​doi.org/​10.1103/​PhysRevLett.93.207204

[30] Guifré Vidal. Efficient Classical Simulation of Slightly Entangled Quantum Computations. Phys. Rev. Lett., 91: 147902, Oct 2003. 10.1103/​PhysRevLett.91.147902.
https:/​/​doi.org/​10.1103/​PhysRevLett.91.147902

[31] F. Verstraete, V. Murg, and J.I. Cirac. Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems. Advances in Physics, 57 (2): 143–224, 2008. 10.1080/​14789940801912366.
https:/​/​doi.org/​10.1080/​14789940801912366

[32] Mihir K Bhaskar, Stuart Hadfield, Anargyros Papageorgiou, and Iasonas Petras. Quantum algorithms and circuits for scientific computing. Quantum Information & Computation, 16 (3-4): 197–236, 2016. 10.5555/​3179448.3179450.
https:/​/​doi.org/​10.5555/​3179448.3179450

[33] Nathan Wiebe and Martin Roetteler. Quantum arithmetic and numerical analysis using repeat-until-success circuits. Quantum Info. Comput., 16 (1-2): 134–178, January 2016. ISSN 1533-7146. 10.5555/​3179320.3179329.
https:/​/​doi.org/​10.5555/​3179320.3179329

[34] Jumpei Niwa, Keiji Matsumoto, and Hiroshi Imai. General-purpose parallel simulator for quantum computing. Phys. Rev. A, 66: 062317, Dec 2002. 10.1103/​PhysRevA.66.062317.
https:/​/​doi.org/​10.1103/​PhysRevA.66.062317

[35] René Steijl and George N. Barakos. Parallel evaluation of quantum algorithms for computational fluid dynamics. Computers & Fluids, 173: 22 – 28, 2018. ISSN 0045-7930. https:/​/​doi.org/​10.1016/​j.compfluid.2018.03.080.
https:/​/​doi.org/​10.1016/​j.compfluid.2018.03.080

[36] Donlad M. Monro. Interpolation by fast Fourier and Chebyshev transforms. International Journal for Numerical Methods in Engineering, 14 (11): 1679–1692, 1979. 10.1002/​nme.1620141109.
https:/​/​doi.org/​10.1002/​nme.1620141109

[37] S. Ramasesha, Swapan K. Pati, H.R. Krishnamurthy, Z. Shuai, and J.L. Brédas. Low-lying electronic excitations and nonlinear optic properties of polymers via symmetrized density matrix renormalization group method. Synthetic Metals, 85 (1): 1019 – 1022, 1997. ISSN 0379-6779. https:/​/​doi.org/​10.1016/​S0379-6779(97)80136-1.
https:/​/​doi.org/​10.1016/​S0379-6779(97)80136-1

[38] Till D. Kühner and Steven R. White. Dynamical correlation functions using the density matrix renormalization group. Phys. Rev. B, 60: 335–343, Jul 1999. 10.1103/​PhysRevB.60.335.
https:/​/​doi.org/​10.1103/​PhysRevB.60.335

[39] U. Schollwöck. The density-matrix renormalization group. Rev. Mod. Phys., 77: 259–315, Apr 2005. 10.1103/​RevModPhys.77.259.
https:/​/​doi.org/​10.1103/​RevModPhys.77.259

[40] Christa Zoufal, Aurélien Lucchi, and Stefan Woerner. Quantum generative adversarial networks for learning and loading random distributions. npj Quantum Information, 5 (1), nov 2019. 10.1038/​s41534-019-0223-2. URL https:/​/​doi.org/​10.1038.
https:/​/​doi.org/​10.1038/​s41534-019-0223-2

[41] Juan Miguel Arrazola, Timjan Kalajdzievski, Christian Weedbrook, and Seth Lloyd. Quantum algorithm for nonhomogeneous linear partial differential equations. Phys. Rev. A, 100: 032306, Sep 2019. 10.1103/​PhysRevA.100.032306.
https:/​/​doi.org/​10.1103/​PhysRevA.100.032306

[42] Ashley Milsted, Martin Ganahl, Stefan Leichenauer, Jack Hidary, and Guifre Vidal. TensorNetwork on TensorFlow: A Spin Chain Application Using Tree Tensor Networks. arXiv e-prints, art. arXiv:1905.01331, May 2019.
arXiv:1905.01331

[43] Cupjin Huang, Mario Szegedy, Fang Zhang, Xun Gao, Jianxin Chen, and Yaoyun Shi. Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design. arXiv e-prints, art. arXiv:1909.02559, Sep 2019.
arXiv:1909.02559

Cited by

[1] Oleksandr Kyriienko, Annie E. Paine, and Vincent E. Elfving, "Solving nonlinear differential equations with differentiable quantum circuits", Physical Review A 103 5, 052416 (2021).

[2] Youssef Moawad, Wim Vanderbauwhede, and René Steijl, "Investigating hardware acceleration for simulation of CFD quantum circuits", Frontiers in Mechanical Engineering 8, 925637 (2022).

[3] Marc K. Ritter, Yuriel Núñez Fernández, Markus Wallerberger, Jan von Delft, Hiroshi Shinaoka, and Xavier Waintal, "Quantics Tensor Cross Interpolation for High-Resolution Parsimonious Representations of Multivariate Functions", Physical Review Letters 132 5, 056501 (2024).

[4] Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz, "Quantum algorithms for approximate function loading", Physical Review Research 5 3, 033114 (2023).

[5] Francesco Slongo, Philipp Hauke, Pietro Faccioli, and Cristian Micheletti, "Quantum-inspired encoding enhances stochastic sampling of soft matter systems", Science Advances 9 43, eadi0204 (2023).

[6] Jason Iaconis, Sonika Johri, and Elton Yechao Zhu, "Quantum state preparation of normal distributions using matrix product states", npj Quantum Information 10 1, 15 (2024).

[7] Andrés Gómez, Álvaro Leitao, Alberto Manzano, Daniele Musso, María R. Nogueiras, Gustavo Ordóñez, and Carlos Vázquez, "A Survey on Quantum Computational Finance for Derivatives Pricing and VaR", Archives of Computational Methods in Engineering 29 6, 4137 (2022).

[8] Gabriele Agliardi, Michele Grossi, Mathieu Pellen, and Enrico Prati, "Quantum integration of elementary particle processes", Physics Letters B 832, 137228 (2022).

[9] Marc Botifoll, Ivan Pinto-Huguet, and Jordi Arbiol, "Machine learning in electron microscopy for advanced nanocharacterization: current developments, available tools and future outlook", Nanoscale Horizons 7 12, 1427 (2022).

[10] Mudassir Moosa, Thomas W Watts, Yiyou Chen, Abhijat Sarma, and Peter L McMahon, "Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions", Quantum Science and Technology 9 1, 015002 (2024).

[11] Joseph Tindall and Matthew Fishman, "Gauging tensor networks with belief propagation", SciPost Physics 15 6, 222 (2023).

[12] Javier Gonzalez-Conde, Ángel Rodríguez-Rozas, Enrique Solano, and Mikel Sanz, "Efficient Hamiltonian simulation for solving option price dynamics", Physical Review Research 5 4, 043220 (2023).

[13] Paula García-Molina, Javier Rodríguez-Mediavilla, and Juan José García-Ripoll, "Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations", Physical Review A 105 1, 012433 (2022).

[14] Jielun Chen, E.M. Stoudenmire, and Steven R. White, "Quantum Fourier Transform Has Small Entanglement", PRX Quantum 4 4, 040318 (2023).

[15] Nikita Gourianov, Michael Lubasch, Sergey Dolgov, Quincy Y. van den Berg, Hessam Babaee, Peyman Givi, Martin Kiffner, and Dieter Jaksch, "A quantum-inspired approach to exploit turbulence structures", Nature Computational Science 2 1, 30 (2022).

[16] David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch, "Filtering variational quantum algorithms for combinatorial optimization", Quantum Science and Technology 7 1, 015021 (2022).

[17] Ruojing Peng, Johnnie Gray, and Garnet Kin-Lic Chan, "Arithmetic circuit tensor networks, multivariable function representation, and high-dimensional integration", Physical Review Research 5 1, 013156 (2023).

[18] A.D. Muñoz-Moller, L. Pereira, L. Zambrano, J. Cortés-Vega, and A. Delgado, "Variational Determination of Multiqubit Geometrical Entanglement in Noisy Intermediate-Scale Quantum Computers", Physical Review Applied 18 2, 024048 (2022).

[19] Gumaro Rendon, Jacob Watkins, and Nathan Wiebe, "Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation", Quantum 8, 1266 (2024).

[20] Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa, and Mikel Sanz, "Efficient quantum amplitude encoding of polynomial functions", Quantum 8, 1297 (2024).

[21] Sergi Ramos-Calderer, "Efficient quantum interpolation of natural data", Physical Review A 106 6, 062427 (2022).

[22] Erika Ye and Nuno F. G. Loureiro, "Quantum-inspired method for solving the Vlasov-Poisson equations", Physical Review E 106 3, 035208 (2022).

[23] Seema B. Hegde, Aayush Jamuar, and Raghunath Kulkarni, 2023 International Conference on Smart Systems for applications in Electrical Sciences (ICSSES) 1 (2023) ISBN:979-8-3503-4729-6.

[24] Sergi Ramos-Calderer, Adrián Pérez-Salinas, Diego García-Martín, Carlos Bravo-Prieto, Jorge Cortada, Jordi Planagumà, and José I. Latorre, "Quantum unary approach to option pricing", Physical Review A 103 3, 032414 (2021).

[25] Bernhard Jobst, Kevin Shen, Carlos A. Riofrío, Elvira Shishenina, and Frank Pollmann, "Efficient MPS representations and quantum circuits from the Fourier modes of classical image data", arXiv:2311.07666, (2023).

[26] Óscar Amaro and Diogo Cruz, "A Living Review of Quantum Computing for Plasma Physics", arXiv:2302.00001, (2023).

[27] Adam Holmes and A. Y. Matsuura, "Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions", arXiv:2005.04351, (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-28 08:28:24) and SAO/NASA ADS (last updated successfully 2024-03-28 08:28:25). The list may be incomplete as not all publishers provide suitable and complete citation data.