Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1805.10549 · Physical Review Letters

Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing

Yiğit Subaşı, Rolando D. Somma, Davide Orsucci

Published Feb 14, 2019• 221 citations
arXivHTMLPDF

Abstract

We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state $|x⟩$ that is proportional to the solution of the system of linear equations $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$. The time complexities of our algorithms are $O\mathbf{(}{\ensuremath{\kappa}}^{2}\mathrm{log}(\ensuremath{\kappa})/\ensuremath{\epsilon}\mathbf{)}$ and $O\mathbf{(}\ensuremath{\kappa}\mathrm{log}(\ensuremath{\kappa})/\ensuremath{\epsilon}\mathbf{)}$, where $\ensuremath{\kappa}$ is the condition number of $A$ and $\ensuremath{\epsilon}$ is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of $A$, the projector onto the initial state $|b⟩$, and single-qubit Pauli operators. The algorithms are conceptually simple and easy to implement. They are not obtained from equivalences between the gate model and adiabatic quantum computing. They do not use phase estimation or variable-time amplitude amplification, and do not require large ancillary systems. We discuss a gate-based implementation via Hamiltonian simulation and prove that our second algorithm is almost optimal in terms of $\ensuremath{\kappa}$. Like previous methods, our techniques yield an exponential quantum speed-up under some assumptions. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms.

DOI
10.1103/physrevlett.122.060504

Related papers

Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem

Pedro C. S. Costa, Dong An, Yuval R. Sanders +3 more

Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian.Such approaches have enabled near-linear scaling in the condition number κ of the linear system, without requiring a complicated variable-time amplitude amplification procedure.However, the most efficient of those procedures is still asymptotically suboptimal by a factor of log(κ).Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete-time evolutions.In combination with the qubitized quantum walk, our discrete adiabatic theorem gives a speed-up for all adiabatic algorithms.Here, we use this combination to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in κ, matching a known lower bound on the complexity.Our O[κ log(1/ )] complexity is also optimal in terms of the combined scaling in κ and the precision .Compared to existing suboptimal methods, our algorithm is simpler and easier to implement.Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications.

arXiv:2111.08152•PRX Quantum•Oct 7, 2022•196 citations

Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs

David Jennings, Matteo Lostaglio, Sam Pallister +2 more

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.

arXiv:2305.11352•PRX Quantum•Oct 7, 2025•52 citations

A shortcut to an optimal quantum linear system solver

Alexander M. Dalzell

Given a linear system of equations $A\boldsymbol{x}=\boldsymbol{b}$, quantum linear system solvers (QLSSs) approximately prepare a quantum state $|\boldsymbol{x}\rangle$ for which the amplitudes are proportional to the solution vector $\boldsymbol{x}$. Asymptotically optimal QLSSs have query complexity $O(κ\log(1/\varepsilon))$, where $κ$ is the condition number of $A$, and $\varepsilon$ is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm $\lVert\boldsymbol{x}\rVert$ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is $(1+O(\varepsilon))κ\ln(2\sqrt{2}/\varepsilon)$. If the norm is unknown, our method allows it to be estimated up to a constant factor using $O(\log\log(κ))$ applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal $O(κ\log\log(κ)\log\log\log(κ)+κ\log(1/\varepsilon))$ total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(κ)$ complexity can be achieved for norm estimation, yielding an optimal QLSS with $O(κ\log(1/\varepsilon))$ complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of $56κ+1.05κ\ln(1/\varepsilon)+o(κ)$ for the complexity of our optimal QLSS.

arXiv:2406.12086•Jun 17, 2024•69 citations

Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity

Yin Yang, Yue Yu, Long Zhang

Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity $\mathcal{O}(κ_A\log\frac1\varepsilon)$ without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.

quant-pharXiv:2609.19676•Sep 18, 2026•2 citations

Alternative adiabatic quantum algorithms with algorithmic applications

Cunningham, Joseph

Adiabatic Quantum Computing (AQC) is a powerful framework for designing quantum algorithms, yet its practical implementation is often hampered by the difficulty of engineering precise, continuous time-dependent Hamiltonians or the substantial computational overhead of time discretisation. This thesis develops alternative adiabatic frameworks based on dissipative and stochastic quantum evolution to circumvent these challenges.The core methodology introduces novel dynamics where discrete quantum operations, such as time-independent Hamiltonian evolution with Poisson-distributed phase randomisation or randomised unitary applications (qubitization), replace continuous evolution. This stochastic approach allows the system’s average behaviour to be rigorously analysed using new, generalised adiabatic theorems, including the development of novel quantitative bounds for unbounded Hamiltonians and specialised dissipative generators.Algorithmically, this work demonstrates that these discrete, stochastic procedures can achieve the optimal asymptotic time complexity of continuous AQC while mitigating discretisation costs. Specifically, adapted-schedule implementations are shown to yield optimal scaling for the Quantum Linear Systems Problem (QLSP), achieving complexity proportional to the condition number $O(\kappa)$, and $O(\sqrt{N/M})$ scaling for unstructured search. By establishing highly efficient, implementable alternatives to continuous AQC, this research offers a significant pathway toward robust and scalable quantum computation. The study also investigates the general family of diagonal Hamiltonians for optimisation problems, revealing that finding the optimal scheduling required for peak performance is, in general, an NP-hard problem.

•Oct 17, 2025•0 citations

Quantum Algorithms and Complexity for Numerical Problems

Zhang, Chi

Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.

•Jan 1, 2011•0 citations
We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state ∣x⟩|x⟩∣x⟩ that is proportional to the solution of the system of linear equations Ax\ensuremath→=b\ensuremath→A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}Ax\ensuremath→=b\ensuremath→​. The time complexities of our algorithms are O(\ensuremathκ2log(\ensuremathκ)/\ensuremathϵ)O\mathbf{(}{\ensuremath{\kappa}}^{2}\mathrm{log}(\ensuremath{\kappa})/\ensuremath{\epsilon}\mathbf{)}O(\ensuremathκ2log(\ensuremathκ)/\ensuremathϵ) and O(\ensuremathκlog(\ensuremathκ)/\ensuremathϵ)O\mathbf{(}\ensuremath{\kappa}\mathrm{log}(\ensuremath{\kappa})/\ensuremath{\epsilon}\mathbf{)}O(\ensuremathκlog(\ensuremathκ)/\ensuremathϵ), where \ensuremathκ\ensuremath{\kappa}\ensuremathκ is the condition number of AAA and \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of AAA, the projector onto the initial state ∣b⟩|b⟩∣b⟩, and single-qubit Pauli operators. The algorithms are conceptually simple and easy to implement. They are not obtained from equivalences between the gate model and adiabatic quantum computing. They do not use phase estimation or variable-time amplitude amplification, and do not require large ancillary systems. We discuss a gate-based implementation via Hamiltonian simulation and prove that our second algorithm is almost optimal in terms of \ensuremathκ\ensuremath{\kappa}\ensuremathκ. Like previous methods, our techniques yield an exponential quantum speed-up under some assumptions. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms.
Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian.Such approaches have enabled near-linear scaling in the condition number κ of the linear system, without requiring a complicated variable-time amplitude amplification procedure.However, the most efficient of those procedures is still asymptotically suboptimal by a factor of log(κ).Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete-time evolutions.In combination with the qubitized quantum walk, our discrete adiabatic theorem gives a speed-up for all adiabatic algorithms.Here, we use this combination to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in κ, matching a known lower bound on the complexity.Our O[κ log(1/ )] complexity is also optimal in terms of the combined scaling in κ and the precision .Compared to existing suboptimal methods, our algorithm is simpler and easier to implement.Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific 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.
Given a linear system of equations Ax=bA\boldsymbol{x}=\boldsymbol{b}Ax=b, quantum linear system solvers (QLSSs) approximately prepare a quantum state ∣x⟩|\boldsymbol{x}\rangle∣x⟩ for which the amplitudes are proportional to the solution vector x\boldsymbol{x}x. Asymptotically optimal QLSSs have query complexity O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)), where κκκ is the condition number of AAA, and ε\varepsilonε is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm ∥x∥\lVert\boldsymbol{x}\rVert∥x∥ is known exactly, our QLSS requires only a single application of kernel reflection (a straightforward extension of the eigenstate filtering (EF) technique of previous work) and the query complexity of the QLSS is (1+O(ε))κln⁡(22/ε)(1+O(\varepsilon))κ\ln(2\sqrt{2}/\varepsilon)(1+O(ε))κln(22​/ε). If the norm is unknown, our method allows it to be estimated up to a constant factor using O(log⁡log⁡(κ))O(\log\log(κ))O(loglog(κ)) applications of kernel projection (a direct generalization of EF) yielding a straightforward QLSS with near-optimal O(κlog⁡log⁡(κ)log⁡log⁡log⁡(κ)+κlog⁡(1/ε))O(κ\log\log(κ)\log\log\log(κ)+κ\log(1/\varepsilon))O(κloglog(κ)logloglog(κ)+κlog(1/ε)) total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that O(κ)O(κ)O(κ) complexity can be achieved for norm estimation, yielding an optimal QLSS with O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)) complexity while still avoiding the need to invoke the adiabatic theorem. Finally, we compute an explicit upper bound of 56κ+1.05κln⁡(1/ε)+o(κ)56κ+1.05κ\ln(1/\varepsilon)+o(κ)56κ+1.05κln(1/ε)+o(κ) for the complexity of our optimal QLSS.
Quantum linear systems algorithms (QLSAs) aim to solve linear systems $A\bb{x}=\bb{b}$ exponentially faster than classical methods under certain conditions. In this work, we develop quantum algorithms for solving linear algebraic equations from an ODE-based perspective. Inspired by the linear combination of Hamiltonian simulation (LCHS) representation in the Fourier approach \cite{Childs2017QLSA}, we express the solution $\bb{x}$ as a linear combination of solutions to a system of linear convection equations, which become Schrödinger-type equations with unitary evolutions in the Fourier domain. We refer to this representation as LC-Schrödingerization. Based on this result, we construct an LCHS-based quantum algorithm with two LCHS instances: one for time-marching and one for numerical integration. The key construction uses the derivative of a Gaussian-smoothed hat function and recovers the solution over a fixed auxiliary interval. This permits a truncation time independent of the target accuracy and avoids the loss in success probability from selecting a single grid point. Periodization and explicit Fourier coefficients provide the corresponding projection error bounds. Under the stated oracle assumptions and given a constant-factor estimate of the solution norm, direct simulation of the select operators and block preconditioning achieve the optimal matrix-query complexity O(κAlog⁡1ε)\mathcal{O}(κ_A\log\frac1\varepsilon)O(κA​logε1​) without using variable-time amplitude amplification (VTAA). The same upper bound holds for queries to the right-hand-side preparation oracle.
Adiabatic Quantum Computing (AQC) is a powerful framework for designing quantum algorithms, yet its practical implementation is often hampered by the difficulty of engineering precise, continuous time-dependent Hamiltonians or the substantial computational overhead of time discretisation. This thesis develops alternative adiabatic frameworks based on dissipative and stochastic quantum evolution to circumvent these challenges.The core methodology introduces novel dynamics where discrete quantum operations, such as time-independent Hamiltonian evolution with Poisson-distributed phase randomisation or randomised unitary applications (qubitization), replace continuous evolution. This stochastic approach allows the system’s average behaviour to be rigorously analysed using new, generalised adiabatic theorems, including the development of novel quantitative bounds for unbounded Hamiltonians and specialised dissipative generators.Algorithmically, this work demonstrates that these discrete, stochastic procedures can achieve the optimal asymptotic time complexity of continuous AQC while mitigating discretisation costs. Specifically, adapted-schedule implementations are shown to yield optimal scaling for the Quantum Linear Systems Problem (QLSP), achieving complexity proportional to the condition number O(κ)O(\kappa)O(κ), and O(N/M)O(\sqrt{N/M})O(N/M​) scaling for unstructured search. By establishing highly efficient, implementable alternatives to continuous AQC, this research offers a significant pathway toward robust and scalable quantum computation. The study also investigates the general family of diagonal Hamiltonians for optimisation problems, revealing that finding the optimal scheduling required for peak performance is, in general, an NP-hard problem.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.