On Certified Randomness from Fourier Sampling or Random Circuit Sampling

Abstract

Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson (2018, 2020) proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of his protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by Aaronson's work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson's protocol. In further support of Aaronson's proposal, we prove a Fourier Sampling version of Aaronson's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption - at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.

References in corpus (17)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Random Numbers Certified by Bell's Theorem
• Characterizing Quantum Supremacy in Near-Term Devices
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Certified randomness in quantum physics
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Sample complexity of device-independently certified "quantum supremacy"
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Quantum supremacy and random circuits
• Verifiable Quantum Advantage without Structure
• Depth-efficient proofs of quantumness
• Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent
• Generalized Quantum Arthur-Merlin Games

Cited by in corpus (2)

• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs