Efficient classical sampling from Gaussian boson sampling distributions on unweighted graphs.

Area of Science:

• Quantum Information Science
• Computational Complexity
• Statistical Physics

Background:

• Gaussian Boson Sampling (GBS) is a key area for demonstrating quantum computational advantage.
• GBS has potential applications in solving complex graph-related problems.
• Efficient classical sampling from GBS distributions is crucial for verification and comparison.

Purpose of the Study:

• To propose novel Markov chain Monte Carlo (MCMC) algorithms for sampling GBS distributions.
• To analyze the theoretical mixing time of these algorithms on unweighted graphs.
• To demonstrate practical performance improvements on graph problems using these algorithms.

Main Methods:

• Development of a double-loop variant of Glauber dynamics.
• Theoretical analysis using refined canonical path arguments to prove polynomial mixing time for dense graphs.
• Numerical experiments on unweighted graphs up to 256 vertices.

Main Results:

• The proposed double-loop Glauber dynamics achieves a stationary distribution matching the GBS distribution.
• Polynomial mixing time is proven for dense graphs.
• Up to 10x performance improvement observed for max-Hafnian and densest k-subgraph problems compared to random search and simulated annealing.

Conclusions:

• The developed MCMC algorithms provide both theoretical guarantees and practical advantages for classical sampling from GBS distributions.
• This work advances the potential for using GBS in quantum advantage demonstrations and graph problem-solving.
• The algorithms are scalable and outperform existing methods on relevant graph problems.