Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity v
summary
Shows conditional linear quantum lower bounds for zero-edge-weight triangle and a list of computational geometry problems by quantizing classical fine-grained reductions. Uses a quantum walks framework plus dynamic data structures to prove that a sorted variant of 3SUM is as hard as 3SUM on quantum machines, ruling out sublinear-time algorithms under the 3SUM conjecture. Reports the known quantum 3SUM query algorithm is n^{3/4} and that only up to quadratic speedups are possible, so many proposed quantum gains are tight.
AI-written summary · about
chapters (7)
- 0:00Start
- 0:18How useful are Quantum Computers?
- 2:47For example
- 4:18Upper Bounds and Lower Bounds in Complexity Theory
- 5:25Our technique: Fine-grained Reduction
- 11:333SUM based lower bound for O-Edge-Wt-Triangle Findi
- 18:35Quantum Walk Based Reduction from 3SUM to Sorted-3SUM
related talks
46mSymmetries, Graph Properties, and Quantum Speedups
34mA NASA Perspective on Quantum Computing, with Emphasis on Recent Results in Distributed Computing
44mNo Quantum Speedup Over Gradient Descent for Non-Smooth Convex Optimization
01h 06mQuantum Algorithms for Approximating Partition Functions
01h 10mQuantum Advantage with Shallow Clifford Circuits
06mHow looking at a problem quantumly could solve it faster?
19mAn Industry Perspective on the Path Forward in Quantum Optimization
01h 09mRecent Progress in Quantum Advantage