What Can Quantum Optics Say about Computational Complexity Theory?
- 11 February 2015
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 114 (6), 060501
- https://doi.org/10.1103/physrevlett.114.060501
Abstract
Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain results that are of interest from both quantum theory and the computational complexity theory point of view. We derive a general formula for calculating the output probabilities, and by considering input thermal states, we show that the output probabilities are proportional to permanents of positive-semidefinite Hermitian matrices. It is believed that approximating permanents of complex matrices in general is a #P-hard problem. However, we show that these permanents can be approximated with an algorithm in the complexity class, as there exists an efficient classical algorithm for sampling from the output probability distribution. We further consider input squeezed-vacuum states and discuss the complexity of sampling from the probability distribution at the output.
Keywords
Other Versions
Funding Information
- Centre of Excellence for Environmental Decisions, Australian Research Council (CE110001027)
This publication has 18 references indexed in Scilit:
- Experimental boson samplingNature Photonics, 2013
- Boson Sampling on a Photonic ChipScience, 2013
- Photonic Boson Sampling in a Tunable CircuitScience, 2013
- A linear-optical proof that the permanent is # P -hardProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2011
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entriesJournal of the ACM, 2004
- PP is as Hard as the Polynomial-Time HierarchySIAM Journal on Computing, 1991
- On Approximation Algorithms for # PSIAM Journal on Computing, 1985
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Equivalence of Semiclassical and Quantum Mechanical Descriptions of Statistical Light BeamsPhysical Review Letters, 1963
- Photon CorrelationsPhysical Review Letters, 1963