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

The complexity of simulating quantum physics: dynamics and equilibrium

Abhinav Deshpande

Published Jan 1, 2021• 0 citations
Publisher

Abstract

Quantum computing is the offspring of quantum mechanics and computer science, two great scientific fields founded in the 20th century. Quantum computing is a relatively young field and is recognized as having the potential to revolutionize science and technology in the coming century. The primary question in this field is essentially to ask which problems are feasible with potential quantum computers and which are not. In this dissertation, we study this question with a physical bent of mind. We apply tools from computer science and mathematical physics to study the complexity of simulating quantum systems. In general, our goal is to identify parameter regimes under which simulating quantum systems is easy (efficiently solvable) or hard (not efficiently solvable). This study leads to an understanding of the features that make certain problems easy or hard to solve. We also get physical insight into the behavior of the system being simulated. In the first part of this dissertation, we study the classical complexity of simulating quantum dynamics. In general, the systems we study transition from being easy to simulate at short times to being harder to simulate at later times. We argue that the transition timescale is a useful measure for various Hamiltonians and is indicative of the physics behind the change in complexity. We illustrate this idea for a specific bosonic system, obtaining a complexity phase diagram that delineates the system into easy or hard for simulation. We also prove that the phase diagram is robust, supporting our statement that the phase diagram is indicative of the underlying physics. In the next part, we study open quantum systems from the point of view of their potential to encode hard computational problems. We study a class of fermionic Hamiltonians subject to Markovian noise described by Lindblad jump operators and illustrate how, sometimes, certain Lindblad operators can induce computational complexity into the problem. Specifically, we show that these operators can implement entangling gates, which can be used for universal quantum computation. We also study a system of bosons with Gaussian initial states subject to photon loss and detected using photon-number-resolving measurements. We show that such systems can remain hard to simulate exactly and retain a relic of the "quantumness" present in the lossless system. Finally, in the last part of this dissertation, we study the complexity of simulating a class of equilibrium states, namely ground states. We give complexity-theoretic evidence to identify two structural properties that can make ground states easier to simulate. These are the existence of a spectral gap and the existence of a classical description of the ground state. Our findings complement and guide efforts in the search for efficient algorithms.

DOI
10.13016/dalh-5dhv

Related papers

Quantum Stochastic Processes and Quantum Many-Body Physics

Johannes Bausch

This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable $X$ into a sum of $n$ iid random variables $Y_i$, i.e. $X=\sum_{i=1}^n Y_i$, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.

•Oct 4, 2017•1 citation

Locality and complexity in simulations of complex quantum systems

Martin Kliesch

Simulations play a crucial role in the investigation of complex quantum systems. In this thesis, locality structures of quantum systems are exploited to obtain complexity theoretic results with various physical implications. More specifically, rigorous mathematical tools are used and developed further, to investigate open quantum systems and thermal states. Moreover, important advances in photonic quantum simulations are discussed. For open quantum spin lattice systems new simulation schemes are provided. It is shown that Markovian dynamics can be simulated efficiently in the unitary circuit model, which can be seen as a dissipative Church-Turing type theorem. Moreover, Markovian dynamics is quasi-local and can be locally simulated on classical computers with a cost scaling polynomially in the system size. These results generalize standard tools from the investigation of Hamiltonian systems to open quantum systems. In particular, they provide a rigorous basis for their numerical simulation. However, also a major roadblock for making such simulations reliable is identified: Testing positivity of certain common approximations to mixed quantum states, called matrix product operators, is shown to be NP-hard in the system size and undecidable in the thermodynamic limit. Also more state space structures, originating from the spatial locality structure are discussed: Most states in state space cannot be generated efficiently with local Liouvillian dynamics and pure states generated in real- space renormalization schemes turn out to have local corrections in spatial dimensions larger than one. For thermal states on spin and fermionic lattice systems, a perturbation formula is provided and exponential clustering of correlations at high enough temperature is proven. This has various consequences: It leads to the extension of the concept of intensive temperature to interacting quantum systems, allows for efficient classical local simulations at high enough temperature, provides an upper bound on phase transition temperatures, and implies stability of thermal states against Hamiltonian perturbations. For photonic quantum simulations, sample complexity lower bounds for the verification of Boson-Sampling simulations are explained, which are applicable to a restricted setting. These bounds rely on a lower bound on the min-entropy of the output distribution of Boson-Sampling. This indicates that Boson-Sampling cannot be verified efficiently classically. Complementary to that, a reliable verification scheme for photonic state preparations is discussed, which uses single mode measurements as a simple quantum resource. The verification scheme is efficient for a large class of photonic simulations, including Boson-Sampling experiments with constantly many photons and state preparations necessary for measurement based quantum computing.

•Jan 1, 2015•0 citations

Quantum Algorithms and Complexity for Numerical Problems

Zhang, Chi

Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.

•Jan 1, 2011•0 citations

Quantum Simulations

Antti Regelin

Quantum simulation involves using a quantum system to study another quantum system. The proposal to simulate quantum physics using quantum mechanical devices, as outlined by Richard Feynman in 1982, stems from classical computers' challenges in simulating quantum systems. The pursuit of simulating complex quantum systems has led to the intersection of quantum mechanics and quantum computing. This offers new opportunities to understand and manipulate the quantum world. Central to describing quantum dynamics is the Hamiltonian operator $\hat{H}$, which governs the time evolution of physical systems and serves as the mathematical foundation for quantum simulations. This thesis explores the methodologies and advancements in simulating Hamiltonian operators on quantum computers, focusing on decomposing these operators into quantum gates and the efficiency gains over classical computational approaches. Initially, the thesis explains the fundamental theory and basics of quantum computing. Further it dives into the foundations of the Hamiltonian operator within quantum mechanics, highlighting its role in describing the dynamics of quantum systems. The complexity and high-dimensional nature of Hamiltonian matrices necessitate using quantum computers to simulate quantum phenomena accurately and efficiently. The process of simulating the Hamiltonian operator on a quantum computer involves a detailed examination of the strategies for decomposing the operator into a sequence of quantum gates. This decomposition is crucial for translating the abstract mathematical description of quantum systems into the physical operations of a quantum computer. By utilizing the principles of quantum mechanics, such as superposition and entanglement, quantum gates manipulate qubits to mimic the evolution of quantum states as the Hamiltonian operator dictates. Latter portions of the thesis are dedicated to comparing the efficiency of quantum simulations against traditional classical simulations and inspecting efficient quantum simulations. Quantum computers offer a polynomial or an exponential speedup for certain classes of problems, such as those involving highly entangled quantum states or requiring the simulation of complex quantum dynamics. This advantage is due to the quantum computer's ability to naturally represent and process quantum information - a task for which classical computers require exponential resources as the system size increases. The efficiency of simulating the Hamiltonian operator on a quantum computer is further enhanced through optimization techniques and algorithmic improvements. These include error mitigation strategies and the development of quantum algorithms tailored to specific types of Hamiltonian operators. The thesis presents a comprehensive analysis of these methods, demonstrating how they make quantum simulations more practical and accessible for scientific research and technological development. In conclusion this thesis is a literature review that examines the transformative potential of quantum simulations. By efficiently simulating the Hamiltonian operator on quantum computers researchers can explore quantum phenomena with precision, paving the way for breakthroughs in quantum physics, materials science, and beyond. The advancements in quantum computing technology and algorithmic approaches discussed here highlight the current capabilities and future explorations in the quantum realm.

•Sep 9, 2026•0 citations

Quantum Algorithms with Applications to Simulating Physical Systems

Anirban Ch Narayan Chowdhury

The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.

•Jan 1, 2019•0 citations

Complexity of Quadratic Bosonic Hamiltonian Simulation: BQP-Completeness and PostBQP-Hardness

Lilith Zschetzsche, Refik Mansuroglu, Norbert Schuch

The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are BQP-complete. Importantly, this class includes two known BQP-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a PostBQP-complete problem, which constitutes a jump in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.

quant-pharXiv:2603.26561•Mar 30, 2026•1 citation
Quantum computing is the offspring of quantum mechanics and computer science, two great scientific fields founded in the 20th century. Quantum computing is a relatively young field and is recognized as having the potential to revolutionize science and technology in the coming century. The primary question in this field is essentially to ask which problems are feasible with potential quantum computers and which are not. In this dissertation, we study this question with a physical bent of mind. We apply tools from computer science and mathematical physics to study the complexity of simulating quantum systems. In general, our goal is to identify parameter regimes under which simulating quantum systems is easy (efficiently solvable) or hard (not efficiently solvable). This study leads to an understanding of the features that make certain problems easy or hard to solve. We also get physical insight into the behavior of the system being simulated. In the first part of this dissertation, we study the classical complexity of simulating quantum dynamics. In general, the systems we study transition from being easy to simulate at short times to being harder to simulate at later times. We argue that the transition timescale is a useful measure for various Hamiltonians and is indicative of the physics behind the change in complexity. We illustrate this idea for a specific bosonic system, obtaining a complexity phase diagram that delineates the system into easy or hard for simulation. We also prove that the phase diagram is robust, supporting our statement that the phase diagram is indicative of the underlying physics. In the next part, we study open quantum systems from the point of view of their potential to encode hard computational problems. We study a class of fermionic Hamiltonians subject to Markovian noise described by Lindblad jump operators and illustrate how, sometimes, certain Lindblad operators can induce computational complexity into the problem. Specifically, we show that these operators can implement entangling gates, which can be used for universal quantum computation. We also study a system of bosons with Gaussian initial states subject to photon loss and detected using photon-number-resolving measurements. We show that such systems can remain hard to simulate exactly and retain a relic of the "quantumness" present in the lossless system. Finally, in the last part of this dissertation, we study the complexity of simulating a class of equilibrium states, namely ground states. We give complexity-theoretic evidence to identify two structural properties that can make ground states easier to simulate. These are the existence of a spectral gap and the existence of a classical description of the ground state. Our findings complement and guide efforts in the search for efficient algorithms.
This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable XXX into a sum of nnn iid random variables YiY_iYi​, i.e. X=∑i=1nYiX=\sum_{i=1}^n Y_iX=∑i=1n​Yi​, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.
Simulations play a crucial role in the investigation of complex quantum systems. In this thesis, locality structures of quantum systems are exploited to obtain complexity theoretic results with various physical implications. More specifically, rigorous mathematical tools are used and developed further, to investigate open quantum systems and thermal states. Moreover, important advances in photonic quantum simulations are discussed. For open quantum spin lattice systems new simulation schemes are provided. It is shown that Markovian dynamics can be simulated efficiently in the unitary circuit model, which can be seen as a dissipative Church-Turing type theorem. Moreover, Markovian dynamics is quasi-local and can be locally simulated on classical computers with a cost scaling polynomially in the system size. These results generalize standard tools from the investigation of Hamiltonian systems to open quantum systems. In particular, they provide a rigorous basis for their numerical simulation. However, also a major roadblock for making such simulations reliable is identified: Testing positivity of certain common approximations to mixed quantum states, called matrix product operators, is shown to be NP-hard in the system size and undecidable in the thermodynamic limit. Also more state space structures, originating from the spatial locality structure are discussed: Most states in state space cannot be generated efficiently with local Liouvillian dynamics and pure states generated in real- space renormalization schemes turn out to have local corrections in spatial dimensions larger than one. For thermal states on spin and fermionic lattice systems, a perturbation formula is provided and exponential clustering of correlations at high enough temperature is proven. This has various consequences: It leads to the extension of the concept of intensive temperature to interacting quantum systems, allows for efficient classical local simulations at high enough temperature, provides an upper bound on phase transition temperatures, and implies stability of thermal states against Hamiltonian perturbations. For photonic quantum simulations, sample complexity lower bounds for the verification of Boson-Sampling simulations are explained, which are applicable to a restricted setting. These bounds rely on a lower bound on the min-entropy of the output distribution of Boson-Sampling. This indicates that Boson-Sampling cannot be verified efficiently classically. Complementary to that, a reliable verification scheme for photonic state preparations is discussed, which uses single mode measurements as a simple quantum resource. The verification scheme is efficient for a large class of photonic simulations, including Boson-Sampling experiments with constantly many photons and state preparations necessary for measurement based quantum computing.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.
Quantum simulation involves using a quantum system to study another quantum system. The proposal to simulate quantum physics using quantum mechanical devices, as outlined by Richard Feynman in 1982, stems from classical computers' challenges in simulating quantum systems. The pursuit of simulating complex quantum systems has led to the intersection of quantum mechanics and quantum computing. This offers new opportunities to understand and manipulate the quantum world. Central to describing quantum dynamics is the Hamiltonian operator H^\hat{H}H^, which governs the time evolution of physical systems and serves as the mathematical foundation for quantum simulations. This thesis explores the methodologies and advancements in simulating Hamiltonian operators on quantum computers, focusing on decomposing these operators into quantum gates and the efficiency gains over classical computational approaches. Initially, the thesis explains the fundamental theory and basics of quantum computing. Further it dives into the foundations of the Hamiltonian operator within quantum mechanics, highlighting its role in describing the dynamics of quantum systems. The complexity and high-dimensional nature of Hamiltonian matrices necessitate using quantum computers to simulate quantum phenomena accurately and efficiently. The process of simulating the Hamiltonian operator on a quantum computer involves a detailed examination of the strategies for decomposing the operator into a sequence of quantum gates. This decomposition is crucial for translating the abstract mathematical description of quantum systems into the physical operations of a quantum computer. By utilizing the principles of quantum mechanics, such as superposition and entanglement, quantum gates manipulate qubits to mimic the evolution of quantum states as the Hamiltonian operator dictates. Latter portions of the thesis are dedicated to comparing the efficiency of quantum simulations against traditional classical simulations and inspecting efficient quantum simulations. Quantum computers offer a polynomial or an exponential speedup for certain classes of problems, such as those involving highly entangled quantum states or requiring the simulation of complex quantum dynamics. This advantage is due to the quantum computer's ability to naturally represent and process quantum information - a task for which classical computers require exponential resources as the system size increases. The efficiency of simulating the Hamiltonian operator on a quantum computer is further enhanced through optimization techniques and algorithmic improvements. These include error mitigation strategies and the development of quantum algorithms tailored to specific types of Hamiltonian operators. The thesis presents a comprehensive analysis of these methods, demonstrating how they make quantum simulations more practical and accessible for scientific research and technological development. In conclusion this thesis is a literature review that examines the transformative potential of quantum simulations. By efficiently simulating the Hamiltonian operator on quantum computers researchers can explore quantum phenomena with precision, paving the way for breakthroughs in quantum physics, materials science, and beyond. The advancements in quantum computing technology and algorithmic approaches discussed here highlight the current capabilities and future explorations in the quantum realm.
The simulation of quantum physical systems is expected to be an important application for quantum computers. The work presented in this dissertation aims to improve the resource requirements of quantum computers for solving simulation problems, by providing both novel quantum algorithms and improved implementations of existing ones. I present three main results that cover diverse aspects of simulation including equilibrium physics, the preparation of useful quantum states, and simulations based on classical stochastic processes. The results rely on established quantum algorithms and other recent techniques which I review. My first original contribution is a new quantum algorithm to sample from the thermal Gibbs state of quantum Hamiltonians. The complexity of this algorithm has an exponentially improved dependence on precision compared to an earlier quantum algorithm, and also provides polynomial improvements in other parameters. My second contribution is an improved algorithm to implement reflections about the eigenstates of unitary operators and Hamiltonians, an operation that can be used to prepare ground states of many-body Hamiltonians by quantum amplitude amplification. The improved algorithm for implementing reflections significantly reduces the number of ancilla qubits required over earlier implementations. The improvement relies in part on a novel quantum algorithm for efficiently preparing states with Gaussian-like amplitudes, which may have broad applications. I also prove a lower bound for implementing reflections, which shows that our algorithm is almost optimal. My third and final contribution regards quantum algorithms for classical stochastic processes, which are of importance in statistical physics. I present a quantum algorithm that estimates the average running time of a stochastic process, and provides a quadratic speed-up over a comparable classical algorithm.
The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are BQP-complete. Importantly, this class includes two known BQP-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a PostBQP-complete problem, which constitutes a jump in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.