Daniel
Brod
UFF Niteroi
Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for quantum devices capable of performing tasks that are out of reach of their classical counterparts. Most recent photonic quantum computational advantage experiments were performed within this Gaussian variant of bosonsampling, having observed events with over 100 photons and seriously challenged the capabilities of competing classical algorithms. Thus, there is significant interest in solidifying the mathematical and complexity-theoretic foundations for the hardness of simulating these devices. We show that there is no efficient classical algorithm to approximately sample from the output of an ideal Gaussian boson sampling device unless the polynomial hierarchy collapses, under the same two conjectures as the original bosonsampling proposal by Aaronson and Arkhipov.
Crucial to the proof is a new method for programming a Gaussian boson sampling device such that the output probabilities are proportional to permanents of (submatrices of) an arbitrary matrix. This provides considerable flexibility in programming, and likely has applications much beyond those discussed here. We leverage this to make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., in the high-collision regime). Our reduction suffices to prove that GBS is hard in the constant-collision regime, though we believe some ingredients of it can be used to push this direction further.
____________________________________________
Zoom meeting details
Topic: Quantum Information and Quantum Computing Working Group Seminar
Time: Wednesday, 26.01.2022, 15:15 Warsaw (CET)
Join Zoom Meeting
https://tinyurl.com/quantun-cft
Meeting ID: 87850698108
Passcode: quantin
If you encounter any problems with connecting to the Zoom meeting, please email calegari@cft.edu.pl.
