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

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2212.10775 · Quantum Information Processing

An efficient quantum algorithm for simulating polynomial dynamical systems

Amit Surana, Abeynaya Gnanasekaran, Tuhin Sahai

Published Mar 13, 2024• 22 citations
arXivHTMLPDF
DOI
10.1007/s11128-024-04311-2

Related papers

Efficient simulation of many-body localized systems

Yichen Huang

An efficient numerical method is developed using the matrix product formalism for computing the properties at finite energy densities in one-dimensional (1D) many-body localized (MBL) systems. Arguing that any efficient (possibly quantum) algorithm can only have a polynomially small energy resolution, we propose a (rigorous) polynomial-time (classical) algorithm that outputs a diagonal density operator supported on a microcanonical ensemble of an inverse polynomial bandwidth. The proof uses no other conditions for MBL but assumes that the effect of any local perturbation (e.g., injecting conserved charges) is restricted to a region whose radius grows logarithmically with time. A non-optimal version of this algorithm efficiently simulates the quantum phase estimation algorithm in 1D MBL systems; a heuristic version of the algorithm can be easily coded and used to, e.g., detect energy-tuned dynamical quantum phase transitions between MBL phases. We extend the algorithm to two and higher spatial dimensions using the projected entangled pair formalism.

arXiv:1508.04756•Aug 19, 2015•6 citations

Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes +4 more

International Journal of Theoretical Physics•May 18, 2018•7 citations

Numerical methods for complex quantum dynamics with applications to quantum biology and quantum many-body dynamics

R. Rosenbach

Multi-component quantum systems that interact strongly with their environments are difficult to simulate numerically. This challenge is approached by introducing the numerically exact Time Evolving Density Matrix with Orthogonal Polynomial Algorithm (TEDOPA). The application of this algorithm allows for the efficient simulation of open quantum system dynamics, including spin-boson models and generalizations of it to multi-component systems. In this thesis, TEDOPA is introduced and applied to pigment-protein complexes that play a key role in the photosynthetic process and that have been studied extensively in the last years. Further methodical and numerical improvements of TEDOPA are developed, resulting in major speed-ups for certain parameter regimes.

•Jan 1, 2015•0 citations

Quantum algorithms for quantum dynamics

Alexander Miessen, Pauline J. Ollitrault, Francesco Tacchino +1 more

Nature Computational Science•Dec 30, 2022•93 citations

Improved Quantum Algorithms for Simulating Many-Body Systems

Sophia Simon

Quantum computers are expected to significantly outperform classical computers for certain computational tasks. One of the most promising applications is the simulation of many-body systems such as complex molecules or materials. In this thesis, we present several quantum algorithms for simulating many-body systems that can provide considerably better scaling than prior approaches. First, we describe a fully coherent quantum algorithm for simulating molecular dynamics within the Born-Oppenheimer approximation that leads to super-polynomially better scaling with respect to the error tolerance than previous work. Our algorithm utilizes the Koopman-von Neumann formulation of classical mechanics. This allows us to express the classical equations of motion as unitary dynamics which can be efficiently simulated on a quantum computer. We demonstrate that these simulations can be performed either at constant energy or at constant temperature. The latter allows us to estimate thermodynamic properties such as the Helmholtz free energy of the system. Next, we present two closely related quantum algorithms for solving continuous optimization problems such as finding the equilibrium configurations of molecules. These algorithms do not require any explicit gradient estimations. Instead, we encode the optimization problem into the dynamics of a quantum or classical system with friction. The dynamics are governed by a carefully chosen time-dependent Hamiltonian and thus can be simulated using efficient Hamiltonian simulation algorithms. We provide evidence that our fully coherent quantum algorithms can, in certain cases, provide exponentially better asymptotic scaling than approaches based on gradient descent. Lastly, we present a quantum algorithm for preparing the ground state of a set of interacting systems that can circumvent the exponential scaling suggested by the Van Vleck catastrophe. Our algorithm utilizes a divide-and-conquer strategy that repeatedly uses phase estimation to merge ground states of increasingly larger subsystems. We provide rigorous bounds for this approach and show that, under certain assumptions, our algorithm scales only quasi-polynomially with the number of systems.

•Jun 1, 2026•0 citations

Polynomial-Time Algorithm for Simulation of Weakly Interacting Quantum Spin Systems

Sergey B. Bravyi, David Peter Divincenzo, Daniel Loss

arXiv:0707.1894•Communications in Mathematical Physics•Jul 14, 2008•14 citations
An efficient numerical method is developed using the matrix product formalism for computing the properties at finite energy densities in one-dimensional (1D) many-body localized (MBL) systems. Arguing that any efficient (possibly quantum) algorithm can only have a polynomially small energy resolution, we propose a (rigorous) polynomial-time (classical) algorithm that outputs a diagonal density operator supported on a microcanonical ensemble of an inverse polynomial bandwidth. The proof uses no other conditions for MBL but assumes that the effect of any local perturbation (e.g., injecting conserved charges) is restricted to a region whose radius grows logarithmically with time. A non-optimal version of this algorithm efficiently simulates the quantum phase estimation algorithm in 1D MBL systems; a heuristic version of the algorithm can be easily coded and used to, e.g., detect energy-tuned dynamical quantum phase transitions between MBL phases. We extend the algorithm to two and higher spatial dimensions using the projected entangled pair formalism.
Multi-component quantum systems that interact strongly with their environments are difficult to simulate numerically. This challenge is approached by introducing the numerically exact Time Evolving Density Matrix with Orthogonal Polynomial Algorithm (TEDOPA). The application of this algorithm allows for the efficient simulation of open quantum system dynamics, including spin-boson models and generalizations of it to multi-component systems. In this thesis, TEDOPA is introduced and applied to pigment-protein complexes that play a key role in the photosynthetic process and that have been studied extensively in the last years. Further methodical and numerical improvements of TEDOPA are developed, resulting in major speed-ups for certain parameter regimes.
Quantum computers are expected to significantly outperform classical computers for certain computational tasks. One of the most promising applications is the simulation of many-body systems such as complex molecules or materials. In this thesis, we present several quantum algorithms for simulating many-body systems that can provide considerably better scaling than prior approaches. First, we describe a fully coherent quantum algorithm for simulating molecular dynamics within the Born-Oppenheimer approximation that leads to super-polynomially better scaling with respect to the error tolerance than previous work. Our algorithm utilizes the Koopman-von Neumann formulation of classical mechanics. This allows us to express the classical equations of motion as unitary dynamics which can be efficiently simulated on a quantum computer. We demonstrate that these simulations can be performed either at constant energy or at constant temperature. The latter allows us to estimate thermodynamic properties such as the Helmholtz free energy of the system. Next, we present two closely related quantum algorithms for solving continuous optimization problems such as finding the equilibrium configurations of molecules. These algorithms do not require any explicit gradient estimations. Instead, we encode the optimization problem into the dynamics of a quantum or classical system with friction. The dynamics are governed by a carefully chosen time-dependent Hamiltonian and thus can be simulated using efficient Hamiltonian simulation algorithms. We provide evidence that our fully coherent quantum algorithms can, in certain cases, provide exponentially better asymptotic scaling than approaches based on gradient descent. Lastly, we present a quantum algorithm for preparing the ground state of a set of interacting systems that can circumvent the exponential scaling suggested by the Van Vleck catastrophe. Our algorithm utilizes a divide-and-conquer strategy that repeatedly uses phase estimation to merge ground states of increasingly larger subsystems. We provide rigorous bounds for this approach and show that, under certain assumptions, our algorithm scales only quasi-polynomially with the number of systems.