Abstract
We develop an alternative boson sampling model operating on single-photon states followed by linear interferometry and Gaussian measurements. The hardness proof for simulating such continuous-variable measurements is established in two main steps, making use of the symmetry of quantum evolution under time reversal. Namely, we first construct a twofold version of scattershot boson sampling in which, as opposed to the original proposal, both legs of a collection of two-mode squeezed vacuum states undergo parallel linear-optical transformations. This twofold scattershot model yields, as a corollary, an instance of boson sampling from Gaussian states where photon counting is hard to simulate. Then, a time-reversed setup is used to exhibit a boson sampling model in which the simulation of Gaussian measurements - namely the outcome of eight-port homodyne detection - is proven to be computationally hard. These results illustrate how the symmetry of quantum evolution under time reversal may serve as a tool for analyzing the computational complexity of novel physically motivated computational problems.
Original language | English |
---|---|
Article number | 032326 |
Number of pages | 7 |
Journal | Physical Review A |
Volume | 96 |
Issue number | 3 |
Early online date | 14 Sep 2017 |
DOIs | |
Publication status | Published - Sep 2017 |