Verifiable quantum advantage based on polynomials with planted structures

Markus Bläser, Michael Gullans, Dominik Hangleiter +2

A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also v…