A concept of computational complexity is applied for analysis of classical and quantum dynamical systems. It is argued that evolution of wave functions in nonintegrable quatnum systems lies in complexity class EXP because of rapid growth of number of elementary computational operations needed to predict their future. On the other hand, evolution of wave functions in integrable systems can be predicted by the fast algorithms and thus it belongs to P class. This difference between integrable and nonintegrable systems in our approahc looks identically for classical and quantum systems. In this paper an informational approach is applied for analysis of dynamics in classical and quantum systems to find a universal different between integrable and nonintegrable motion. As a basic tool to analyze compleixty of dynamics we use a number of elementary computational operations O(T) (computational complexity) needed to determine a state of a sytem for time interval T.
A concept of computational complexity is applied for analysis of classical and quantum dynamical systems. It is argued that evolution of wave functions in nonintegrable quatnum systems lies in complexity class EXP because of rapid growth of number of elementary computational operations needed to predict their future. On the other hand, evolution of wave functions in integrable systems can be predicted by the fast algorithms and thus it belongs to P class. This difference between integrable and nonintegrable systems in our approahc looks identically for classical and quantum systems. In this paper an informational approach is applied for analysis of dynamics in classical and quantum systems to find a universal different between integrable and nonintegrable motion. As a basic tool to analyze compleixty of dynamics we use a number of elementary computational operations O(T) (computational complexity) needed to determine a state of a sytem for time interval T.
It is shown that evolution of wave functions in nonintegrable quantum systems is unpredictable for a long time T because of rapid growth of number of elementary computational operations O(T)∼Tα. On the other hand, the evolution of wave functions in integrable systems can be predicted by the fast algorithms O(T)∼(log2T)β for logarithmically short time and thus there is an algorithmic "compressibility" of their dynamics. The difference between integrable and nonintegrable systems in our approach looks identically for classical and quantum systems. Therefore the minimal number of bit operations O(T) needed to predict a state of system for time interval T can be used as universal sign of chaos.
We study the Hamiltonian-independent contribution to the complexity of quantum optimal control problems. The optimization of controls that steer quantum systems to desired objectives can itself be considered a classical dynamical system that executes an analog computation. The system-independent component of the equations of motion of this dynamical system can be integrated analytically for various classes of discrete quantum control problems. For the maximization of observable expectation values from an initial pure state and the maximization of the fidelity of quantum gates, the time complexity of the corresponding computation belongs to the class continuous log (CLOG), the lowest analog complexity class, equivalent to the discrete complexity class NC. The simple scaling of the Hamiltonian-independent contribution to these problems with quantum system dimension indicates that with appropriately designed search algorithms, quantum optimal control can be rendered efficient even for large systems.
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.
We study the Hamiltonian dynamics of a many-body quantum system subjected to periodic projective measurements, which leads to probabilistic cellular automata dynamics. Given a sequence of measured values, we characterize their dynamics by performing a principal component analysis (PCA). The number of principal components required for an almost complete description of the system, which is a measure of complexity we refer to as PCA complexity, is studied as a function of the Hamiltonian parameters and measurement intervals. We consider different Hamiltonians that describe interacting, noninteracting, integrable, and nonintegrable systems, including random local Hamiltonians and translational invariant random local Hamiltonians. In all these scenarios, we find that the PCA complexity grows rapidly in time before approaching a plateau. The dynamics of the PCA complexity can vary quantitatively and qualitatively as a function of the Hamiltonian parameters and measurement protocol. Importantly, the dynamics of PCA complexity present behavior that is considerably less sensitive to the specific system parameters for models which lack simple local dynamics, as is often the case in nonintegrable models. In particular, we point out a figure of merit that considers the local dynamics and the measurement direction to predict the sensitivity of the PCA complexity dynamics to the system parameters.
Based on the concepts of integrability and nonintegrability of a quantum system presented in a previous paper [Zhang, Feng, Yuan, and Wang, Phys. Rev. A 40, 438 (1989)], a realization of the dynamics in the quantum phase space is now presented. For a quantum system with dynamical group scrG and in one of its unitary irreducible-representation carrier spaces ${\mathit{gerh}}_{\mathrm{\ensuremath{\Lambda}}}$, the quantum phase space is a 2${\mathit{M}}_{\mathrm{\ensuremath{\Lambda}}}$-dimensional topological space, where ${\mathit{M}}_{\mathrm{\ensuremath{\Lambda}}}$ is the quantum-dynamical degrees of freedom. This quantum phase space is isomorphic to a coset space scrG/scrH via the unitary exponential mapping of the elementary excitation operator subspace of scrg (algebra of scrG), where scrH (\ensuremath{\subset}scrG) is the maximal stability subgroup of a fixed state in ${\mathit{gerh}}_{\mathrm{\ensuremath{\Lambda}}}$. The phase-space representation of the system is realized on scrG/scrH, and its classical analogy can be obtained naturally. It is also shown that there is consistency between quantum and classical integrability. Finally, a general algorithm for seeking the manifestation of ``quantum chaos'' via the classical analogy is provided. Illustrations of this formulation in several important quantum systems are presented.
We devote our studies to the subject of weakly nonintegrable dynamics of systems with a macroscopic number of degrees of freedom. Our main points of interest are the relations between the timescales of thermalization and the timescales of chaotization; the choice of appropriate observables and the structure of equations coupling them; identifying the classes of weakly nonintegrable dynamics and developing tools to diagnose the properties specific to such classes. We discuss the traditional in the field methods for thermalization timescale computation and employ them to study the scaling the timescale with the proximity to the integrable limit. We then elaborate on a novel framework based on the full Lyapunov spectra computation for large systems as a powerful tool for the characterization of weak nonintegrability. In particular, the Lyapunov spectrum scaling offers a quantitative description allowing us to infer the structure of the underlying network of observables. Proximity to integrable limit is associated with the rapid growth of thermalization timescales and, thus, potential numerical challenges. We solve these challenges by performing numerical tests using computationally efficient model - unitary maps. The great advantage of unitary maps for numerical applications is time-discrete error-free evolution. We use these advantages to perform large timescale and system size computations in extreme proximity to the integrable limit. To demonstrate the scope of obtained results we report on the application of the developed framework to Hamiltonian systems.