Breaking and Making Quantum Speedups

The main goal of this workshop is to share recent exciting developments in quantum algorithms and complexity. There are two quantum algorithms that go beyond period-finding which were promising candidates for classically verifiable quantum advantage: quartic speedups for planted inference (like Planted k-XOR [SOKB25]) and DQI [JSW+25] style algorithms for certain search problems over linear codes (such as SIS∞  [CLZ22]). Both the results by [SOKB25] and [CLZ22] have recently been “dequantized” — classical algorithms have been found which falsify the claims of super-quadratic quantum advantage in both works, at least in certain parameter regimes. 

On a more optimistic note, we discuss new quantum algorithmic ideas which are promising candidates for obtaining quantum advantage.

When: 14 December, 8:30am - 4:30pm

Where: Blackwattle 1, PARKROYAL Darling Harbour, Sydney