Hi all,
this week Petia Arabadjieva will tell us about her master thesis "Towards more practical proofs of quantum computational advantage through knowledge assumptions", see below for the abstract.
The talk will take place on Thursday at 14:00 in HIT E41.1.
Best,
Ladina
****
Title: Towards more practical proofs of quantum computational advantage through knowledge assumptions
Abstract: Demonstrating quantum advantage, the point where a quantum computer can solve a problem that no existing classical computer can, is both a theoretical and technological challenge. It requires a problem that is plausibly intractable for classical algorithms and which admits an efficient quantum algorithm, ideally one that can be performed with noisy intermediate-scale quantum (NISQ) devices. Additionally, the problem's solution should be efficiently verifiable by a classical computer. Existing single-round protocols (like asking the quantum computer to factor a large number) require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. As such, current proofs of quantum advantage are out of reach for near-term devices.
In this talk, I will provide an overview of the main paradigms for demonstrating quantum computational advantage, highlighting their respective strengths and weaknesses, with an emphasis on interactive (i.e. multi-round) proofs of quantumness. The main focus will be an exposition of the two-round BCMVV18 protocol. Finally, I will briefly outline the main result of my thesis: how we modified the BCMVV18 protocol into a single-round proof of quantumness through the use of a knowledge assumption.