STOC 2022 Workshop: The Multiple Facets of Quantum Proofs
The The Multiple Facets of Quantum Proofs workshop took place at STOC TheoryFest 2022 on June 20-24, 2022 in Rome, Italy.
Videos of the talks are available on this link.

Alessandro Chiesa (UC Berkeley and EPFL),
Tom Gur (University of Warwick),
Dakshita Khurana (UIUC),
Giulio Malavolta (Max Planck Institute), and
Thomas Vidick (Caltech).
Proof systems are fundamental notions in the theory of computation. How does quantum information impact the power of information-theoretic and cryptographic proofs? On the one hand, quantum adversaries may be able to implement new kinds of attacks, by executing quantum algorithms or leveraging quantum correlations. On the other hand, quantum information may enable efficiently verifying richer classes of languages, in the single-prover setting or in multi-prover setting.
This workshop will discuss the multi-faceted impacts that quantum information (and beyond) has on central notions of proofs studied in complexity and cryptography, including NP proofs, interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs. The goal is to raise awareness about this rich area, through a tutorial day and two days of invited talks on recent research. The material will exemplify the impacts of taking a broad, physical perspective on the notion of proof.
The workshop will consist of three days, each consisting of 2-3 sessions of total length of 2.5 hours. The first day will be a tutorial day. The following two days will focus on cutting-edge results on the cryptographic and complexity-theoretic facets of quantum proofs. The first day of workshop is intended for equipping broad STOC audience with the necessary background, and the following two days will focus on recent research. All of the speakers mentioned below confirmed their participation.
Sevag Gharibian
Session 1: Sevag Gharibian

Title: Introduction to quantum proofs

Abstract: This talk gives a gentle introduction to quantum complexity theory, with a focus on proof systems. No background in quantum computing is required. Topics to be discussed include quantum analogues of NP, the "quantum Cook-Levin theorem" of Kitaev, and quantum interactive proofs. Selected key similarities and differences between the power of classical and quantum proof systems will be discussed, intended to lay some of the groundwork for the remainder of the talks in this workshop.

Giulio Malavolta
Session 2: Giulio Malavolta

Title: Classical Verification of Quantum Computation

Abstract: Can we delegate quantum computation to a single untrusted device, in such a way that correctness of the outcome is verifiable classically? This talk will give an overview of the techniques and survey recent advancements towards the resolution of this problem.

Zvika Brakerski
Session 1: Zvika Brakerski

Title: Constructive Post-Quantum Reductions

Abstract: Is it possible to convert classical cryptographic reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interactive reductions do carry over. However, when considering quantum auxiliary input, this conversion results in a non-constructive post-quantum reduction that requires duplicating the quantum auxiliary input, which is in general inefficient or even impossible. This violates the win-win premise of provable cryptography: an attack against a cryptographic primitive should lead to an algorithmic advantage.We initiate the study of constructive quantum reductions and present positive and negative results for converting large classes of classical reductions to the post-quantum setting in a constructive manner. We show that any non-interactive non-adaptive reduction from assumptions with a polynomial solution space (such as decision assumptions) can be made post-quantum constructive. In contrast, assumptions with super-polynomial solution space (such as general search assumptions) cannot be generally converted.

Nick Spooner
Session 2: Nick Spooner

Title: Post-quantum cryptographic proofs

Abstract: Using cryptographic hardness assumptions we can build proof systems with amazing properties, like succinctness and zero knowledge, which are believed to be impossible in the unconditional setting. Do these proof systems remain secure against quantum adversaries? If the hardness assumption is known to be false for quantum adversaries, then clearly the answer is no. However, the converse is far from clear. Even if the underlying assumption is "post-quantum", the original classical security proof can still fail in the quantum setting because quantum information behaves fundamentally differently to classical information. In this tutorial, I will outline the issues that arise and the new techniques that have been developed to tackle them.

Nai-Hui Chia
Session 3: Nai-Hui Chia

Title: Quantum Rewinding for Zero-Knowledge

Abstract: Zero-knowledge (ZK) interactive proof, introduced by Goldwasser, Micali, and Rackoff, is a fundamental primitive in cryptography. ZK protocols provide privacy to the prover by proving a statement without revealing anything except that the statement is true even though the verifier is malicious. To prove the ZK property, one shows the existence of an efficient simulator, such that for all malicious verifiers, the simulator can simulate the view generated by the prover and the malicious verifier. The simulator does not know the proof of the statement but can "rewind" the malicious verifier with black-box access to the verifier. When the malicious verifier only has classical computational power, constant-round black-box ZK (BBZK) protocols exist for all NP languages assuming the existence of one-way functions. Interestingly, in the quantum setting, the malicious verifier can have quantum auxiliary input and use quantum algorithms. This difference fails the classical rewinding techniques due to the no-cloning theorem, and thus the previous security proofs cannot be applied

Anand Natarajan
Session 1: Anand Natarajan

Title: MIP* -- Bell inequalities meet the PCP theorem

Abstract: At its heart, the study of MIP* is about devising protocols that enable a classical verifier efficiently to constrain the behavior of noninteracting, entangled quantum provers. These protocols combine workhorse ideas from classical proof systems, namely probabilistically checkable proofs and locally testable codes, with concepts from quantum information, namely Bell inequalities, the Tsirelson bound, and self-testing. In this talk I will give an overview of the techniques used in designing MIP* protocols, focusing on the task of efficiently testing many entangled qubits. I will also discuss the many open problems that remain.

Igor Shinkar
Session 2: Igor Shinkar

Title: Non-signalling proofs

Abstract: Non-signaling strategies are a generalization of quantum strategies. Recently, they have found applications in TCS, including proving inapproximability results for linear programming and constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCP) systems that are sound against non-signaling strategies. In this work I will survey some of the work done in this direction in the recent years, and present some open problems.

Alexandru Gheorghiu
Session 3: Alexandru Gheorghiu

Title: Proofs of quantumness

Abstract: Recent demonstrations of quantum computational advantage by groups at Google and USTC have highlighted the impressive capabilities of near-term quantum computers. However, these experiments come at the cost of requiring exponential time to check the results. Is it possible to certify quantum advantage efficiently (i.e. in polynomial time)? The answer is yes, using protocols known as proofs of quantumness. In this talk, I will survey this area, discussing the various ways in which proofs of quantumness can be constructed, the types of assumptions they rely on and recent developments towards making them more suitable for use with near-term quantum computers.