Physicists demonstrate that 15=3x5 about half of the time

Aug 19, 2012
The device in the photomicrograph was used to run the first solid-state demonstration of Shor's algorithm. It is made up of four phase qubits and five superconducting resonators, for a total of nine engineered quantum elements. The quantum processor measures one-quarter inch square. Credit: UCSB

Computing prime factors may sound like an elementary math problem, but try it with a large number, say one that contains more than 600 digits, and the task becomes enormously challenging and impossibly time-consuming. Now, a group of researchers at UC Santa Barbara has designed and fabricated a quantum processor capable of factoring a composite number — in this case the number 15 — into its constituent prime factors, 3 and 5.

Although modest compared to a 600-digit number, the achievement represents a milestone on the road map to building a quantum computer capable of factoring much larger numbers, with significant implications for cryptography and cybersecurity. The results are published in the advance online issue of the journal Nature Physics.

"Fifteen is a small number, but what's important is we've shown that we can run a version of Peter Shor's prime factoring algorithm on a solid state quantum processor. This is really exciting and has never been done before," said Erik Lucero, the paper's lead author. Now a postdoctoral researcher in experimental at IBM, Lucero was a doctoral student in physics at UCSB when the research was conducted and the paper was written.

"What is important is that the concepts used in factoring this small number remain the same when factoring much larger numbers," said Andrew Cleland, a professor of physics at UCSB and a collaborator on the experiment. "We just need to scale up the size of this processor to something much larger. This won't be easy, but the path forward is clear."

Practical applications motivated the research, according to Lucero, who explained that factoring very large numbers is at the heart of cybersecurity protocols, such as the most common form of encoding, known as RSA encryption. "Anytime you send a secure transmission — like your credit card information — you are relying on security that is based on the fact that it's really hard to find the prime factors of large numbers," he said. Using a classical computer and the best-known classical algorithm, factoring something like RSA Laboratory's largest published number — which contains over 600 decimal — would take longer than the age of the universe, he continued.

A quantum computer could reduce this wait time to a few tens of minutes. "A quantum computer can solve this problem faster than a classical computer by about 15 orders of magnitude," said Lucero. "This has widespread effect. A quantum computer will be a game changer in a lot of ways, and certainly with respect to computer security."

So, if quantum computing makes RSA encryption no longer secure, what will replace it? The answer, Lucero said, is quantum cryptography. "It's not only harder to break, but it allows you to know if someone has been eavesdropping, or listening in on your transmission. Imagine someone wiretapping your phone, but now, every time that person tries to listen in on your conversation, the audio gets jumbled. With quantum cryptography, if someone tries to extract information, it changes the system, and both the transmitter and the receiver are aware of it."

To conduct the research, Lucero and his colleagues designed and fabricated a quantum processor to map the problem of factoring the number 15 onto a purpose-built superconducting quantum circuit. "We chose the number 15 because it is the smallest composite number that satisfies the conditions appropriate to test Shor's algorithm — it is a product of two prime numbers, and it's not even," he explained.

The quantum processor was implemented using a quantum circuit composed of four superconducting phase qubits — the quantum equivalents of transistors — and five microwave resonators. The complexity of operating these nine quantum elements required building a control system that allows for precise operation and a significant degree of automation — a prototype that will facilitate scaling up to larger and more complex circuits. The research represents a significant step toward a scalable quantum architecture while meeting a benchmark for quantum computation, as well as having historical relevance for quantum information and cryptography.

"After repeating the experiment 150,000 times, we showed that our got the right answer just under half the time" Lucero said. "The best we can expect from Shor's algorithm is to get the right answer exactly 50 percent of the time, so our results were essentially what we'd expect theoretically."

The next step, according to Lucero, is to increase the quantum coherence times and go from nine elements to hundreds, then thousands, and on to millions. "Now that we know 15=3x5, we can start thinking about how to factor larger — dare I say — more practical numbers," he said.

Explore further: Liquid spacetime: A very slippery superfluid, that's what spacetime could be like

Related Stories

Quantum Computer Science on the Internet

Jul 31, 2004

A simulated quantum computer went online on the Internet last month. With the ability to control 31 quantum bits, it is the most powerful of its type in the world. Software engineers can use it to test algorithms that might o ...

Recommended for you

User comments : 31

Adjust slider to filter visible comments by rank

Display comments: newest first

Mike_Massen
1.3 / 5 (6) Aug 19, 2012
How do we know which half is the correct half when it comes to 600 digit numbers and with so many digits will other percentages start to creep in given the large number of permutations...?
SatanLover
2 / 5 (3) Aug 19, 2012
even nowadays processors have an error margin. step in the right direction.
Eikka
4.3 / 5 (12) Aug 19, 2012
How do we know which half is the correct half when it comes to 600 digit numbers and with so many digits will other percentages start to creep in given the large number of permutations...?


If you can expect to get the right answer 50% of the time, it's trivial to just try both answers. If the system outputs more than two different answers, then it's trivial to pick the one that appears half the time.

What is more interesting is:

The answer, Lucero said, is quantum cryptography. "It's not only harder to break, but it allows you to know if someone has been eavesdropping, or listening in on your transmission.


while neglecting to add, that it would initially be much too expensive and difficult to implement over the existing internet, for the ordinary citizens, while at the same time the quantum processors would allow the governments to decode all existing classical communications

I predict a period in the future when privacy will vanish for all except the most powerful
Eikka
1 / 5 (2) Aug 19, 2012
Although even the quantum computer won't solve the best standard of encryption: sending a memory stick full of random bits in the mail to serve as a one-time pad.

There's no computer that can solve that encryption, because in some senses half of the data is already there at the other end and never crosses the public internet. The only way is that the spying party physically intercepts the pad and makes a copy.

The first application of telecommunication using this method was the hot line between England and US that utilized two identical phonograph records recorded full of noise and synchronized at both ends to remove the noise from the phone call. Anyone tapping into the line would only hear a massive hiss.

Benni
1 / 5 (6) Aug 19, 2012
If I could apply this technology to my banking account.....all I need to do is come up an encryption for the half that works in my favor.....Nope, won't work, most banks probably still use mechanical calculators in their inner sanctums that we don't know about.
MrVibrating
2.3 / 5 (3) Aug 19, 2012
Hallelujah. Oi, David Braben, can we get our Elite 4 now please?

(can't imagine what else he could be waiting for)
nuge
not rated yet Aug 19, 2012
"It's not only harder to break, but it allows you to know if someone has been eavesdropping, or listening in on your transmission. Imagine someone wiretapping your phone, but now, every time that person tries to listen in on your conversation, the audio gets jumbled. With quantum cryptography, if someone tries to extract information, it changes the system, and both the transmitter and the receiver are aware of it."


If the analogy is accurate, that means the transmitter and receiver would not only be aware of an attempt to listen in on the communication, but would be interrupted by it. I fear this could be exploited by malevolent hackers trying to "take down the system", even if "just 'cause they can".
desai_nirav_12
not rated yet Aug 20, 2012
How can it be right only 50% of the time ?
Isn't this a deterministic problem ?
Eikka
2.3 / 5 (3) Aug 20, 2012
How can it be right only 50% of the time ?
Isn't this a deterministic problem ?


That depends on who you ask for an opinion. At the moment the consensus is that quantum behaviour is inherently stochastic.
kochevnik
3.7 / 5 (3) Aug 20, 2012
How can it be right only 50% of the time ? Isn't this a deterministic problem ?
LOL god is an underachiever.
Mike_Massen
1 / 5 (6) Aug 20, 2012
Eikka got into the habit of over-simplifying (yet again)
If you can expect to get the right answer 50% of the time, it's trivial to just try both answers. If the system outputs more than two different answers, then it's trivial to pick the one that appears half the time.
Its a big IF, suggest less habituation to narrow views. Who says you will get a small number of possible solutions either side of your 50% decision. As the digits go up & there is no reason to stay with a small number of 600, the solution series starts to look like a power spectra of a discontinuous waveform, not trivial.

Scaling up any quantum system introduces a plethora of complex noise issues of many types, not likely to happen for some time if at all.

Privacy is easy to maintain, choose your risk in a more enlightened way & in conjunction with your classic bell curve in respect of the dynamic. Its so easy to be just as private as your intellect allows for the class of transactions you expect ;-)
Argiod
1 / 5 (5) Aug 20, 2012
LOL, the quantum computer only gets the right answer half the time?
Heck, my success rate is better than that; and I'm math challenged.

At this rate, it would be easier and cheaper to simply toss a coin. It, too, has a statistically even chance of getting the right answer.

Quantum computing still looks to me like a form of divination; a very expensive form.
Mumrah
1 / 5 (1) Aug 20, 2012
I'm still suspicious that the universe might find a way of limiting the power of quantum computers so that they're not really more powerful than standard computers. I guess trying to scale them up is a sure fire way to find out.

For example, suppose a given qbit has a half-life before it decoheres. The problem is (I believe) that if one qbit fails the whole calculation is screwed so you need to do something to reduce the chance of this happening.

If the half-life is related to temperature you may need to do lots of work cooling the qbits (such as reducing the temperature by some ratio) each time you throw in an extra qbit to keep the overall half-life constant.

I find it easy to imagine this scaling in such a way as to prevent you from getting any more computational power (per watt) than with a standard computer.

I may just be unduly pessimistic though :)
Kafpauzo
5 / 5 (1) Aug 20, 2012
If you can expect to get the right answer 50% of the time, it's trivial to just try both answers. If the system outputs more than two different answers, then it's trivial to pick the one that appears half the time.

Its a big IF, suggest less habituation to narrow views. Who says you will get a small number of possible solutions either side of your 50% decision. As the digits go up & there is no reason to stay with a small number of 600, the solution series starts to look like a power spectra of a discontinuous waveform, not trivial.

Checking the answer is far more trivial than that.

The algorithm searches for the two factors of a number. If you get both factors, just try multiplying the two, and see if the result is the original number. If you get only one factor, divide the original number by this, and see if it's evenly divisible.

_Finding_ the factors is a huge amount of work, but _checking_ the result is a trivial operation, done in a tiny fraction of a second.
desai_nirav_12
not rated yet Aug 21, 2012
Hi Eikka. I do realize that Quantum Mechanics deals with wave functions where everything is calculated as a probability. But if the probability is 50%, it is inconclusive.

When we calculate probabilities of particles in infinite potential wells, they are 0 or 1. For a finite barrier height, there is a finite probability of the particle overcoming the potential barrier. Repeating the experiment a number of times will give answers which are close to these probabilities.

For computation using quantum mechanical phenomena, the probabilities will need to be pretty high for a high level of confidence. This could be equivalent to raising the height of the potential barrier so that the probabilities of particle tunneling out are diminished.

How can it be right only 50% of the time ?
Isn't this a deterministic problem ?


That depends on who you ask for an opinion. At the moment the consensus is that quantum behaviour is inherently stochastic.
Vendicar_Decarian
4.5 / 5 (2) Aug 21, 2012
15 equals 3 time 5, half the time?

Is this the statistical result of an American high school exit math test question?
desai_nirav_12
not rated yet Aug 21, 2012
In my previous comment, you observe tunneling for finite barrier height and thickness - experimental proof of the probabilistic nature of quantum mechanics.
Eikka
1 / 5 (1) Aug 21, 2012
Eikka got into the habit of over-simplifying (yet again)


And you think too much of yourself, yet again.

The expected distribution for the correct answer is 50% if you run the algorithm infinite times.

Running the algorithm sufficiently many times allows you to pick the answer that comes up most frequently and simply try if it works. If not, try the second, or the third.

In any case, the right answer will be among the answers that turn up the most, so a few thousand runs of the algorithm will give you a trivially small set of candidates that will almost surely give you the right solution.
desai_nirav_12
not rated yet Aug 22, 2012
Hi Eikka. Can the probability of error be controlled in this experiment ? As I mentioned in the particle in the well problem, the probability of finding the particle outside the well ( tunneling ) can be controlled. Having a higher potential barrier will give lower probability of the particle tunneling.
desai_nirav_12
1 / 5 (1) Aug 22, 2012
Hi all. Also how does this design from UCSB compare to this Quantum von Neumann architecture: http://www.ia.ucs...key=2553
desai_nirav_12
1 / 5 (1) Aug 22, 2012
Hi Eikka. In digital communications, all systems designs are probabilistic with channel noise being Additive White Gaussian Noise. The probabilities of error go as low as 1e-5 to 1e-7 to give a guaranteed quality of service. Can that be done on the quantum computers ?
Mike_Massen
1 / 5 (4) Aug 22, 2012
Eikka retorted in a mumble
Eikka got into the habit of over-simplifying (yet again)
And you think too much of yourself, yet again.
One wonders if it 'takes one to know one' etc.

Eikka, you speak as if you have certainty, the devices to reach anything near 600 digits havent been built yet there is so much unknown, who is it that thinks so much of themselves:-

a. the person who is certain before experimental evidence

or

b. the person who offers questions and observations to look out for

One wonders why you have such certainty, please might I suggest you give your advice to all those companies developing in this area of technology and perhaps others you seem to offer certain opinion on :-)

Cheers

Mike
Tausch
1 / 5 (2) Aug 22, 2012
Hut ab! Congrulations.
And to Eikka's commentary explanatory power/talent.
Deathclock
1 / 5 (2) Aug 23, 2012
How can it be right only 50% of the time ?
Isn't this a deterministic problem ?


A deterministic problem yes, but Shor's algorithm is a quantum algorithm, not a classical one.
Deathclock
2.3 / 5 (3) Aug 23, 2012
LOL, the quantum computer only gets the right answer half the time?
Heck, my success rate is better than that; and I'm math challenged.


A lot of people have no idea what the hell they are talking about here...

Your success rate would be zero with a 600 digit number, because figuring this out by hand would take orders of magnitude longer than the universe has existed.

Quantum algorithms are all non-deterministic, they are optimization algorithms.

As far as how will you know which answer is correct... you won't get two answers... you'll get many. One of them will be close to 50%, the others will be MUCH less, probably far less than 1%.
Mike_Massen
1 / 5 (3) Aug 23, 2012
Thanks Deathclock
As far as how will you know which answer is correct... you won't get two answers... you'll get many. One of them will be close to 50%, the others will be MUCH less, probably far less than 1%.
This is mostly what I was trying to tell Eikka, you will get many possible solutions, the number will of course rise significantly as the number of digits increase and 600 will become a very low benchmark indeed as computational power increases whether quantum based or otherwise...

As I said before for Eikka's benefit
..starts to look like a power spectra of a discontinuous waveform, not trivial.
Such spectra equivalent paradigm may be quite wide indeed with a very large number of terms.

Rather than argue Eikka, wait till we get close to handling even a few dozen digits then we can enter into discussion...
billyum
not rated yet Aug 23, 2012
With data storage and even ram at such relatively low prices, wouldn't running a program One time which just multiplies a matrix of 1 x (1-499 digits), 2 x (1-250 digits) etc, store results
Every number that never was a result is a prime,
Save all Factors of all other numbers in some easily searchable format.
Now you just query the table anytime you need to know factors instead of calculating for "a few tens of minutes" on a theoretical computer.

I am by no means a security expert so there must be something I'm missing here.
Deathclock
1 / 5 (2) Aug 23, 2012
With data storage and even ram at such relatively low prices, wouldn't running a program One time which just multiplies a matrix of 1 x (1-499 digits), 2 x (1-250 digits) etc, store results
Every number that never was a result is a prime,
Save all Factors of all other numbers in some easily searchable format.
Now you just query the table anytime you need to know factors instead of calculating for "a few tens of minutes" on a theoretical computer.

I am by no means a security expert so there must be something I'm missing here.


You're talking 2^n calculations where, in this case, n is 600... you do the math.
eachus
not rated yet Aug 24, 2012
The explanation of why they get 3 and 5 half the time is incredibly mixed up. You always get a number that divides the composite number, 15 in this case. There are four such numbers, 1, 3, 5, and 15. The algorithm returns one of these, so you get the answer you are looking for half the time. The one and n (15) can be thrown away, so the first time you get a number between 2 and n-1, you have a factor.

Do you remember, "The magic word is squeamish ossifrage", (the solution to the Rivest-129 challenge)? The final step of the quadratic sieve algorithm had the same property. The first time they tried it they got 1 and n, the second try got the needed factors.

It is believed that there is some pattern to which answer you get for a composite number with only two prime factors. But AFAIK, no one has published an answer to that conjecture.
sirchick
not rated yet Aug 25, 2012
So what does 3 x 5 = ? the other half of the time ?
Kafpauzo
not rated yet Aug 25, 2012
So what does 3 x 5 = ? the other half of the time ?

According to eachus's comment, half the time they get 15 = 3 x 5, the other half of the time they get 15 = 1 x 15.

More news stories