The computational complexity of linear optics

By Scott Aaronson, Alexei Y. Arkhipov. Theory of Computing, 2010

1,640 citations recorded by the source corpus.

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. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the Permanent-of-Gaussians Conjecture, which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the Permanent Anti-Concentration Conjecture, which says that |Per(A)|>=√(n!)poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/a3ff293375cc6d82459fee7d8cebe72e00bc9086

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Quantum computational supremacy (2017, background): “Second, and less obviously, they allow us to rule out a larger class of classical simulations.(9,19,20) Suppose the quantum circuit outputs string z with probability q(z) and a classical simulator does so with probability p(z).”
On the complexity and verification of quantum random circuit sampling (2018, methodology): “An astute reader may have noticed that randomizing the instance of permanent corresponds to starting with a random linear-optical network for the BosonSampling experiment, but still focusing on a fixed output.”
Sufficient Conditions for Efficient Classical Simulation of Quantum Optics (2015, background): “If sampling were classically simulatable, using Stockmeyer’s approximate counting algorithm one could approximate one of these probabilities to within a multiplicative error in BPPNP [Stockmeyer’s algorithm allows for the proportionality factors to be of the order 2−poly(N)]; this would lead to the ”
Advances in high-dimensional quantum entanglement (2019, background): “[187] Scott Aaronson and Alex Arkhipov, “The computational complexity of linear optics,” Proceedings of the forty-third annual ACM symposium on Theory of computing , 333 (2011).”
Quantum Chemistry in the Age of Quantum Computing. (2018, methodology): “K(k;l) i;i+1 (k;l) i;i+1 Y i2even K(k;l) i;i+1 (k;l) i;i+1 : (62) A cycle lis composed of N 2 layers, in analogy with the FGSs preparation: UNN(l) VarMG (l) 2 = dY Ne k=1 U(k;l) VarMG (k;l) : (63) Finally, the Lcycles are assembled sequentially to form the complete variational ansatz U VarMG () ”
Complexity-Theoretic Foundations of Quantum Supremacy Experiments (2016, methodology): “ng an oracle A relative to which SampBPP = SampBQP and yet PH is inﬁnite. In other words, we show that any strong supremacy theorem for quantum sampling, along the lines of what Aaronson and Arkhipov [AA13] and Bremner, Montanaro, and Shepherd [BMS15, BMS16] were seeking, must use non-relativizing t”
Sampling of partially distinguishable bosons and the relation to the multidimensional permanent (2014, background): “Boson-Sampling [2, 3, 5] constitutes a special instance of this general scattering problem: Each input mode is populated by at most one boson and m (cid:29) n , which makes events with more than one particle per output mode improbable.”
High-efficiency multiphoton boson sampling (2017, neutral): “178(5) for the three-, four- and five-boson sampling, respectively.”
Harnessing the Power of the Second Quantum Revolution (2020, background): “Building on foundational studies of the complexity of sampling [137,138], Google has claimed quantum supremacy in the context of sampling from a probability distribution as generated from a 2D random quantum circuit [139].”