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 .
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 .
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.
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.
Finite-element methods are industry standards for finding numerical solutions to partial differential equations. However, the application scale remains pivotal to the practical use of these methods, even for modern-day supercomputers. Large, multi-scale applications, for example, can be limited by their requirement of prohibitively large linear system solutions. It is therefore worthwhile to investigate whether near-term quantum algorithms have the potential for offering any kind of advantage over classical linear solvers. In this study, we investigate the recently proposed variational quantum linear solver (VQLS) for discrete solutions to partial differential equations. This method was found to scale polylogarithmically with the linear system size, and the method can be implemented using shallow quantum circuits on noisy intermediate-scale quantum (NISQ) computers. Herein, we utilize the hybrid VQLS to solve both the steady Poisson equation and the time-dependent heat and wave equations.
A hybrid quantum–classical approach to solving the load balancing problem in real-time computer systems is proposed, with a focus on reliability assessment and control. The approach is based on the use of a Variational Quantum Linear Solver (VQLS) to process large sparse linear systems arising from the spatio-temporal discretization of load distribution models and task flows among computational nodes. An algorithmic scheme is presented for transforming an engineering model of a real-time system into a quantum-realizable problem formulation. Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. This scheme includes decomposing the system matrix into a linear combination of Pauli operators, preparing a quantum state corresponding to the right-hand side, and optimizing a variational ansatz. It is shown that the resulting quantum solution state is most effective when used not for full reconstruction of the load vector, but for direct estimation of aggregated and local metrics, such as peak load, slack to deadline violations, and integral stability indicators, which are directly related to system failures and performance degradation. The proposed approach is considered as a tool for quantum benchmarking of classical load balancing algorithms, as well as a potential foundation for building reliability management systems for computer systems operating in a near–real-time regime. Key words. Reliability of computer systems, Bayesian neural networks, ensemble methods, artificial intelligence, hybrid models, risk assessment, fault tolerance, uncertainty modeling, failure prediction, software security, system resilience, neural networks, fault trees, machine learning, quantum systems, quantum algorithms, quantum machine learning, hybrid models.
Based on a photonic computing platform, we experimentally validate a generalized variational quantum linear solver (VQLS) by systematically solving four-dimensional linear equation systems across different fields. In the complex field, in addition to solving non-singular systems that admit a unique solution, we investigate ill-conditioned problems arising from singularity--an issue frequently encountered in practical applications. To tackle these challenges, we introduce perturbation terms, a treatment inspired by Tikhonov regularization, and develop an algorithm capable of handling a wide range of systems. Furthermore, we extend the VQLS to the finite field F2 by redesigning the cost function to incorporate modulo 2 and imposing several constraints on the solution vector. This modulo 2 VQLS is inherently free from singularity. It is adapt to stabilizer coding theory and may find applications in areas such as decoders and the design of quantum gate sequences. Therefore, our work demonstrates the practical potential of VQLS in quantum computing, providing a solid experimental foundation and methodological guidance for its real-world applications.