Quantum Distributed Algorithms for Detection of Cliques
summary
Takes any classical distributed listing routine and converts it into a faster quantum detection routine by running nested Grover searches over carefully batched candidate sets, reusing classically broadcast neighborhood data; concrete gains include turning triangle listing N^{1/3} into K4 detection in N^{1/5} rounds in the quantum congested clique, and a general recipe: list K_q then quantumly extend by T to detect K_{q+T} faster. Works with CONGEST via random partitions and load balancing, and shows a separation (detection faster than listing) and barriers to stronger lower bounds.
AI-written summary · about
chapters (8)
- 0:00Subgraph Existence
- 0:59Main Result
- 6:39Quantum Distributed Settings
- 7:44Grover Search (1996)
- 8:24Distributed Grover Search (Le Gall, Magniez 2018)
- 11:54Nested Grover Search
- 16:45K3 Detection in Quantum Congested Clique
- 22:46Summary
related talks
34mA NASA Perspective on Quantum Computing, with Emphasis on Recent Results in Distributed Computing
46mSymmetries, Graph Properties, and Quantum Speedups
01h 06mQuantum Algorithms for Approximating Partition Functions
01h 10mQuantum Advantage with Shallow Clifford Circuits
44mQuantum Complexity of Clique Homology
18mAutomated distribution of quantum circuits via hypergraph partitioning
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum
48mQuantum Linear Algebra Using Subspace States