A Linear-Optical Proof that the Permanent is #P-Hard

Abstract

One of the crown jewels of complexity theory is Valiant's 1979 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 due to Knill, Laflamme, and Milburn---one can give a different and arguably more intuitive proof of this theorem.

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

References in corpus (3)

• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Permanents in linear optical networks
• A simple encoding of a quantum circuit amplitude as a matrix permanent

Cited by in corpus (64)

• Experimental Boson Sampling
• Average-case complexity versus approximate simulation of commuting quantum computations
• BosonSampling with single-photon Fock states from a bright solid-state source
• Single microwave-photon detector using an artificial $\Lambda$-type three-level system
• Multi-photon quantum interference in a multi-port integrated photonic device
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• Single-photon detection and cryogenic reconfigurability in Lithium Niobate nanophotonic circuits
• Simulating boson sampling in lossy architectures
• On the hardness of classically simulating the one clean qubit model
• Interference of Identical Particles from Entanglement to Boson-Sampling
• Quantum Indistinguishability by Path Identity: The awakening of a sleeping beauty
• What can quantum optics say about computational complexity theory?
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• How many qubits are needed for quantum computational supremacy?
• Sufficient bound on the mode mismatch of single photons for scalability of the boson sampling computer
• Active demultiplexing of single-photons from a solid-state source
• Universality of Generalized Bunching and Efficient Assessment of Boson Sampling
• Quantum Experiments and Graphs II: Quantum Interference, Computation and State Generation
• Dynamical phase transitions in sampling complexity
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Stimulated generation of indistinguishable single photons from a quantum ladder system
• Tight bound on trace distance between a realistic device with partially indistinguishable bosons and the ideal Boson Sampling
• Exponential data encoding for quantum supervised learning
• Noise in BosonSampling and the threshold of efficient classical simulatability
• Quantum circuits and low-degree polynomials over F_2
• Generalized concurrence in boson sampling
• Power of Quantum Computation with Few Clean Qubits
• A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
• Quantum software for linear photonic simulations
• Non-linear Boson Sampling
• Simulating and assessing boson sampling experiments with phase-space representations
• Decision and function problems based on boson sampling
• Distinguishing noisy boson sampling from classical simulations
• Linear optics only allows every possible quantum operation for one photon or one port
• The scaling of boson sampling experiments
• Quantum-inspired permanent identities
• Exact sampling hardness of Ising spin models
• Complexity of full counting statistics of free quantum particles in product states
• A method to determine which quantum operations can be realized with linear optics with a constructive implementation recipe
• Quantum supremacy and quantum phase transitions
• Robustness of quantum Fourier transform interferometry
• Initial states and apodisation for quantum field simulations in phase-space
• Virtual distillation with noise dilution
• Noise thresholds for classical simulability of non-linear Boson sampling
• Coherent states in projected Hilbert spaces
• Evaluation of bipartite entanglement between two optical multi-mode systems using mode translation symmetry
• No-go theorems for photon state transformations in quantum linear optics
• Multiparameter estimation for qubit states with collective measurements: a case study
• Quantum supremacy in driven quantum many-body systems
• Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix
• Majorization and the time complexity of linear optical networks
• Approximating outcome probabilities of linear optical circuits
• Optimized numerical gradient and Hessian estimation for variational quantum algorithms
• Computational complexity of exterior products and multi-particle amplitudes of non-interacting fermions in entangled states
• The matrix permanent and determinant from a spin system
• Efficiently simulating the work distribution of multiple identical bosons with boson sampling
• Quantum estimation bound of Gaussian matrix permanent
• Permanents, Bosons and Linear Optics
• Boson sampling with ultracold atoms in a programmable optical lattice
• Matrix phase-space representations for gaussian boson sampling
• Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
• Nonnegativity for hafnians of certain matrices
• Two-detector reconstruction of multiphoton states in linear optical networks