CoChat
Sign Up
Cited by 874Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyComplexity and Algorithms in Graphs

The computational complexity of linear optics

Open access
Aaronson, Scott, Arkhipov, Alex·2011·Proceedings of the forty-third annual ACM symposium on Theory of computing
DOI 10.1145/1993636.1993682
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/1993636.1993682

Cites

85 of 85 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Correlations resulting from quantum interference of multiple indistinguishable non-interacting bosons in large linear optical circuits cannot be efficiently simulated with classical computers.

    “Correlations resulting from quantum interference of multiple indistinguishable non-interacting bosons in large linear optical circuits cannot be efficiently simulated with classical computers192021.”

    From Observing fermionic statistics with photons in arbitrary processes (2013) · cites this paper as [20]

    The Abstract and §1.1 describe a model of identical, noninteracting photons passing through a linear-optical network and give evidence that sampling its output is hard to simulate classically. The claim overstates the result as unconditional: the paper says classical intractability rests on plausible complexity assumptions, and its approximate-simulation result requires two unproven conjectures. Page numbers are unavailable in our copy. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • Correlations resulting from quantum interference of multiple indistinguishable non-interacting bosons in large linear optical circuits cannot be efficiently simulated with classical computers.

    “Correlations resulting from quantum interference of multiple indistinguishable non-interacting bosons in large linear optical circuits cannot be efficiently simulated with classical computers192021.”

    From Observing fermionic statistics with photons in arbitrary processes (2013) · cites this paper as [21]

    Section 1.1 describes identical, noninteracting photons passing through a linear-optical network, and Section 1.2.1 gives a hardness result for exact classical sampling. But the claim’s unqualified “cannot be efficiently simulated” overstates the paper: the exact result depends on avoiding a collapse of the polynomial hierarchy, while Section 1.2.2 says the argument for approximate simulation still has a gap. (LLM, conf=0.87)

    Experimental — accuracy not yet measured

  • Both GBS and CV-IQP circuits have been shown to be intractable to simulate classically.

    “Both GBS [106,110] and CV-IQP circuits [109,111] have been shown to be intractable to simulate classically.”

    From Continuous-variable quantum neural networks (2019) · cites this paper as [110]

    Section 1.2, “Our Results” (page unavailable), gives hardness results for classical simulation of BosonSampling with the paper’s photon-input model. It does not establish that Gaussian boson sampling (GBS) is hard to simulate. The citation is attached to GBS, not CV-IQP, so the paper’s discussion of other quantum circuits does not support the CV-IQP part of the sentence. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • The existence of an efficient classical algorithm for sampling from the boson sampling distribution implies the existence of a classically efficient algorithm for the calculation of the permanent of a related matrix.

    “Aaronson and Arkhipov found that the existence of an efficient classical algorithm for sampling from the distribution implies the existence of a classically efficient algorithm for the calculation of the permanent of a related matrix.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Aaronson and Arkhipov, 2011

    Theorem 3 states that an efficient classical approximate sampler would make estimation of the squared magnitude of a related Gaussian matrix’s permanent solvable in BPP with an NP oracle. Section 1.2.1 likewise connects exact classical sampling to approximating a #P-hard probability using an NP oracle. Neither result establishes an ordinary efficient classical algorithm for calculating the permanent itself. (LLM, conf=0.90)

    Experimental — accuracy not yet measured

  • Boson sampling was first proposed as a candidate for quantum computational supremacy by Aaronson and Arkhipov 2011.

    “Boson sampling was first proposed as a candidate for quantum computational supremacy by (Aaronson and Arkhipov, 2011).”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Aaronson and Arkhipov, 2011

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Related

Authors
Aaronson, S., & Arkhipov, A.
Affiliations
Massachusetts Institute of Technology (US)
ORCID
Aaronson, Scott
Venue
Proceedings of the forty-third annual ACM symposium on Theory of computing
Publisher
ACM
Published
2011-06-06
Pages
333-342
DOI
10.1145/1993636.1993682
OpenAlex
W1993292204
Cited by
874
References
85
Citations by year
2026: 41 · 2025: 69 · 2024: 82 · 2023: 87 · 2022: 71 · 2021: 97 · 2020: 67 · 2019: 83 · 2018: 67 · 2017: 76 · 2016: 48 · 2015: 29 · 2014: 24 · 2013: 17 · 2012: 13
FWCI
14.26
Type
conference paper
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
ACM Symposium on Theory of Computing (STOC) (publishedVersion)
Funders
  • National Science Foundation (0844626)
  • Defense Advanced Research Projects Agency
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
linear optics, quantum computing, computational complexity, classical simulation of quantum computation, polynomial hierarchy collapse

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review