Quantum computers provide advantages
An unconditional proof by Robert König and his collaborators
Quantum computers should be able to solve problems more efficiently than conventional computers by exploiting quantum effects. At least that’s the vision underlying the area of quantum computing. A team of researchers has now shown that quantum computers indeed provide advantages. They developed a quantum circuit which can solve a difficult algebraic problem.
The quantum circuit has a simple structure: it has constant depth. Here, the depth is the number of time steps necessary to run the circuit. Each step involves gates which can be executed simultaneously. Constant depth amounts to the property that the depth does not depend on the size of the problem. With their result on such constant-depth circuits, Robert König, professor for the theory of complex quantum systems, together with David Gosset from the University of Waterloo and Sergey Bravyi from IBM, have now established an important foundation for quantum technologies.
In their work titled "Quantum advantage with shallow circuits", they show that the problem of interest cannot be solved by a classical circuit of constant depth. This establishes that quantum circuits are more powerful than classical ones. The authors also clarify the underlying reason: the quantum circuit exploits the non-locality of quantum physics.
Why are quantum computers "better"?
Each output bit of a classical constant-depth circuit is determined locally by input bits in its "light cone". In contrast, constant-depth quantum circuits can exploit the phenomenon of quantum nonlocality to perform computations beyond the capabilities of their classical counterparts.
Conventional computers obey the laws of classical physics. They work with binary numbers: 0 and 1. The smallest unit of information, a bit, can be represented by the presence of absence of electrical charge at a specific location. This determines whether the bit is set to 1 or 0.
In a quantum computer, 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.
Prior to this work, there was only some evidence for the advantage of quantum computers. For example, Shor’s quantum algorithm 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 roads towards quantum computers
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.
In recent years, a globally respected research focus in quantum technology has developed in Munich. At the TUM in Garching, a new center for quantum research is being created and in September 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).
Go to press release from TUM: First proof of quantum computer advantage