Understanding this breakthrough requires a fair amount of background. Most readers will know that a quantum advantage is when a quantum computer answers a problem with a dramatically better runtime than a classical computer and that verifiability means it is easy to check that the answer is correct. The structure that is mentioned in the title of the paper refers to the distinction between periodic functions and random functions. The former are important to famous quantum algorithms such as Shor’s, while the latter are important in cryptography. The authors of the paper devised their own unusual problem to which several valid answers are possible. They considered a quantum processor that can give a superposition of inputs to a random oracle function and a normal computer that can only access the function classically. They showed that this setup produces a verifiable quantum advantage despite there not being any structure in the problem that the quantum computer could exploit. Research Roundup for July 2022 – Quantum Computing Report