The paper by Scott Aaronson and Alex Arkhipov from MIT explores the computational complexity of linear optics, specifically a model of computation involving noninteracting bosons. They define a model where identical photons are generated, pass through a linear-optical network, and are then measured to count the number of photons in each mode. This model is not known to be universal for quantum computation but is believed to be intractable for classical computers under plausible assumptions. The authors present two main results: 1. **Exact BOSONSAMPLING**: If there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then the polynomial hierarchy collapses to the third level. This assumes extremely accurate simulation. 2. **Approximate BOSONSAMPLING**: Even an approximate or noisy classical simulation would imply a collapse of the polynomial hierarchy. This relies on two unproven conjectures: the *Permanent-of-Gaussians Conjecture* and the *Permanent Anti-Concentration Conjecture*. The paper also discusses the experimental implications of these results, suggesting a linear-optics experiment that could test the computational power of quantum systems. The experiment would use simple optical elements to induce a Haar-random unitary transformation on an input state of photons and check if the probabilities of various final states correspond to the permanents of submatrices of the unitary matrix, as predicted by quantum mechanics. The authors argue that this experiment could provide strong evidence against the Extended Church-Turing Thesis, which states that all computational problems efficiently solvable by realistic physical devices are efficiently solvable by a probabilistic Turing machine. They highlight several advantages of their proposed experiment over building a conventional quantum computer, such as bypassing the need for explicit coupling between pairs of photons and leveraging the coherence properties of photons in linear optics.The paper by Scott Aaronson and Alex Arkhipov from MIT explores the computational complexity of linear optics, specifically a model of computation involving noninteracting bosons. They define a model where identical photons are generated, pass through a linear-optical network, and are then measured to count the number of photons in each mode. This model is not known to be universal for quantum computation but is believed to be intractable for classical computers under plausible assumptions. The authors present two main results: 1. **Exact BOSONSAMPLING**: If there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then the polynomial hierarchy collapses to the third level. This assumes extremely accurate simulation. 2. **Approximate BOSONSAMPLING**: Even an approximate or noisy classical simulation would imply a collapse of the polynomial hierarchy. This relies on two unproven conjectures: the *Permanent-of-Gaussians Conjecture* and the *Permanent Anti-Concentration Conjecture*. The paper also discusses the experimental implications of these results, suggesting a linear-optics experiment that could test the computational power of quantum systems. The experiment would use simple optical elements to induce a Haar-random unitary transformation on an input state of photons and check if the probabilities of various final states correspond to the permanents of submatrices of the unitary matrix, as predicted by quantum mechanics. The authors argue that this experiment could provide strong evidence against the Extended Church-Turing Thesis, which states that all computational problems efficiently solvable by realistic physical devices are efficiently solvable by a probabilistic Turing machine. They highlight several advantages of their proposed experiment over building a conventional quantum computer, such as bypassing the need for explicit coupling between pairs of photons and leveraging the coherence properties of photons in linear optics.