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.
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 .
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.
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.
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.
Variational quantum algorithms have found success in the noisy intermediate-scale quantum era owing to their hybrid quantum-classical approach which mitigate the problems of noise in quantum computers. In our paper, we introduce the dynamic ansatz in the variational quantum linear solver for a system of linear algebraic equations. In this improved algorithm, the number of layers in the hardware efficient ansatz circuit is evolved, starting from a small and gradually increasing until convergence of the solution is reached. We demonstrate the algorithm advantage in comparison to the standard static ansatz by utilizing fewer quantum resources and with a smaller quantum depth on average in the presence and absence of quantum noise and in cases when the number of qubits or condition number of the system matrices are increased. The numbers of iterations and layers can be altered by a switching parameter. The performance of the algorithm in using quantum resources is quantified by a newly defined metric.
Solving linear systems is at the foundation of many algorithms. Recently, quantum linear system algorithms (QLSAs) have attracted great attention since they converge to a solution exponentially faster than classical algorithms in terms of the problem dimension. However, low-complexity circuit implementations of the oracles assumed in these QLSAs constitute the major bottleneck for practical quantum speed-up in solving linear systems. In this work, we focus on the application of QLSAs for linear systems that are expressed as a low rank tensor sums, which arise in solving discretized PDEs. Previous works uses modified Krylov subspace methods to solve such linear systems with a per-iteration complexity being polylogarithmic of the dimension but with no guarantees on the total convergence cost. We propose a quantum algorithm based on the recent advances on adiabatic-inspired QLSA and perform a detailed analysis of the circuit depth of its implementation. We rigorously show that the total complexity of our implementation is polylogarithmic in the dimension, which is comparable to the per-iteration complexity of the classical heuristic methods.