Quantum Rewinding Tutorial, Part 2: How to Run a Quantum Attacker Many Times
summary
Shows a concrete alternating projectors procedure that repairs a measured quantum prover by alternating the challenge projector Pi_R with a projector implemented via the Marriott–Watrous estimator, producing many accepting transcripts and yielding post‑quantum soundness for Kilian‑style succinct arguments. The reduction pays a polynomial overhead (authors report worst‑case blowups like ~1/ε^5 and an additive ε loss per repair), needs nonuniform classical advice to bootstrap, and preserves only a repaired success probability rather than the original prover state.
AI-written summary · about
chapters (6)
- 0:00Start
- 38:13Return to Substance Lemma
- 43:51How Do You Measure the Proven Successful Ability
- 44:40Estimate the Success Probability of the Prover
- 46:22Estimate Success Probability
- 57:10Epsilon Guarantee
