Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions
- 6 May 2022
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 105 (5) , 052412
Abstract
We prove that a classical computer can efficiently sample from the photon-number probability distribution of a Gaussian state prepared by using an optical circuit that is shallow and local. Our paper generalizes previous known results for qubits to the continuous-variable domain. The key to our proof is the observation that the adjacency matrices characterizing the Gaussian states generated by shallow and local circuits have small bandwidth. To exploit this structure, we devise fast algorithms to calculate loop Hafnians of banded matrices. Since sampling from deep optical circuits with exponential-scaling photon loss is classically simulable, our results pose a challenge to the feasibility of demonstrating quantum supremacy on photonic platforms with local interactions.Keywords
All Related Versions
This publication has 57 references indexed in Scilit:
- Faster exponential-time algorithms in graphs of bounded average degreeInformation and Computation, 2015
- Boson Sampling from a Gaussian StatePhysical Review Letters, 2014
- Algorithm for finding clusters with a known distribution and its application to photon-number resolution using a superconducting transition-edge sensorJournal of the Optical Society of America B, 2012
- Gaussian quantum informationReviews of Modern Physics, 2012
- Efficiently computing the permanent and Hafnian of some banded Toeplitz matricesLinear Algebra and its Applications, 2009
- From moments of sum to moments of productJournal of Multivariate Analysis, 2008
- Efficient Classical Simulation of Slightly Entangled Quantum ComputationsPhysical Review Letters, 2003
- Experimental realization of any discrete unitary operatorPhysical Review Letters, 1994
- Updating the Inverse of a MatrixSIAM Review, 1989
- The complexity of computing the permanentTheoretical Computer Science, 1979