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

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 quantum computing 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 digits — 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 quantum processor 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 quantum 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.

**Citation**: Physicists demonstrate that 15=3x5 about half of the time (2012, August 19) retrieved 20 June 2019 from https://phys.org/news/2012-08-ucsb-153x5.html

## User comments

Mike_MassenSatanLoverEikkaIf 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:

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

EikkaThere'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.

BenniMrVibrating(can't imagine what else he could be waiting for)

nugeIf 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_12Isn't this a deterministic problem ?

EikkaThat depends on who you ask for an opinion. At the moment the consensus is that quantum behaviour is inherently stochastic.

kochevnikMike_MassenScaling 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 ;-)

ArgiodHeck, 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.

MumrahFor 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 :)

KafpauzoChecking 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_12When 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.

desai_nirav_12EikkaAnd 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_12desai_nirav_12desai_nirav_12Mike_MassenEikka, 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

DeathclockA deterministic problem yes, but Shor's algorithm is a quantum algorithm, not a classical one.

DeathclockA 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_MassenAs I said before for Eikka's benefit 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...

billyumEvery 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.

DeathclockYou're talking 2^n calculations where, in this case, n is 600... you do the math.

eachusDo 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.

sirchickKafpauzoAccording 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.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more