A Simple Quantum Sketch With Applications to Graph Algorithms
summary
A log-qubit sketch stores several copies of the uniform superposition over set S and answers “how many disjoint pairs from a partition lie inside S” by measuring with projectors onto x±y. Measurements are destructive and single-pair partial querys plus a unitary swap let the sketch be updated in a stream. Sampling returns a pair with a ±1 sign if only one endpoint lies in S. Result: exponential quantum advantage in the two-player hidden-matching setting, a polynomial streaming advantage for triangle counting, and an exponential streaming advantage for Max-Dicut.
AI-written summary · about
chapters (14)
- 0:00Quantum sketching primitive
- 3:13Hidden matching sketch
- 7:43Quantum sketch construction
- 11:05Q&A
- 15:05Quantum streaming for graphs
- 17:36Triangle counting in streams
- 21:57Triangle counting generalized
- 25:16Sketch with swap and queries
- 27:45Q&A
- 31:39Swap and measurement ops
- 35:01Max cut quantum advantage
- 44:36Bias histogram streaming
- 49:17Summary
- 50:49Q&A
related talks
41mQuantum Computing deep dive
22mQuantum space, ground space traversal, and how to embed multi-prover...
59mDiving Into Q#
25mTalk By Ilya Mironov (Google Brain)
01h 20mVerifiable Quantum Supremacy: What I Hope Will Be Done
25mQuantum NP and Beyond
20mQuantum Circuit Compilation with #SAT
01h 02mQuantum Computing Deep Dive