Quantum Garbled Circuits
summary
Defines quantum randomized encoding (decomposable, gate-by-gate) and constructs random Clifford + classical side information encodings that decode to the original quantum circuit, with perfect simulation available unconditionally and computational simulation assuming a quantum‑secure one‑way function. Encoding computes in constant depth class QC0 with fan-out; computational-size blowup is polynomial in circuit size, perfect-security size is doubly exponential in depth. Decoding and simulation run linear in encoding size. Applications include QMA Sigma protocols and quantum private simultaneous messages; Morimae‑style arguments block fully classical encodings.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 0:35Randomized encodings
- 8:20Defining garbled circuits
- 10:50Quantum setting definition
- 12:50Construction and complexity
- 18:30Applications in zero knowledge
- 20:05Technical Q&A session
- 21:55Construction overview
- 30:38Handling measurements
- 35:19Applications and open problems
related talks
28mA type-theoretic account of quantum computation (Extended Abstract)
01h 31mLightning Talks
01h 10mQuantum Advantage with Shallow Clifford Circuits
21mCobble: Compiling Block Encodings for Quantum Computational Linear Algebra
44mQuantum Meets Minimum Circuit Size Problem
01h 03mApproaching the Quantum Singleton Bound with Approximate Error Correction
19mAvenues for Quantum Error Correction and Mitigation
58mBosonic (And Other) Codes With Interesting Logical Gate Sets