Feynman gave in 1982 a keynote speech \textit{Simulating Physics with Computers} (Int. J. Theor. Phys. {\bf 21}, 467 (1982)) in which he talked ``...about the possibility...that the computer will do exactly the same as nature". The motivation was that: ``...the physical world is quantum mechanical, and therefore the proper problem is the simulation of quantum physics". Here I try after more than forty years to answer Feynman's question of whether it is possible to perform exact computer simulations. Many computer simulations are not exact, they contain mean field approximations that disobey the symmetry in the quantum dynamics with Newton's third law, e.g. almost all astrophysical simulations of galaxy systems. After a review of computer simulations and the problems of simulating real systems, I argue that Newton's discrete dynamics, which is used in almost all computer simulations and which is exact in the same sense as Newton's analytic dynamics, is the classical limit path of Feynman's quantum paths. However, the physical world is not known exactly and it is much more complex than any simulated systems, and so far no real systems have been simulated exactly. Hence, more than forty years later, and after hundreds of thousands of computer simulations of the physical system's dynamics the answer to Feynman's question is still negative. But although it is not possible to simulate the dynamics exactly for any real systems, the simulations have been and will be of great use in Natural Science.
Feynman gave in 1982 a keynote speech \textit{Simulating Physics with Computers} (Int. J. Theor. Phys. {\bf 21}, 467 (1982)) in which he talked ...about the possibility...that the computer will do exactly the same as nature". The motivation was that: ...the physical world is quantum mechanical, and therefore the proper problem is the simulation of quantum physics". Here I try after more than forty years to answer Feynman's question of whether it is possible to perform exact computer simulations. Many computer simulations are not exact, they contain mean field approximations that disobey the symmetry in the quantum dynamics with Newton's third law, e.g. almost all astrophysical simulations of galaxy systems. After a review of computer simulations and the problems of simulating real systems, I argue that Newton's discrete dynamics, which is used in almost all computer simulations and which is exact in the same sense as Newton's analytic dynamics, is the classical limit path of Feynman's quantum paths. However, the physical world is not known exactly and it is much more complex than any simulated systems, and so far no real systems have been simulated exactly. Hence, more than forty years later, and after hundreds of thousands of computer simulations of the physical system's dynamics the answer to Feynman's question is still negative. But although it is not possible to simulate the dynamics exactly for any real systems, the simulations have been and will be of great use in Natural Science.
This chapter describes the possibility of simulating physics in the classical approximation, a thing which is usually described by local differential equations. But the physical world is quantum mechanical, and therefore the proper problem is the simulation of quantum physics. A computer which will give the same probabilities as the quantum system does. The present theory of physics allows space to go down into infinitesimal distances, wavelengths to get infinitely great, terms to be summed in infinite order, and so forth; and therefore, if this proposition is right, physical law is wrong. Quantum theory and quantizing is a very specific type of theory. The chapter talks about the possibility that there is to be an exact simulation, that the computer will do exactly the same as nature. There are interesting philosophical questions about reasoning, and relationship, observation, and measurement and so on, which computers have stimulated people to think about anew, with new types of thinking.
The question "What is real?" can be traced back to the shadows in Plato's cave. Two thousand years later, Rene Descartes lacked knowledge about arguing against an evil deceiver feeding us the illusion of sensation. Descartes' epistemological concept later led to various theories of sensory experiences. The concept of "illusionism", proposing that even the very conscious experience we have is an illusion, is not only a red-pill scenario found in the 1999 science fiction movie "The Matrix" but is also a philosophical concept promoted by modern tinkers, most prominently by Daniel Dennett. Reflection upon a possible simulation and our perceived reality was beautifully visualized in "The Matrix", bringing the old ideas of Descartes to coffee houses around the world. Irish philosopher Bishop Berkeley was the father of what was later coined as "subjective idealism", basically stating that "what you perceive is real". With the advent of quantum technologies based on the control of individual fundamental particles, the question of whether our universe is a simulation isn't just intriguing. Our ever-advancing understanding of fundamental physical processes will likely lead us to build quantum computers utilizing quantum effects for simulating nature quantum-mechanically in all complexity, as famously envisioned by Richard Feynman. In this article, we outline constraints on the limits of computability and predictability in/of the universe, which we then use to design experiments allowing for first conclusions as to whether we participate in a simulation chain. Eventually, in a simulation in which the computer simulating a universe is governed by the same physical laws as the simulation, the exhaustion of computational resources will halt all simulations down the simulation chain unless an external programmer intervenes, which we may be able to observe.
Quantum mechanics occupies a unique position in the history of science. It has survived all experimental tests to date, culminating with the most precise comparison of any measurement to any theory – a 1987 measurement of the electron's magnetic moment, or gyromagnetic ratio g e = 2.002 319 304 39 (Van Dyck et al. 1987), agreeing with QED theory to 12 digits. Despite this and other dramatic successes of quantum mechanics, its foundations are often questioned, owing to the glaring difficulties in reconciling quantum physics with the classical laws of physics that govern macroscopic bodies. If quantum mechanics is indeed a complete theory of nature, why does it not apply to everyday life? Even Richard Feynman (1982), a fierce defender of quantum mechanics, memorably stated that: We have always had a great deal of difficulty in understanding the world view that quantum mechanics represents … Okay, I still get nervous with it … It has not yet become obvious to me that there is no real problem. I cannot define the real problem, therefore I suspect there's no real problem, but I'm not sure there's no real problem. In the dawn of the twenty-first century, John A. Wheeler's big question “Why the quantum?” has returned to the forefront of physics with full steam. Advances in experimental physics are beginning to realize the same thought-experiments that proved helpful to Einstein, Bohr, Heisenberg, Schrödinger, and the other founders of quantum mechanics.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
Envisioned by Richard Feynman in the early 1980s, quantum simulation has received dramatic impetus thanks to the development of a variety of plateforms able to emulate a wide class of quantum Hamiltonians.During the past decade, most of the quantum simulators have implemented rather well-known models, hence permitting a direct comparison with theoretical calculations and a precise benchmarking of their reliability.The field has now reached a maturity such that one can address difficult problems, which cannot be solved efficiently using classical algorithms.These advances provide unprecedented opportunities to explore previously unreachable fields, test theoretical predictions, and inspire novel approaches.This contribution is an elementary introduction to quantum simulation.We discuss the challenges, define both digital and analog quantum simulators, and list the demanding conditions they require.We also provide a brief account of the contributions gathered in the dossier on Quantum simulation in the Compte rendus Physique of the French Academy of Sciences [1][2][3][4][5][6].The latter completes excellent reviews that appeared previously, see for instance . Universal models and the role of simulations in many-body physicsUnderstanding the behavior of macroscopic quantum systems is a major challenge of modern physics.The basic laws of low-energy physics are by now quite well known at the microscopic, say atomic, scale.Conversely, many fundamental questions remain open, and even debated, about the collective dynamics at the macroscopic scale.By "macroscopic scale", here we mean systems made up of a huge number of constituents, or degrees of freedom, say 10 6 , 10 23 , or even more, as relevant in condensed matter physics or in astrophysics, for instance.Such huge systems cannot be treated exactly, be it a the classical level and, even worse, at the quantum level.Yet, it is the main outcome of the thermodynamic approach that the collective behavior of a macroscopic system can drastically differ from that of its elementary constituents.For instance, the elementary interactions between the H 2 O molecules are fundamentally unchanged when a water bucket turns from the liquid phase to the solid phase at zero degree Celsius.Similarly, the interactions between the microscopic magnetic moments do not show any brutal change when a magnetic material gets magnetized underneath the Curie temperature.Hence, the dramatic effects observed in macroscopic systems are governed by large-scale instabilities, without obvious counterparts at the microscopic level.This observation takes a universal character, summarized in the celebrated motto "More is Different" [15].Such so-called emerging phenomena also appear in quantum systems, where new effects that are impossible in the classical world show up below some critical temperature or at zero temperature when some interaction parameter passes through a critical value.Celebrated examples include the superfluid transition in helium or super-conducting transitions and other metal-insulator transitions in electronic systems.Strikingly enough at first sight, while emerging phenomena only appear in very large scale macroscopic systems, their germs are contained in the mutual interactions of their elementary constituents.Hence, local two-body interactions are sufficient to explain a huge class of phase transitions, such as the liquid-solid and magnetic transitions mentioned above.The Boltzmann statistical approach proved particularly successful in describing this connection between the microscopic and macroscopic scales.To understand emerging phenomena on grounds as fundamental as possible, the programme is now well established: One tries to identify the basic microscopic terms that seem to be relevant and disregards all the other microscopic details.One then elaborates a model, as generic as possible, likely to reproduce the main experimental observations.The most usual examples are the Ising and Heisenberg models for magnetic transitions, or the Hubbard model for metal-insulator transitions [16][17][18].Then all is left to do is to check that the phenomenon of interest indeed emerges from the dynamics of the simplified model.The realization of this programme is nothing but a simulation.It consists in building up a simplified system that mimics the main properties of a real system.
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.