Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions
Published in preprint, 2020
Recommended citation: Haoyu Qi, Diego Cifuentes, Kamil Brádler, Robert Israel, Timjan Kalajdzievski, Nicolás Quesada (2020). "Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions." arXiv:2009.11824. https://arxiv.org/abs/2009.11824
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 work 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.