Classical Simulation of Quantum Systems?

    James Franson
    • Physics Department, University of Maryland Baltimore County, Baltimore, MD 21250, USA
Physics 9, 66
Richard Feynman suggested that it takes a quantum computer to simulate large quantum systems, but a new study shows that a classical computer can work when the system has loss and noise.
R. A. Brewster and J. D. Franson [6]
Figure 1: The Wigner quasiprobability distribution W(x,y) for a quantum state containing two photons. The dimensionless parameters x and y correspond to the two phase quadratures of the electromagnetic field. The presence of negative values, which cannot occur for a true probability distribution, illustrates the quantum-mechanical properties of the system. Rahimi-Keshari et al. [2] used an approach based on Wigner distributions to show that the quantum process of boson sampling could be simulated classically if the system in which the process takes place has sufficiently large loss and noise.

The field of quantum computing originated with a question posed by Richard Feynman. He asked whether or not it was feasible to simulate the behavior of quantum systems using a classical computer, suggesting that a quantum computer would be required instead [1]. Saleh Rahimi-Keshari from the University of Queensland, Australia, and colleagues [2] have now demonstrated that a quantum process that was believed to require an exponentially large number of steps to simulate on a classical computer could in fact be simulated in an efficient way if the system in which the process occurs has sufficiently large loss and noise.

The quantum process considered by Rahimi-Keshari et al. is known as boson sampling, in which the probability distribution of photons (bosons) that undergo a linear optical process [3] is measured or sampled. In experiments of this kind [4, 5], N single photons are sent into a large network of beams splitters (half-silvered mirrors) and combined before exiting through M possible output channels. The calculation of the probability distribution for finding the photons in each of the M output channels is equivalent to calculating the permanent of a matrix. The permanent is the same as the more familiar determinant but with all of the minus signs replaced with plus signs. On any classical computer, the number of computational steps required to calculate the permanent of a matrix is believed to increase exponentially with increasing values of M [3], which would make the problem impossible to solve for large values of M.

Rahimi-Keshari and colleagues argue that simulating boson-sampling experiments is not as difficult as calculating the permanent of a matrix if the loss and noise in the experiments are sufficiently large. Their theoretical proof is based on the use of quasiprobability distributions [6, 7], such as the Wigner distribution. As a simple example, the Wigner distribution for a state containing two photons in a single channel is shown in Fig. 1. Quasiprobability distributions have many of the same properties as classical probability distributions, but the Wigner distribution can have negative values, which demonstrates the quantum-mechanical nature of the system. The researchers showed that, for sufficiently large loss and noise, the Wigner distribution describing the photons was positive and, therefore, that the results of the experiment could be simulated classically without requiring an exponentially large number of computational steps.

This proof does not overturn Feynman’s suggestion about the need for quantum simulation in general but clarifies when it applies. A boson-sampling system is a simple but representative case of a quantum system that, when large enough, is seemingly unsolvable with a classical computer. Rahimi-Keshari and co-workers’ study is significant in that it provides upper bounds on the experimental conditions in order for that to be the case.

These results are closely related to the fact that the experimental errors in a quantum computer must be sufficiently small in order to perform quantum error correction. The information in a quantum computer is represented by qubits, which can take on various physical forms, including single photons, trapped ions, electronic spins, and superconducting Josephson junctions. Error correction involves identifying and correcting experimental errors that affect the fragile states of the qubits without disturbing their values. Protocols for quantum error correction have a maximum allowed error rate, which is typically calculated using a “top-down” approach that uses quantum information techniques that are independent of the physical nature of the qubits. The methods used by Rahimi-Keshari et al. might allow a “bottom-up” approach in which the physical properties of the qubits themselves can be used to bound the maximum error rate for a quantum computation that cannot be simulated classically.

Experimental tests of nonlocality typically involve mathematical inequalities that bound the predictions of classical field theories [8] or local hidden variable theories. [9]. Quantum mechanics predicts the violation of these inequalities, but this can only be observed if the experimental errors are sufficiently small, which is similar to the situation for boson sampling or quantum computing. To date, these inequalities have applied only to specific experimental setups, such as tests of Bell’s inequality [9]. It may be possible to apply the techniques used in the study by Rahimi-Keshari and co-workers to derive other types of inequalities or more general bounds on the predictions of any classical theory.

Quantum computers are expected to be able to solve certain problems that are not feasible on a classical computer, such as factoring large integers. To the best of my knowledge, there is no rigorous proof that quantum computers can provide an exponential speed-up compared to classical computers [10]. For example, the argument that boson sampling cannot be simulated classically (even in the limit of no experimental errors) is based on the assumption that various computational complexity classes are not equivalent [3]; certain kinds of calculations require many more steps than others using the best-known algorithms, and this is believed to be true for any algorithm. Perhaps Rahimi-Keshari and colleagues’ approach could be used to avoid the need for this assumption. That would be an important step towards answering Feynman’s original question [1] in a more rigorous way.

This research is published in Physical Review X.


  1. R. P. Feynman, “Simulating Physics with Computers,” Int. J. Theor. Phys 21, 467 (1982).
  2. S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves, “Sufficient Conditions for Efficient Classical Simulation of Quantum Optics,” Phys. Rev. X 6, 021039 (2016).
  3. S. Aaronson and A. Arkhipov, “The Computational Complexity of Linear Optics,” in Proceedings of the ACM Symposium on the Theory of Computing, STOC (Association for Computing Machinery, New York, 2011), p. 33[Amazon][WorldCat].
  4. J. B. Spring et al., “Boson Sampling on a Photonic Chip,” Science 339, 798 (2013).
  5. M. Tillmann, B. Dakic, R. Heilmann, S. Nolte, A. Szameit, and P. Walther, “Experimental Boson Sampling,” Nature Photon. 7, 540 (2013).
  6. R. A. Brewster and J. D. Franson, “Generalized Delta Functions and Their Use in Quasi-Probability Distributions,” arXiv:1605.04321.
  7. W. P. Schleich, Quantum Optics in Phase Space (Wiley-VCH, Berlin, 2001)[Amazon][WorldCat].
  8. J. D. Franson, “Violations of a Simple Inequality for Classical Fields,” Phys. Rev. Lett. 67, 290 (1991).
  9. J. S. Bell, “On the Einstein Podolsky Rosen Paradox,” Physics (Long Island City) 1, 195 (1964).
  10. M. J. Bremner, R. Jozsa, and D. J. Shepherd, “Classical Simulation of Commuting Quantum Computations Implies Collapse of the Polynomial Hierarchy,” Proc. R. Soc. London A 467, 459 (2010).

About the Author

Image of James Franson

James Franson received his Ph.D. from the California Institute of Technology and was previously at the Johns Hopkins University Applied Physics Laboratory. He is now a professor of physics at the University of Maryland Baltimore County (UMBC). His research interests include nonlocal interferometry, quantum optics, and quantum communications. He is a Fellow of the American Physical Society and the Optical Society of America. In 2008 he was recognized as an Outstanding Referee by the American Physical Society.

Read PDF

Subject Areas

Quantum PhysicsOpticsQuantum Information

Related Articles

How to Speed up a Quantum Network
Quantum Information

How to Speed up a Quantum Network

Sending photons to a remote site in groups should allow quantum links to be more rapidly established across future quantum networks than if photons are sent one at a time. Read More »

Stiffening a Spring Made of Light

Stiffening a Spring Made of Light

Adding a nonlinear crystal to an optical spring can change the spring’s stiffness, a finding that could allow the use of such devices as gravitational-wave detectors. Read More »

Shielding Quantum Light in Space and Time
Quantum Physics

Shielding Quantum Light in Space and Time

A way to create single photons whose spatiotemporal shapes do not expand during propagation could limit information loss in future photonic quantum technologies. Read More »

More Articles