Solving 1D Poisson problem with a Variational Quantum Linear Solver

Giorgio Tosti Balducci, Boyang Chen, Matthias Möller, Roeland De Breuker · 2024

Read Solving 1D Poisson problem with a Variational Quantum Linear Solver by Giorgio Tosti Balducci, Boyang Chen, Matthias Möller, Roeland De Breuker (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04938.txt.

Introduction

Giorgio Tosti Balducci, Boyang Chen, Matthias Möller, and Roeland De Breuker solve a classic equation on quantum hardware in a paper from two thousand twenty-four. Hybrid quantum algorithms promise to solve linear systems on near-term devices. Most demos, though, use easy physics problems with very friendly matrices.

The team tackles tridiagonal systems, which arise from one-dimensional finite element models such as the Poisson problem. They give a new way to split such matrices into quantum gates, using fewer terms than a plain Pauli approach. The split trades term count against circuit depth that today's hardware can handle. They report the first runs of this solver class on tridiagonal systems, in simulation and on real quantum hardware.

Catalog record

CREATORGiorgio Tosti Balducci, Boyang Chen, Matthias Möller, Roeland De Breuker
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-04938

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solving 1D Poisson problem with a Variational Quantum Linear Solver Giorgio Tosti Balducci, Boyang Chen, Matthias Möller, Roeland De Breuker Abstract Different hybrid quantum-classical algorithms have recently been developed as a near-term way to solve linear systems of equations on quantum devices. However, the focus has so far been mostly on the methods, rather than the problems that they need to tackle. In fact, these algorithms have been run on real hardware only for problems in quantum physics, such as Hamiltonians of a few qubits systems. These problems are particularly favorable for quantum hardware, since their matrices are the sum of just a few unitary terms and since only shallow quantum circuits are required to estimate the cost function. However, for many interesting problems in linear algebra, it appears far less trivial to find an efficient decomposition and to trade it off with the depth of the cost quantum circuits. A first simple yet interesting instance to consider are tridiagonal systems of equations. These arise, for instance, in the discretization of one-dimensional finite element analyses. This work presents a method to solve a class of tridiagonal systems of equations with the variational quantum linear solver (VQLS), a recently proposed variational hybrid algorithm for solving linear systems. In particular, we present a new decomposition for this class of matrices based on both Pauli strings and multi–qubit gates, resulting in less terms than those obtained by just using Pauli gates. Based on this decomposition, we discuss the tradeoff between the number of terms and the near-term implementability of the quantum circuits. Furthermore, we present the first simulated and real-hardware results obtained by solving tridiagonal linear systems with VQLS, using the decomposition proposed. I Introduction Current quantum computers are a tool in search for applications. Even though several quantum algorithms have deep practical implications and offer up to exponential speed-ups, their promises are so far purely theoretical. Good examples of this are Shor’s algorithm for period finding [ 1 ] and Grover’s for database search [ 2 ] . The reason why no implementations at useful scales exist for this algorithms is that quantum hardware is still far from its maturity. In fact, we are in the so-called Noisy Intermediate Scale Quantum (NISQ) era [ 3 ] , in which quantum computers have 50 to 100 physical qubits, that are noisy and mostly not error-corrected. As a consequence, one of today’s challenges is to find problem-method combinations that can run on NISQ devices with limited error. There are ultimately two ways to go. In the first one a problem is sought for that is classically hard but quantum efficient, regardless of the practical interest in the problem itself [ 4 ] . These are the applications aimed at proving quantum supremacy. A second case is when a NISQ computer is used to solve a relevant problem. Here however, the algorithms are not the ones promising a speed-up on fully connected and error-corrected quantum hardware, but others that take into account the limitations of today’s machines. Proabably the most prominent class of these methods are the so-called Variational Quantum Algorithms (VQAs) [ 5 ] . These already found applications in different disciplines, such as quantum chemistry [ 6 , 7 , 8 ] and quantum machine learning [ 9 , 10 , 11 ] . Recently VQAs were also developed for solving linear system of equations [ 12 , 13 , 14 , 15 , 16 ] , a problem encountered in many different scientific and engineering disciplines. Unlike the seminal work of Harrow, Hassiddim and Lloyd on solving linear systems on an ideal quantum device [ 17 ] , these algorithms do not promise an exponential speed-up. However, they were applied successfully to problems of dimensions 2^{300}\times 2^{300} on a simulator [ 12 ] and 1024\times 1024 on a quantum computer [ 14 ] . To the best of the authors’ knowledge, the latter is the largest linear systems ever to be solved on quantum hardware. However, the linear systems in previous works, which were solved on quantum hardware with a variational linear solver [ 14 ] can be thought of as technology demonstrators. In fact, in these instances, the system’s matrix is always chosen as a Hamiltonian acting on few qubits, that can be efficiently encoded on a quantum computer. The question yet to be answered is whether variational linear solvers can efficiently solve problems that stem from real-world applications and that are not specifically tuned to the hardware. A simple, yet interesting starting point are tridiagonal linear systems, which derive, for instance, from the discretization of the Poisson problem in one dimension [ 18 ] . In this work, we adopt a VQA for linear systems, namely the Variational Quantum Linear Solver (VQLS) [ 14 ] and focus on the problem of decomposing the Poisson 1D discrete matrix in unitary terms. This decomposition is an important step, as the algorithm’s efficiency depends on the number of unitary components, since this affects the amount of quantum circuits to evaluate. To this end, we compare the naive decomposition in Pauli strings with a novel approach, that includes multi-qubit gates. We show that the new decomposition almost halves the number of unitary terms, but also that these correspond to deeper, thus less near-term quantum circuits. Finally, we present and discuss the results obtained by solving small tridiagonal linear systems both on a simulator and on quantum hardware. We ultimately remark that this work is not intended as isolated. In our view, this will be the first step before extending the application of VQAs to other linear systems, which derive from the numerical discretization of partial differential equations. II Background II-A The Quantum Linear System Problem Let A be a square complex N\times N matrix and \bm{b} a complex N -dimensional vector. The aim is to find the complex vector \bm{x} such that A\bm{x}=\bm{b}. (1) In general, ( 1 ) is not in a form suitable for quantum computation, since, \bm{x} and \bm{b} do not necessarily have unit norm and thus are not valid quantum states. Nevertheless, an analogous problem can be solved, that is A|x\rangle=|b\rangle, (2) where |x\rangle=\bm{x}/||x|| and |b\rangle=\bm{b}/||b|| . Eq. ( 2 ) is known as the Quantum Linear System Problem (QLSP). Solving ( 2 ) on a quantum computer requires A and |b\rangle to be encoded in terms of unitary gates and quantum states. This means that the matrix A must be decomposed as A=\sum_{l=1}^{L}c_{l}A_{l}, (3) where c_{l}\in\mathbb{C} and A_{l} are unitary N\times N complex matrices. Also, the state |b\rangle needs to be prepared as |b\rangle=B|0\rangle=\sum_{m=1}^{M}c_{m}B_{m}|0\rangle, (4) with c_{m} and B_{m} being, respectively, complex scalars and unitary matrices. As explained later in the paper, the problem of reducing the number of unitary components of A and B is crucial for the success and the efficiency of a variational linear solver. II-B The VQLS algorithm The Variational Quantum Linear Solver [ 14 ] is an algorithm that allows to find an approximate solution |x_{f}\rangle to the generic QLSP. In essence, it consists in minimizing a cost function that represents the distance between the states |\psi\rangle=A|x\rangle and |b\rangle . The optimization parameters \bm{\theta} determine the tentative solution |x\rangle at every iteration as |x(\bm{\theta})\rangle=V(\bm{\theta})|0\rangle,

Read the complete text