Classical Simulation of Boson Sampling Based on Graph Structure.

Area of Science:

• Quantum Information Science
• Computational Physics
• Quantum Computing

Background:

• Boson sampling is crucial for demonstrating quantum supremacy on near-term quantum devices.
• Classical simulation of boson sampling is computationally challenging.
• Linear-optical circuits are a key platform for boson sampling experiments.

Purpose of the Study:

• Develop efficient classical sampling algorithms for boson sampling.
• Analyze the complexity of simulating linear-optical circuits.
• Investigate the transition in simulation complexity based on circuit depth and connectivity.

Main Methods:

• Developed classical sampling algorithms exploiting the graph structure of linear-optical circuits.
• Analyzed algorithm complexity in terms of treewidth.
• Studied approximated simulations for local Haar-random linear-optical circuits.
• Performed numerical likelihood tests on experimental data.

Main Results:

• Algorithm complexity scales with the treewidth of the circuit graph.
• Efficient simulation is possible for shallow circuits (depth < quadratic in lattice spacing) with exponentially small error.
• A sharp transition in complexity occurs as photon interference increases with circuit depth.
• The treewidth-based algorithm showed higher likelihood than experimental data in a Gaussian boson sampling test.

Conclusions:

• Treewidth provides a measure of classical simulation difficulty for boson sampling.
• Circuit depth critically influences the transition from efficient to exponential classical simulation complexity.
• The developed algorithms offer a pathway for more accurate classical verification of quantum experiments.