Spoofing cross entropy measure in boson sampling

Understand

Cross entropy (XE) measure is a widely used benchmarking to demonstrate quantum computational advantage from sampling problems, such as random circuit sampling using superconducting qubits and boson sampling (BS).

• We present a heuristic classical algorithm that attains a better XE than the current BS experiments in a verifiable regime and is likely to attain a better XE score than the near-future BS experiments in a reasonable running time.
• The key idea behind the algorithm is that there exist distributions that correlate with the ideal BS probability distribution and that can be efficiently computed.
• The correlation and the computability of the distribution enable us to post-select heavy outcomes of the ideal probability distribution without computing the ideal probability, which essentially leads to a large XE.