A linear-optical proof that the permanent is # P -hard

2011/07/06 by Scott Aaronson · 1 citation
Computer Science · Physics and Astronomy · #Algebra over a field #Calculus (dental) #Complexity and Algorithms in Graphs #Fundamental theorem #Matrix (chemical analysis) #Proof theory #Quantum #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Universality (dynamical systems) #cs.CC #quant-ph

paper · pdf · doi:10.1098/rspa.2011.0232

12 pages, 2 figures, to appear in Proceedings of the Royal Society A. doi: 10.1098/rspa.2011.0232

openalex publication_date 2011/07/06 · arxiv created 2011/09/08 · arxiv updated 2015/05/29 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

Abstract

One of the crown jewels of complexity theory is Valiant's theorem that computing the permanent of an n × n matrix is # P -hard. Here we show that, by using the model of linear-optical quantum computing —and in particular, a universality theorem owing to Knill, Laflamme and Milburn—one can give a different and arguably more intuitive proof of this theorem.

Citations

• The complexity of computing the permanent
• Simple encoding of a quantum circuit amplitude as a matrix permanent
• On the computational complexity of the Jones and Tutte polynomials
• Elementary gates for quantum computation
• Quantum computing, postselection, and probabilistic polynomial-time

Cited by

• Distributed Phase Sensing with Multiphoton States in Optical Interferometry

Related

• New Hardness Results for the Permanent Using Linear Optics
• A Quantum Optics Argument for the #P-hardness of a Class of Multidimensional Integrals
• The Computational Complexity of Linear Optics
• Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent
• Quantum Computing, Postselection, and Probabilistic Polynomial-Time