A complexity transition in displaced Gaussian Boson sampling.

Area of Science:

• Quantum computing and information theory
• Computational complexity
• Linear optics and quantum optics

Background:

• Gaussian Boson Sampling (GBS) is a key problem for demonstrating quantum computational advantage.
• High photon numbers are desirable for GBS but experimentally challenging to produce using squeezed states.
• Existing GBS methods face limitations in scalability and experimental feasibility for large photon numbers.

Purpose of the Study:

• To investigate the computational complexity of GBS by introducing coherent state displacements.
• To explore a modified GBS problem, termed Displaced GBS, for enhanced quantum advantage.
• To identify regimes where Displaced GBS exhibits classical tractability or quantum advantage.

Main Methods:

• Introduction of coherent state displacements to squeezed states in GBS, creating Displaced GBS.
• Utilizing a connection to graph theory's matching polynomial for algorithmic development.
• Developing an efficient classical algorithm for Displaced GBS under specific conditions (high displacement or non-negative graph representation).

Main Results:

• An efficient classical algorithm is presented for Displaced GBS when displacement is high or the output state corresponds to a non-negative graph.
• Complexity-theoretic arguments demonstrate potential quantum advantage for Displaced GBS in the low-displacement regime.
• Numerical analysis quantifies the transition point between classical and quantum computational regimes.

Conclusions:

• Displaced GBS provides a promising avenue for achieving quantum advantage, potentially overcoming experimental challenges of high photon numbers.
• The study establishes a clear link between graph theory and the computational complexity of photonic quantum systems.
• Understanding the complexity transition in Displaced GBS is crucial for designing future quantum advantage experiments.