Attested & literatureAlgorithmsQuantum sampling algorithm2026-08-12

Sampling the output of a linear-optical network

boson samplinglinear opticspermanentpolynomial hierarchysampling complexity

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

Sample from the output distribution of a rudimentary optical device: identical photons are generated, sent through a network of beamsplitters and phase shifters, and then non-adaptively measured to count the photons in each mode. The question is whether a classical computer can do the same sampling efficiently. The probability of any particular output equals the squared modulus of the permanent of a submatrix of the network's unitary. Permanents of non-negative matrices are approximable in probabilistic polynomial time by the Jerrum-Sinclair-Vigoda algorithm, but approximating a complex permanent to within a constant factor is hard, and the authors call this difference the starting point for everything in the paper. The main technical device is that a submatrix of a Haar-random unitary is close in variation distance to a matrix of independent complex Gaussians once the network is large enough relative to the photon number. That lets an arbitrary Gaussian permanent estimation instance be hidden inside one output probability of the sampler, so a classical approximate sampler would yield an algorithm for that estimation problem in the polynomial hierarchy.

Circuit & simulation

problem

encodetransform

algorithm

transformmeasure

readout

measure

What this takes and returns

TakesNothingWhat joins here

No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

ReturnsNothingWhat joins here

No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.

Nothing in the Atlas meets this end.

This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →

How it works

The probability of any particular output equals the squared modulus of the permanent of a submatrix of the network's unitary. Permanents of non-negative matrices are approximable in probabilistic polynomial time by the Jerrum-Sinclair-Vigoda algorithm, but approximating a complex permanent to within a constant factor is hard, and the authors call this difference the starting point for everything in the paper. The main technical device is that a submatrix of a Haar-random unitary is close in variation distance to a matrix of independent complex Gaussians once the network is large enough relative to the photon number. That lets an arbitrary Gaussian permanent estimation instance be hidden inside one output probability of the sampler, so a classical approximate sampler would yield an algorithm for that estimation problem in the polynomial hierarchy. This record's speedup class, "Superpolynomial", is a secondary source's classification of the approximation and simulation algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "in the classical case, the aij's are nonnegative real numbers—which means that we can approximate Per(A) in probabilistic polynomial time, by using the celebrated algorithm of Jerrum, Sinclair, and Vigoda [30]. In the quantum case, by contrast, the aij's are complex numbers. And it is not hard to show that, given a general matrix A ∈ Cn×n, even approximating Per(A) to within a constant factor is #P-complete.". Reported cost: Stated as complexity-theoretic consequences rather than as a running time. Exact sampling is not efficiently solvable classically unless P^#P = BPP^NP and the polynomial hierarchy collapses to the third level. For approximate sampling, a classical sampler running in time polynomial in the input size and 1/ε would put the Gaussian permanent estimation problem in BPP^NP..

Implementation

FrameworkUnsupported

boson-sampling-linear-optics.txt

ALGORITHM: Sampling the output of a linear-optical network
PROBLEM: Sample from the output distribution of a rudimentary optical device: identical photons are generated, sent through a network of beamsplitters and phase shifters, and then non-adaptively measured to count the photons in each mode. The question is whether a classical computer can do the same sampling efficiently.
IDEA: The probability of any particular output equals the squared modulus of the permanent of a submatrix of the network's unitary. Permanents of non-negative matrices are approximable in probabilistic polynomial time by the Jerrum-Sinclair-Vigoda algorithm, but approximating a complex permanent to within a constant factor is hard, and the authors call this difference the starting point for everything in the paper. The main technical device is that a submatrix of a Haar-random unitary is close in variation distance to a matrix of independent complex Gaussians once the network is large enough relative to the photon number. That lets an arbitrary Gaussian permanent estimation instance be hidden inside one output probability of the sampler, so a classical approximate sampler would yield an algorithm for that estimation problem in the polynomial hierarchy.
REPORTED COST: Stated as complexity-theoretic consequences rather than as a running time. Exact sampling is not efficiently solvable classically unless P^#P = BPP^NP and the polynomial hierarchy collapses to the third level. For approximate sampling, a classical sampler running in time polynomial in the input size and 1/ε would put the Gaussian permanent estimation problem in BPP^NP.
BASIS: section 1.2.1, Theorem 1 of arXiv:1011.3245: "The exact BosonSampling problem is not efficiently solvable by a classical computer, unless P#P = BPPNP and the polynomial hierarchy collapses to the third level."; section 1.2.2, Theorem 3: "Suppose there exists a classical algorithm C that takes as input a description of A as well as an error bound ε, and that samples from a probability distribution D′A such that ‖D′A − DA‖ ≤ ε in poly(|A|, 1/ε) time. Then the |GPE|²± problem is solvable in BPPNP." Read for this record: the abstract and contents, the whole of section 1, the definitions in section 2, the setup of section 4, section 5.1-5.2 including the Haar-unitary hiding theorem, the statement of Theorem 7 and the two conjectures, and section 10. The bulk of the technical proofs in sections 3 through 9 was not read.
PRIMARY SOURCE: Scott Aaronson, Alex Arkhipov (2010), The Computational Complexity of Linear Optics — https://arxiv.org/abs/1011.3245

This is a literature reference record, not an executable circuit.

A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.

Quantum vs classical

Classical baseline

Compare Quantum sampling algorithm with the strongest classical method for the same instance, input budget, and output metric.

Quantum claim

This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.

How to compare

Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.

Declared gaps

Nobody has reviewed this record for gaps yet.

Literature & references

The Computational Complexity of Linear Optics2010 · Scott Aaronson, Alex Arkhipov

Primary source, and the source of this record's claims. Consult it for the split that matters: Theorem 1 is unconditional but assumes exact sampling, while the approximate-sampling result rests on the Permanent-of-Gaussians Conjecture and the Permanent Anti-Concentration Conjecture, both stated as conjectures in section 1.2.3 and neither proved. Section 9 is where the authors set out the evidence for the first and the barrier to proving it. The technical proofs were not read for this record.

arxiv.org/abs/1011.3245 ↗

Verification

Attested & literature

Peer-reviewed paper

Method: Curation only. The problem statement and speedup class were checked against the Quantum Algorithm Zoo's entry "Probabilistic Sampling" (Approximation and Simulation Algorithms); the primary reference's title, authors and submission year were read from its arXiv abs page; the complexity claim was taken from a clause of that paper's abstract (section 1.2.1, Theorem 1 of arXiv:1011.3245: "The exact BosonSampling problem is not efficiently solvable by a classical computer, unless P#P = BPPNP and the polynomial hierarchy collapses to the third level."; section 1.2.2, Theorem 3: "Suppose there exists a classical algorithm C that takes as input a description of A as well as an error bound ε, and that samples from a probability distribution D′A such that ‖D′A − DA‖ ≤ ε in poly(|A|, 1/ε) time. Then the |GPE|²± problem is solvable in BPPNP." Read for this record: the abstract and contents, the whole of section 1, the definitions in section 2, the setup of section 4, section 5.1-5.2 including the Haar-unitary hiding theorem, the statement of Theorem 7 and the two conjectures, and section 10. The bulk of the technical proofs in sections 3 through 9 was not read.). No circuit was constructed, simulated or run.
Result: Pass · the record's problem, speedup class and primary reference agree with the two sources named above.
Caveat: This is a literature record: nothing was constructed, compiled, simulated or run, and no sampling experiment was performed here. The division between what is proved and what is conjectured is the whole substance of this entry. The exact-sampling hardness result is unconditional, but the authors themselves flag in the abstract that it assumes an extremely accurate simulation, which is not what any device does. The realistic result, for approximate sampling, is conditional on two named and explicitly unproven conjectures — the Permanent-of-Gaussians Conjecture and the Permanent Anti-Concentration Conjecture — and the paper's own summary figure states the chain of implications as holding modulo those conjectures, with a section devoted to evidence for one of them and to the barrier to proving it. This model is not known or believed to be universal for quantum computation, and the authors say it even seems unlikely that it can do universal classical computation. They state that they have no evidence such a device could factor integers or solve any decision or promise problem outside BPP. And unlike factoring there is believed to be no NP witness, so a successful large experiment cannot be checked classically the way a claimed factorization can. The Zoo's entry groups this with other sampling results, including instantaneous quantum polynomial-time circuits and log-concave sampling, which this record does not cover.

Facts

Record type: Literature reference
Speedup class (secondary source): Superpolynomial
Primary source on the speedup: Stated by the primary source: "in the classical case, the aij's are nonnegative real numbers—which means that we can approximate Per(A) in probabilistic polynomial time, by using the celebrated algorithm of Jerrum, Sinclair, and Vigoda [30]. In the quantum case, by contrast, the aij's are complex numbers. And it is not hard to show that, given a general matrix A ∈ Cn×n, even approximating Per(A) to within a constant factor is #P-complete."
Reported cost: Stated as complexity-theoretic consequences rather than as a running time. Exact sampling is not efficiently solvable classically unless P^#P = BPP^NP and the polynomial hierarchy collapses to the third level. For approximate sampling, a classical sampler running in time polynomial in the input size and 1/ε would put the Gaussian permanent estimation problem in BPP^NP.
Secondary source for the speedup class: Quantum Algorithm Zoo — "Probabilistic Sampling"
Section it is filed under: Approximation and Simulation Algorithms
Complexity basis: section 1.2.1, Theorem 1 of arXiv:1011.3245: "The exact BosonSampling problem is not efficiently solvable by a classical computer, unless P#P = BPPNP and the polynomial hierarchy collapses to the third level."; section 1.2.2, Theorem 3: "Suppose there exists a classical algorithm C that takes as input a description of A as well as an error bound ε, and that samples from a probability distribution D′A such that ‖D′A − DA‖ ≤ ε in poly(|A|, 1/ε) time. Then the |GPE|²± problem is solvable in BPPNP." Read for this record: the abstract and contents, the whole of section 1, the definitions in section 2, the setup of section 4, section 5.1-5.2 including the Haar-unitary hiding theorem, the statement of Theorem 7 and the two conjectures, and section 10. The bulk of the technical proofs in sections 3 through 9 was not read.
Circuit: Not supplied

Source

The Computational Complexity of Linear Optics ↗

Kind: curated reference
Reviewed by: Leona Quantum curation pass
License: Citation metadata only; source publication terms apply