MilestoneTheory & algorithmsConfirmed

Bravyi, Gosset and König prove an advantage for shallow quantum circuits

Apr 3, 2017

Sergey Bravyi, David Gosset and Robert König prove, without unproven assumptions, that constant-depth quantum circuits solve a problem that classical circuits of constant depth cannot. The problem, the 2D Hidden Linear Function problem, is a version of Bernstein–Vazirani without a black box.

Why it matters

Most claims of quantum advantage rest on conjectures about classical hardness. This one is a proof, though it compares restricted circuit models rather than full computers.

Sergey Bravyi · David Gosset · Robert König · IBM

See it on the timeline