Quantum Meets the Minimum Circuit Size Problem
summary
Defines concrete quantum MCSP variants (Boolean, state, unitary) and proves MQCSP in QCMA as an upper bound and NP-hardness for a multi-output quantum MCSP. Builds explicit search-to-decision reduction and a self-reduction for the state/unitary versions by exploiting circuit reversibility to reconstruct gates gate‑by‑gate. Shows S‑MCSP can break certain pseudorandom states and one‑way functions, and relates S‑MCSP instances to estimating wormhole volume under AdS/CFT plus a volume=complexity assumption.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:17Motivation
- 0:48Meta Complexity
- 1:37Minimum Circuit Size Problem (MCSP)
- 4:33Why MCSP?
- 5:48Roadmap
- 6:40Computational Problems in the Quantum World are Diffe
- 10:01Minimum Quantum Circuit Size Problem (MQCSP)
- 13:24Basic Complexity Results
- 16:16A Bird-Eye View
- 18:35Challenges and Difficulties in the Quantum Setting
- 22:35SMCSP
- 24:26Quantum-Unique Reductions
- 32:46Summary
- 33:56Future Directions
related talks
44mQuantum Meets Minimum Circuit Size Problem
18mSAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum(…)
22mQuantum space, ground space traversal, and how to embed multi-prover...
01h 10mQuantum Advantage with Shallow Clifford Circuits
30mQuantum Constant Propagation
34mTime-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
22mOptimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation
49mQuantum Garbled Circuits