Quantum Weak Coin Flipping with Arbitrarily Small Bias

on YouTube ↗01h 05m

" summary

Claim: quantum weak coin flipping can reach arbitrarily small bias (ε → 0). Proof uses Kitaev SDP duality, rewrites cheating bounds as point games built from eigenvalue-weight pairs, and characterizes allowed moves via convex-cone duality and operator monotone functions. Existence proof is nonconstructive but verified and simplified from Mochon; qubit cost scales like O(log(1/ε)) while round complexity explodes (roughly (1/ε)^(1/ε)). Construction relies on catalytic intermediate points and a discretization with parameters ω → 0, γ → ∞.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:47Secure Computation
3. 1:35Strong vs Weak Coin Flipping
4. 3:25Security Conditions
5. 4:32Quantum Coin Flipping
6. 7:13Why care about coin flipping
7. 11:17Status of weak coin flipping result
8. 12:48Roadmap
9. 17:16Proof outline
10. 18:41Protocol
11. 21:07Cheating Probabilities as SDPs
12. 28:38Dual Feasible Points as security witness
13. 46:16EBM, operator monotone, valid functions
14. 50:10Duals, duals of duals, ...
15. 53:25Examples of valid functions
16. 53:56"Equivalence" of EBM and Valid functions
17. 56:37Time independent point game