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.

1. 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.