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

DOI10.1098/rspa.2011.0232zbMath1323.68290arXiv1109.1674OpenAlexW3104131304MaRDI QIDQ2901811

Scott Aaronson

Publication date: 31 July 2012

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1109.1674

zbMATH Keywords

permanentquantum computinglinear opticsbosons\(\#\mathrm{P}\)-completevaliant

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

Nonnegativity for hafnians of certain matrices ⋮ Majorization and the time complexity of linear optical networks ⋮ Commuting quantum circuits and complexity of Ising partition functions ⋮ Strong simulation of linear optical processes ⋮ Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$ ⋮ Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation ⋮ On the permanents of circulant and degenerate Schur matrices ⋮ ASYMPTOTIC EVALUATION OF BOSONIC PROBABILITY AMPLITUDES IN LINEAR UNITARY NETWORKS IN THE CASE OF LARGE NUMBER OF BOSONS ⋮ Unnamed Item ⋮ Simulating macroscopic quantum correlations in linear networks ⋮ Boson-sampling with non-interacting fermions

Cites Work

• The complexity of computing the permanent
• PP is closed under intersection
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• On the computational complexity of the Jones and Tutte polynomials
• Quantum computing, postselection, and probabilistic polynomial-time