The ability of quantum systems to host exponentially complex dynamics has the potential to revolutionize science and technology. Therefore, much effort has been devoted to developing of protocols for computation, communication and metrology, which exploit this scaling, despite formidable technical difficulties. Here we show that the mere frequent observation of a small part of a quantum system can turn its dynamics from a very simple one into an exponentially complex one, capable of universal quantum computation. After discussing examples, we go on to show that this effect is generally to be expected: almost any quantum dynamics becomes universal once 'observed' as outlined above. Conversely, we show that any complex quantum dynamics can be 'purified' into a simpler one in larger dimensions. We conclude by demonstrating that even local noise can lead to an exponentially complex dynamics.
The ability of quantum systems to host exponentially complex dynamics has the potential to revolutionize science and technology. Therefore, much effort has been devoted to developing of protocols for computation, communication and metrology, which exploit this scaling, despite formidable technical difficulties. Here we show that the mere frequent observation of a small part of a quantum system can turn its dynamics from a very simple one into an exponentially complex one, capable of universal quantum computation. After discussing examples, we go on to show that this effect is generally to be expected: almost any quantum dynamics becomes universal once 'observed' as outlined above. Conversely, we show that any complex quantum dynamics can be 'purified' into a simpler one in larger dimensions. We conclude by demonstrating that even local noise can lead to an exponentially complex dynamics.
The Exponential scaling is a defining characteristic of quantum science that underpins both its transformative computational potential and its profound theoretical challenges. Unlike classical systems whose state spaces typically scale linearly or polynomially with system size, quantum systems exhibit exponential growth of Hilbert space dimensionality as the number of quantum degrees of freedom increases. This scaling governs quantum information storage, entanglement complexity, quantum simulation capabilities, and the difficulty of classical emulation of quantum phenomena. This article examines the physical origins of exponential scaling, its implications across quantum computing, quantum many-body physics, quantum sensing, and quantum communication, and the emerging strategies developed to harness or mitigate exponential complexity. The discussion highlights how exponential scaling simultaneously represents the power and the bottleneck of modern quantum technologies.
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.
One of the greatest challenges in the fields of quantum information processing and quantum technologies is the detailed coherent control over each and every constituent of quantum systems with an ever increasing number of particles. Within this endeavor, harnessing of many-body entanglement against the detrimental effects of the environment is a major pressing issue. Besides being an important concept from a fundamental standpoint, entanglement has been recognized as a crucial resource for quantum speed-ups or performance enhancements over classical methods. Understanding and controlling many-body entanglement in open systems may have strong implications in quantum computing, quantum simulations of many-body systems, secure quantum communication or cryptography, quantum metrology, our understanding of the quantum-to-classical transition, and other important questions of quantum foundations.In this paper we present an overview of recent theoretical and experimental efforts to underpin the dynamics of entanglement under the influence of noise. Entanglement is thus taken as a dynamic quantity on its own, and we survey how it evolves due to the unavoidable interaction of the entangled system with its surroundings. We analyze several scenarios, corresponding to different families of states and environments, which render a very rich diversity of dynamical behaviors.In contrast to single-particle quantities, like populations and coherences, which typically vanish only asymptotically in time, entanglement may disappear at a finite time. In addition, important classes of entanglement display an exponential decay with the number of particles when subject to local noise, which poses yet another threat to the already-challenging scaling of quantum technologies. Other classes, however, turn out to be extremely robust against local noise. Theoretical results and recent experiments regarding the difference between local and global decoherence are summarized. Control and robustness-enhancement techniques, scaling laws, statistical and geometrical aspects of multipartite-entanglement decay are also reviewed; all in order to give a broad picture of entanglement dynamics in open quantum systems addressed to both theorists and experimentalists inside and outside the field of quantum information.
One of the greatest challenges in the fields of quantum information processing and quantum technologies is the detailed coherent control over each and every constituent of quantum systems with an ever increasing number of particles. Within this endeavor, harnessing of many-body entanglement against the detrimental effects of the environment is a major pressing issue. Besides being an important concept from a fundamental standpoint, entanglement has been recognized as a crucial resource for quantum speed-ups or performance enhancements over classical methods. Understanding and controlling many-body entanglement in open systems may have strong implications in quantum computing, quantum simulations of many-body systems, secure quantum communication or cryptography, quantum metrology, our understanding of the quantum-to-classical transition, and other important questions of quantum foundations. In this paper we present an overview of recent theoretical and experimental efforts to underpin the dynamics of entanglement under the influence of noise. Entanglement is thus taken as a dynamic quantity on its own, and we survey how it evolves due to the unavoidable interaction of the entangled system with its surroundings. We analyze several scenarios, corresponding to different families of states and environments, which render a very rich diversity of dynamical behaviors. In contrast to single-particle quantities, like populations and coherences, which typically vanish only asymptotically in time, entanglement may disappear at a finite time. In addition, important classes of entanglement display an exponential decay with the number of particles when subject to local noise, which poses yet another threat to the already-challenging scaling of quantum technologies. Other classes, however, turn out to be extremely robust against local noise. Theoretical results and recent experiments regarding the difference between local and global decoherence are summarized. Control and robustness- enhancement techniques, scaling laws, statistical and geometrical aspects of multipartite-entanglement decay are also reviewed; all in order to give a broad picture of entanglement dynamics in open quantum systems addressed to both theorists and experimentalists inside and outside the field of quantum information.
A significant amount of research is currently devoted to quantum technologies, i.e., technologies that harness the complex features of quantum systems for practical purposes. Remarkably, these have the potential to shape the way we will live in the future by, for example, providing new ways of breaking the current cryptographic security measures or by exponentially enhancing the computational capability of computers. This, in turn, could serve as a means for studying phenomena so complex that they render classical computers completely unusable. With these promises at hand, methods that efficiently certify the correct functioning of quantum devices and computations become of paramount importance. Specifically, it is often required to assess a characterization of the quantum states that come out from a specific computation or experiment. The traditional method of quantum state tomography relies on a rather straightforward but brute-force approach to reconstruct the full density matrix that encodes a quantum state. This method is highly demanding because of the curse of dimensionality, according to which the number of required measurements scales with the system’s dimension, and thus exponentially with the number of qubits. As the quantum protocols demand a progressively higher number of qubits, overall, a complete characterization of quantum states through tomography loses its effectiveness, thus calling for a partial but simpler reconstruction of states. Furthermore, an additional obstacle must be taken into account. In particular, the same complex features of the quantum realm that would help to navigate through the sea of potential applications hinder a growth of the current technological state of the art, which indeed is limited within the so-called NISQ (Noisy Intermediate-Scale Quantum) devices. These, as the name suggests, are characterized by inevitable noises and imperfections, and as such are not advanced enough for achieving a real quantum advantage in the near term. In this Thesis we are going to discuss new techniques for the estimation of properties of unknown quantum states in the context of quantum information science. The protocols that we will present are flexible enough to not only include state tomography within them, but to also adapt to noises and imperfections present in the computational devices. Ivan Palmisano was funded by the CITI-GENS project. This project received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions COFUND Action (Grant Agreement No 945231). All views expressed in this article are strictly those of the author and may under no circumstances be regarded as an official position of the European Research Executive Agency or the European Commission.
The simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.