Abstract
We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P#P=BPPNP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation.
Keywords
Quantum computerHierarchyComputer scienceComputationPolynomial hierarchyTime complexityComputational complexity theoryPolynomialQuantumTheoretical computer scienceAlgorithmMathematicsQuantum mechanicsPhysicsMathematical analysis
Affiliated Institutions
Related Publications
Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
A line of work initiated by Terhal and DiVincenzo [Terhal/DiVincenzo, arXiv, 2002] and Bremner, Jozsa, and Shepherd [Bremner/Jozsa/Sheperd, Proc. Royal Soc. A, 2010], shows that...
Quantum circuit complexity
We propose a complexity model of quantum circuits analogous to the standard (acyclic) Boolean circuit model. It is shown that any function computable in polynomial time by a qua...
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such de...
Quantum advantage with shallow circuits
Quantum outperforms classical Quantum computers are expected to be better at solving certain computational problems than classical computers. This expectation is based on (well-...
A Study of Complex Deep Learning Networks on High-Performance, Neuromorphic, and Quantum Computers
Current deep learning approaches have been very successful using convolutional neural networks trained on large graphical-processing-unit-based computers. Three limitations of t...
Publication Info
- Year
- 2011
- Type
- article
- Pages
- 333-342
- Citations
- 811
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
811
OpenAlex
Cite This
Scott Aaronson,
A. A. Архипов
(2011).
The computational complexity of linear optics.
, 333-342.
https://doi.org/10.1145/1993636.1993682
Identifiers
- DOI
- 10.1145/1993636.1993682