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.
Learn more: First proof of quantum computer advantage
The Latest on: Quantum computers
via Google News
The Latest on: Quantum computers
- The Year in Math and Computer Science on December 21, 2018 at 7:12 am
But at times in 2018, even 30 could feel old. Two students, one in graduate school and the other just 18, in two separate discoveries, remapped the borders that separate quantum computers from ordinar... […]
- quantum computing on December 21, 2018 at 7:11 am
18-year-old Ewin Tang has proven that classical computers can solve the “recommendation problem” nearly as fast as quantum computers. The result eliminates one of the best examples of quantum speedup. ... […]
- 'Kondo metamagnet' is first in a family of eccentric quantum crystals on December 21, 2018 at 6:24 am
Spintronics, a growing movement, is dedicated to creating spin-based technologies for data transfer, data storage and computation, including fundamentally new kinds of chips for quantum computers. […]
- Quantum Stimulus: Congress Sends Computing Proposal to Trump on December 20, 2018 at 1:14 pm
WASHINGTON — A proposal that could pump more than $1 billion into helping the U.S. tech industry develop powerful "quantum computers" is now on the desk of President Donald Trump. Congress sent the bi... […]
- McAfee: When quantum computing threats strike, we won't know it on December 20, 2018 at 12:50 pm
Quantum computing may not be at the point where it can instantly break current encryption protocols, but Steve Grobman believes that when that day finally arrives, we likely won't know it. […]
- National Quantum Initiative Act Passes Congress on December 20, 2018 at 12:45 pm
“Quantum research at universities and national laboratories must be translated to industry to make quantum computers and other devices, and to define markets for these devices, and the government can ... […]
- Is Quantum Computing a Cybersecurity Threat? on December 20, 2018 at 12:00 pm
Cybersecurity researchers and analysts are rightly worried that a new type of computer, based on quantum physics rather than more standard electronics, could break most modern cryptography. The effect ... […]
- President poised to sign bill creating quantum computing initiative on December 20, 2018 at 11:16 am
It could help the US claim the lead in quantum computers. Visions of an American quantum computing initiative are close to becoming a practical reality. The House of Representatives has passed its ver... […]
- House Okays Quantum Computing R&D Bill on December 20, 2018 at 11:02 am
The House voted late yesterday to approve H.R. 6227, the National Quantum Initiative Act, which would create a Federal program to speed quantum research and development “for the economic and national ... […]
via Bing News