Quantum Meets Minimum Circuit Size Problem

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


Duration: 43:46
511 views
4

Nai-Hui Chia (Rice University)
https://simons.berkeley.edu/talks/nai-hui-chia-rice-university-2023-02-15
Lower Bounds, Learning, and Average-Case Complexity

Abstract
In this talk, we study quantum computing through the lens of the minimum circuit size problem (MCSP). In particular, we start by defining problems of computing quantum circuit complexity of Boolean functions, unitaries, and quantum states. Then, we will explore their hardness, the relations between the three quantum MCSPs and their variants, and their connections to quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity. Due to the fundamental differences between classical and quantum circuits, most results require extra care and reveal properties and phenomena unique to the quantum setting. The talk will be mainly based on [arXiv 2108.03171], and we will also discuss recent attempts to connect quantum meta-complexity problems to quantum primitives.



Other Videos By Simons Institute for the Theory of Computing


2023-02-18Learning with Distributional Inverters
2023-02-18What (Doesn't) Make Learning Algorithms Generalize?
2023-02-17Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
2023-02-17On Low End Obfuscation and Learning
2023-02-17Average-case Complexity for Polynomials, and All That
2023-02-17On the Average-case Complexity of the Nearest Boolean Vector to a Subspace
2023-02-17New Approaches to Heuristic Pac-learning vs. PRFs
2023-02-16Succinct Neural Networks
2023-02-16New Lower Bounds and Derandomization for ACC, and a...
2023-02-16Learning Safe Action Models
2023-02-16Quantum Meets Minimum Circuit Size Problem
2023-02-16A Duality Between One-Way Functions and Average-Case Symmetry of Information
2023-02-15Learning Versus Pseudorandom Generators in Constant Parallel Time
2023-02-15Quantum Learning Algorithms Imply Circuit Lower Bounds
2023-02-15Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
2023-02-15Replicability in Learning
2023-02-15Extending Generalization Theory Towards Addressing Modern Challenges in Machine Learning
2023-02-14The Mystery of the Missing String
2023-02-14How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
2023-02-14Journey with Eric Allender: From Turing Machines to Circuits, and Back
2023-02-14Improved Learning from Time-bounded Kolmogorov Complexity


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Lower Bounds Learning and Average-Case Complexity
Nai-Hui Chia