# The computational complexity of linear optics

@article{Aaronson2011TheCC, title={The computational complexity of linear optics}, author={Scott Aaronson and Alexei Y. Arkhipov}, journal={Electron. Colloquium Comput. Complex.}, year={2011}, volume={17}, pages={170} }

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… Expand

#### 704 Citations

BosonSampling with realistic single-photon sources

- Physics
- 2013 Conference on Lasers & Electro-Optics Europe & International Quantum Electronics Conference CLEO EUROPE/IQEC
- 2013

Summary form only given. The extended Church-Turing thesis posits that any computable function can be calculated efficiently by a probabilistic Turing machine. If this thesis held true, the global… Expand

Cracking the Quantum Advantage threshold for Gaussian Boson Sampling

- Physics
- 2021

Quantum advantage, defined as a computational result unattainable with classical computers, is a major goal of scientists currently developing quantum technologies. Recently, quantum advantage was… Expand

BosonSampling with Lost Photons

- Computer Science, Physics
- ArXiv
- 2015

It is shown that, if k out of n photons are lost, then BosonSampling cannot sample classically from a distribution that is 1/n^Theta(k)-close to the ideal distribution, unless a $\text{BPP}^{\text{NP}}$ machine can estimate the permanents of Gaussian matrices in $n^{O(k)}$ time. Expand

On “ The Computational Complexity of Linear Optics ”

- 2011

The great promise of the field of quantum computing is that one day we will be able to build devices that operate according to the laws of quantum mechanics and lets us solve computational problems… Expand

Quantum Experiments and Graphs II: Computation and State Generation with Probabilistic Sources and Linear Optics

- Computer Science
- 2018

It is shown how general linear optical quantum entanglement experiments with probabilistic sources can be described using graph theory using complex weights in undirected graphs, and how to easily understand in a graphical way quantum experiments such asEntanglement swapping. Expand

Exploring Quantum Computation Through the Lens of Classical Simulation

- Computer Science
- 2020

This project looks at the problem of classically simulating quantum circuits through decompositions into stabilizer circuits, a restricted class of quantum computation which can be efficiently simulated classically. Expand

Variational quantum unsampling on a quantum photonic processor

- Mathematics, Physics
- 2019

A promising route towards the demonstration of near-term quantum advantage (or supremacy) over classical systems relies on running tailored quantum algorithms on noisy intermediate-scale quantum… Expand

Achieving quantum supremacy with sparse and noisy commuting quantum computations

- Mathematics, Physics
- 2016

The class of commuting quantum circuits known as IQP (instantaneous quantum polynomial-time) has been shown to be hard to simulate classically, assuming certain complexity-theoretic conjectures. Here… Expand

The Quantum Computer Puzzle (Expanded Version)

- Physics, Mathematics
- 2016

Quantum computers are hypothetical devices, based on quantum physics, that would enable us to perform certain computations hundreds of orders of magnitude faster than digital computers. This feature… Expand

The Power of Quantum Fourier Sampling

- Computer Science, Physics
- TQC
- 2016

This work uses Quantum Fourier Sampling to construct a class of distributions that can be sampled by a quantum computer, and shows a general class of quantumly sampleable distributions each of which is based on an "Efficiently Specifiable" polynomial, for which a classical approximate sampler implies an average-case approximation. Expand

#### References

SHOWING 1-10 OF 149 REFERENCES

A scheme for efficient quantum computation with linear optics

- Physics, Medicine
- Nature
- 2001

It is shown that efficient quantum computation is possible using only beam splitters, phase shifters, single photon sources and photo-detectors and are robust against errors from photon loss and detector inefficiency. Expand

Quantum Circuits That Can Be Simulated Classically in Polynomial Time

- Computer Science, Mathematics
- SIAM J. Comput.
- 2002

It is shown that two-bit operations characterized by 4 × 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynometric time. Expand

Photonic Boson Sampling in a Tunable Circuit

- Computer Science, Medicine
- Science
- 2013

The central premise of boson sampling was tested, experimentally verifying that three-photon scattering amplitudes are given by the permanents of submatrices generated from a unitary describing a six-mode integrated optical circuit. Expand

Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

- Physics, Mathematics
- Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- 2010

We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is… Expand

Boson Sampling on a Photonic Chip

- Physics, Medicine
- Science
- 2013

A quantum boson-sampling machine (QBSM) is constructed to sample the output distribution resulting from the nonclassical interference of photons in an integrated photonic circuit, a problem thought to be exponentially hard to solve classically. Expand

Quantum computing, postselection, and probabilistic polynomial-time

- Computer Science, Mathematics
- Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- 2005

It is shown that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently, or probabilistic polynomial-time, and implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection. Expand

Classical simulation of noninteracting-fermion quantum circuits

- Physics, Computer Science
- ArXiv
- 2001

It is shown that a class of quantum computations that was recently shown to be efficiently simulatable on a classical computer by Valiant corresponds to a physical model of noninteracting fermions in one dimension. Expand

Quantum Complexity Theory

- Computer Science
- SIAM J. Comput.
- 1997

This paper gives the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis, and proves that bits of precision suffice to support a step computation. Expand

Bounds for small-error and zero-error quantum algorithms

- Mathematics, Computer Science
- 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
- 1999

We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the… Expand

Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance

- Physics, Medicine
- Nature
- 2001

A simple, parameter-free but predictive model of decoherence effects in the authors' system is presented, which is in principle scalable to systems containing many quantum bits, but such scalability is not implied by the present work. Expand