Beating classical heuristics for the binary paint shop problem with the QAOA
summary
Work shows the binary paint shop problem (BPSP, APX-hard) maps to a spin glass and a constant-depth QAOA gives provable average improvements in the n→∞ limit. Performance: p=1 is near random, p=2 beats red‑first, QAOA p=4 beats greedy, p=7 beats recursive greedy. Qubits scale with number of car pairs while circuit depth stays constant. Small experiments on an AWS Braket trapped-ion device show signal for 2–8 cars, but 9–11 are indistinguishable from random.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 1:00Welcome
- 1:37Quantum Applications
- 6:14Finding an Algorithm
- 9:10The Problem
- 11:07Why Quantum
- 13:40QAOA
- 14:39QAOA Algorithm
- 16:08Results
- 17:14Infinite Size Problem
- 18:11Experiments
- 19:13Questions
related talks
52mThe Virtues of the Quantum Approximate Optimization Algorithm
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
41mQuantum Computing in Practice: Where We Are, What Works, and What’s Next
01h 05mVerifiable quantum advantage: old and new ideas
18mSAQR-QC: A Logic for Scalable but Approximate Quantitative Reasoning about Quantum(…)
01h 10mQuantum Advantage with Shallow Clifford Circuits
37mQuantum Pseudorandomness and Classical Complexity
17mExploring Quantum Algorithms for Optimal Sensor Placement in Production Environments