In this section
@article{Li:2025:10.1038/s41534-025-01062-5,
author = {Li, Z and Solomons, NR and Bulmer, JFF and Patel, RB and Walmsley, IA},
doi = {10.1038/s41534-025-01062-5},
journal = {npj Quantum Information},
title = {A complexity transition in displaced Gaussian Boson sampling},
url = {http://dx.doi.org/10.1038/s41534-025-01062-5},
volume = {11},
year = {2025}
}
TY - JOUR
AB - Gaussian Boson Sampling (GBS) is the problem of sampling from the output of photon-number-resolving measurements of squeezed states input to a linear optical interferometer. For purposes of demonstrating quantum computational advantage as well as practical applications,a large photon number is often desirable. However, producing squeezed states with high photon numbers is experimentally challenging. In this work, we examine the computational complexity implications of increasing the photon number by introducing coherent states. This displaces the state in phase space and as such we call this modified problem Displaced GBS. By utilising a connection to the matching polynomial in graph theory, we first describe an efficient classical algorithm for Displaced GBS when displacement is high or when the output state is represented by a non-negative graph. Then we provide complexity theoretic arguments for the quantum advantage of the problem in the low-displacement regime and numerically quantify where the complexity transition occurs.
AU - Li,Z
AU - Solomons,NR
AU - Bulmer,JFF
AU - Patel,RB
AU - Walmsley,IA
DO - 10.1038/s41534-025-01062-5
PY - 2025///
SN - 2056-6387
TI - A complexity transition in displaced Gaussian Boson sampling
T2 - npj Quantum Information
UR - http://dx.doi.org/10.1038/s41534-025-01062-5
VL - 11
ER -