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.
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
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
Familiarity with linear algebra will be good, along with complex numbers and computational complexity.
- “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.
D. 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
Desarrollado por el Departamento de Computación, FCEyN, UBA