Abstract
We investigate the effects of photon loss and spectrally impure sources on Gaussian boson sampling (GBS) when used in dense-subgraph-finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to such errors, to such an extent that there exist classical algorithms that can efficiently simulate the underlying GBS. These results suggest that, unlike the GBS problem itself, the speed-up of GBS-based algorithms over classical approaches when applied to the dense-subgraph problem is not exponential. They do suggest, however, that any advantage offered could be achieved on a quantum device with far less stringent requirements on photon loss and purity than general GBS.
| Original language | English |
|---|---|
| Article number | 054043 |
| Journal | Physical Review Applied |
| Volume | 20 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - 21 Nov 2023 |
Bibliographical note
Funding Information:We would like to thank Patrick Yard and Anthony Laing for feedback on the manuscript and Ryan Mann for useful discussions. N.R.S. is supported by the Quantum Engineering Centre for Doctoral Training, through Engineering and Physical Sciences Research Council (EPSRC) Grant No. EP/SO23607/1.
Publisher Copyright:
© 2023 authors. Published by the American Physical Society. Published by the American Physical Society under the terms of the "https://creativecommons.org/licenses/by/4.0/"Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
Research Groups and Themes
- QETLabs