Qubit-Efficient Quantum Algorithm for Linear Differential Equations

• URL: http://arxiv.org/abs/2507.16995v1
• Date: Tue, 22 Jul 2025 20:08:34 GMT
• Title: Qubit-Efficient Quantum Algorithm for Linear Differential Equations
• Authors: Di Fang, David Lloyd George, Yu Tong,
• Abstract summary: We propose a quantum algorithm for solving linear ordinary differential equations (ODEs) with a provable runtime guarantee.<n>Our algorithm uses only a single ancilla qubit, and is locality preserving, i.e., when the coefficient matrix of the ODE is $k$-local.<n>We also discuss the connection between our proposed algorithm and Lindbladian simulation as well as its application to the interacting Hatano-Nelson model.
• Score: 0.6410191755165466
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As quantum hardware rapidly advances toward the early fault-tolerant era, a key challenge is to develop quantum algorithms that are not only theoretically sound but also hardware-friendly on near-term devices. In this work, we propose a quantum algorithm for solving linear ordinary differential equations (ODEs) with a provable runtime guarantee. Our algorithm uses only a single ancilla qubit, and is locality preserving, i.e., when the coefficient matrix of the ODE is $k$-local, the algorithm only needs to implement the time evolution of $(k+1)$-local Hamiltonians. We also discuss the connection between our proposed algorithm and Lindbladian simulation as well as its application to the interacting Hatano-Nelson model, a widely studied non-Hermitian model with rich phenomenology.

Related papers

• Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations [0.46664938579243576]
  We prove constant factor bounds for a promising new quantum differential equation solver, the linear combination of Hamiltonian simulation algorithm.<n>Our new formulae improve over previous state of the art by at least two orders of magnitude, where the speedup can be far greater if state preparation has a significant cost.
  arXiv  Detail & Related papers  (2025-06-25T18:50:44Z)
• Explicit near-optimal quantum algorithm for solving the advection-diffusion equation [0.0]
  An explicit quantum algorithm is proposed for modeling dissipative initial-value problems.<n>We propose a quantum circuit based on a simple coordinate transformation that turns the dependence on the summation index into a trigonometric function.<n>The proposed algorithm can be used for modeling a wide class of nonunitary initial-value problems.
  arXiv  Detail & Related papers  (2025-01-19T19:03:29Z)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations.<n>The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.<n>The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians [11.53984890996377]
  We propose a new quantum algorithm for ODEs by harnessing open quantum systems. We use the natural non-unitary dynamics of Lindbladians with the aid of a new technique called the non-diagonal density matrix encoding. Our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters.
  arXiv  Detail & Related papers  (2024-10-25T15:27:41Z)
• Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
  We present a quantum algorithm for a non-linear differential equation of the form $fracd|urangledt.<n>We also introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case.
  arXiv  Detail & Related papers  (2024-07-10T14:08:58Z)
• Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL [0.562479170374811]
  We adapt a well-known algorithm for linear systems of equations, originally proposed by Harrow, Hassidim and Lloyd (HHL), by adapting it into a predictor-corrector instead of a direct solver. This strategy enables the intelligent omission of computationally costly steps commonly found in many classical algorithms, while simultaneously mitigating the notorious readout problems associated with extracting a quantum state. The versatility of the approach is illustrated through applications in various fields such as smoothed particle hydrodynamics, plasma simulations, and reactive flow configurations.
  arXiv  Detail & Related papers  (2024-06-28T15:31:10Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.