Quantum Poisson solver without arithmetic

Abstract

Solving differential equations is one of the most promising applications of quantum computing. The Poisson equation has applications in various domains of physics and engineering, including the simulation of ocean current dynamics. Here, we propose an efficient quantum algorithm for solving the one-dimensional Poisson equation based on the controlled R _y rotations. Our quantum Poisson solver (QPS) removes the need for expensive routines such as phase estimation, quantum arithmetic or Hamiltonian simulation. The computational cost of our QPS is 3n in qubits and 5/3n ³ in one- and two-qubit gates, where n is the logarithmic of the number of discrete points. An overwhelming reduction of the constant factors of the big-O complexity is achieved, which is critical to evaluate the practicality of implementing the algorithm on a quantum computer. In terms of the error ε, the complexity is log(1/ε) in qubits and poly(log(1/ε)) in operations. The algorithms are demonstrated using a quantum virtual computing system, and the circuits are executed successfully on the IBM real quantum computers. The present QPS could exhibit a potential real-world application for solving differential equations on noisy intermediate-scale quantum (NISQ) devices.

Keywords

Poisson equation / Quantum linear systems algorithm / Quantum arithmetic / Matrix diagonalization

References

[1] Ambainis A. Variable time amplitude amplification and quantum algorithms for linear algebra problems. 29th Int Symp Theore Aspects Compu Sci Int, 2012, 14: 636-647

[2] Arrazola JM, Kalajdzievski T, Weedbrook C, Lloyd S. Quantum algorithm for nonhomogeneous linear partial differential equations. Phys Rev A, 2019, 100(3): 032306,

[3] Arute F, Arya K, Babbush R, Bacon D, Bardin JC, Barends R, et al.. Quantum supremacy using a programmable superconducting processor. Nature, 2019, 574(7779): 505-510,

[4] Barenco A, Bennett CH, Cleve R, DiVincenzo DP, Margolus N, Shor P, et al.. Elementary gates for quantum computation. Phys Rev A, 1995, 52(5): 3457-3467,

[5] Berry DW. High-order quantum algorithm for solving linear differential equations. J Phys A Math Theor, 2014, 47(10): 105301,

[6] Berry DW, Childs AM, Kothari R (2015) Hamiltonian simulation with nearly optimal dependence on all parameters. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Berkeley, CA, pp 792–809

[7] Berry DW, Childs AM, Ostrander A, Wang GM. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Commun Math Phys, 2017, 356(3): 1057-1081,

[8] Bhaskar MK, Hadfield S, Papageorgiou A, Petras I (2016) Quantum algorithms and circuits for scientific computing. Quantum Inf Comput 16(3–4):197–236

[9] Cao YD, Papageorgiou A, Petras I, Traub J, Kais S. Quantum algorithm and circuit design solving the Poisson equation. New J Phys, 2013, 15: 013021,

[10] Childs AM, Kothari R, Somma RD. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J Comput, 2017, 46(6): 1920-1950,

[11] Childs AM, Liu JP. Quantum spectral methods for differential equations. Commun Math Phys, 2020, 375(2): 1427-1457,

[12] Childs AM, Liu JP, Ostrander A. High-precision quantum algorithms for partial differential equations. Quantum, 2021, 5: 1-40,

[13] Cleve R, Watrous J (2000) Fast parallel circuits for the quantum Fourier transform. In: 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, pp 526–536

[14] Costa PCS, Jordan S, Ostrander A. Quantum algorithm for simulating the wave equation. Phys Rev A, 2019, 99(1): 012323,

[15] Damianou PA. A beautiful sine formula. Am Math Mon, 2014, 121(2): 120-135,

[16] Demmel JW. . Applied numerical linear algebra, 1997 Philadelphia SIAM,

[17] Dervovic D, Herbster M, Mountney P, Severini S, Usher N, Wossnig L (2018) Quantum linear systems algorithms: a primer. Preprint at arXiv:1802.08227

[18] Figgatt C, Ostrander A, Linke NM, Landsman KA, Zhu D, Maslov D, et al.. Parallel entangling operations on a universal ion-trap quantum computer. Nature, 2019, 572(7769): 368-372,

[19] Ford W. . Numerical linear algebra with applications: using MATLAB, 2014 New York Academic Press

[20] Häner T, Roetteler M, Svore KM (2018) Optimizing quantum circuits for arithmetic. Preprint at arXiv:1805.12445

[21] Harrow AW, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Phys Rev Lett, 2009, 103(15): 150502,

[22] IBM ibmq_santiago v1.2.0 (2020) IBM Quantum team. https://quantum-computing.ibm.com

[23] IBM ibmqx2 v2.2.4 (2020) IBM Quantum team. https://quantum-computing.ibm.com

[24] Kalajdzievski T, Arrazola JM. Exact gate decompositions for photonic quantum computing. Phys Rev A, 2019, 99(2): 022341,

[25] Klappenecker A, Rotteler M (2001) Discrete cosine transforms on quantum computers. In: 2nd International Symposium on Image and Signal Processing and Analysis, Pula, pp 464–468

[26] Kosior A, Kudela H. Parallel computations on GPU in 3D using the vortex particle method. Comput Fluids, 2013, 80(SI): 423-428,

[27] Krantz P, Kjaergaard M, Yan F, Orlando TP, Gustavsson S, Oliver WD. A quantum engineer’s guide to superconducting qubits. Appl Phys Rev, 2019, 6(2): 021318,

[28] Leymann F, Barzen J. The bitter truth about gate-based quantum algorithms in the NISQ era. Quantum Sci Technol, 2020, 5(4): 044007,

[29] Leyton SK, Osborne TJ (2008) A quantum algorithm to solve nonlinear differential equations. Preprint at arXiv:0812.4423

[30] Low GH, Chuang IL. Optimal Hamiltonian simulation by quantum signal processing. Phys Rev Lett, 2017, 118(1): 010501,

[31] Markaida BG, Wu LA (2020) Experimental implementation of leakage elimination operators and subspaces protection. Preprint at arXiv:2007.04694

[32] Maslov D. Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures. Phys Rev A, 2007, 76(5): 052310,

[33] Montanaro A (2016) Quantum algorithms: an overview. npj Quantum Inf 2:15023

[34] Preskill J. Quantum COMPUTING in the NISQ era and beyond. Quantum, 2018, 2: 79,

[35] Rasmussen SE, Groenland K, Gerritsma R, Schoutens K, Zinner NT. Single-step implementation of high-fidelity n-bit Toffoli gates. Phys Rev A, 2020, 101(2): 022308,

[36] Shor PW (1994) Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994, pp 124–134

[37] Steijl R, Barakos GN. Parallel evaluation of quantum algorithms for computational fluid dynamics. Comput Fluids, 2018, 173: 22-28,

[38] Tomza M, Jachymski K, Gerritsma R, Negretti A, Calarco T, Idziaszek Z, et al.. Cold hybrid ion-atom systems. Rev Mod Phys, 2019, 91(3): 035001,

[39] Vatan F, Williams C. Optimal quantum circuits for general two-qubit gates. Phys Rev A, 2004, 69(3): 032315,

[40] Wang SB, Wang ZM, Li WD, Fan LX, Cui GL, Wei ZQ et al (2020a) Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method. Quantum Inf Proc 19(10):347

[41] Wang SB, Wang ZM, Li WD, Fan LX, Wei ZQ, Gu YJ. Quantum fast Poisson solver: the algorithm and complete and modular circuit design. Quantum Inf Process, 2020, 19(6): 170,

[42] Wang ZM, Chen ZY, Wang SB, Li WD, Gu YJ, Guo GP, et al.. A quantum circuit simulator and its applications on Sunway TaihuLight supercomputer. Sci Rep, 2021, 11(1): 355, pmcid: 7801639

[43] Wei HR, Di YM (2012) Decomposition of orthogonal matrix and synthesis of two-qubit and three-qubit orthogonal gates. Preprint at arXiv:1203.0722

[44] Zulehner A, Wille R (2019) Compiling SU(4) quantum circuits to IBM QX architectures. In: 24th Asia and South Pacific Design Automation Conference, Tokyo, pp 185–190

Funding

Natural Science Foundation of Shandong Province(ZR2021ZD19)

National Natural Science Foundation of China(12005212)