Efficient Classical Algorithm for Boson Sampling with Partially Distinguishable Photons

Area of Science:

• Quantum computing
• Quantum optics
• Computational complexity

Background:

• Boson sampling is a key quantum computation task.
• Photons with partial distinguishability present simulation challenges.
• Demonstrating quantum advantage requires overcoming classical simulation efficiency.

Purpose of the Study:

• To develop a classical algorithm for simulating boson sampling with partially distinguishable photons.
• To identify conditions under which this classical simulation remains efficient.
• To establish a lower bound for photon indistinguishability needed for quantum advantage.

Main Methods:

• Expressing boson sampling with partial distinguishability using fewer photons.
• Developing a classical simulation algorithm based on this expression.
• Analyzing the computational cost scaling with the number of photons.

Main Results:

• Boson sampling with partially distinguishable photons can be simplified.
• An efficient classical simulation algorithm is proposed.
• Conditions for efficient simulation determine the threshold for quantum advantage, showing polynomial cost increase with more photons.

Conclusions:

• Partially distinguishable photons can be leveraged for efficient classical simulation of boson sampling.
• This work provides a benchmark for quantum advantage claims in boson sampling experiments.
• The findings guide the design of future experiments to demonstrate quantum computational superiority.