ABSTRACT Quantum discrete adiabatic linear‐system algorithms may require increasingly long coherent circuit sequences as the number of evolution steps grows. A batchwise quantum discrete adiabatic linear‐system solver is presented, in which the evolution is partitioned into sequentially dependent circuit batches. Each batch is followed by computational‐basis measurement, classical state reconstruction, and state re‐preparation for the next batch, thereby reducing the longest uninterrupted coherent circuit depth while preserving the intended discrete evolution structure. The reconstruction exploits the real–imaginary structure of the evolving state together with a sign‐prediction procedure. Selected DeepQuantum simulations evaluate the conditional solution fidelity under different evolution settings, sampling budgets, noise levels, sign‐prediction thresholds, condition numbers, and matrix dimensions. The results indicate that high conditional solution fidelity can be retained under suitable discretization and reconstruction settings and clarify the trade‐off among coherent depth, measurement overhead, and classical processing. The proposed framework provides a simulation‐based foundation and practical design guidance for future quantum‐hardware studies of adiabatic linear‐system solvers.
ABSTRACT Quantum discrete adiabatic linear‐system algorithms may require increasingly long coherent circuit sequences as the number of evolution steps grows. A batchwise quantum discrete adiabatic linear‐system solver is presented, in which the evolution is partitioned into sequentially dependent circuit batches. Each batch is followed by computational‐basis measurement, classical state reconstruction, and state re‐preparation for the next batch, thereby reducing the longest uninterrupted coherent circuit depth while preserving the intended discrete evolution structure. The reconstruction exploits the real–imaginary structure of the evolving state together with a sign‐prediction procedure. Selected DeepQuantum simulations evaluate the conditional solution fidelity under different evolution settings, sampling budgets, noise levels, sign‐prediction thresholds, condition numbers, and matrix dimensions. The results indicate that high conditional solution fidelity can be retained under suitable discretization and reconstruction settings and clarify the trade‐off among coherent depth, measurement overhead, and classical processing. The proposed framework provides a simulation‐based foundation and practical design guidance for future quantum‐hardware studies of adiabatic linear‐system solvers.
Existing quantum discrete adiabatic approaches are hindered by circuit depth that increases linearly with the number of evolution steps, a significant challenge for current quantum hardware with limited coherence times. To address this, we propose a co-designed framework that synergistically integrates dynamic circuit capabilities with real-time classical processing. This framework reformulates the quantum adiabatic evolution into discrete, dynamically adjustable segments. The unitary operator for each segment is optimized on-the-fly using classical computation, and circuit multiplexing techniques are leveraged to reduce the overall circuit depth scaling from O(steps×depth(U)) to O(depth(U)). We implement and benchmark a quantum discrete adiabatic linear solver based on this framework for linear systems of W∈{2,4,8,16} dimensions with condition numbers κ∈{10,20,30,40,50}. Our solver successfully overcomes previous depth limitations, maintaining over 80% solution fidelity even under realistic noise models. Key algorithmic optimizations contributing to this performance include a first-order approximation of the discrete evolution operator, a tailored dynamic circuit design exploiting real-imaginary component separation, and noise-resilient post-processing techniques.
In adiabatic quantum computing the aim is to track an eigenstate as the Hamiltonian changes. In the usual setup this is achieved using the natural time-dependent Hamiltonian evolution of the system and the main technical tool is the adiabatic theorem. We propose several alternative processes that achieve the same goal, but can easily be implemented on a gate-based quantum computer without the overhead of simulating time-dependent Hamiltonian evolution. We give a general framework for deriving `adiabatic' theorems for these processes.
As an application, we give various algorithms for solving the Quantum Linear Systems Problem (QLSP) with optimal scaling in the condition number. One of these algorithms was previously developed in [Cunningham, Roland 2024] and another can be seen as a randomised version of the discrete adiabatic algorithm of [Costa et al. 2022].
We also describe versions of Trotterisation in our framework, which allows several results from [An et al. 2025] to be reproduced in a randomised setting. In particular, bounds on the Trotter error in terms of the fidelity are obtained that are asymptotically better than the standard bounds.
Linear system solvers are widely used in scientific computing, with the primary goal of solving linear system problems. Classical iterative algorithms typically rely on the conjugate gradient method. The rise of quantum computing has spurred interest in quantum linear system problems (QLSP), particularly following the introduction of the HHL algorithm by Harrow et al. in 2009, which demonstrated the potential for exponential speedup compared to classical algorithms. However, the performance of the HHL algorithm is constrained by its dependence on the square of the condition number. To address this limitation, alternative approaches based on adiabatic quantum computing (AQC) have been proposed, which exhibit complexity scaling linearly with the condition number. AQC solves QLSP by smoothly varying the parameters of the Hamiltonian. However, this method suffers from high Hamiltonian simulation complexity. In response, this work designs new Hamiltonians and proposes a quantum discrete adiabatic linear solver based on block encoding and eigenvalue separation techniques (BEES-QDALS). This approach bypasses Hamiltonian simulation through a first-order approximation and leverages block encoding to achieve equivalent non-unitary operations on qubits. By comparing the fidelity of the original algorithm and BEES-QDALS when solving QLSP with a fixed number of steps, and the number of steps required to reach a target fidelity, it is found that BEES-QDALS significantly outperforms the original algorithm. Specifically, BEES-QDALS achieves higher fidelity with the same number of steps and requires fewer steps to reach the same target fidelity.
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.
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.
To solve linear systems Ax=b, we propose a sample-based quantum linear solver combining quantum Krylov-state sampling with classical variational diagonalization. Rather than simulating the cost Hamiltonian Hb(A)=A†(I−∣b⟩⟨b∣)A, we measure quantum Krylov states e−iAT∣b⟩ generated by the original Hermitian operator A in the computational basis. We then classically diagonalize the projected cost Hamiltonian to reconstruct an approximate solution. Using a representation of A−1∣b⟩ as a linear combination of quantum Krylov states, we derive lower bounds on computational-basis sampling probabilities from solution amplitudes. We establish support-discovery guarantees for finite nonnegative-time grid sampling and signed-time sampling, which permits both positive and negative evolution times. The former bounds the maximum evolution time, whereas the latter improves ideal shot complexity at the cost of occasional long evolutions. For a condition-number bound κ on A, a lower bound βL on the solution probability weight of each of L target basis states, and failure probability δ, signed-time sampling achieves O(κ2βL−1log(L/δ)) shots, matching a worst-case lower bound up to constants within an evolution-only observation model in a specified parameter regime. Finally, we analyze the effects of finite-length qDRIFT compilation and circuit reuse on sampling and derive an infidelity bound for the reconstructed solution.