Followup Paper.pdf

Scott Aaronson presents a new proof that computing the permanent of an n × n matrix is #P-hard, using the model of linear-optical quantum computing. The proof is based on three facts: postselected linear optics is capable of universal quantum computation, quantum computations can encode #P-hard quantities in their amplitudes, and amplitudes in n-photon linear-optics circuits can be expressed as the permanents of n × n matrices. This approach provides an alternative to Valiant's 1979 theorem and offers a more intuitive understanding of the permanent's #P-hardness. The proof is self-contained, with all necessary results proved within the paper, and assumes only familiarity with quantum computing notation. The author argues that this new proof is valuable, despite being potentially more complicated than Valiant's original proof, as it provides a different perspective and illustrates the power of quantum computing as a "high-level programming language" for complexity theory.