IBM Researchers’ Clifford Group Investigation Unexpectedly Reveals New Quantum Advantage Proof

(IBM.Quantum.blog) IBM researchers has discovered a new mathematical proof of quantum advantage – the elusive threshold at which quantum computers outperform classical machines in certain use cases.
Sergey Bravyi and Dmitri Maslov are authors of this IBM Quantum blog and explain they began their current line of investigation to study the structural property of the Clifford group, describing a set of transformations that generate entanglement, play an important role in quantum computing error correction, and are used in (randomized) benchmarking. In a series of one-thing-leads-to-another findings, they ended up discovering a new mathematical proof of quantum advantage.
Their arXiv preprint, “Hadamard-free circuits expose the structure of the Clifford group,” shows the smallest known computation that is more efficient when implemented quantumly rather than on a classical reversible computer, counting the 2-(qu)bit gates in respective circuits. This illustrates what can be called a “white box” quantum advantage. In contrast, a number of “black box”-style advantages are known, with the difference that a black box assumes no knowledge of own inner workings, whereas white box is an explicit circuit.
A black box algorithm usually concerns discovering a property of the function computed by the given black box. The Bernstein–Vazirani algorithm is an example of a black box algorithm that discovers the hidden linear function computed by the black box with a single query, thus providing a quantum advantage over the best possible classical algorithm (whose query complexity is linear in the number of inputs to the black box).