How to model unitary oracles
summary
Argues that “efficient” unitaries must track global phase and that oracle access should allow conjugates and transposes as well as controlled and inverse queries; proves indifferentiability from a classical oracle fails unless the oracle exposes U†/U/U^T, gives a Simon-style attack on a binary-phase PRU construction, and shows any ancilla‑respecting homomorphism like determinant forces an exponential ancilla blowup (dimensions ~2^{2^n}), so many natural extensions are provably infeasible. Tools: gate‑by‑gate reductions, representation theory, indifferentiability, Hadamard/Simon techniques.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 0:54Efficient unitary implementation
- 4:07Global phase in unitaries
- 13:34Controlled access for unitaries
- 18:20Conjugates and transposes
- 21:42Black box separations
- 28:52Indifferentiability limits
- 33:51Pseudorandom unitaries
- 41:14Controlled and conjugate operations
- 57:46Ancilla complexity and errors
- 1:00:13Q&A
related talks
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
45mInteractive Proofs for Synthesizing Quantum States and Unitaries
20mUnitary property testing lower bounds by polynomials
22mOptimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation
23mA feasible and unitary programming language with quantum control
01h 06mQuantum Advantage Without Structure
02h 41mLightning Talks
41mOne-Way Functions Imply Secure Computation in a Quantum World