First Proof of Quantum Computer Advantage
October 19, 2018 | TUMEstimated reading time: 2 minutes
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.
Suggested Items
Trackwise Awarded Prestigious King’s Award for Enterprise for Innovation
04/24/2024 | TrackwiseTrackwise Designs plc, the innovative manufacturer of specialist products using printed circuit technology, is delighted to be recognised with a prestigious King’s Award for Enterprise. Announced, Friday 21 April, Trackwise has been recognised for its excellence in Innovation for its length-unlimited, multilayer flexible printed circuits.
Three Industry Leaders Receive IPC President’s Award
04/17/2024 | IPCIn recognition of their leadership and significant contributions of time and talent to IPC and the electronics industry, three IPC volunteers were presented with the IPC President’s Award at IPC APEX EXPO in Anaheim, Calif., on April 9, 2024.
Marcy's Musings: The Growing Industry
04/16/2024 | Marcy LaRont -- Column: Marcy's MusingsAfter decades of steady decline in the U.S. and Europe, the PCB industry is finally growing, especially in China Plus One countries. The U.S. for example, which seemed to have abdicated its title as the world leader in innovating high-technology cutting-edge manufacturing processes, is now in a race to regain what it lost and then some. The PCB fabrication industry is growing in the West, thanks to DoD funding, the CHIPS and Science Act, and hopefully, the passing of HR 3249, the Printed Circuit Board and Substrates Act.
FTG Announces Q1 2024 Financial Results
04/12/2024 | Firan Technology Group CorporationDuring Q1 2024, the Corporation has continued to invest in technology in existing sites, grow the business organically, and integrate the two acquisitions completed last year. FTG is strategically deploying its capital in ways that will drive increased shareholder returns for the future in both the near term and long term. Specifically, FTG accomplished the following in Q1 2024, which continues to improve the Corporation and position it for the future:
An Ultimate Goal in Sustainability: Recyclable PCBs
04/11/2024 | Marcy LaRont, PCB007 MagazineWho doesn’t believe in recycling? “Re-use, repurpose, recycle” has been a drumbeat for more than two decades. Our children learn about it in primary school. Full university departments devoted to environmental science and sustainability in universities forward their discipline for the world's benefit. In theory, we all get behind the concept of recycling, even if the nuances of execution may fall short.