The researchers from Massachusetts Institute of Technology (MIT) and Austria’s University of Innsbruck call it “the beginning of the end for encryption schemes“.
Most encryption used today uses integer factorisation, or “the factoring problem“, and its security comes from the difficulty of factoring large numbers.
For example, finding the prime factors, or multipliers, for the number 15 is fairly easy as it’s a small number.
However, a larger number such as 91, may take some pen and paper.
An even larger number, say with 232 digits, has taken scientists two years to factor, using hundreds of classical computers operating in parallel.
In encryption, two different, but intimately related numbers, are used for the encryption and decryption, making it easy to calculate but hard to reverse.
However, a quantum computer is expected to outperform traditional computers and crack this problem by using hundreds of atoms, essentially in parallel, to quickly factor huge numbers because data is encoded in the ‘spin’ of individual electrons.
Unlike standard computers, quantum bits, or qubits can exist in multiple states at once rather than the binary 1 or 0 of conventional bits.
This means they can perform multiple calculations in parallel and hold far more information than normal bits.
For example, a computer with just 1,000 qubits could easily crack modern encryption keys while smartphone games like Angry Birds typically use 40,000 conventional bits to run.
It typically takes about 12 qubits to factor the number 15, but researchers at MIT and the University of Innsbruck in Austria have found a way to pare that down to five qubits, each represented by a single atom.
This has been designed and built by a quantum computer from five atoms in an ion trap. The computer uses laser pulses to carry out algorithms on each atom, to correctly factor the number 15.
“The approach thus provides the potential for designing a powerful quantum computer, but with fewer resources,” said the research paper.
“We factor the number 15 by effectively employing and controlling seven qubits and four ‘cache qubits’ and by implementing generalised arithmetic operations, known as modular multipliers.”
The system is designed in a way that more atoms and lasers can be added to build a bigger and faster quantum computer, able to factor much larger numbers.
The scientists said the results represent the first scalable implementation of Shor’s algorithm, a quantum algorithm named after mathematician Peter Shor in 1994 to solve the factorisation problem.
“We show that Shor’s algorithm, the most complex quantum algorithm known to date, is realisable in a way where, yes, all you have to do is go in the lab, apply more technology, and you should be able to make a bigger quantum computer,” said Isaac Chuang, professor of physics and professor of electrical engineering and computer science at MIT.
“It might still cost an enormous amount of money to build – you won’t be building a quantum computer and putting it on your desktop anytime soon – but now it’s much more an engineering effort, and not a basic physics question.”
The researchers claimed the ion-trap quantum computer returns the correct factors with a confidence level exceeding 99 per cent.
Please like, share and tweet this article.
Pass it on: New Scientist