We present a variational algorithm for fault tolerant quantum computing to solve a system of linear equations which directly maximises the parameters of the target fidelity. This so-called measurement test algorithm can be applied to any computational task with a solution that is represented as eigenvector of a self-adjoint matrix. The solution is prepared as state of a register in the quantum computer by a von Neumann measurement of a corresponding observable, which is implemented using the phase estimation algorithm. The probability to project the system thus into the unknown target state, which equals the target fidelity, is measured in terms of relative frequencies and iteratively optimised to read out the target state. The new algorithm overcomes three issues of previous variational quantum algorithms: i) It does not rely on a decomposition in terms of Pauli strings and therefore can compute eigenvectors of dense matrices. ii) The accuracy is not limited by the condition number $κ$ of the matrix, provided a logarithmic number ($O(\logκ)$) of qubits is used to encode the eigenvalues and iii) the target fidelity $F_T = 1-ε$ can be reached with an accuracy $ε$ that scales with $1/N$ for $N$ measurements per iteration. We demonstrate this by numerical simulations for dense random real-valued $16\times 16$ matrices with non-vanishing determinant.
We present a variational algorithm for fault tolerant quantum computing to solve a system of linear equations which directly maximises the parameters of the target fidelity. This so-called measurement test algorithm can be applied to any computational task with a solution that is represented as eigenvector of a self-adjoint matrix. The solution is prepared as state of a register in the quantum computer by a von Neumann measurement of a corresponding observable, which is implemented using the phase estimation algorithm. The probability to project the system thus into the unknown target state, which equals the target fidelity, is measured in terms of relative frequencies and iteratively optimised to read out the target state. The new algorithm overcomes three issues of previous variational quantum algorithms: i) It does not rely on a decomposition in terms of Pauli strings and therefore can compute eigenvectors of dense matrices. ii) The accuracy is not limited by the condition number κ of the matrix, provided a logarithmic number (O(logκ)) of qubits is used to encode the eigenvalues and iii) the target fidelity FT=1−ε can be reached with an accuracy ε that scales with 1/N for N measurements per iteration. We demonstrate this by numerical simulations for dense random real-valued 16×16 matrices with non-vanishing determinant.
Quantum algorithms have been developed for efficiently solving linear algebra tasks. However, they generally require deep circuits and hence universal fault-tolerant quantum computers. In this work, we propose variational algorithms for linear algebra tasks that are compatible with noisy intermediate-scale quantum devices. We show that the solutions of linear systems of equations and matrix-vector multiplications can be translated as the ground states of the constructed Hamiltonians. Based on the variational quantum algorithms, we introduce Hamiltonian morphing together with an adaptive ansätz for efficiently finding the ground state, and show the solution verification. Our algorithms are especially suitable for linear algebra problems with sparse matrices, and have wide applications in machine learning and optimisation problems. The algorithm for matrix multiplications can be also used for Hamiltonian simulation and open system simulation. We evaluate the cost and effectiveness of our algorithm through numerical simulations for solving linear systems of equations. We implement the algorithm on the IBM quantum cloud device with a high solution fidelity of 99.95%.
Abstract This paper presents a hybrid variational quantum algorithm that finds a random eigenvector of a unitary matrix with a known quantum circuit. The algorithm is based on the SWAP test on trial states generated by a parametrized quantum circuit. The eigenvector is described by a compact set of classical parameters that can be used to reproduce the found approximation to the eigenstate on demand. This variational eigenvector finder can be adapted to solve the generalized eigenvalue problem, to find the eigenvectors of normal matrices and to perform quantum principal component analysis on unknown input mixed states. These algorithms can all be run with low-depth quantum circuits, suitable for an efficient implementation on noisy intermediate-scale quantum computers and, with some restrictions, on linear optical systems. In full-scale quantum computers, where there might be optimization problems due to barren plateaus in larger systems, the proposed algorithms can be used as a primitive to boost known quantum algorithms. Limitations and potential applications are discussed.
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.
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix A and a vector b the task is to find the vector x such that Ax=b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional A with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of A, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of A is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of A and the vector of Euclidean norms of the rows of A.
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 .
Quantum algorithms for solving linear systems of equations have generated excitement because of the potential speed-ups involved and the importance of solving linear equations in many applications. However, applying these algorithms can be challenging. The Harrow-Hassidim-Lloyd algorithm and improvements thereof require complex subroutines suitable for fault-tolerant hardware such as Hamiltonian simulation, making it ill-suited to current hardware. Variational algorithms, on the other hand, involve expensive optimization loops, which can be prone to barren plateaus and local optima. We describe a quantum algorithm for solving linear systems of equations that avoids these problems. Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix. This approach only utilizes basic quantum subroutines like the Hadamard test or the swap test, so it is well-suited to current hardware. There is no optimization loop, so barren plateaus and local optima do not present a problem. The low-rank aspect of the identity enables us to efficiently transfer information to and from the quantum computer. This approach can produce accurate results on current hardware. As evidence of this, we estimate an inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer. To our knowledge, no system of equations this large has previously been solved to this level of accuracy on a quantum computer.