This paper presents evidence that quantum computers, specifically those built using linear optical elements, cannot be efficiently simulated by classical computers. The authors define a model of computation involving identical photons passing through a linear-optical network and being measured to count the number of photons in each mode. While this model is not known to be universal for quantum computation, it is shown to solve sampling and search problems that are classically intractable under plausible assumptions. The paper proves that if a classical algorithm can sample from the same probability distribution as a linear-optical network, then P^#P = BPP^NP, leading to a collapse of the polynomial hierarchy. However, the authors argue that even approximate or noisy classical simulations would imply a collapse of the polynomial hierarchy, assuming two unproven conjectures: the Permanent-of-Gaussians Conjecture and the Permanent Anti-Concentration Conjecture. These conjectures state that approximating the permanent of a Gaussian matrix is #P-hard and that the permanent of a Gaussian matrix is large with high probability. The authors also show that boson sampling, a problem of sampling from the output distribution of a boson computer, is hard for classical computers. They prove that if a classical algorithm can simulate boson sampling, then the permanent of a Gaussian matrix can be approximated in BPP^NP, implying a collapse of the polynomial hierarchy. The paper also discusses the experimental implications of these results, suggesting that a linear-optics experiment could provide evidence against the Extended Church-Turing Thesis by demonstrating that quantum computers can solve problems that are intractable for classical computers. The authors conclude that their results provide strong evidence that quantum computers have capabilities outside the entire polynomial hierarchy, complementing recent evidence from other researchers. They also highlight the importance of understanding the computational complexity of boson sampling and the role of permanents in quantum computing.This paper presents evidence that quantum computers, specifically those built using linear optical elements, cannot be efficiently simulated by classical computers. The authors define a model of computation involving identical photons passing through a linear-optical network and being measured to count the number of photons in each mode. While this model is not known to be universal for quantum computation, it is shown to solve sampling and search problems that are classically intractable under plausible assumptions. The paper proves that if a classical algorithm can sample from the same probability distribution as a linear-optical network, then P^#P = BPP^NP, leading to a collapse of the polynomial hierarchy. However, the authors argue that even approximate or noisy classical simulations would imply a collapse of the polynomial hierarchy, assuming two unproven conjectures: the Permanent-of-Gaussians Conjecture and the Permanent Anti-Concentration Conjecture. These conjectures state that approximating the permanent of a Gaussian matrix is #P-hard and that the permanent of a Gaussian matrix is large with high probability. The authors also show that boson sampling, a problem of sampling from the output distribution of a boson computer, is hard for classical computers. They prove that if a classical algorithm can simulate boson sampling, then the permanent of a Gaussian matrix can be approximated in BPP^NP, implying a collapse of the polynomial hierarchy. The paper also discusses the experimental implications of these results, suggesting that a linear-optics experiment could provide evidence against the Extended Church-Turing Thesis by demonstrating that quantum computers can solve problems that are intractable for classical computers. The authors conclude that their results provide strong evidence that quantum computers have capabilities outside the entire polynomial hierarchy, complementing recent evidence from other researchers. They also highlight the importance of understanding the computational complexity of boson sampling and the role of permanents in quantum computing.