The evolution of a classically chaotic Hamiltonian system is characterised by a computational complexity that increases exponentially with the time elapsed. Quantum systems do not exhibit such behaviour. It is therefore tempting to solve a classical problem by quantising it and following the motion of a small wavepacket. This paper shows that nothing can be gained by this subterfuge: an adequate quantum simulation requires a Hilbert space whose dimension increases exponentially with the planned duration of the simulation.
The evolution of a classically chaotic Hamiltonian system is characterised by a computational complexity that increases exponentially with the time elapsed. Quantum systems do not exhibit such behaviour. It is therefore tempting to solve a classical problem by quantising it and following the motion of a small wavepacket. This paper shows that nothing can be gained by this subterfuge: an adequate quantum simulation requires a Hilbert space whose dimension increases exponentially with the planned duration of the simulation.
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^, 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.
Quantum devices, such as quantum simulators, quantum annealers, and quantum computers, may be exploited to solve problems beyond what is tractable with classical computers. This may be achieved as the Hilbert space available to perform such `calculations' is far larger than that which may be classically simulated. In practice, however, quantum devices have imperfections, which may limit the accessibility to the whole Hilbert space. We thus determine that the dimension of the space of quantum states that are available to a quantum device is a meaningful measure of its functionality, though unfortunately this quantity cannot be directly experimentally determined. Here we outline an experimentally realisable approach to obtaining the required Hilbert space dimension of such a device to compute its time evolution, by exploiting the thermalization dynamics of a probe qubit. This is achieved by obtaining a fluctuation-dissipation theorem for high-temperature chaotic quantum systems, which facilitates the extraction of information on the Hilbert space dimension via measurements of the decay rate, and time-fluctuations.
Two approaches to quantum-classical correspondence are distinguished according to the classical dynamical theory with which quantum theory is compared. The first of these, Ehrenfest correspondence, defines a dynamical regime in which the quantum expectation values follow approximately a classical trajectory. The second of these, Liouville correspondence, applies when the quantum probability distributions remain well approximated by a density in the classical phase space. The former applies only for narrow states, whereas the latter may remain valid even for quantum states that have spread to the system size. A spin model is adopted for this correspondence study because the quantum state is discrete and finite- dimensional, and thus no artificial truncation of the Hilbert space is required. The quantum time-evolution is given by a discrete unitary mapping. The corresponding classical model is volume-preserving (non-dissipative) and the time-evolution is given by a symplectic map. In classically chaotic regimes, the widths of initially narrow quantum states grow, on average, exponentially with time, until saturation at the system size. This initial spreading rate is well approximated by the classical Lyapunov exponent when the accessible classical phase space is predominantly chaotic. Because of the exponential growth rate of the quantum variance, the Ehrenfest regime is delimited by a break-time that grows logarithmically with increasing quantum numbers. The small differences between quantum expectation values and corresponding Liouville averages of dynamical variables also grow exponentially, initially, if the classical behaviour is chaotic. This exponential rate is independent of h and consistently larger than the classical Lyapunov exponent by at least a factor of two. Interestingly, this exponential growth rate does not continue until these differences approach magnitudes of order the system size, but crosses over to power-law growth (or simply saturates), when the differences have reached magnitudes no larger than order ħ. Because of the exponential growth of these quantum-classical differences, the Liouville regime is also delimited by a break-time that grows logarithmically with increasing quantum numbers. However, due to the early saturation of the exponential growth of the differences, the Liouville log break-time applies only in a restricted domain. After spreading to the system size, the quantum states relax to an approximately time-independent state. This is characterised by equilibrium distributions that are subject to rapidly oscillating fluctuations about the coarse-grained classical steady-state. If the accessible classical phase space is predominantly chaotic, then the equilibrium quantum probability distributions are nearly microcanonical. Otherwise the steady-state quantum probability distributions accurately reflect the details of the KAM surfaces in the classical phase space. The equilibrium regime quantum fluctuations, which are quantum-classical differences, are shown to approach zero as a negative power of the quantum numbers. Since the differences between quantum expectation values and individual classical trajectories grow exponentially in time to a magnitude that scales with the system size, the Ehrenfest regime is delimited by an unrestricted log break-time. The log break-time may be short compared to experimental time-scales for some chaotic macroscopic bodies, and, as a result, an observable breakdown of Ehrenfest correspondence may arise for some macroscopic systems. Although the Liouville regime is also delimited by a log break-time, an observable breakdown of correspondence between quantum mechanics and Liouville mechanics for macroscopic bodies is not likely since their differences, expressed relative to the dimensions of the observable, approach zero in the limit of large quantum numbers.
We investigate the limitations of quantum computers for solving nonlinear dynamical systems. In particular, we tighten the worst-case bounds of the quantum Carleman linearisation (QCL) algorithm [Liu et al., PNAS 118, 2021] answering one of their open questions. We provide a further significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector. Given a natural choice of coordinates for a dynamical system with one or more positive Lyapunov exponents and solutions that grow sub-exponentially, we prove that any such algorithm has complexity scaling at least exponentially in the integration time. As such, an efficient quantum algorithm for simulating chaotic systems or regimes is likely not possible.
The relationship between chaos and quantum mechanics has been somewhat uneasy--even stormy, in the minds of some people. However, much of the confusion may stem from inappropriate comparisons using formal analyses. In contrast, our starting point here is that a complete dynamical description requires a full understanding of the evolution of measured systems, necessary to explain actual experimental results. This is of course true, both classically and quantum mechanically. Because the evolution of the physical state is now conditioned on measurement results, the dynamics of such systems is intrinsically nonlinear even at the level of distribution functions. Due to this feature, the physically more complete treatment reveals the existence of dynamical regimes--such as chaos--that have no direct counterpart in the linear (unobserved) case. Moreover, this treatment allows for understanding how an effective classical behavior can result from the dynamics of an observed quantum system, both at the level of trajectories as well as distribution functions. Finally, we have the striking prediction that time-series from measured quantum systems can be chaotic far from the classical regime, with Lyapunov exponents differing from their classical values. These predictions can be tested in next-generation experiments.