Algorithms · Quantum sampling algorithm
Sampling the output of a linear-optical network
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.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Superpolynomial
- Primary source on the speedupStated 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 costStated 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.
- Papers1
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.
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 →
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..
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 →
- 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.
- Speedup class
- Superpolynomial (checked against the record's own primary paper, which states it)
- 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
This record is not a concrete 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.
Nobody has reviewed this record for gaps yet.
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.
Related entries
References
- The Computational Complexity of Linear Optics
Scott Aaronson, Alex Arkhipov · 2010
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.