Quantum algorithm for linear systems

Jincheng Zhang

Linear matrix systems represent a fundamental class of problems in mathematics, physics, and engineering, and their efficient solution is crucial for various applications. Traditional methods often rely on computationally intensive algorithms, limiting scalability. This paper explores the potential of leveraging the inherent non-linear properties of linear matrices to design novel quantum algorithms for solving linear systems. We propose a quantum algorithm predicated on the principle that by mapping a linear system into a non-linear representation via a specific matrix transformation, we can achieve speedups that surpass classical approaches. The core mechanism involves constructing a quantum circuit that systematically explores this non-linear space, leveraging quantum phenomena like superposition and entanglement to enhance the search process. The paper details the design of a quantum algorithm for solving linear systems, emphasizing the benefits of this approach and its potential to unlock new possibilities in quantum computation.

Osama M. Raisuddin, Suvranu De

Liam Michael Ogren, Lauren Michelle Baker

Carlos Bravo-Prieto, Ryan LaRose, Marco Cerezo +3 more

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\rangle$ such that $A|x\rangle \propto |b\rangle$. 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\rangle$ and $A|x\rangle$, and we derive an operational meaning for this cost in terms of the solution precision $\epsilon$. 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 \times 32$. Furthermore, we numerically find that the complexity of our algorithm scales efficiently in both $1/\epsilon$ and $\kappa$, with $\kappa$ the condition number of $A$. Our algorithm provides a heuristic for quantum linear systems that could make this application more near term.

Junhyung Lyle Kim, Nai-Hui Chia, Anastasios Kyrillidis

Solving systems of linear equations is a fundamental problem, but it can be computationally intensive for classical algorithms in high dimensions. Existing quantum algorithms can achieve exponential speedups for the quantum linear system problem (QLSP) in terms of the problem dimension, but the advantage is bottlenecked by condition number of the coefficient matrix. In this work, we propose a new quantum algorithm for QLSP inspired by the classical proximal point algorithm (PPA). Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing QLSP solver, thereby directly approximating the solution vector instead of approximating the inverse of the coefficient matrix. By carefully choosing the step size eta, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches. Importantly, this is the first iterative framework for QLSP where a tunable parameter eta and initialization x_0 allows controlling the trade-off between the runtime and approximation error.

Osama M. Raisuddin, Suvranu De