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.
Featured image: Quantum (Q), classical (C) and quantum inspired algorithms (QI) studied in this work, together with some asymptotic (sometimes heuristic) time costs. Note how in some cases, such as the Fourier transform or interpolation, the quantum and quantum-inspired algorithms can provide an exponential speedup over traditional versions. In the quantum-inspired case, this speedup is only achieved for functions that do not require a lot of entanglement to be encoded, but this can include many common set of problems.
Popular summary
► 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] 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).
[2] Adam Holmes and A. Y. Matsuura, “Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions”, arXiv:2005.04351.
[3] 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 SAO/NASA ADS (last updated successfully 2021-04-19 21:02:47). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2021-04-19 21:02:45).
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.
Coinsmart. Beste Bitcoin-Börse in Europa
Source: https://quantum-journal.org/papers/q-2021-04-15-431/
