When do you need an inverse or controlled unitary oracle?
summary
Amplitude estimation provably needs both U and U^{-1} to get the usual 1/ε vs 1/ε^2 quantum speedup: with only forward queries and large dimension d ≳ 1/ε^2 the optimal cost is Θ(1/ε^2). Proof uses compressed‑oracle purification and a Feynman‑path histogram decomposition to show forward queries only produce incoherent (probability) errors. By contrast controlled‑U is useful only to reveal global phase: controls only detect global phase and can be removed at cost of ancillas (≈log n and a d‑sized register).
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:05Motivation for unitaries
- 8:42Why inverse unitaries help
- 20:43Amplitude estimation regimes
- 37:27Controlled unitaries: when needed
- 50:20Removing controlled unitaries
- 1:00:00Summary and questions
related talks
20mUnitary property testing lower bounds by polynomials
45mInteractive Proofs for Synthesizing Quantum States and Unitaries
01h 00mExplicit Orthogonal and Unitary Designs
01h 06mQuantum Advantage Without Structure
01h 09mRecent Progress in Quantum Advantage
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
20mThe Quantum Supremacy Tsirelson Inequality
21mQuantum versus Randomized Communication Complexity, with Efficient Players