Abstract: 

Quantum computers are now being (slowly) built by various companies, but we may be many years away from the possibility of these machines demonstrating something like factoring of numbers in a short amount of time. In the interim period, how can we demonstrate that we are doing something only a quantum computer can do? That is, can we get a «proof of quantumness» from these machines.

We could visit the laboratories where these machines are being built and convince ourselves each component has a quantum mechanical description, but do these components combine to do something only a quantum computer can do? At the end of the day, we can only interact with these machines in a «classical» manner: we send strings of data to these labs and receive strings back. We may as well treat these machines as a black box with minimal assumptions.

This is analogous to interactive proof systems and their related complexity classes such as NP, where a time-bounded verifier receives proofs from a computationally unbounded prover.

In this course I will give an overview to the approaches taken in addressing the question of producing proofs of quantumness, taking in ideas from the foundations of quantum physics to complexity theory and cryptography.

Objectives of the course:

By the end students should:

– Be able to explain the basics of quantum computation

– Be able to explain why proofs of quantumness might not fit within the standard paradigm of interactive proof systems like NP

– Have an appreciation for the violation of a Bell inequality (the basis for the 2022 Nobel

Prize in Physics) and its implications

– Be able to distinguish different assumptions going into proofs of quantumness, and

– Be able to describe a protocol for a proof of quantumness not based on the Bell Inequality

Language: English

Brief index:

– Brief introduction to quantum computing

– NP and the quantum complexity class BQP

– Bell nonlocality and entanglement

– Interactive proof systems with efficient quantum provers

– Proofs of quantumness from one-way functions

Suggested bibliography:

– “If Quantum Mechanics Falsifiable? A computational perspective on the foundations of Quantum Mechanics”, D. Aharonov and U. Vazirani https://arxiv.org/abs/1206.3686

– “Bell nonlocality”, N. Brunner et al, Rev. Mod. Phys. 86, 419 (2014)

– “Classically-Verifiable Quantum Advantage from a Computational Bell Test”, G. Kahanamoku-Meyer et al, Nat. Phys. 18, 918-924 (2022)

– “A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device”, Z. Brakerski et al, https://arxiv.org/abs/1804.00640

Student’s preferred background: familiarity with linear algebra will be good, along with complex numbers and computational complexity.