We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility with Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in [Formula: see text](N log(N)) time on a quantum circuit made of [Formula: see text](log(N)) qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready for implementation in applications such as machine learning.
We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility with Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in [Formula: see text](N log(N)) time on a quantum circuit made of Formula: see text qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready for implementation in applications such as machine learning.
We propose a realistic hybrid classical-quantum linear solver to solve systems of linear equations of a specific type, and demonstrate its feasibility using Qiskit on IBM Q systems. This algorithm makes use of quantum random walk that runs in O(Nlog(N)) time on a quantum circuit made of O(log(N)) qubits. The input and output are classical data, and so can be easily accessed. It is robust against noise, and ready to implement for applications.
Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı . [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number κ of the linear system and the target error ϵ . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O ( κ log ( 1 / ϵ ) ) —an exponential improvement in ϵ , and a shaving of a log κ scaling factor in κ . Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 κ at ϵ = 10 − 10 for Hermitian matrices.
We propose a hybrid quantum-classical implementation of the Harrow-Hassidim-Lloyd (HHL) algorithm for the matrix inversion (linear-systems) problem, a key subroutine in quantum computing. Rather than claiming a new complexity result, we provide an assumption-explicit proof sketch, aligned with established literature, that contextualizes matrix inversion as Bounded-Error Quantum Polynomial Time (BQP)-complete and offers reduction-based intuition via Grover-type amplitude amplification. We implement HHL for 2 × 2, 4 × 4, and 8 × 8 Hermitian matrices using Qiskit and evaluate performance using simulator-based experiments with calibrated noise models and executions on IBM Quantum and IonQ backends. To enhance robustness on Noisy Intermediate-Scale Quantum (NISQ) hardware, we integrate measurement-error mitigation, zero-noise extrapolation, and post-selection, and we quantify performance using fidelity and mean squared error. Results from noiseless simulation, calibrated-noise simulation, and real-device execution show that mitigation improves reconstruction fidelity for small Hermitian systems, particularly for deeper circuits. These findings support mitigation-aware feasibility on current NISQ devices; however, they do not establish present-day runtime advantage over optimized classical solvers. The proposed workflow is relevant to quantum optimization, quantum machine learning, and quantum chemistry, where linear-system primitives arise frequently. Future work will focus on reducing phase-estimation depth (e.g., iterative or semiclassical variants), improving compilation and benchmarking transparency, and re-evaluating larger instances on higher-fidelity hardware.
Gaussian processes are widely known for their ability to provide probabilistic predictions in supervised machine learning models. Their non-parametric nature and flexibility make them particularly effective for regression tasks. However, training a Gaussian process model using standard methods requires matrix inversions with a cubic time complexity, which poses significant computational challenges for inference on larger datasets. Quantum algorithms, such as the HHL algorithm, have been proposed as solutions that overcome the need for classical matrix inversions by efficiently solving linear systems of equations using quantum computers. However, to gain a computational advantage over classical algorithms, these algorithms require fault-tolerant quantum computers with a large number of qubits, which are not yet available. The Variational Quantum Linear Solver is a hybrid quantum-classical algorithm that solves linear systems of equations by optimizing the parameters of a variational quantum circuit using a classical computer. This method is especially suitable for noisy intermediate-scale quantum computers, as it does not require many qubits. It can be used to compute the posterior distribution of a Gaussian process by reformulating the matrix inversion into a set of linear systems of equations. We empirically demonstrate that using the Variational Quantum Linear Solver to perform inference for Gaussian process regression delivers regression quality comparable to that of classical methods.
State-of-the-art noisy intermediate-scale quantum devices (NISQ), although imperfect, enable computational tasks that are manifestly beyond the capabilities of modern classical supercomputers. However, present quantum computations are restricted to exploring specific simplified protocols, whereas the implementation of full-scale quantum algorithms aimed at solving concrete large scale problems arising in data analysis and numerical modelling remains a challenge. Here we introduce and implement a hybrid quantum algorithm for solving linear systems of equations with exponential speedup, utilizing quantum phase estimation, one of the exemplary core protocols for quantum computing. We introduce theoretically classes of linear systems that are suitable for current generation quantum machines and solve experimentally a 217-dimensional problem on superconducting IBMQ devices, a record for linear system solution on quantum computers. The considered large-scale algorithm shows superiority over conventional solutions, demonstrates advantages of quantum data processing via phase estimation and holds high promise for meeting practically relevant challenges.
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.