Layout of IBM's four superconducting quantum bit device. (Image: IBM Research,
Layout of IBM's four superconducting quantum bit device. (Image: IBM Research,

Scientists develop new quantum circuitFirst proof of quantum computer advantage

Quantum computers promise to revolutionize the future of computing. A scientist from the Technical University of Munich (TUM) together with his colleagues from the University of Waterloo and from IBM have now demonstrated for the first time that quantum computers do indeed offer advantages over conventional computers.

For many years, quantum computers were not much more than an idea. Today, companies, governments and intelligence agencies are investing in the development of quantum technology. Robert König, professor for the theory of complex quantum systems at the TUM, in collaboration with David Gosset from the Institute for Quantum Computing at the University of Waterloo and Sergey Bravyi from IBM, has now placed a cornerstone in this promising field.

Why should quantum computers be faster?

Conventional computers obey the laws of classical physics. They rely on the binary numbers 0 and 1. These numbers are stored and used for mathematical operations. In conventional memory units, each bit – the smallest unit of information – is represented by a microscopic dot on a microchip. Each of these dots can hold a charge that determines whether the bit is set to 1 or 0.

In a quantum computer, however, a bit can be both 0 and 1 at the same time. This is because the laws of quantum physics allow electrons to be in multiple places at one time. Quantum bits, or qubits, thus exist in multiple overlapping states. This so-called superposition allows quantum computers to perform operations on many values in one fell swoop whereas a single conventional computer typically must execute these operations sequentially. The promise of quantum computing lies in the ability to solve certain problems significantly faster.

From conjecture to proof

König and his colleagues have now conclusively demonstrated the advantage of quantum computers. To this end, they developed a quantum circuit that can solve a specific "difficult" algebraic problem. The new circuit has a simple structure: it only performs a fixed number of operations on each qubit. Such a circuit is referred to as having a constant depth. In their work, the researchers prove that the problem at hand cannot be solved using classical constant-depth circuits. They furthermore answer the question of why the quantum algorithm beats any comparable classical circuit: The quantum algorithm exploits the non-locality of quantum physics.

Prior to this work, the advantage of quantum computers had neither been proven nor experimentally demonstrated – notwithstanding that evidence pointed in this direction. One example is Shor’s quantum algorithm, which efficiently solves the problem of prime factorization. However, it is merely a complexity-theoretic conjecture that this problem cannot be efficiently solved without quantum computers. It is also conceivable that the right approach has simply not yet been found for classical computers.

A step on the road to quantum computing

Robert König considers the new results primarily as a contribution to complexity theory. "Our result shows that quantum information processing really does provide benefits – without having to rely on unproven complexity-theoretic conjectures," he says. Beyond this, the work provides new milestones on the road to quantum computers. Because of its simple structure, the new quantum circuit is a candidate for a near-term experimental realization of quantum algorithms.


S. Bravyi, D. Gosset, R. König: “Quantum advantage with shallow circuits”, Science, 19 October 2018. DOI: 10.1126/science.aar3106

More Information:

The results have fallen on fertile ground in Munich: A globally acclaimed quantum technology research focus has been established here in recent years, with a new research building for quantum research under construction at the TUM in Garching. In September the TUM, together with the Ludwig-Maximilians-Universität München (LMU), was awarded the contract for the Cluster of Excellence Munich Center for Quantum Science and Technology (MCQST).


Prof. Dr. Robert König
Technische Universität München
Institute for Advanced Study (IAS) & Zentrum Mathematik
Tel: +49 89 289-17042

Technical University of Munich

Article at

Illustration of a network

Highly endowed EU grants for research at TUM

The European Research Council (ERC) has awarded five Consolidator Grants to scientists at the Technical University of Munich (TUM). The recipients will use the funding to pursue research in quantum computers, sustainable...

First author Stefan Pogorzalek (r) and co-author Dr. Frank Deppe with the cryostat, in which they have realized a quantum LAN for the first time.

The quantum internet is within reach

An international team headed by physicists from the Technical University of Munich (TUM) has, for the first time ever, experimentally implemented secure quantum communication in the microwave band in a local quantum...

Der Helixnebel, 700 Lichtjahre von der Erde entfernt. Der Cluster ORIGINS erforscht die Entstehung des Universums und des ersten Lebens. (Bild: ESO/VISTA/J. Emerson)

TUM successfully presents four research Clusters of Excellence

The Technical University of Munich (TUM) has got off to another successful start in the extremely competitive Excellence Initiative organized by Germany’s government and federal states. Over the next seven years, four...

Zukunftsvision: Quantencomputer mit Chips aus Diamant und Graphen – Grafik: Christoph Hohmann / NIM

Center for Quantum Engineering comes to Garching

In recent years, a globally esteemed research focus on quantum technologies has developed on the Garching campus. The German Council of Science and Humanities now supports the creation of a new central institute at the...

Momentaufnahmen der simulierten Rotation eines Tennisschlägers während der Flugphase. Während sich der Schläger um 360 Grad um die Querachse dreht, führt der Tennisschläger-Effekt zu einer unbeabsichtigten zusätzlichen 180 Grad-Rotation um seine Längsachse, so dass nach der Gesamtdrehung die rote Unterseite nach oben zeigt. (Bild: Steffen Glaser / TUM)

Classical mechanics helps control quantum computers

Quantum technology is seen as an important future-oriented technology: smaller, faster and with higher performance than conventional electronics. However, exploiting quantum effects is difficult because nature’s smallest...

Mit flüssigem Stickstoff gekühlter Hochtemperatur-Supraleiter. Die Voraussage, ob und wann ein Material supraleitend wird, hängt entscheidend davon ab, ob Anregungen Energie benötigen oder nicht. Eine Vorausberechnung dieser Eigenschaft ist jedoch schwieriger als gedacht, da sich ein zugrunde liegendes mathematisches Problem als prinzipiell unlösbar erwiesen hat. - Foto: Ulli Benz / TUM

Quantum physics problem proved unsolvable

A mathematical problem underlying fundamental questions in particle and quantum physics is provably unsolvable, according to scientists at UCL, Universidad Complutense de Madrid – ICMAT and Technical University of Munich....

Elektron im Quanten-Punkt, beeinflusst von Kernspins der Umgebung – Grafik: Fabian Flassig / TUM

Quantum computer made of standard semiconductor materials

Physicists at the Technical University of Munich, the Los Alamos National Laboratory and Stanford University (USA) have tracked down semiconductor nanostructure mechanisms that can result in the loss of stored information –...

Eine App liefert intuitive graphische Darstellungen von Quantenzuständen gekoppelter Spins - Bild: Steffen Glaser / TUM

Visualizing the “matrix”

Magnetic resonance tomography (MRT) images are an important diagnostic tool. The achievable contrast depends on how well the nuclear spins that form the basis of the imaging signals can be controlled. Mathematically, the...

Zukunftsvision Quantencomputer mit Chips aus Diamant und Graphen – Grafik: Christoph Hohmann / NIM

Possible read head for quantum computers

Nitrogen-vacancy centers in diamonds could be used to construct vital components for quantum computers. But hitherto it has been impossible to read optically written information from such systems electronically. Using a...

Das Bild zeigt ein Nanoroehrchen (schwarz), das wie eine Gitarrensaite eingespannt und zu Schwingungen angeregt werden kann. Ein benachbartes elektrisches Feld sorgt dafür, das nur zwei der vielen möglichen Zustände angesteuert werden. Bild: M.J. Hartmann, TUM

Quantum computers counting on carbon nanotubes

Carbon nanotubes can be used as quantum bits for quantum computers. A study by physicists at the Technische Universität München (TUM) has shown how nanotubes can store information in the form of vibrations. Up to now,...