A cryptographic proof of quantumness is a hypothetical test that could be used to prove a quantum computational advantage based on hardness assumptions from cryptography. An experimental realization of such a test would be a major milestone in the development of quantum computation. However, error tolerance is a persistent challenge for implementing such tests: we need a test that not only can be passed by an efficient quantum prover, but one that can be passed by a prover that exhibits a certain amount of computational error. In this talk I will present a technique for improving the error-tolerance in a cryptographic proof of quantumness. The technique is based on hiding a Greenberger-Horne-Zeilinger (GHZ) state within a sequence of classical bits. After giving an overview of this new approach, I will discuss one of the central tools used in the security proof: a strengthened uncertainty principle for the discrete Fourier transform.
Reference: C. Miller, "Hidden-State Proofs of Quantumness," https://arxiv.org/abs/2410.06368
