Quantum Computing

Quantum Conundrum: Clifford Group Investigation Unexpectedly Reveals New Quantum Advantage Proof

Share this post:

In research, scientists often set out to make a discovery only to find their work has taken them unexpectedly in some new direction. When we began our current line of investigation, the goal was 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, however, we ended up discovering a new mathematical proof of quantum advantage – the elusive threshold at which quantum computers outperform classical machines in certain use cases.

Our 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).

We used a circuit, rather than an algorithm, to more transparently demonstrate the quantum advantage. A quantum circuit, being an ordered sequence of instructions for qubits, is the fundamental building block of quantum computation. The ability to express solutions to problems by quantum circuits requiring fewer resources (such as the number of gates used) than classical circuits solving the same problem defines the power and extent of the advantage by a quantum computer.

Our paper contains an instance of computational quantum advantage where an optimal classical 8-gate reversible linear circuit is implemented more efficiently using seven entangling gates as a quantum Clifford circuit. This work extends previous studies examining quantum advantage.

In 2018, Sergey and a group of colleagues proved there are problems that require only a fixed circuit depth when done on a quantum computer, even if you increase the number of qubits used for inputs. These same problems require the circuit depth to grow larger when you increase the number of inputs on a classical computer. That study was the first demonstration of unconditional separation between quantum and classical algorithms and pointed out that shallow quantum circuits are more powerful than their classical counterparts. The new result complements this earlier work: whereas the year 2018 paper focused on computational asymptotics, the new example demonstrates an explicit numeric advantage.

Our research on quantum advantage continues, as we look for new examples and study other types of advantage.  By increasing our understanding of quantum advantage and how it can be achieved, we gain a better understanding of when it makes sense to apply a quantum computer to solve a particular computational problem.

IBM Quantum

Quantum starts here


Researcher in quantum information and computation, IBM Quantum

Dmitri Maslov

Chief Software Architect, IBM Quantum

More Quantum Computing stories

We’ve moved! The IBM Research blog has a new home

In an effort better integrate the IBM Research blog with the IBM Research web experience, we have migrated to a new landing page: https://research.ibm.com/blog

Continue reading

Pushing the boundaries of human-AI interaction at IUI 2021

At the 2021 virtual edition of the ACM International Conference on Intelligent User Interfaces (IUI), researchers at IBM will present five full papers, two workshop papers, and two demos.

Continue reading

From HPC Consortium’s success to National Strategic Computing Reserve

Founded in March 2020 just as the pandemic’s wave was starting to wash over the world, the Consortium has brought together 43 members with supercomputing resources. Private and public enterprises, academia, government and technology companies, many of whom are typically rivals. “It is simply unprecedented,” said Dario Gil, Senior Vice President and Director of IBM Research, one of the founding organizations. “The outcomes we’ve achieved, the lessons we’ve learned, and the next steps we have to pursue are all the result of the collective efforts of these Consortium’s community.” The next step? Creating the National Strategic Computing Reserve to help the world be better prepared for future global emergencies.

Continue reading