Alex B. Grilo: Recent advances in Zero-knowledge proofs in the quantum setting

Channel:
United States QuICS
Subscribers:
2,470
Published on ● Video Link: https://www.youtube.com/watch?v=KZwSkcYC4hY


Duration: 1:01:51
240 views
0

Zero-knowledge proofs are a fundamental building block in classical Cryptography,
having far-reaching applications. Recently, there has been some effort in improving
our understanding of Zero-knowledge for quantum complexity classes, that will
hopefully lead us to striking objects as in the classical case. The goal of this talk
is to give an overview of some of such results, in particular:
- All multi-prover system with entangled provers protocols can be made ZK
- Simpler ZK protocols for QMA (which includes the first Proof of Knowledge
ZK protocol and the first Non-interactive ZK protocol in the secret parameters
model).

Such results are achieved through new tools, namely Simulatable codes,
QMA-completeness (under standard Karp reductions) of Consistency of Local
Density Matrices and Simulatable proofs, that could be useful in different
contexts.

This talk is based on a joint work with William Slofstra and Henry Yuen, and on
a joint work with Anne Broadbent.



Other Videos By QuICS


2020-08-17Dmitry Green: A superconducting circuit realization of combinatorial gauge symmetry
2020-07-23Matt Hastings: The Power of Adiabatic Quantum Computation with No Sign Problem
2020-06-19William Slofstra: Arkhipov's theorem, games, groups, and graphs
2020-06-10Ramis Movassagh:Cayley path & quantum supremacy:Average case # P-Hardness of random circuit sampling
2020-06-04Steve Flammia: Characterization of Solvable Spin Models via Graph Invariants
2020-05-20Aram Harrow: Small Quantum Computers and Large Classical Data Sets
2020-02-05Dominik Hangleiter: (How) can we verify quantum supremacy?
2020-02-05Giacomo Torlai: Enhancing Quantum Simulators with Neural Networks
2019-11-21Felix Leditzky: Playing Games with Multiple Access Channels
2019-11-14Anand Natarajan: NEEXP ⊆ MIP*
2019-11-14Alex B. Grilo: Recent advances in Zero-knowledge proofs in the quantum setting
2019-10-03Andrea Coladangelo: A simple two-player dimension witness based on embezzlement
2019-09-06John Preskill: Quantum speedups in the NISQ era
2019-09-06Aditya Nema: Unitary Designs and quantum channels with super additive classical capacity
2019-09-06Krysta Svore: Programming for quantum solutions today and tomorrow
2019-09-06R. Teal Witter: Applications of the quantum algorithm for st-connectivity
2019-09-06Ken Brown: Error Reduction, Fault Tolerance, and Scalability
2019-09-06Chris Granade: Bayesian ACRONYM Tuning
2019-09-06Bryan O'Gorman: Parametrization of tensor network contraction
2019-09-06David Gosset: Simulation of quantum circuits by low-rank stabilizer decompositions
2019-09-06Alex B. Grilo: A simple protocol for verifiable delegation of quantum computation in one round


Tags:
quantum computing
interactive proofs
complexity theory