A research-level analysis of the next milestones in quantum advantage, focusing on the 100 logical qubit regime. Three concrete goals are proposed: (1) demonstrating fault-tolerant quantum advantage using IQP circuits, (2) closing the verification loophole via random circuits with symmetries (graph states, Bell sampling, stabilizer measurements) in a trusted-experimenter scenario, and (3) achieving classically verifiable quantum advantage in an untrusted server scenario using random circuits with planted secrets. The post also discusses certifiable random number generation as a first practical application, and highlights open theoretical challenges around noise thresholds and verification-simulation gaps.
Table of contents
The next milestone: classically verifiable quantum advantage1. Demonstrate fault-tolerant quantum advantage2. Closing the verification loopholeThree milestonesWhat I did not talk aboutSo long, and thanks for all the fish!References1.1K Impressions