Verifiable Quantum Advantage Without Structure | Quantum Colloquium

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=sKqhWutmIuA


Duration: 1:14:19
1,948 views
38

Mark Zhandry (Princeton)
https://simons.berkeley.edu/events/quantum-colloquium-verifiable-quantum-advantage-without-structure
Quantum Colloquium

“Structure” has long played a central role in proposals for super-polynomial quantum advantage. This is especially true for problems whose solutions can be efficiently verified, where all prior results require algebraic computational conjectures or oracles with very specific features. In this talk, I will discuss a new approach for verifiable quantum advantage which, for a reasonable complexity-theoretic notion of “structure”, requires no structure at all.

* Joint work with Takashi Yamakawa



Other Videos By Simons Institute for the Theory of Computing


2022-04-27Cardinality Bounds and Parameterization for Latent Variable Graphical Models
2022-04-27Latent Variable Justifies the Stronger IV Bounds
2022-04-26Generalized Instrumental Inequalities: Complexity, Sharpness, Robustness
2022-04-26Sequential Models
2022-04-26The Most General Causal Theory of Correlations Restricted to Bounded Multipartite...
2022-04-26Experimental Entanglement of Temporal Order
2022-04-26Self-Tests of Physical Theories in Networks and Their Implications for the Foundations of...
2022-04-25Applications of The Inflation Technique for Causal Inference
2022-04-23The Arrow of Time in Causal Networks
2022-04-20Quantum Colloquium – Panel
2022-04-20Verifiable Quantum Advantage Without Structure | Quantum Colloquium
2022-04-19Equilibrium Computation and Machine Learning
2022-04-13Panel | Quantum Colloquium
2022-04-13Is There Evidence of Exponential Quantum Advantage in Quantum Chemistry? | Quantum Colloquium
2022-04-12Stability and Learning in Repeated Games
2022-04-07The Science of Cause and Effect: From Deep Learning to Deep Understanding
2022-04-06Panel | Quantum Colloquium
2022-04-06On the Limits for Certifying Quantum Speedups for Noisy Circuits | Quantum Colloquium
2022-04-02Inference on Auctions with Weak Assumptions on Information
2022-04-02Reinforcement Learning for Complex Security Games and Beyond
2022-04-02Communicating with Anecdotes


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Quantum Colloquium
Mark Zhandry