Showing 1–46 of 46 results for author: An, D

Quantum simulation of slow analytic time-dependent Hamiltonians

Authors: Chenhao Zhao, Yinan Li, Dong An

Abstract: We develop a quantum algorithm for slow analytic Hamiltonians $\widetilde H(t)=H(t/T)$ with $\|H(s)\|\leqα$ that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of $H(s)$, together with Fourier component decay and truncation bounds that enable an efficient finite-dimensional simulation. Combined with Floquet embedding… ▽ More We develop a quantum algorithm for slow analytic Hamiltonians $\widetilde H(t)=H(t/T)$ with $\|H(s)\|\leqα$ that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of $H(s)$, together with Fourier component decay and truncation bounds that enable an efficient finite-dimensional simulation. Combined with Floquet embedding and optimal time-independent Hamiltonian simulation technique, this gives query complexity $\widetilde{\mathcal O}\!\left(αT+\log(1/\varepsilon)\right)$ and additional gate complexity $\widetilde{\mathcal O}\!\left((αT+\log(1/\varepsilon))^2\log(1/\varepsilon)\right)$, assuming coherent access to $H'(s)$ and endpoint derivatives. For slow analytic control Hamiltonians, only block encodings of the time-independent control operators are required, with the same query complexity and lower gate overhead. Our method also extends to Gevrey Hamiltonians and improves the precision dependence for simulating slow analytic semi-dissipative linear differential equations. △ Less

Submitted 18 August, 2026; originally announced August 2026.

Fast Nondestructive Readout for High-Clock-Rate Atom Array Quantum Processor

Authors: Xu-Zhao-Qiu Zeng, Chang You, Qing-Wei Wang, Zi-Feng Li, Yi Ji, Dong An, Chao Yu, Jia-Rui Liu, Zi-Mo He, Jia-Rui Gu, Yuhao Mei, Hao-Wen Cheng, Yu-Chen Zhang, Rui Lin, Zhan Wu, Jun Rui, Jun Zhang, Ming-Cheng Chen, Yu-Hao Deng, Chao-Yang Lu, Jian-Wei Pan

Abstract: Neutral-atom arrays have rapidly advanced to support thousands of qubits and execute high-fidelity logical operations. However, these processors remain severely throttled by their slowest fundamental operation: nondestructive qubit measurement, which requires milliseconds and fundamentally limits the system's clock rate. This bottleneck arises from both an inherent photon-budget dilemma---sufficie… ▽ More Neutral-atom arrays have rapidly advanced to support thousands of qubits and execute high-fidelity logical operations. However, these processors remain severely throttled by their slowest fundamental operation: nondestructive qubit measurement, which requires milliseconds and fundamentally limits the system's clock rate. This bottleneck arises from both an inherent photon-budget dilemma---sufficient fluorescence for reliable state discrimination must be collected without excessive heating or loss---and frame-based imaging, which imposes one common exposure and decision latency on intrinsically independent, site-local measurements. Here, we overcome these limitations with a fast, nondestructive readout architecture based on real-time, site-resolved adaptive protection. By integrating continuous photon counting with a dynamic feedforward framework, we decode qubit states with sub-microsecond latency and instantly shield atoms from redundant scattering. Demonstrated in parallel across a 100-qubit reconfigurable atom array, with adaptive protection on a 25-site subarray, this dynamic decision protocol reduces the average probe time to just $15\ μ\text{s}$. Model-free benchmarking yields a discrimination infidelity of $4.1 \times 10^{-5}$ and an atom loss of $2.1 \times 10^{-4}$, simultaneously setting new performance records for atom arrays. Exploiting this capability, we operate repeated quantum circuits at an unprecedented 1.7 kHz clock rate with atoms reused over 120 consecutive rounds---nearly sevenfold higher than the previous record---and enter the sub-millisecond cycle regime for the first time. By removing nondestructive readout as the dominant cycle-time bottleneck, this work unlocks high-clock-rate mid-circuit syndrome extraction, paving the way for high-throughput, fault-tolerant quantum computation. △ Less

Submitted 17 August, 2026; originally announced August 2026.

Quantum simulation of real-world nonlinear dynamics via Koopman method

Authors: Baoyang Zhang, Dong An, Zhaoyuan Meng, Yefei Yu, Xiaoxiao Xiao, Zhen Lu, Yue Yang

Abstract: Nonlinear dynamics is ubiquitous in nature, ranging from chemical pattern formation to ocean circulation, yet its simulation on quantum computers is fundamentally limited by the unitary nature of quantum evolution. We propose the quantum Koopman method, a data-driven framework that embeds nonlinear dynamics into a learned linear representation and implements the resulting evolution using shallow q… ▽ More Nonlinear dynamics is ubiquitous in nature, ranging from chemical pattern formation to ocean circulation, yet its simulation on quantum computers is fundamentally limited by the unitary nature of quantum evolution. We propose the quantum Koopman method, a data-driven framework that embeds nonlinear dynamics into a learned linear representation and implements the resulting evolution using shallow quantum circuits. This method learns Koopman observables from trajectory data, projects the lifted dynamics onto a finite-dimensional subspace, and decomposes the corresponding non-unitary propagator into parallel spectral channels. We utilize the Koopman method on a superconducting processor to simulate three distinct nonlinear systems, comprising reaction-diffusion dynamics, fluid motion on a sphere, and satellite-derived observations of Gulf Stream currents, employing up to 32 parallel circuits of 10 qubits. These quantum simulations capture the dominant multiscale patterns and statistical signatures of the underlying dynamics, and reveal a transition from performance limited by hardware noise in weakly nonlinear systems to performance limited by finite-dimensional Koopman representations as nonlinear scale interactions increase. This transition identifies a practical boundary for quantum-amenable nonlinear dynamics, establishing a hardware-validated route for simulating moderately nonlinear dynamics on near-term quantum hardware. △ Less

Submitted 8 July, 2026; originally announced July 2026.

Consistent Evaluation of Operators Involving the Position Operator in the Bloch Representation: Application to the Orbital Moment

Authors: Daehyeon An, Junmo Jeon, Se Kwon Kim

Abstract: The position operator plays a central role in condensed-matter observables such as velocity, orbital moment, and electric polarization. In solid-state physics, the evaluation of operators incorporating the position operator has not reached a consensus, as observed in the operator-level discrepancy between the local circulation of Wannier functions and the self-rotation of wave packets. Here, to ac… ▽ More The position operator plays a central role in condensed-matter observables such as velocity, orbital moment, and electric polarization. In solid-state physics, the evaluation of operators incorporating the position operator has not reached a consensus, as observed in the operator-level discrepancy between the local circulation of Wannier functions and the self-rotation of wave packets. Here, to achieve a consistent evaluation of such operators, we propose three rules for evaluating operators involving the position operator in the Bloch representation. The rules are devised to satisfy physical conditions: independence from the choice of unit cell, preservation of Hermitian conjugacy for the product of operators, and recovery of the correct intraband velocity. We further address the gauge dependence of the position operator and introduce a scheme termed gauge filtration, which systematically removes gauge-dependent contributions from the operators containing the position operator. This methodology ensures that the quantities obtained from the operator evaluation correspond to observable physical phenomena. By applying our framework, we reconcile the results concerning the self-rotation of the wave packet and the local circulation of the Wannier function. We expect our proposal to establish a consistent framework for evaluating operators involving the position operator. △ Less

Submitted 10 June, 2026; originally announced June 2026.

Linear Combination of Hamiltonian Simulation with Commutator Scaling

Authors: Junaid Aftab, Dong An, Konstantina Trivisa

Abstract: The Linear Combination of Hamiltonian Simulation (LCHS) framework simulates dissipative linear dynamics by representing time evolution as an integral over unitary operators, which is discretized by quadrature and implemented via Hamiltonian simulation. While existing analyses achieve near-optimal scaling in time and precision using norm-based quantities of the dissipative generator, we show that i… ▽ More The Linear Combination of Hamiltonian Simulation (LCHS) framework simulates dissipative linear dynamics by representing time evolution as an integral over unitary operators, which is discretized by quadrature and implemented via Hamiltonian simulation. While existing analyses achieve near-optimal scaling in time and precision using norm-based quantities of the dissipative generator, we show that implementing the Hamiltonian simulation steps with Multi-Product Formulas (MPFs) yields commutator-sensitive error and complexity bounds. We demonstrate that the quadrature rule affects not only discretization error but also commutator structure and query complexity. This dependence is quantified through post-quadrature analysis for abstract MPF error profiles and for general time-independent and local Hamiltonians using known commutator-sensitive MPF error estimates. We compare uniform trapezoidal and free-scale sinh--sinh quadrature, showing improved quadrature-cardinality scaling for the latter, and illustrate the framework with applications to fractional diffusion, advection--diffusion, and open quantum systems. △ Less

Submitted 9 June, 2026; originally announced June 2026.

Comments: 45+15 pages. Comments are welcome

Pauli-structured preconditioning for quantum linear system solvers

Authors: Hantao Nie, Zhijian Lai, Dong An

Abstract: Preconditioning is a fundamental technique for accelerating classical linear system solvers, and understanding when its benefits persist in quantum linear system (QLS) solvers is important for assessing the practical resource requirements of quantum linear algebra. In QLS algorithms, however, the potential advantage of preconditioning may be offset by the normalization overhead incurred by composi… ▽ More Preconditioning is a fundamental technique for accelerating classical linear system solvers, and understanding when its benefits persist in quantum linear system (QLS) solvers is important for assessing the practical resource requirements of quantum linear algebra. In QLS algorithms, however, the potential advantage of preconditioning may be offset by the normalization overhead incurred by composing separate block-encodings of the system matrix and the preconditioner, as observed in recent work. This limitation leaves open whether additional algebraic structure can make preconditioning effective in quantum access models. Motivated by this question, we show that Pauli-structured representations of both the system matrix and the preconditioner allow the preconditioned operator to be accessed through regrouped Pauli expansions. In this setting, algebraic regrouping of Pauli products can reduce the Pauli coefficient weight of the preconditioned operator, thereby altering the normalization parameters relevant to quantum algorithms. We derive explicit size and coefficient-weight bounds for the regrouped Pauli representations, and we trace their consequences for both direct block-encoding constructions and randomized Pauli linear system solvers. These results identify when Pauli-structured preconditioning can reduce the effective complexity parameters of QLS algorithms, rather than merely improving the classical condition number. Numerical experiments on a finite-dimensional synthetic benchmark show reductions in norm-aware direct block-encoding diagnostics and in the randomized QLS per-sample depth proxy. △ Less

Submitted 1 June, 2026; originally announced June 2026.

Comments: 15 pages

MSC Class: 81P68; 68Q12; 65F08 ACM Class: F.1.2; F.2.1; G.1.3

Constant Factor Analysis of Optimal Quantum Linear Solvers in Practice

Authors: Pedro C. S. Costa, Alexander M. Dalzell, Dong An, Dominic W. Berry

Abstract: Optimal quantum linear equation solvers provide complexity $O(κ\log(1/ε))$, where $κ$ is the condition number and $ε$ is the allowable error. The optimal solver using a discrete adiabatic approach [PRX Quantum 3, 040303 (2022)] has large analytically proven constant factors for the upper bound on the complexity. The constant factors were later found to be about 1,200 times smaller in numerical tes… ▽ More Optimal quantum linear equation solvers provide complexity $O(κ\log(1/ε))$, where $κ$ is the condition number and $ε$ is the allowable error. The optimal solver using a discrete adiabatic approach [PRX Quantum 3, 040303 (2022)] has large analytically proven constant factors for the upper bound on the complexity. The constant factors were later found to be about 1,200 times smaller in numerical testing [Quantum 9, 1887 (2025)]. This meant it is about an order of magnitude more efficient than using a randomised approach from [PRX Quantum 6, 040373 (2025)], which has far smaller analytically proven constant factors. Recently, a ``Shortcut'' method has been found to provide an optimal solver which also has small proven constant factors. In the present work, we conduct a comprehensive numerical analysis comparing this method with the adiabatic solver for two families of random linear systems. We find that, in the case where the solution norm is unknown, the adiabatic solver provides slightly better performance. If the solution norm is known, then the shortcut method provides significantly better performance for non-Hermitian matrices. △ Less

Submitted 27 April, 2026; v1 submitted 23 April, 2026; originally announced April 2026.

Comments: 20 pages, 24 figures

Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search

Authors: Zhijian Lai, Dong An, Jiang Hu, Zaiwen Wen

Abstract: Grover's algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems of size $N$. Recent studies have reformulated this task as a maximization problem on the unitary manifold and solved it via linearly convergent Riemannian gradient ascent (RGA) methods, resulting in a complexity of $O(\sqrt{N/M}\log (1/\varepsilon))$, where $M$ denotes the numbe… ▽ More Grover's algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems of size $N$. Recent studies have reformulated this task as a maximization problem on the unitary manifold and solved it via linearly convergent Riemannian gradient ascent (RGA) methods, resulting in a complexity of $O(\sqrt{N/M}\log (1/\varepsilon))$, where $M$ denotes the number of target items and $\varepsilon$ denotes the success probability error. In this work, we adopt the Riemannian modified Newton (RMN) method to solve the quantum search problem, under the assumption that the ratio $ M/N$ is known. We show that, in this setting, the Riemannian Newton direction is collinear with the Riemannian gradient in the sense that the Riemannian gradient is always an eigenvector of the corresponding Riemannian Hessian. This structure removes the overhead of Hessian inversion and allows the proposed RMN method to retain the local quadratic convergence in terms of the error $\varepsilon$. More precisely, we rigorously prove an overall complexity of $O(\sqrt{N/M}+\log\log(1/\varepsilon))$. Furthermore, our approach remains Grover-compatible, namely, it relies exclusively on the standard Grover diffusion and oracle operators to ensure algorithmic implementability, and its parameter update process can be efficiently precomputed on classical computers. △ Less

Submitted 15 June, 2026; v1 submitted 26 March, 2026; originally announced March 2026.

MSC Class: 81P68; 90C26; 65K10 ACM Class: F.2.2; G.1.6

Efficient Quantum Simulation for Nonlinear Stochastic Differential Equations

Authors: Xiangyu Li, Ahmet Burak Catli, Ho Kiat Lim, Matthew Pocrnic, Dong An, Jin-Peng Liu, Nathan Wiebe

Abstract: Nonlinear stochastic differential equations (NSDEs) are a pillar of mathematical modeling for scientific and engineering applications. Accurate and efficient simulation of large-scale NSDEs is prohibitive on classical computers due to the large number of degrees of freedom, and it is challenging on quantum computers due to the linear and unitary nature of quantum mechanics. We develop a quantum al… ▽ More Nonlinear stochastic differential equations (NSDEs) are a pillar of mathematical modeling for scientific and engineering applications. Accurate and efficient simulation of large-scale NSDEs is prohibitive on classical computers due to the large number of degrees of freedom, and it is challenging on quantum computers due to the linear and unitary nature of quantum mechanics. We develop a quantum algorithm to tackle nonlinear differential equations driven by the Ornstein-Uhlenbeck (OU) stochastic process. The query complexity of our algorithm scales logarithmically with the error tolerance and nearly quadratically with the simulation time. Our algorithmic framework comprises probabilistic Carleman linearization (PCL) to tackle nonlinearity coupled with stochasticity, and stochastic linear combination of Hamiltonian simulations (SLCHS) to simulate stochastic non-unitary dynamics. We obtain probabilistic exponential convergence for the Carleman linearization of Liu et al. [1], provided the NSDE is stable and reaches a steady state. We extend deterministic LCHS to stochastic linear differential equations, retaining near-optimal parameter scaling from An et al. [2] except for the nearly quadratic time scaling. This is achieved by using Monte Carlo integration for time discretization of both the stochastic inhomogeneous term in LCHS and the truncated Dyson series for each Hamiltonian simulation. △ Less

Submitted 12 March, 2026; originally announced March 2026.

Comments: 70 pages

Quantum circuit design from a retraction-based Riemannian optimization framework

Authors: Zhijian Lai, Hantao Nie, Jiayuan Wu, Dong An

Abstract: Designing quantum circuits for ground state preparation is a fundamental task in quantum information science. However, standard Variational Quantum Algorithms (VQAs) are often constrained by limited ansatz expressivity and difficult optimization landscapes. To address these issues, we adopt a geometric perspective, formulating the problem as the minimization of an energy cost function directly ove… ▽ More Designing quantum circuits for ground state preparation is a fundamental task in quantum information science. However, standard Variational Quantum Algorithms (VQAs) are often constrained by limited ansatz expressivity and difficult optimization landscapes. To address these issues, we adopt a geometric perspective, formulating the problem as the minimization of an energy cost function directly over the unitary group. We establish a retraction-based Riemannian optimization framework for this setting, ensuring that all algorithmic procedures are implementable on quantum hardware. Within this framework, we unify existing randomized gradient approaches under a Riemannian Random Subspace Gradient Projection (RRSGP) method. While recent geometric approaches have predominantly focused on such first-order gradient descent techniques, efficient second-order methods remain unexplored. To bridge this gap, we derive explicit expressions for the Riemannian Hessian and show that it can be estimated directly on quantum hardware via parameter-shift rules. Building on this, we propose the Riemannian Random Subspace Newton (RRSN) method, a scalable second-order algorithm that constructs a Newton system from measurement data. Numerical simulations indicate that RRSN achieves quadratic convergence, yielding high-precision ground states in significantly fewer iterations compared to both existing first-order approaches and standard VQA baselines. Ultimately, this work provides a systematic foundation for applying a broader class of efficient Riemannian algorithms to quantum circuit design. △ Less

Submitted 24 February, 2026; originally announced February 2026.

Comments: 28 pages

MSC Class: 81P68; 90C26; 65K10

Ensemble-Based Quantum Signal Processing for Error Mitigation

Authors: Suying Liu, Yulong Dong, Dong An, Murphy Yuezhen Niu

Abstract: Despite rapid advances in quantum hardware, noise remains a central obstacle to deploying quantum algorithms on near-term devices. In particular, random coherent errors that accumulate during circuit execution constitute a dominant and fundamentally challenging noise source. We introduce a noise-resilient framework for Quantum Signal Processing (QSP) that mitigates such coherent errors without inc… ▽ More Despite rapid advances in quantum hardware, noise remains a central obstacle to deploying quantum algorithms on near-term devices. In particular, random coherent errors that accumulate during circuit execution constitute a dominant and fundamentally challenging noise source. We introduce a noise-resilient framework for Quantum Signal Processing (QSP) that mitigates such coherent errors without increasing circuit depth or ancillary qubit requirements. Our approach uses ensembles of noisy QSP circuits combined with measurement-level averaging to suppress random phase errors in Z rotations. Building on this framework, we develop robust QSP algorithms for implementing polynomial functions of Hermitian matrices and for estimating observables, with applications to Hamiltonian simulation, quantum linear systems, and ground-state preparation. We analyze the trade-off between approximation error and hardware noise, which is essential for practical implementation under the stringent depth and coherence constraints of current quantum hardware. Our results establish a practical pathway for integrating error mitigation seamlessly into algorithmic design, advancing the development of robust quantum computing, and enabling the discovery of scientific applications with near- and mid-term quantum devices. △ Less

Submitted 27 January, 2026; originally announced January 2026.

Comments: 8+14 pages

Contour-integral based quantum eigenvalue transformation: analysis and applications

Authors: Shan Jiang, Dong An

Abstract: Eigenvalue transformations appear ubiquitously in scientific computation, ranging from matrix polynomials to differential equations, and are beyond the reach of the quantum singular value transformation framework. In this work, we study the efficiency of quantum algorithms based on contour integral representation for eigenvalue transformations from both theoretical and practical aspects. Theoretic… ▽ More Eigenvalue transformations appear ubiquitously in scientific computation, ranging from matrix polynomials to differential equations, and are beyond the reach of the quantum singular value transformation framework. In this work, we study the efficiency of quantum algorithms based on contour integral representation for eigenvalue transformations from both theoretical and practical aspects. Theoretically, we establish a complete complexity analysis of the contour integral approach proposed in [Takahira, Ohashi, Sogabe, and Usuda. Quant. Inf. Comput., 22, 11\&12, 965--979 (2021)]. Moreover, we combine the contour integral approach and the sampling-based linear combination of unitaries to propose a quantum algorithm for estimating observables of eigenvalue transformations using only $3$ additional qubits. Practically, we design contour integral based quantum algorithms for Hamiltonian simulation, matrix polynomials, and solving linear ordinary differential equations, and show that the contour integral algorithm can outperform all the existing quantum algorithms in the case of solving asymptotically stable differential equations. △ Less

Submitted 25 January, 2026; v1 submitted 17 January, 2026; originally announced January 2026.

Comments: 31 pages including appendix, fixed some statement

Improved gap dependence in adiabatic state preparation by adaptive schedule

Authors: Xi Guo, Dong An

Abstract: Adiabatic quantum computing is a powerful framework for state preparation, while its evolution time often scales quadratically in the inverse Hamiltonian spectral gap, leading to sub-optimal computational complexity. In this work, we introduce a nonlinear adaptive strategy for finding the time scheduling function, and show that the gap dependence can be quadratically improved to be inverse linear… ▽ More Adiabatic quantum computing is a powerful framework for state preparation, while its evolution time often scales quadratically in the inverse Hamiltonian spectral gap, leading to sub-optimal computational complexity. In this work, we introduce a nonlinear adaptive strategy for finding the time scheduling function, and show that the gap dependence can be quadratically improved to be inverse linear for a wide range of systems under a mild gap measure condition. Through variational analysis, we further demonstrate the optimality of our schedule for systems with linear gap and the partial optimality for general systems, while we also rigorously show that the commonly used linear schedule is never optimal. △ Less

Submitted 12 December, 2025; v1 submitted 11 December, 2025; originally announced December 2025.

A Grover-compatible manifold optimization algorithm for quantum search

Authors: Zhijian Lai, Dong An, Jiang Hu, Zaiwen Wen

Abstract: Grover's algorithm is a fundamental quantum algorithm that offers a quadratic speedup for the unstructured search problem by alternately applying physically implementable oracle and diffusion operators. In this paper, we reformulate the unstructured search as a maximization problem on the unitary manifold and solve it via the Riemannian gradient ascent (RGA) method. To overcome the difficulty that… ▽ More Grover's algorithm is a fundamental quantum algorithm that offers a quadratic speedup for the unstructured search problem by alternately applying physically implementable oracle and diffusion operators. In this paper, we reformulate the unstructured search as a maximization problem on the unitary manifold and solve it via the Riemannian gradient ascent (RGA) method. To overcome the difficulty that generic RGA updates do not, in general, correspond to physically implementable quantum operators, we introduce Grover-compatible retractions to restrict RGA updates to valid oracle and diffusion operators. Theoretically, we establish a local Riemannian $μ$-Polyak-Łojasiewicz (PL) inequality with $μ= \tfrac{1}{2}$, which yields a linear convergence rate of $1 - κ^{-1}$ toward the global solution. Here, the condition number $κ= L_{\mathrm{Rie}} / μ$, where $L_{\mathrm{Rie}}$ denotes the Riemannian Lipschitz constant of the gradient. Taking into account both the geometry of the unitary manifold and the special structure of the cost function, we show that $L_{\mathrm{Rie}} = O(\sqrt{N})$ for problem size $N = 2^n$. Consequently, the resulting iteration complexity is $O(\sqrt{N} \log(1/\varepsilon))$ for attaining an $\varepsilon$-accurate solution, which matches the quadratic speedup of $O(\sqrt{N})$ achieved by Grover's algorithm. These results demonstrate that an optimization-based viewpoint can offer fresh conceptual insights and lead to new advances in the design of quantum algorithms. △ Less

Submitted 9 June, 2026; v1 submitted 9 December, 2025; originally announced December 2025.

Comments: Newly added supplementary materials

MSC Class: 81P68; 90C26; 65K10

Digital adiabatic evolution is universally accurate

Authors: Yangyu Lu, Yifei Huang, Dong An, Qi Zhao, Dingshun Lv, Xiao Yuan

Abstract: Adiabatic evolution is a central paradigm in quantum physics. Digital simulations of adiabatic processes are generally viewed as costly, since algorithmic errors typically accumulate over the long evolution time, requiring exceptionally deep circuits to maintain accuracy. This work demonstrates that digital adiabatic evolution is intrinsically accurate and robust to simulation errors. We analyze t… ▽ More Adiabatic evolution is a central paradigm in quantum physics. Digital simulations of adiabatic processes are generally viewed as costly, since algorithmic errors typically accumulate over the long evolution time, requiring exceptionally deep circuits to maintain accuracy. This work demonstrates that digital adiabatic evolution is intrinsically accurate and robust to simulation errors. We analyze two Hamiltonian simulation methods -- Trotterization and generalized quantum signal processing -- and prove that the simulation error does not increase with time. Numerical simulations of molecular systems and linear equations confirm the theory, revealing that digital adiabatic evolution is substantially more efficient than previously assumed. Remarkably, our estimation for the first-order Trotterization error can be 10^6 times tighter than previous analyses for the transverse field Ising model even with less than 6 qubits. The findings establish fundamental robustness of digital adiabatic evolution and provide a basis for accurate, efficient implementations on fault-tolerant -- and potentially near-term -- quantum platforms. △ Less

Submitted 14 October, 2025; originally announced October 2025.

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Authors: Hantao Nie, Dong An, Zaiwen Wen

Abstract: Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in… ▽ More Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an $ε$-optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs. △ Less

Submitted 28 June, 2026; v1 submitted 11 October, 2025; originally announced October 2025.

Comments: Accepted in Quantum; 31 pages, 1 figure

Journal ref: Quantum 10, 2154 (2026)

Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties

Authors: Zhong-Xia Shang, Dong An, Changpeng Shao

Abstract: Fast-forwarding refers to the ability to simulate a system of time $t$ using significantly fewer than $t$ queries or circuit depth. While various Hamiltonian systems are known to circumvent the no fast-forwarding theorem, analogous results for dissipative dynamics, governed by Lindbladians, remain largely unexplored. We first present a quantum algorithm for simulating purely dissipative Lindbladia… ▽ More Fast-forwarding refers to the ability to simulate a system of time $t$ using significantly fewer than $t$ queries or circuit depth. While various Hamiltonian systems are known to circumvent the no fast-forwarding theorem, analogous results for dissipative dynamics, governed by Lindbladians, remain largely unexplored. We first present a quantum algorithm for simulating purely dissipative Lindbladians with unitary jump operators, achieving additive query complexity $\mathcal{O}\left(t + \log(\varepsilon^{-1})\right)$ up to error~$\varepsilon$, improving previous algorithms. When the jump operators have certain structures (i.e., block-diagonal Paulis), the algorithm can be modified to achieve exponential fast-forwarding, attaining circuit depth $\mathcal{O}\left(\log\left(t + \log(\varepsilon^{-1})\right)\right)$, while preserving query complexity via parallel access. Using these fast-forwarding techniques, we develop a quantum algorithm for estimating Gibbs state properties of the form $\langle ψ_1 | e^{-β(H + I)} | ψ_2 \rangle$, up to additive error $ε$, with $H$ the Hamiltonian and $β$ the inverse temperature. For input states exhibiting certain coherence conditions -- e.g.,~$\langle 0|^{\otimes n} e^{-β(H + I)} |+\rangle^{\otimes n}$ -- our method achieves exponential improvement in complexity (measured by circuit depth), $\mathcal{O} (2^{-n/2} ε^{-1} \log β),$ compared to the quantum singular value transformation-based approach, with complexity $\tilde{\mathcal{O}} (ε^{-1} \sqrtβ )$. We show how to apply this exponential improvement to applications such as the ground state overlap testing and amplitude estimation. For general $| ψ_1 \rangle$ and $| ψ_2 \rangle$, we also show how the level of improvement is changed with the coherence resource in $| ψ_1 \rangle$ and $| ψ_2 \rangle$. △ Less

Submitted 22 May, 2026; v1 submitted 11 September, 2025; originally announced September 2025.

Comments: 39 pages

Journal ref: Reports on Progress in Physics, 2026

Large time-step discretisation of adiabatic quantum dynamics

Authors: Dong An, Pedro C. S. Costa, Dominic W. Berry

Abstract: Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time step sizes in time discretization can be much larger than expected, and… ▽ More Adiabatic quantum computing is a general framework for preparing eigenstates of Hamiltonians on quantum devices. However, its digital implementation requires an efficient Hamiltonian simulation subroutine, which may introduce extra computational overhead or complicated quantum control logic. In this work, we show that the time step sizes in time discretization can be much larger than expected, and the overall complexity is greatly reduced. Remarkably, regardless of the general convergence order of the numerical method, we can choose a uniform time step size independent of tolerated error and evolution time for sufficiently accurate simulation. Furthermore, with the boundary cancellation condition where the continuous diabatic errors are exponentially suppressed, we provide strong evidence on an exponential convergence of even first-order Trotter with uniform time step size. We apply our analysis to the example of adiabatic unstructured search and show several preferable features of the Trotterized adiabatic approach: it can match the Grover lower bound, it does not require a priori knowledge on the number of marked states, and its performance can be asymptotically comparable with that of the quantum approximate optimization algorithm. △ Less

Submitted 29 August, 2025; originally announced September 2025.

Comments: 48 pages, 5 figures

Fourier transform-based linear combination of Hamiltonian simulation

Authors: Xi Huang, Dong An

Abstract: Linear combination of Hamiltonian simulation (LCHS) connects the general linear non-unitary dynamics with unitary operators and serves as the mathematical backbone of designing near-optimal quantum linear differential equation algorithms. However, the existing LCHS formalism needs to find a kernel function subject to complicated technical conditions on a half complex plane. In this work, we establ… ▽ More Linear combination of Hamiltonian simulation (LCHS) connects the general linear non-unitary dynamics with unitary operators and serves as the mathematical backbone of designing near-optimal quantum linear differential equation algorithms. However, the existing LCHS formalism needs to find a kernel function subject to complicated technical conditions on a half complex plane. In this work, we establish an alternative formalism of LCHS based on the Fourier transform. Our new formalism completely removes the technical requirements beyond the real axis, providing a simple and flexible way of constructing LCHS kernel functions. Specifically, we construct a different family of the LCHS kernel function, providing a $1.81$ times reduction in the quantum differential equation algorithms based on LCHS, and an $8.27$ times reduction in its quantum circuit depth at a truncation error of $ε\le 10^{-8}$. Additionally, we extend the scope of the LCHS formula to the scenario of simulating linear unstable dynamics for a short or intermediate time period. △ Less

Submitted 27 August, 2025; originally announced August 2025.

Comments: 18 pages, 3 figures

Quantum Differential Equation Solvers with Low State Preparation Cost: Eliminating the Time Dependence in Dissipative Equations

Authors: Gengzhi Yang, Akwum Onwunta, Dong An

Abstract: Linear dissipative differential equation is a fundamental model for a large number of physical systems, such as quantum dynamics with non-Hermitian Hamiltonian, open quantum system dynamics, diffusion process and damped system. In this work, we propose efficient quantum algorithms for simulating linear dissipative differential equations. The key idea of our algorithms is to perform the simulation… ▽ More Linear dissipative differential equation is a fundamental model for a large number of physical systems, such as quantum dynamics with non-Hermitian Hamiltonian, open quantum system dynamics, diffusion process and damped system. In this work, we propose efficient quantum algorithms for simulating linear dissipative differential equations. The key idea of our algorithms is to perform the simulation only over an effective time period when the dynamics has not significantly dissipated yet, rather than over the entire physical evolution period. We conduct detailed analysis on the complexity of our algorithms and show that, while maintaining low state preparation cost, our algorithms can completely eliminate the time dependence. This is a more than exponential improvement compared to the previous state-of-the-art quantum algorithms. △ Less

Submitted 20 August, 2025; originally announced August 2025.

Extended parameter shift rules with minimal derivative variance for parameterized quantum circuits

Authors: Zhijian Lai, Jiang Hu, Dong An, Zaiwen Wen

Abstract: Parameter shift rules (PSRs) are useful methods for computing arbitrary-order derivatives of the cost function in parameterized quantum circuits. The basic idea of PSRs is to evaluate the cost function at different parameter shifts, then use specific coefficients to combine them linearly to obtain the exact derivatives. In this work, we propose an extended parameter shift rule (EPSR) which general… ▽ More Parameter shift rules (PSRs) are useful methods for computing arbitrary-order derivatives of the cost function in parameterized quantum circuits. The basic idea of PSRs is to evaluate the cost function at different parameter shifts, then use specific coefficients to combine them linearly to obtain the exact derivatives. In this work, we propose an extended parameter shift rule (EPSR) which generalizes a broad range of existing PSRs and has the following two advantages. First, EPSR offers an infinite number of possible parameter shifts, allowing the selection of the optimal parameter shifts to minimize the final derivative variance and thereby obtaining the more accurate derivative estimates with limited quantum resources. Second, EPSR extends the scope of the PSRs in the sense that EPSR can handle arbitrary Hermitian operator $H$ in gate $U(x) = \exp (iHx)$ in the parameterized quantum circuits, while existing PSRs are valid only for simple Hermitian generators $H$ such as simple Pauli words. Additionally, we show that the widely used ``general PSR'', introduced by Wierichs et al. (2022), is a special case of our EPSR, and we prove that it yields globally optimal shifts for minimizing the derivative variance under the weighted-shot scheme. Finally, through numerical simulations, we demonstrate the effectiveness of EPSR and show that the usage of the optimal parameter shifts indeed leads to more accurate derivative estimates. △ Less

Submitted 7 December, 2025; v1 submitted 12 August, 2025; originally announced August 2025.

Comments: 33 pages, 6 figures

Journal ref: Physical Review Applied 25, no. 1 (2026): 014005

Silicon single-photon detector achieving over 84% photon detection efficiency with flexible operation modes

Authors: Dong An, Chao Yu, Ming-Yang Zheng, Anran Guo, Junsong Wang, Ruizhi Li, Huaping Ma, Xiu-Ping Xie, Xiao-Hui Bao, Qiang Zhang, Jun Zhang, Jian-Wei Pan

Abstract: Silicon single-photon detectors (Si SPDs) play a crucial role in detecting single photons in the visible spectrum. For various applications, photon detection efficiency (PDE) is the most critical characteristic for effectively collecting photons. Here, we present a Si SPD with a remarkable PDE of up to 84.4% at 785 nm, supporting multiple operation modes. We design and fabricate a thick-junction S… ▽ More Silicon single-photon detectors (Si SPDs) play a crucial role in detecting single photons in the visible spectrum. For various applications, photon detection efficiency (PDE) is the most critical characteristic for effectively collecting photons. Here, we present a Si SPD with a remarkable PDE of up to 84.4% at 785 nm, supporting multiple operation modes. We design and fabricate a thick-junction Si single-photon avalanche diode (SPAD) that enhances the avalanche probability through a backside-illumination structure, while minimizing noise through the design of a doping-compensated avalanche region. To maximize PDE, we implement a readout circuit with a 50 V quenching voltage, enabling operation in free-running, gating, or hybrid modes. The SPAD, along with its readout circuits and affiliated circuits, is integrated into a compact SPD module. In free-running mode, the module achieves a maximum PDE of 84.4%, with a dark count rate of 260 cps, and an afterpulse probability of 2.9% at 268 K. This work provides a practical solution for applications requiring ultra-high-efficiency Si SPD with multiple operation modes. △ Less

Submitted 24 July, 2025; originally announced July 2025.

Comments: Accepted by IEEE Journal of Selected Topics in Quantum Electronics

Interpolation-based coordinate descent method for parameterized quantum circuits

Authors: Zhijian Lai, Jiang Hu, Taehee Ko, Jiayuan Wu, Dong An

Abstract: Parameterized quantum circuits (PQCs) are ubiquitous in the design of hybrid quantum-classical algorithms. In this work, we propose an interpolation-based coordinate descent (ICD) method to address the parameter optimization problem in PQCs. The ICD method provides a unified framework for existing structure optimization techniques such as Rotosolve, sequential minimal optimization, ExcitationSolve… ▽ More Parameterized quantum circuits (PQCs) are ubiquitous in the design of hybrid quantum-classical algorithms. In this work, we propose an interpolation-based coordinate descent (ICD) method to address the parameter optimization problem in PQCs. The ICD method provides a unified framework for existing structure optimization techniques such as Rotosolve, sequential minimal optimization, ExcitationSolve, and others. ICD employs interpolation to approximate the PQC cost function, effectively recovering its underlying trigonometric structure, and then performs an argmin update on a single parameter in each iteration. In contrast to previous studies on structure optimization, we determine the optimal interpolation nodes to mitigate statistical errors arising from quantum measurements. Moreover, in the common case of $r$ equidistant frequencies, we show that the optimal interpolation nodes are equidistant nodes with spacing $2π/(2r+1)$ (under constant variance assumption), and that our ICD method simultaneously minimizes the mean squared error, the condition number of the interpolation matrix, and the average variance of the approximated cost function. We perform numerical simulations and test on the MaxCut problem, the transverse field Ising model, and the XXZ model. Numerical results imply that our ICD method is more efficient than the commonly used gradient descent and random coordinate descent method. △ Less

Submitted 6 November, 2025; v1 submitted 6 March, 2025; originally announced March 2025.

Comments: 29+20 pages, 13 figures

Journal ref: Communications Physics (2026) Published 07 January 2026

Assessing Quantum and Classical Approaches to Combinatorial Optimization: Testing Quadratic Speed-ups for Heuristic Algorithms

Authors: Pedro C. S. Costa, Mauro E. S. Morales, Dong An, Yuval R. Sanders

Abstract: Many recent investigations conclude, based on asymptotic complexity analyses, that quantum computers could accelerate combinatorial optimization (CO) tasks relative to a purely classical computer. However, asymptotic analysis alone cannot support a credible claim of quantum advantage. Here, we highlight the challenges involved in benchmarking quantum and classical heuristics for combinatorial opti… ▽ More Many recent investigations conclude, based on asymptotic complexity analyses, that quantum computers could accelerate combinatorial optimization (CO) tasks relative to a purely classical computer. However, asymptotic analysis alone cannot support a credible claim of quantum advantage. Here, we highlight the challenges involved in benchmarking quantum and classical heuristics for combinatorial optimization (CO), with a focus on the Sherrington-Kirkpatrick problem. Whereas hope remains that a quadratic quantum advantage is possible,our numerical analysis casts doubt on the idea that current methods exhibit any quantum advantage at all. This doubt arises because even a simple classical approach can match with quantum methods we investigated. We conclude that more careful numerical investigations are needed to evaluate the potential for quantum advantage in CO, and we give some possible future directions for such investigations. △ Less

Submitted 17 December, 2024; originally announced December 2024.

Comments: 11 pages, 8 figures

Laplace transform based quantum eigenvalue transformation via linear combination of Hamiltonian simulation

Authors: Dong An, Andrew M. Childs, Lin Lin, Lexing Ying

Abstract: Eigenvalue transformations, which include solving time-dependent differential equations as a special case, have a wide range of applications in scientific and engineering computation. While quantum algorithms for singular value transformations are well studied, eigenvalue transformations are distinct, especially for non-normal matrices. We propose an efficient quantum algorithm for performing a cl… ▽ More Eigenvalue transformations, which include solving time-dependent differential equations as a special case, have a wide range of applications in scientific and engineering computation. While quantum algorithms for singular value transformations are well studied, eigenvalue transformations are distinct, especially for non-normal matrices. We propose an efficient quantum algorithm for performing a class of eigenvalue transformations that can be expressed as a certain type of matrix Laplace transformation. This allows us to significantly extend the recently developed linear combination of Hamiltonian simulation (LCHS) method [An, Liu, Lin, Phys. Rev. Lett. 131, 150603, 2023; An, Childs, Lin, arXiv:2312.03916] to represent a wider class of eigenvalue transformations, such as powers of the matrix inverse, $A^{-k}$, and the exponential of the matrix inverse, $e^{-A^{-1}}$. The latter can be interpreted as the solution of a mass-matrix differential equation of the form $A u'(t)=-u(t)$. We demonstrate that our eigenvalue transformation approach can solve this problem without explicitly inverting $A$, reducing the computational complexity. △ Less

Submitted 6 November, 2024; originally announced November 2024.

Comments: 29+7 pages

Quantum Linear System Solvers: A Survey of Algorithms and Applications

Authors: Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, Dominic W. Berry

Abstract: Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with… ▽ More Solving linear systems of equations plays a fundamental role in numerous computational problems from different fields of science. The widespread use of numerical methods to solve these systems motivates investigating the feasibility of solving linear systems problems using quantum computers. In this work, we provide a survey of the main advances in quantum linear systems algorithms, together with some applications. We summarize and analyze the main ideas behind some of the algorithms for the quantum linear systems problem in the literature. The analysis begins by examining the Harrow-Hassidim-Lloyd (HHL) solver. We note its limitations and reliance on computationally expensive quantum methods, then highlight subsequent research efforts which aimed to address these limitations and optimize runtime efficiency and precision via various paradigms. We focus in particular on the post-HHL enhancements which have paved the way towards optimal lower bounds with respect to error tolerance and condition number. By doing so, we propose a taxonomy that categorizes these studies. Furthermore, by contextualizing these developments within the broader landscape of quantum computing, we explore the foundational work that have inspired and informed their development, as well as subsequent refinements. Finally, we discuss the potential applications of these algorithms in differential equations, quantum machine learning, and many-body physics. △ Less

Submitted 9 January, 2025; v1 submitted 4 November, 2024; originally announced November 2024.

Comments: 42 pages, 7 figures

Design nearly optimal quantum algorithm for linear differential equations via Lindbladians

Authors: Zhong-Xia Shang, Naixu Guo, Dong An, Qi Zhao

Abstract: Solving linear ordinary differential equations (ODE) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed non-unitary dynamics into intrinsically unitary quantum circuits. In this work, we propose a new quantum algorithm for solving ODEs by harnessing open quantum systems. Specifica… ▽ More Solving linear ordinary differential equations (ODE) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed non-unitary dynamics into intrinsically unitary quantum circuits. In this work, we propose a new quantum algorithm for solving ODEs by harnessing open quantum systems. Specifically, we propose a novel technique called non-diagonal density matrix encoding, which leverages the inherent non-unitary dynamics of Lindbladians to encode general linear ODEs into the non-diagonal blocks of density matrices. This framework enables us to design quantum algorithms with both theoretical simplicity and high performance. Combined with the state-of-the-art quantum Lindbladian simulation algorithms, our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters under a plausible input model. We also give applications of our algorithm including the Gibbs state preparations and the partition function estimations. △ Less

Submitted 27 August, 2025; v1 submitted 25 October, 2024; originally announced October 2024.

Comments: 8+11 pages, 1 figure, and 1 table. PRL version

Journal ref: Physical Review Letters 135 (12), 120604, 2025

Fast-forwarding quantum algorithms for linear dissipative differential equations

Authors: Dong An, Akwum Onwunta, Gengzhi Yang

Abstract: We establish improved complexity estimates of quantum algorithms for linear dissipative ordinary differential equations (ODEs) and show that the time dependence can be fast-forwarded to be sub-linear. Specifically, we show that a quantum algorithm based on truncated Dyson series can prepare history states of dissipative ODEs up to time $T$ with cost… ▽ More We establish improved complexity estimates of quantum algorithms for linear dissipative ordinary differential equations (ODEs) and show that the time dependence can be fast-forwarded to be sub-linear. Specifically, we show that a quantum algorithm based on truncated Dyson series can prepare history states of dissipative ODEs up to time $T$ with cost $\widetilde{\mathcal{O}}(\log(T) (\log(1/ε))^2 )$, which is an exponential speedup over the best previous result. For final state preparation at time $T$, we show that its complexity is $\widetilde{\mathcal{O}}(\sqrt{T} (\log(1/ε))^2 )$, achieving a polynomial speedup in $T$. We also analyze the complexity of simpler lower-order quantum algorithms, such as the forward Euler method and the trapezoidal rule, and find that even lower-order methods can still achieve $\widetilde{\mathcal{O}}(\sqrt{T})$ cost with respect to time $T$ for preparing final states of dissipative ODEs. As applications, we show that quantum algorithms can simulate dissipative non-Hermitian quantum dynamics and heat processes with fast-forwarded complexity sub-linear in time. △ Less

Submitted 20 January, 2026; v1 submitted 16 October, 2024; originally announced October 2024.

Comments: 32+11 pages

Journal ref: Quantum 10, 1986 (2026)

Feedforward Quantum Singular Value Transformation

Authors: Yulong Dong, Dong An, Murphy Yuezhen Niu

Abstract: In this paper, we introduce a major advancement in Quantum Singular Value Transformation (QSVT) through the development of Feedforward QSVT (FQSVT), a framework that significantly enhances the efficiency and robustness of quantum algorithm design. By leveraging intermediate measurements and feedforward operations, FQSVTs reclaim quantum information typically discarded in conventional QSVT, enablin… ▽ More In this paper, we introduce a major advancement in Quantum Singular Value Transformation (QSVT) through the development of Feedforward QSVT (FQSVT), a framework that significantly enhances the efficiency and robustness of quantum algorithm design. By leveraging intermediate measurements and feedforward operations, FQSVTs reclaim quantum information typically discarded in conventional QSVT, enabling more efficient transformations. Our results show that FQSVTs can exponentially accelerate the projection of quantum states onto energy subspaces, outperforming probabilistic projection and adiabatic algorithms with superior efficiency and a drastic reduction in query complexity. In the context of superconducting qubits, FQSVTs offer a powerful tool for managing energy subspaces, improving efficiency for state preparation and leakage detection. △ Less

Submitted 14 August, 2024; originally announced August 2024.

Multi-product Hamiltonian simulation with explicit commutator scaling

Authors: Junaid Aftab, Dong An, Konstantina Trivisa

Abstract: The well-conditioned multi-product formula (MPF), proposed by [Low, Kliuchnikov, and Wiebe, 2019], is a simple high-order time-independent Hamiltonian simulation algorithm that implements a linear combination of standard product formulas of low order. While the MPF aims to simultaneously exploit commutator scaling among Hamiltonians and achieve near-optimal time and precision dependence, its lack… ▽ More The well-conditioned multi-product formula (MPF), proposed by [Low, Kliuchnikov, and Wiebe, 2019], is a simple high-order time-independent Hamiltonian simulation algorithm that implements a linear combination of standard product formulas of low order. While the MPF aims to simultaneously exploit commutator scaling among Hamiltonians and achieve near-optimal time and precision dependence, its lack of a rigorous error bound on the nested commutators renders its practical advantage ambiguous. In this work, we conduct a rigorous complexity analysis of the well-conditioned MPF, demonstrating explicit commutator scaling and near-optimal time and precision dependence at the same time. Using our improved complexity analysis, we present several applications of practical interest where the MPF based on a second-order product formula can achieve a polynomial speedup in both system size and evolution time, as well as an exponential speedup in precision, compared to second-order and even higher-order product formulas. Compared to post-Trotter methods, the MPF based on a second-order product formula can achieve polynomially better scaling in system size, with only poly-logarithmic overhead in evolution time and precision. △ Less

Submitted 13 March, 2024; originally announced March 2024.

Comments: 28 pages

The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver

Authors: Pedro C. S. Costa, Dong An, Ryan Babbush, Dominic Berry

Abstract: The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number $κ$ and the allowable error $ε$ [PRX Quantum \textbf{3}, 040303 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we s… ▽ More The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number $κ$ and the allowable error $ε$ [PRX Quantum \textbf{3}, 040303 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,200 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is about an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient. △ Less

Submitted 11 October, 2025; v1 submitted 12 December, 2023; originally announced December 2023.

Comments: 16 pages, 35 figures

Journal ref: Quantum 9, 1887 (2025)

Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters

Authors: Dong An, Andrew M. Childs, Lin Lin

Abstract: We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the… ▽ More We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters. △ Less

Submitted 14 December, 2025; v1 submitted 6 December, 2023; originally announced December 2023.

Comments: Published version with newly added Section 4.4.4, updated Appendix F, and improved presentation

Journal ref: Communications in Mathematical Physics 407 (1), 19 (2026)

Quantum algorithms for linear and non-linear fractional reaction-diffusion equations

Authors: Dong An, Konstantina Trivisa

Abstract: High-dimensional fractional reaction-diffusion equations have numerous applications in the fields of biology, chemistry, and physics, and exhibit a range of rich phenomena. While classical algorithms have an exponential complexity in the spatial dimension, a quantum computer can produce a quantum state that encodes the solution with only polynomial complexity, provided that suitable input access i… ▽ More High-dimensional fractional reaction-diffusion equations have numerous applications in the fields of biology, chemistry, and physics, and exhibit a range of rich phenomena. While classical algorithms have an exponential complexity in the spatial dimension, a quantum computer can produce a quantum state that encodes the solution with only polynomial complexity, provided that suitable input access is available. In this work, we investigate efficient quantum algorithms for linear and nonlinear fractional reaction-diffusion equations with periodic boundary conditions. For linear equations, we analyze and compare the complexity of various methods, including the second-order Trotter formula, time-marching method, and truncated Dyson series method. We also present a novel algorithm that combines the linear combination of Hamiltonian simulation technique with the interaction picture formalism, resulting in optimal scaling in the spatial dimension. For nonlinear equations, we employ the Carleman linearization method and propose a block-encoding version that is appropriate for the dense matrices that arise from the spatial discretization of fractional reaction-diffusion equations. △ Less

Submitted 14 December, 2025; v1 submitted 29 October, 2023; originally announced October 2023.

Journal ref: Quantum 10, 1969 (2026)

Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost

Authors: Dong An, Jin-Peng Liu, Lin Lin

Abstract: We propose a simple method for simulating a general class of non-unitary dynamics as a linear combination of Hamiltonian simulation (LCHS) problems. LCHS does not rely on converting the problem into a dilated linear system problem, or on the spectral mapping theorem. The latter is the mathematical foundation of many quantum algorithms for solving a wide variety of tasks involving non-unitary proce… ▽ More We propose a simple method for simulating a general class of non-unitary dynamics as a linear combination of Hamiltonian simulation (LCHS) problems. LCHS does not rely on converting the problem into a dilated linear system problem, or on the spectral mapping theorem. The latter is the mathematical foundation of many quantum algorithms for solving a wide variety of tasks involving non-unitary processes, such as the quantum singular value transformation (QSVT). The LCHS method can achieve optimal cost in terms of state preparation. We also demonstrate an application for open quantum dynamics simulation using the complex absorbing potential method with near-optimal dependence on all parameters. △ Less

Submitted 23 October, 2023; v1 submitted 2 March, 2023; originally announced March 2023.

Comments: 6+15 pages, 1 figure

Journal ref: Phys. Rev. Lett. 131, 150603 (2023)

Quantum differential equation solvers: limitations and fast-forwarding

Authors: Dong An, Jin-Peng Liu, Daochen Wang, Qi Zhao

Abstract: We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational o… ▽ More We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of ``non-quantumness'': real part gap and non-normality of the coefficient matrix. We then show that homogeneous ODEs in the absence of both types of ``non-quantumness'' are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency. More specifically, we obtain exponential improvements in both $T$ and the spectral norm of the coefficient matrix for inhomogeneous ODEs with efficiently implementable eigensystems, including various spatially discretized linear evolutionary partial differential equations. We give fast-forwarding algorithms that are conceptually different from existing ones in the sense that they neither require time discretization nor solving high-dimensional linear systems. △ Less

Submitted 9 July, 2025; v1 submitted 9 November, 2022; originally announced November 2022.

Comments: Published version with improved presentation

Journal ref: Communications in Mathematical Physics 406 (8), 189 (2025)

Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation

Authors: Dong An, Di Fang, Stephen Jordan, Jin-Peng Liu, Guang Hao Low, Jiasu Wang

Abstract: Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition $R < 1$, where $R$ measures the ratio of nonlinearity to dissipation using the $\ell_2$ norm. Here we develop an efficient quantum algorithm b… ▽ More Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition $R < 1$, where $R$ measures the ratio of nonlinearity to dissipation using the $\ell_2$ norm. Here we develop an efficient quantum algorithm based on [1] for reaction-diffusion equations, a class of nonlinear partial differential equations (PDEs). To achieve this, we improve upon the Carleman linearization approach introduced in [1] to obtain a faster convergence rate under the condition $R_D < 1$, where $R_D$ measures the ratio of nonlinearity to dissipation using the $\ell_{\infty}$ norm. Since $R_D$ is independent of the number of spatial grid points $n$ while $R$ increases with $n$, the criterion $R_D<1$ is significantly milder than $R<1$ for high-dimensional systems and can stay convergent under grid refinement for approximating PDEs. As applications of our quantum algorithm we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics. In particular, we show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information. △ Less

Submitted 6 November, 2023; v1 submitted 2 May, 2022; originally announced May 2022.

Comments: 61 pages, 5 figures. Published in Communications in Mathematical Physics

Optimal scaling quantum linear systems solver via discrete adiabatic theorem

Authors: Pedro C. S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, Dominic W. Berry

Abstract: 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 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 procedur… ▽ 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 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 sub-optimal 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. We use this discrete adiabatic theorem 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 $\mathcal{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. △ Less

Submitted 15 November, 2021; originally announced November 2021.

Comments: 56 pages, 8 figures

Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation

Authors: Dong An, Di Fang, Lin Lin

Abstract: We propose a simple quantum algorithm for simulating highly oscillatory quantum dynamics, which does not require complicated quantum control logic for handling time-ordering operators. To our knowledge, this is the first quantum algorithm that is both insensitive to the rapid changes of the time-dependent Hamiltonian and exhibits commutator scaling. Our method can be used for efficient Hamiltonian… ▽ More We propose a simple quantum algorithm for simulating highly oscillatory quantum dynamics, which does not require complicated quantum control logic for handling time-ordering operators. To our knowledge, this is the first quantum algorithm that is both insensitive to the rapid changes of the time-dependent Hamiltonian and exhibits commutator scaling. Our method can be used for efficient Hamiltonian simulation in the interaction picture. In particular, we demonstrate that for the simulation of the Schrödinger equation, our method exhibits superconvergence and achieves a surprising second order convergence rate, of which the proof rests on a careful application of pseudo-differential calculus. Numerical results verify the effectiveness and the superconvergence property of our method. △ Less

Submitted 11 April, 2022; v1 submitted 4 November, 2021; originally announced November 2021.

Journal ref: Quantum 6, 690 (2022)

Coupling two laser-cooled ions via a room-temperature conductor

Authors: Da An, Alberto M. Alonso, Clemens Matthiesen, Hartmut Häffner

Abstract: We demonstrate coupling between the motions of two independently trapped ions with a separation distance of 620 $μ$m. The ion-ion interaction is enhanced via a room-temperature electrically floating metallic wire which connects two surface traps. Tuning the motion of both ions into resonance, we show flow of energy with a coupling rate of 11 Hz. Quantum-coherent coupling is hindered by strong surf… ▽ More We demonstrate coupling between the motions of two independently trapped ions with a separation distance of 620 $μ$m. The ion-ion interaction is enhanced via a room-temperature electrically floating metallic wire which connects two surface traps. Tuning the motion of both ions into resonance, we show flow of energy with a coupling rate of 11 Hz. Quantum-coherent coupling is hindered by strong surface electric-field noise in our device. Our ion wire-ion system demonstrates that room-temperature conductors can be used to mediate and tune interactions between independently trapped charges over distances beyond those achievable with free-space dipole-dipole coupling. This technology may be used to sympathetically cool or entangle remotely trapped charges and enable coupling between disparate physical systems. △ Less

Submitted 2 July, 2021; originally announced July 2021.

Parallel transport dynamics for mixed quantum states with applications to time-dependent density functional theory

Authors: Dong An, Di Fang, Lin Lin

Abstract: Direct simulation of the von Neumann dynamics for a general (pure or mixed) quantum state can often be expensive. One prominent example is the real-time time-dependent density functional theory (rt-TDDFT), a widely used framework for the first principle description of many-electron dynamics in chemical and materials systems. Practical rt-TDDFT calculations often avoid the direct simulation of the… ▽ More Direct simulation of the von Neumann dynamics for a general (pure or mixed) quantum state can often be expensive. One prominent example is the real-time time-dependent density functional theory (rt-TDDFT), a widely used framework for the first principle description of many-electron dynamics in chemical and materials systems. Practical rt-TDDFT calculations often avoid the direct simulation of the von Neumann equation, and solve instead a set of Schrödinger equations, of which the dynamics is equivalent to that of the von Neumann equation. However, the time step size employed by the Schrödinger dynamics is often much smaller. In order to improve the time step size and the overall efficiency of the simulation, we generalize a recent work of the parallel transport (PT) dynamics for simulating pure states [An, Lin, Multiscale Model. Simul. 18, 612, 2020] to general quantum states. The PT dynamics provides the optimal gauge choice, and can employ a time step size comparable to that of the von Neumann dynamics. Going beyond the linear and near adiabatic regime in previous studies, we find that the error of the PT dynamics can be bounded by certain commutators between Hamiltonians, density matrices, and their derived quantities. Such a commutator structure is not present in the Schrödinger dynamics. We demonstrate that the parallel transport-implicit midpoint (PT-IM) method is a suitable method for simulating the PT dynamics, especially when the spectral radius of the Hamiltonian is large. The commutator structure of the error bound, and numerical results for model rt-TDDFT calculations in both linear and nonlinear regimes, confirm the advantage of the PT dynamics. △ Less

Submitted 31 May, 2021; originally announced May 2021.

Time-dependent unbounded Hamiltonian simulation with vector norm scaling

Authors: Dong An, Di Fang, Lin Lin

Abstract: The accuracy of quantum dynamics simulation is usually measured by the error of the unitary evolution operator in the operator norm, which in turn depends on certain norm of the Hamiltonian. For unbounded operators, after suitable discretization, the norm of the Hamiltonian can be very large, which significantly increases the simulation cost. However, the operator norm measures the worst-case erro… ▽ More The accuracy of quantum dynamics simulation is usually measured by the error of the unitary evolution operator in the operator norm, which in turn depends on certain norm of the Hamiltonian. For unbounded operators, after suitable discretization, the norm of the Hamiltonian can be very large, which significantly increases the simulation cost. However, the operator norm measures the worst-case error of the quantum simulation, while practical simulation concerns the error with respect to a given initial vector at hand. We demonstrate that under suitable assumptions of the Hamiltonian and the initial vector, if the error is measured in terms of the vector norm, the computational cost may not increase at all as the norm of the Hamiltonian increases using Trotter type methods. In this sense, our result outperforms all previous error bounds in the quantum simulation literature. Our result extends that of [Jahnke, Lubich, BIT Numer. Math. 2000] to the time-dependent setting. We also clarify the existence and the importance of commutator scalings of Trotter and generalized Trotter methods for time-dependent Hamiltonian simulations. △ Less

Submitted 21 May, 2021; v1 submitted 24 December, 2020; originally announced December 2020.

Journal ref: Quantum 5, 459 (2021)

Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance

Authors: Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, Jiasu Wang

Abstract: Inspired by recent progress in quantum algorithms for ordinary and partial differential equations, we study quantum algorithms for stochastic differential equations (SDEs). Firstly we provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting. As applications, we apply it to compute expectation values determined by classical solutions of SDE… ▽ More Inspired by recent progress in quantum algorithms for ordinary and partial differential equations, we study quantum algorithms for stochastic differential equations (SDEs). Firstly we provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting. As applications, we apply it to compute expectation values determined by classical solutions of SDEs, with improved dependence on precision. We demonstrate the use of this algorithm in a variety of applications arising in mathematical finance, such as the Black-Scholes and Local Volatility models, and Greeks. We also provide a quantum algorithm based on sublinear binomial sampling for the binomial option pricing model with the same improvement. △ Less

Submitted 22 June, 2021; v1 submitted 11 December, 2020; originally announced December 2020.

Comments: 37 pages, 6 figures

Journal ref: Quantum 5, 481 (2021)

Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions

Authors: Yu Tong, Dong An, Nathan Wiebe, Lin Lin

Abstract: Preconditioning is the most widely used and effective way for treating ill-conditioned linear systems in the context of classical iterative linear system solvers. We introduce a quantum primitive called fast inversion, which can be used as a preconditioner for solving quantum linear systems. The key idea of fast inversion is to directly block-encode a matrix inverse through a quantum circuit imple… ▽ More Preconditioning is the most widely used and effective way for treating ill-conditioned linear systems in the context of classical iterative linear system solvers. We introduce a quantum primitive called fast inversion, which can be used as a preconditioner for solving quantum linear systems. The key idea of fast inversion is to directly block-encode a matrix inverse through a quantum circuit implementing the inversion of eigenvalues via classical arithmetics. We demonstrate the application of preconditioned linear system solvers for computing single-particle Green's functions of quantum many-body systems, which are widely used in quantum physics, chemistry, and materials science. We analyze the complexities in three scenarios: the Hubbard model, the quantum many-body Hamiltonian in the planewave-dual basis, and the Schwinger model. We also provide a method for performing Green's function calculation in second quantization within a fixed particle manifold and note that this approach may be valuable for simulation more broadly. Besides solving linear systems, fast inversion also allows us to develop fast algorithms for computing matrix functions, such as the efficient preparation of Gibbs states. We introduce two efficient approaches for such a task, based on the contour integral formulation and the inverse transform respectively. △ Less

Submitted 28 September, 2021; v1 submitted 30 August, 2020; originally announced August 2020.

Journal ref: Phys. Rev. A 104, 032422 (2021)

Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm

Authors: Dong An, Lin Lin

Abstract: We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with $\mathcal{O}(κ~\text{poly}(\log(κ/ε)))$ runtime, where $κ$ is the condition number, and $ε$ is the target accuracy. This is near optimal with respect to both $κ$ and $ε$. Our method is applicable to general non-Hermitian matrices, and the… ▽ More We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with $\mathcal{O}(κ~\text{poly}(\log(κ/ε)))$ runtime, where $κ$ is the condition number, and $ε$ is the target accuracy. This is near optimal with respect to both $κ$ and $ε$. Our method is applicable to general non-Hermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the time-optimal AQC, vanilla AQC, and the recently proposed randomization method. △ Less

Submitted 9 March, 2022; v1 submitted 12 September, 2019; originally announced September 2019.

Comments: 28 pages, 3 figures

Journal ref: ACM Transactions on Quantum Computing 3, 2, Article 5 (June 2022)

Distance scaling and polarization of electric-field noise in a surface ion trap

Authors: Da An, Clemens Matthiesen, Erik Urban, Hartmut Häffner

Abstract: We probe electric-field noise in a surface ion trap for ion-surface distances $d$ between 50 and 300 $μ\mathrm{m}$ in the normal and planar directions. We find the noise distance dependence to scale as $d^{-2.6}$ in our trap and a frequency dependence which is consistent with $1/f$ noise. Simulations of the electric-field noise specific to our trap geometry provide evidence that we are not limited… ▽ More We probe electric-field noise in a surface ion trap for ion-surface distances $d$ between 50 and 300 $μ\mathrm{m}$ in the normal and planar directions. We find the noise distance dependence to scale as $d^{-2.6}$ in our trap and a frequency dependence which is consistent with $1/f$ noise. Simulations of the electric-field noise specific to our trap geometry provide evidence that we are not limited by technical noise sources. Our distance scaling data is consistent with a noise correlation length of about 100 $μ\mathrm{m}$ at the trap surface, and we discuss how patch potentials of this size would be modified by the electrode geometry. △ Less

Submitted 19 June, 2019; v1 submitted 15 June, 2019; originally announced June 2019.

Journal ref: Phys. Rev. A 100, 063405 (2019)

Surface trap with dc-tunable ion-electrode distance

Authors: Da An, Clemens Matthiesen, Ahmed Abdelrahman, Maya Berlin-Udi, Dylan Gorman, Sönke Möller, Erik Urban, Hartmut Häffner

Abstract: We describe the design, fabrication, and operation of a novel surface-electrode Paul trap that produces a radio-frequency-null along the axis perpendicular to the trap surface. This arrangement enables control of the vertical trapping potential and consequentially the ion-electrode distance via dc-electrodes only. We demonstrate confinement of single $^{40}$Ca$^+$ ions at heights between $50~μ$m a… ▽ More We describe the design, fabrication, and operation of a novel surface-electrode Paul trap that produces a radio-frequency-null along the axis perpendicular to the trap surface. This arrangement enables control of the vertical trapping potential and consequentially the ion-electrode distance via dc-electrodes only. We demonstrate confinement of single $^{40}$Ca$^+$ ions at heights between $50~μ$m and $300~μ$m above planar copper-coated aluminium electrodes. We investigate micromotion in the vertical direction and show cooling of both the planar and vertical motional modes into the ground state. This trap architecture provides a platform for precision electric-field noise detection, trapping of vertical ion strings without excess micromotion, and may have applications for scalable quantum computers with surface ion traps. △ Less

Submitted 16 July, 2018; originally announced July 2018.