Distributed Quantum Proofs for Replicated Data
summary
Claim: replicated-data consistency can be certified with log N qubits per certificate and per message, versus Θ(N) classically. Construction uses quantum fingerprints — a superposition over random hash functions and their hashes — and pairwise equality via the SWAP test. The protocol works on a path with two terminals (Alice/Bob), tolerates non‑product or corrupted certificates, and lets certificates be reused without collapsing when data is equal. Classical randomized lower bound of linear size is proved; extending to general graphs remains work.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:14Replicated Data
- 1:16Distributed Certification
- 3:36Certificates
- 4:45Why Should we Care?
- 5:29Example: Certificate = Data
- 7:36Parameters
- 8:05Qubits
- 8:22Our Results
- 9:59Main Result
- 10:20Communication Complexity
- 12:13Distance Equality
- 13:22A Quantum Protocol
- 16:58The Quantum Fingerprints
- 17:42The SWAP Test
- 18:38More Challenges
- 19:07Conclusion & Questions
related talks
45mClassical Verification of Quantum Computational Advantage
49mCertifying almost all quantum states with few single-qubit measurements
16mAsynchronous Multi-Party Quantum Computation
42mTests for "Quantumness"
01h 03mQuantum Proofs of Knowledge
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
16mQuantum Information Meets Cryptography
32mBeating Classical Impossibility of Position Verification