Finding the solution to linear systems is at the heart of many applications in science and technology. Over the years, a number of algorithms have been proposed to solve this problem on a digital quantum device, yet most of these are too demanding to be applied to the current noisy hardware. In this work, an original algorithmic procedure to solve the quantum linear system problem (QLSP) is presented, which combines ideas from variational quantum algorithms and the framework of classical shadows. The result is the shadow quantum linear solver (SQLS), a quantum algorithm solving the QLSP while avoiding the need for large controlled unitaries and requiring a number of qubits that is logarithmic in the system size. In particular, our heuristics show an exponential advantage of the SQLS in circuit execution per cost function evaluation when compared with other notorious variational approaches to solving linear systems of equations. We test the convergence of the SQLS on a number of linear systems, and the results highlight how the theoretical bounds on the number of resources used by the SQLS are conservative. Finally, we apply this algorithm to a physical problem of practical relevance by leveraging decomposition theorems from linear algebra to solve the discretized Laplace equation in a two-dimensional grid.
Finding the solution to linear systems is at the heart of many applications in science and technology. Over the years, a number of algorithms have been proposed to solve this problem on a digital quantum device, yet most of these are too demanding to be applied to the current noisy hardware. In this work, an original algorithmic procedure to solve the quantum linear system problem (QLSP) is presented, which combines ideas from variational quantum algorithms and the framework of classical shadows. The result is the shadow quantum linear solver (SQLS), a quantum algorithm solving the QLSP while avoiding the need for large controlled unitaries and requiring a number of qubits that is logarithmic in the system size. In particular, our heuristics show an exponential advantage of the SQLS in circuit execution per cost function evaluation when compared with other notorious variational approaches to solving linear systems of equations. We test the convergence of the SQLS on a number of linear systems, and the results highlight how the theoretical bounds on the number of resources used by the SQLS are conservative. Finally, we apply this algorithm to a physical problem of practical relevance by leveraging decomposition theorems from linear algebra to solve the discretized Laplace equation in a two-dimensional grid.
Solving linear systems of equations is central to many engineering and
scientific fields. Several quantum algorithms have been proposed for linear
systems, where the goal is to prepare ∣x⟩ such that A∣x⟩∝∣b⟩. While these algorithms are promising, the time horizon for their
implementation is long due to the required quantum circuit depth. In this work,
we propose a variational hybrid quantum-classical algorithm for solving linear
systems, with the aim of reducing the circuit depth and doing much of the
computation classically. We propose a cost function based on the overlap
between ∣b⟩ and A∣x⟩, and we derive an operational meaning for
this cost in terms of the solution precision ϵ. We also introduce a
quantum circuit to estimate this cost, while showing that this cost cannot be
efficiently estimated classically. Using Rigetti's quantum computer, we
successfully implement our algorithm up to a problem size of 32×32.
Furthermore, we numerically find that the complexity of our algorithm scales
efficiently in both 1/ϵ and κ, with κ the condition
number of A. Our algorithm provides a heuristic for quantum linear systems
that could make this application more near term.
Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations of the form Ax=b. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called Ansatz tree. The CQS approach and the Ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as 2300×2300 by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. These experiments demonstrate the algorithms' ability to scale to system sizes within reach in near-term quantum devices of about 100-300 qubits.
Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare | x ⟩ such that A | x ⟩ ∝ | b ⟩ . We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision ϵ is achieved. Specifically, we prove that C ⩾ ϵ 2 / κ 2 , where C is the VQLS cost function and κ is the condition number of A . We present efficient quantum circuits to estimate C , while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of 1024 × 1024 . Finally, we numerically solve non-trivial problems of size up to 2 50 × 2 50 . For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in ϵ , κ , and the system size N .
We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity O(ε1logm), where m is the number of variables and ε is the target precision, without dependence on the sparsity s, and could possibly be without explicit dependence on condition number κ. This shows a significant improvement over previous quantum linear solvers where the dependence on κ,s is at least linear. At the same time, when the rows have an arbitrary structure and have at most s nonzero entries, we obtain the circuit depth O(ε1logs) using extra O(s) ancilla qubits, so the depth grows only logarithmically with sparsity s. When the sparsity s grows as O(logm), then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.
Variational Quantum Algorithms (VQAs) have emerged as promising methods for tackling complex problems on near-term quantum devices. Among these algorithms, the Variational Quantum Linear Solver (VQLS) addresses linear systems of the form Ax=b, aiming to prepare a quantum state ∣x⟩ such that A∣x⟩ is proportional to the quantum state corresponding to b. A key advantage of VQLS is its use of amplitude encoding, which requires a number of qubits that scales logarithmically with the linear system size. However, the existing literature has primarily focused on linear systems of limited size or with a specific structure. In this study, we extend the application of VQLS to more general and larger problem instances, including problems where state preparation is non-trivial and problems within the real domain of fluid dynamics. Our investigation reveals some critical challenges inherent to VQLS, including the need for a sufficiently expressive ansatz, the large number of circuit executions required to estimate the cost function, and the high gate count in the circuits in the most general setting. Our analysis highlights the obstacles that need to be addressed for a broader application of VQLS and concludes that further research is necessary to fully leverage the algorithm's capabilities in addressing real-world problems.
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.