Fast-forwarding quantum algorithms for linear dissipative differential equations

• URL: http://arxiv.org/abs/2410.13189v1
• Date: Thu, 17 Oct 2024 03:33:47 GMT
• Title: Fast-forwarding quantum algorithms for linear dissipative differential equations
• Authors: Dong An, Akwum Onwunta, Gengzhi Yang,
• Abstract summary: We show that a quantum algorithm based on truncated Dyson series can prepare history states of dissipative ODEs up to time $T$ with cost $widetildemathcalO(log(T) (log (1/epsilon))2 )$. As applications, we show that quantum algorithms can simulate dissipative non-Hermitian quantum dynamics and heat process with fast-forwarded complexity sub-linear in time.
• Score: 2.5677613431426978
• License:
• 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 $\widetilde{\mathcal{O}}(\log(T) (\log(1/\epsilon))^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/\epsilon))^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 process with fast-forwarded complexity sub-linear in time.

Related papers

• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Unbiased random circuit compiler for time-dependent Hamiltonian simulation [8.694056486825318]
  Time-dependent Hamiltonian simulation is a critical task in quantum computing. We develop an unbiased random compiler for TDHS. We perform numerical simulations for a spin model under the interaction picture and the adiabatic ground state preparation for molecular systems.
  arXiv  Detail & Related papers  (2022-12-19T13:40:05Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem.
  arXiv  Detail & Related papers  (2021-06-02T12:50:56Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)
• Efficient quantum algorithm for dissipative nonlinear differential equations [1.1988695717766686]
  We develop a quantum algorithm for dissipative quadratic $n$-dimensional ordinary differential equations. Our algorithm has complexity $T2 qmathrmpoly(log T, log n, log 1/epsilon)/epsilon$, where $T$ is the evolution time, $epsilon$ is the allowed error, and $q$ measures decay of the solution.
  arXiv  Detail & Related papers  (2020-11-06T04:27:00Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$. The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
  arXiv  Detail & Related papers  (2020-09-09T18:00:09Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.