Quantum computer factors numbers, could be scaled up

[Jim__]

From phys.org:

...

In 1994, Peter Shor, the Morss Professor of Applied Mathematics at MIT, came up with a quantum algorithm that calculates the prime factors of a large number, vastly more efficiently than a classical computer. However, the algorithm's success depends on a computer with a large number of quantum bits. While others have attempted to implement Shor's algorithm in various quantum systems, none have been able to do so with more than a few quantum bits, in a scalable way.

Now, in a paper published today in the journal Science, researchers from MIT and the University of Innsbruck in Austria report that they have designed and built a quantum computer from five atoms in an ion trap. The computer uses laser pulses to carry out Shor's algorithm on each atom, to correctly factor the number 15. The system is designed in such 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 results, they say, represent the first scalable implementation of Shor's algorithm.

"We show that Shor's algorithm, the most complex quantum algorithm known to date, is realizable 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," says 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."

...

Chuang and his colleagues have now come up with a new, scalable quantum system for factoring numbers efficiently. While it typically takes about 12 qubits to factor the number 15, they found a way to shave the system down to five qubits, each represented by a single atom. Each atom can be held in a superposition of two different energy states simultaneously. The researchers use laser pulses to perform "logic gates," or components of Shor's algorithm, on four of the five atoms. The results are then stored, forwarded, extracted, and recycled via the fifth atom, thereby carrying out Shor's algorithm in parallel, with fewer qubits than is typically required.

more ...

[RKP5637]

1. Absolutely incredible! I recall so long ago we were just fantasizing about something like

this one day.

[caraher]

2. 15

How many times have quantum computers factored 15 anyway? I remember back in the late 90s or so when I was in grad school hearing at a conference that they'd factored 15 successfully for the first time. (And the immediate reaction I heard was someone asking, "What answer did they get?&quot

What's the largest number factored to date? (Obviously, the news here is that they think their computer is scalable... but it would be nice for someone to factor, say, 21, just for variety!)

[Jim__]

3. I believe 15 is the smallest number Shor's algorithm will work on - so it's a natural place to start

My belief is based on a short description of the algorithm given in wikipedia:

The problem we are trying to solve is: given an odd composite number N, find an integer d, strictly between 1 and N, that divides N. We are interested in odd values of N because any even value of N trivially has the number 2 as a prime factor. We can use a primality testing algorithm to make sure that N is indeed composite.

Moreover, for the algorithm to work, we need N not to be the power of a prime. This can be tested by checking that (N)^1/k is not an integer, for all k <= log₂(N).

The same wiki entry does indicate that they have factored 21:

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored 15 into 3 × 5, using an NMR implementation of a quantum computer with 7 qubits.[4] After IBM's implementation, two independent groups, one at the University of Science and Technology of China, and the other one at the University of Queensland, have implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits.[5][6] In 2012, the factorization of 15 was repeated.[7] Also in 2012, the factorization of 21 was achieved, setting the record for the largest number factored with a quantum computer.[8] In April 2012, the factorization of 143 was achieved, although this used adiabatic quantum computation rather than Shor's algorithm.[9] It was discovered in November 2014, that this adiabatic quantum computation in 2012, had in fact also factored larger numbers, the largest being 56153, which is currently the record for the largest integer factored on a quantum device.

[caraher]

4. Thanks!