A NASA Perspective on Quantum Computing, with Emphasis on Recent Results in Distributed Computing
Talkat Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms · 2024-04-22..04-26·
summary
The papers claim provable round-complexity wins in the quantum CONGEST-CLIQUE model: two algorithms yield an approximately optimal Steiner tree and an exact directed minimum spanning tree in asymptotically fewer communication rounds than any known classical algorithm, by combining distributed Grover with triangle finding, routing tables and min-plus (distance) products to get n^{1/4} rounds versus prior bounds around n^{1/3. The analysis tracks constants and log factors (roughly log^6), pushing the practical crossover to about 10^{18} nodes*, so the speedup is theoretical but not yet implementable.
AI-written summary · about
chapters (14)
- 0:00Quantum distributed algorithms
- 2:16Classical distributed models
- 6:51Quantum models and results
- 9:26New quantum Steiner/spanning trees
- 14:57Survivable network design
- 15:20Grover search subroutine
- 18:26Triangle finding and distance products
- 21:27Shortest paths and routing
- 23:00Asymptotic improvements
- 25:15Open questions and future
- 27:05Broader quantum models
- 28:09Floquet codes update
- 29:34Photon indistinguishability
- 30:47Quantum computing impact
related talks
24mQuantum Distributed Algorithms for Detection of Cliques
31mLimits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity v
46mQuantum computing
32mThe intersection of Quantum Computing and Distributed Systems...
01h 00mQuantum Computing and the Entanglement Frontier
02h 42mQuantum Computing Exposed: Deep Dive
28mThe future of computing with Quantum Computing
24mQuantum Computing: a Treasure Hunt, not a Gold Rush