Introduction to Proofs of Quantumness

In this talk I will give an introduction to proofs of quantumness. Such protocols can be executed using local quantum computations and only classical communication. I will begin by defining and motivating proofs of quantumness. I will then describe the specific construction by Brakerski et al. [1] and how it uses the Learning with Errors problem. Finally, I will briefly describe proofs of quantumness protocols based on other cryptographically hard problems.

[1] Brakerski, Z., Christiano, P., Mahadev, U., Vazirani, U., & Vidick, T. (2021). A cryptographic test of quantumness and certifiable randomness from a single quantum device.