Spoofing cross entropy measure in boson sampling

Abstract

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. Our method scores a better XE than the recent Gaussian BS experiments when implemented at intermediate, verifiable system sizes. Much like current state-of-the-art experiments, we cannot verify that our spoofer works for quantum advantage size systems. However, we demonstrate that our approach works for much larger system sizes in fermion sampling, where we can efficiently compute output probabilities. Finally, we provide analytic evidence that the classical algorithm is likely to spoof noisy BS efficiently.

7+11 pages, 5+6 figures

References in corpus (6)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
• A polynomial-time classical algorithm for noisy random circuit sampling

Cited by in corpus (12)

• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Beyond-classical computation in quantum simulation
• Classical algorithm for simulating experimental Gaussian boson sampling
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• The Second Moment of Hafnians in Gaussian Boson Sampling
• High performance Boson Sampling simulation via data-flow engines
• Boson sampling with ultracold atoms in a programmable optical lattice
• Quantum enhancement of spoofing detection with squeezed states of light
• Gaussian boson sampling with click-counting detectors
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Provable and Verifiable Quantum Advantage in Sample Complexity