How looking at a problem quantumly could solve it faster?
summary
Quantum version of constraint satisfaction sometimes admits solutions where classical version provably doesn't: the 3x3 magic square has no ±1 assignment but does when cells are unitary matrices (Pauli X,Y,Z tensor products). A preprint identifies a class called Max-2-Lin or "max tunneling" problems where quantum solutions are computationally easier, and presents an algorithm that can extract classical solution from a quantum solution, so far matching best classical algorithms.
AI-written summary · about
related talks
01h 10mQuantum Advantage with Shallow Clifford Circuits
31mLimits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity v
01h 28mHow Simulating Balls and Springs Captures the Power of Quantum Computing
20mLarge-scale hybrid quantum computing solution of linear systems of equations
23mMore privacy, better social welfare: using quantum resources for daily problems
38mFacing the Future: A Discussion and Reality Check on Quantum Computing Applications
44mQuantum Meets Minimum Circuit Size Problem
01h 36mAlgorithms for Algebraic Lattices: Classical and Quantum