The Travelling Santa Problem - can quantum solve it?

In this special holiday episode of the Qubit Value Podcast, the discussion centers on the "Traveling Santa Dilemma," a festive framing of the Traveling Salesman Problem (TSP) within the realm of quantum computing. The hosts explain that while pure quantum hardware is still in its "toy-making phase" for such complex optimizations—requiring nearly 10,000 qubits to map just 100 cities due to the scaling nature of one-hot encoding—significant strides are being made via hybrid quantum-classical workflows. The episode explores various technical workarounds like warm starting QAOA, HOBO (Higher-Order Binary Optimization) for qubit compression, and amplitude encoding to maximize the utility of limited hardware. Although classical supercomputers still outperform quantum machines on raw TSP speed as of late 2025, the hosts remain optimistic about the future, pointing to error-correction milestones and the expected arrival of fault-tolerant systems like IBM’s Starling and Blue Jay processors between 2029 and 2033.