A theory of quantum differential equation solvers: limitations and fast-forwarding

• URL: http://arxiv.org/abs/2211.05246v1
• Date: Wed, 9 Nov 2022 22:50:14 GMT
• Title: A theory of quantum differential equation solvers: limitations and fast-forwarding
• Authors: Dong An, Jin-Peng Liu, Daochen Wang, Qi Zhao
• Abstract summary: We show that quantum algorithms suffer from computational overheads due to two types of non-quantumness'' We then show that ODEs in the absence of both types of non-quantumness'' are equivalent to quantum dynamics. We show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency.
• Score: 19.080267236745623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the limitations and fast-forwarding of quantum algorithms for solving linear ordinary differential equation (ODE) systems with 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 homogeneous 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 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. We generalize our results to the inhomogeneous case and find that existing generic quantum ODE solvers cannot be substantially improved. 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 quadratic to exponential improvements in terms of the evolution time $T$ and the spectral norm of the coefficient matrix for the following classes of ODEs: inhomogeneous ODEs with a negative definite coefficient matrix, inhomogeneous ODEs with a coefficient matrix having an eigenbasis that can be efficiently prepared on a quantum computer and eigenvalues that can be efficiently computed classically, and the spatially discretized inhomogeneous heat equation and advection-diffusion equation. 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.

Related papers

• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians [11.53984890996377]
  We propose a new quantum algorithm for ODEs by harnessing open quantum systems. We use the natural non-unitary dynamics of Lindbladians with the aid of a new technique called the non-diagonal density matrix encoding. Our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters.
  arXiv  Detail & Related papers  (2024-10-25T15:27:41Z)
• Double-Logarithmic Depth Block-Encodings of Simple Finite Difference Method's Matrices [0.0]
  Solving differential equations is one of the most computationally expensive problems in classical computing. Despite recent progress made in the field of quantum computing and quantum algorithms, its end-to-end application towards practical realization still remains unattainable.
  arXiv  Detail & Related papers  (2024-10-07T17:44:30Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
  We present a quantum algorithm for a non-linear differential equation of the form $fracd|urangledt. We also introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case.
  arXiv  Detail & Related papers  (2024-07-10T14:08:58Z)
• A Theory of Quantum Jumps [44.99833362998488]
  We study fluorescence and the phenomenon of quantum jumps'' in idealized models of atoms coupled to the quantized electromagnetic field. Our results amount to a derivation of the fundamental randomness in the quantum-mechanical description of microscopic systems.
  arXiv  Detail & Related papers  (2024-04-16T11:00:46Z)
• Hybrid quantum-classical and quantum-inspired classical algorithms for solving banded circulant linear systems [0.8192907805418583]
  We present an efficient algorithm based on convex optimization of combinations of quantum states to solve for banded circulant linear systems. By decomposing banded circulant matrices into cyclic permutations, our approach produces approximate solutions to such systems with a combination of quantum states linear to $K$. We validate our methods with classical simulations and actual IBM quantum computer implementation, showcasing their applicability for solving physical problems such as heat transfer.
  arXiv  Detail & Related papers  (2023-09-20T16:27:16Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Quantum Solver of Contracted Eigenvalue Equations for Scalable Molecular Simulations on Quantum Computing Devices [0.0]
  We introduce a quantum solver of contracted eigenvalue equations, the quantum analogue of classical methods for the energies. We demonstrate the algorithm though computations on both a quantum simulator and two IBM quantum processing units.
  arXiv  Detail & Related papers  (2020-04-23T18:35: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.