Verifiable quantum advantage in extremely low depth
A new preprint describes a quantum sampling problem that can be solved by shallow circuits built from one- and two-qubit gates, is thought to be hard for polynomial-time classical algorithms under lattice-based assumptions, and can be verified efficiently by a classical computer. The paper reports two implementations, including one with log-logarithmic circuit depth.
Gate-based quantum hardware vendors could demonstrate the sampling task within two years on existing devices with modest qubit counts.