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] 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).

[3] Javier Gonzalez-Conde, Ángel Rodríguez-Rozas, Enrique Solano, and Mikel Sanz, "Pricing Financial Derivatives with Exponential Quantum Speedup", arXiv:2101.04023.

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

[5] Paula García-Molina, Javier Rodríguez-Mediavilla, and Juan José García-Ripoll, "Solving partial differential equations in quantum computers", arXiv:2104.02668.

The above citations are from Crossref's cited-by service (last updated successfully 2021-10-22 14:13:57) and SAO/NASA ADS (last updated successfully 2021-10-22 14:13:59). The list may be incomplete as not all publishers provide suitable and complete citation data.