On Certified Randomness from Fourier Sampling or Random Circuit Sampling

Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this 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…

• NS
  National Science Foundation

  Awards: 2044923, 2007462, 2145474, 1714779, CAREER, CCF-2044923, CCF-2145474
• UD
  U.S. Department of Energy

  Award: DE-SC0020360
• OO
  Office of Science
• AF
  Air Force Office of Scientific Research

  Awards: FA9550-, FA9550-18-1-0148, -21-1-, FA9550-21-1-0008, FA9550, FA9550-21-1-0392