Naomi Solomons - The effectiveness of Gaussian boson sampling for dense subgraph finding

The effectiveness of Gaussian boson sampling for dense subgraph finding

This seminar, given by Naomi Solomons, will happend on 09 November 2023, at 14:0. It will take place in Room 105 C25/26.

Find a map of the campus here.

Abstract

Gaussian boson sampling (GBS) is a simplified framework for photonic quantum computing, mostly known due to recent claims of quantum advantage. A potential application of GBS is dense subgraph finding. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS. These results imply that the speedup of GBS-based algorithms for the dense subgraph problem over classical approaches is at most polynomial, though this could be achieved on a quantum device with dramatically less stringent requirements on loss and photon purity than general GBS. I will also consider recent results that suggest that the limited advantage of using GBS is due to using graphs with only positive weights, and the potential application of this for applications of GBS in graph theory. I will be presenting results from this paper: https://arxiv.org/abs/2301.13217 as well as some further results (and I’ll also talk about this paper: https://arxiv.org/abs/2302.00536 and this paper: https://arxiv.org/abs/2301.09594 ).