Quantum Meets Minimum Circuit Size Problem
summary
Defines three quantum MCSPs (Boolean functions, unitaries, and states) and shows concrete complexity and reductions: MQCSP in QCMA, multi-output MQCSP is NP-hard and MQCSP is SZK-hard, and an MQCSP oracle breaks PRGs so it connects to post-quantum crypto and learning. Verification uses the swap test and coherent test to certify states/unitaries. Provides a search-to-decision reduction (no ancillas) and a state self-reduction via 0/1 decomposition. Applications include distinguishing pseudo-random states and a proposed link to wormhole-volume estimators.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:24Classical MCSP overview
- 1:12Complexity of MCSP
- 2:02Variants and hardness
- 2:44Connections in computer science
- 4:06Motivation for quantum study
- 5:05Defining quantum problem versions
- 7:17Quantum circuit fundamentals
- 9:51Key considerations for quantum
- 11:53Quantum boolean circuit size
- 14:56Complexity class analysis
- 18:04Cryptographic connections
- 20:31Learning and lower bounds
- 24:28Quantum object verification
- 29:36Search-to-decision reductions
- 35:16Self-reduction and applications
- 39:30Conclusion and open questions
related talks
37mQuantum Meets the Minimum Circuit Size Problem
18mSAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum(…)
30mQuantum Constant Propagation
34mTime-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
01h 10mQuantum Advantage with Shallow Clifford Circuits
48mThe Quantum Games PCP: Results and Confessions
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
22mQuantum space, ground space traversal, and how to embed multi-prover...