typodupeerror

## Solid State Quantum Computer Finds 15=3x5 — 48% of the Time262

mikejuk writes "The Shor quantum factoring algorithm has been run for the first time on a solid state device and it successfully factored a composite number. A team from UCSB has managed to build and operate a quantum circuit composed of four superconducting phase qubits. The design creates entangled bits faster than before and the team verified that entanglement was happening using quantum tomography. The final part of the experiment implemented the Shor factoring algorithm using 15 as the value to be factored. In 150,000 runs of the calculation, the chip gave the correct result 48% of the time. As Shor's algorithm is only supposed to give the correct answer 50% of the time, this is a good result but not of practical use."
This discussion has been archived. No new comments can be posted.

## Solid State Quantum Computer Finds 15=3x5 — 48% of the Time

• #### Maths (Score:3, Funny)

by Anonymous Coward on Sunday August 26, 2012 @10:45AM (#41129509)

Sometimes 2+2=5, give the thing a break!

• #### Re:Maths (Score:4, Funny)

by Anonymous Coward on Sunday August 26, 2012 @10:51AM (#41129551)

Of course 2 + 2 = 5. Take two strings. Tie 2 knots in each. Then tie them together and count the knots.

• #### Re: (Score:2, Funny)

by Anonymous Coward
For very large values of 2
• #### Re: (Score:3)

Two is a large value already, it's larger than the average number of ears per capita in the general population.
• #### Can someone explain... (Score:5, Insightful)

on Sunday August 26, 2012 @10:55AM (#41129585) Journal

From TFA:

As Shor's algorithm is only supposed to give the correct answer 50% of the time, this is a good result.

How is it useful to have the correct answer 50% of the time? When designing computing algorithms, wouldn't you want it to return the correct answer 100% of the time?

• #### Re:Can someone explain... (Score:5, Informative)

by Anonymous Coward on Sunday August 26, 2012 @10:58AM (#41129615)

Consider problems which take a lot longer to compute than to verify. It may be much faster to compute the answer with a quantum computer, then check it with a regular computer, than to simply compute it with a regular computer.

• #### Re: (Score:3)

The main problem is the "there is no solution" answer. What if we use the algorithm for a number N for several iterations and found that there are no valid decompositions. Can we ensure that the number is prime?

• #### Re:Can someone explain... (Score:5, Informative)

on Sunday August 26, 2012 @11:50AM (#41129949) Homepage
Thats how we find primes right now. All the practical algorithms are probabilistic. If a number is prime, running the algorithm always returns "prime". If it is composite, running the algorithm will result in "prime" about half the time and "composite" about half the time. This is fine, however, because we can run the algorithm n times and our confidence is .5^n, which grows very small very fast.
• #### Re:Can someone explain... (Score:5, Interesting)

on Sunday August 26, 2012 @11:43AM (#41129905)

That may be so, but computing the prime factorization of 15 is not in that class.

I don't think you should even get to call something a middle-school dropout can figure in his head faster than he can say "Fries with that?" computation. So-called quantum computers still barely qualify as expensive but useless toys.

Post again when a quantum computer can solve a real mathematical puzzle at a speed comparable to what a traditional computer can do. That would be news.

Scientists have been touting the supposedly vast potential of quantum computing for decades now. D-E-C-A-D-E-S. But thanks to fundamental limitations of the nature of what they are, it's really hard to get them to barely work at all. It appears we could forever be stuck at the point where the qubits can be minimally processed but quantum decoherence can't be held off long enough to get a useful result. Meanwhile traditional methods of computing continue to forge ahead, although the rate of increase is slowing. Just keep in mind: quantum computing is 2500 years behind traditional computing methods in general, 175 years behind automated mechanical methods and more than 70 years behind electronic computers.

Electronic computing methods overtook all other methods extremely quickly, but they faced only technical challenges not challenges posed by the fundamental nature of what they were trying to do. You can regard them in some ways as fancy abacuses: they literally count chunks of charge the way an abacus uses the position of beads to represent numbers (or in principle anything else). With qubits, you are attempting to get definite results by exploiting the indefinite character of things like the spin states of electrons. That's not just hard. It may be intractably hard. But if somebody can get it to work it might be very valuable to the NSA and anybody else interested in cracking the security of computing systems.

• #### Re:Can someone explain... (Score:5, Insightful)

on Sunday August 26, 2012 @11:54AM (#41129977)

Yeah, scientists were theorising about the Higgs-boson for deacdes as well. Sometimes it takes that long to get somewhere.

It's very early days for quantum computing. The fact that they've taken something from pure theory and made it actually do something is a fantastic indicator that they're onto something. So what if it takes another 5 decades to get there, the implications would still be incredible by that point.

• #### I'm sorry, that's a crappy example. (Score:3)

because-- we haven't 'gotten there' with the higgs yet-- still may NEVER..

• #### Re: (Score:3)

Er yes we have? Where have you been for the last month?

• #### Re: (Score:2)

And there were people who could outrun the first adding machines by doing it in their head. Nobody said that the this was in itself useful. It IS one more step along the way. It may be that at some point the next step will prove impossible or it may be that step by step we'll get there, but either way, we'll likely learn a few things that do prove useful.

All the same, I'm not going to hold my breath.

• #### Re: (Score:3, Insightful)

yeah. the wright brothers built some stupid linen and balsa wood thing that fluttered above the ground for a few seconds. useless. they've been talking about flight for centuries

morse can send little tappity taps on a wire? big deal. i can't figure out what it means, and does anyone actually believe we're going to string wires all over the country? impossible!

and i heard of this television device. what a crazy unweildy delicate gizmo. shows a fluttering image you have to squint to maybe make out what they a

• #### Re:Can someone explain... (Score:5, Insightful)

on Sunday August 26, 2012 @12:40PM (#41130299)

There should be a "-1 Bitching That This Doesn't Meet My Personal Criteria For News" mod. Every. Damn. Article. Somebody has to come write an essay on how completely not interesting or impressive this is to them.

Yes, factoring 15 isn't particularly impressive. Thank you, Captain Fucking Obvious.

Now if you'd bothered to RTFA, you'd have noted it already directly discusses this:

Of course, factoring 15 isn't something that is going to threaten the PKI and cryptography in general, but factoring larger numbers is just a matter of increasing the number of qubits and this approach does seem to be a scalable solid state approach.

So they can instantly factor numbers (well, with ~50% success), with an approach that *seems scalable*. That's news to me.

Maybe in a few months, there will be another story about how they failed to scale this approach up. That will be an additional piece of news. Failure can be news.

Some of us are interested in the journey, not just the destination.

• #### Re: (Score:3, Informative)

by Anonymous Coward

With qubits, you are attempting to get definite results by exploiting the indefinite character of things like the spin states of electrons. That's not just hard. It may be intractably hard.

Actually, the math and abstract procedure of how to do this is pretty well understood. The question of how to get definite answers from such quantum states is solved, in the sense the algorithm's results are very quickly and easily shown to have worked or not (and not just by multiplying the two factors, the result of the quantum portion of calculation has to be converted into actual factors via classical computation, and is obvious when this fails). The jump from probabilistic states to definite answers

• #### Re: (Score:3)

Ever heard of 'proof of concept'?
• #### Re: (Score:2)

I guess somewhat close to halfway there. If they had also computed the factorization of 14 with about 48% correct results, I'd be 100% more confident that they were onto something. What they've shown is that they made a quantum device that can produce results of 3 and 5 about half the time. Wouldn't you be happier if you knew that it didn't produce 3 and 5 half the time regardless how they program it?

The original abstract (http://www.nature.com/nphys/journal/vaop/ncurrent/full/nphys2385.html) mentions t

• #### Re: (Score:3)

That may be so, but computing the prime factorization of 15 is not in that class.

Actually, it is. There is a reason that kids are taught multiplication long before factoring. It just happens that for numbers this small you can do both in your home.

If I handed you a pencil and paper and asked you to factor 1474 to primes it would take you a LOT longer than if I gave you the factors and asked you to multiply them.

Verifying the factorization of even a 2048 bit number by hand on paper is probably doable, though likely pretty tedious. Calculating those factors if they are just two primes

• #### Re:Can someone explain... (Score:5, Informative)

on Sunday August 26, 2012 @10:59AM (#41129623)

That depends. Sometimes you have a hard time finding a possible result, but verifying it is simple. Factorization is just such a problem. So you repeat the algorithm and test the result until the test succeeds. If this is on average faster than a completely deterministic approach, you have won.

• #### Re:Can someone explain... (Score:5, Insightful)

on Sunday August 26, 2012 @11:12AM (#41129733) Homepage

For a concrete example, the RSA public key includes a number n, which is the sum of two secret primes p and q. The encryption is broken if an attacker can derive p and q from n by factorization. ( http://en.wikipedia.org/wiki/RSA_(algorithm)#Operation [wikipedia.org] )

if you could factorize an RSA public key 48% of the time then it would be a pretty big deal, since it would render RSA completely obsolete.

• #### Re:Can someone explain... (Score:5, Informative)

on Sunday August 26, 2012 @11:19AM (#41129761) Homepage

RSA public key includes a number n, which is the sum of two secret primes p and q

Just FYI, it's the product of two secret primes. Product is for multiplication, while sum is for addition.

• #### Re: (Score:2, Funny)

by Anonymous Coward

Well, at least the poster was half right...

• #### Re: (Score:2, Insightful)

But we are a very long way from that. Right now it takes enormously more effort to do the job with a quantum computer and it can only be done at all with very small numbers like 15. And the results show that hardware is not scalable. It's supposed to get the answer right 50% of the time and it only gets 48% in 150,000 runs. The 2% difference is significant and whatever the cause of that is, it's almost certain to not scale well:

If a 4 bit number gives you a 48% correct rate, that means that it gets the

• #### Re: (Score:3)

2% difference is significant and whatever the cause of that is, it's almost certain to not scale well:

That's a lot of extrapolation from a single data point.

• #### One word: (Score:5, Funny)

on Sunday August 26, 2012 @11:02AM (#41129657)

Close enough for government work.

• #### Re: (Score:2)

Not really, but I did get a good chuckle...

• #### Re:One word: (Score:4, Insightful)

on Sunday August 26, 2012 @11:25AM (#41129789) Journal

In this case, I suspect that the NSA would readily agree... This quantum computer is far too small for any practical purposes that couldn't be brute-forced with a TI-83 much more easily; but tepid accuracy isn't a big deal if checking your work is computationally inexpensive...

• #### Re:One word: (Score:5, Funny)

on Sunday August 26, 2012 @12:40PM (#41130297)

Close enough for government work.

Did you count that with a quantum computer, because by traditional methods I get 5 words 100% of the time.

• #### Re:Can someone explain... (Score:5, Funny)

by Anonymous Coward on Sunday August 26, 2012 @11:03AM (#41129661)

How is it useful to have the correct answer 50% of the time?

Cat life-support devices.

• #### Re: (Score:2)

I assume that you are supposed to run the algorithm a few times and see which answer comes up most often (about 50% of the time) and assume it is true. The point being that running this algorithm a few times is significantly faster than running the equivalent algorithm on a non-quantum(?) computer (particularly when dealing with huge near-prime numbers), so what you lose in accuracy you make up for in time.

This is the basis for most "quantum" things (such as qubits); you can theoretically encode an infinite

• #### Re: (Score:3)

Nah, as others have pointed out, what you do is run the Shor's algorithm, then verify it. If it's wrong, run Shor's again. If it's right, you know you have the factorization. In this way, you can be 100% sure that you've correctly solved the problem, even if Shor's only provides the correct answer some percentage of the time.

What I don't fully understand is why 48% makes this impractical. Having not read TFA, the only way I can imagine that would be the case is if somehow not having exactly a 50% chance

• #### Re:Can someone explain... (Score:4, Informative)

on Sunday August 26, 2012 @12:31PM (#41130245) Homepage Journal

I believe it's just confusing wording. They're saying 48% is good because at best it could only have been 50%. It's impractical because it is only 4 qbits and so conventional computing can easily do the job faster and cheaper for numbers that small (for that matter, it' small enough that a lookup table is an attractive solution).

• #### Re:Can someone explain... (Score:4, Insightful)

on Sunday August 26, 2012 @12:36PM (#41130273) Journal
Let me remind you of the zeroth law of thermodynamics - You can't have nice things.
By that law I predict Shor's algorithm works in practice as follows:
6=2x3 96%
15=3x5 48%
35=5x7 24%
77=7x11 12%
143=11x13 6%
Good luck breaking RSA.
• #### Re: (Score:2, Insightful)

by Anonymous Coward

It's useful because checking that the answer is correct or not is trivial, and having to run the algorithm twice (long term average) is still exponentially faster than relying on classical methods.

• #### Re:Can someone explain... (Score:5, Informative)

on Sunday August 26, 2012 @11:23AM (#41129779)

How is it useful to have the correct answer 50% of the time?

In many cases, it is very useful. If you need to crack a code by factoring a 200 digit number, getting the right answer 50% of the time would be fantastic. You just try repeatedly until you get the right answer.

When designing computing algorithms, wouldn't you want it to return the correct answer 100% of the time?

Of course. That is why the "quantum" computer would be just part of the solution. Overall, your algorithm would look like this:

for (;;)
}
}
}

This solution would be good enough for any problem where verifying an answer is much faster than finding an answer. Most NPC problems [wikipedia.org] fall into this category.

• #### Re: (Score:2)

Most NPC problems fall into this category.

Actually, by definition, *all* NP-complete problems fall into this category (unless P = NP)

• #### Re: (Score:2)

Sometimes it's good enough, sometimes it's not.

• #### Re:Can someone explain... (Score:5, Insightful)

on Sunday August 26, 2012 @12:00PM (#41130007)

An algorithm that could factor a 4096 bit number even 10%
of the time would be enough to consider 4096 key as completely unsafe
for cryptography.

It is easy enough to verify the result.

• #### Re: (Score:2)

Well, since time isn't linear in this case, and so each step/change (time is advancement through possibilities) is not fixed, you can bump into 48%, when measured in linear time.

• #### Re: (Score:2)

Just like converting between units:
(1/3)+(2/3)=1;
0,333333333~+0,666666666~=0,99999999~;
1=0,99999999~.

So in this case, the conversion hit 48% linear time here (and 52% elsewhere, hehe), so (48+52)/2=0.

But math isn't pure logic, and so there can never be proof/disprove of what I have typed in this post...

• #### Re: (Score:2)

Just run the program multiple times and take the mode.

• #### Re: (Score:3)

I have a device that gives you the winning lottery numbers ahead of time, but it has only a 10% chance of being correct. Is it useful?

• #### If I calculate 135257x15643 in my head (Score:2)

If I calculate 135257x15643 in my head, the correct answer is found pretty close to zero in five attempts. Is that good?

• #### Size, not reliability (Score:5, Interesting)

on Sunday August 26, 2012 @10:57AM (#41129601) Journal
Validating the result is cheap on a classical computer. Even for very large values, multiplying two 4096-bit values together and checking the result is incredibly cheap. A quantum computer that could give the right set of divisors for a 4096-bit prime 1% of the time would still let you very quickly find which of the answers that it gave was correct. The limitation is the size, not the reliability.
• #### Why isn't 48% good enough? (Score:2)

Why isn't getting the correct answer 48% of the time impractical?
• #### Re: (Score:3)

Why isn't getting the correct answer 48% of the time impractical?

It's not the 48% that is not good enough, it's factoring a number such as 15, which is easy enough to do already without going through all the trouble of using a quantum computer. Basically, this is a very significant stepping stone, but we're not living in a world of quantum computing yet.

• #### Re: (Score:3)

Then the summary was worded terribly.

• #### Re: (Score:2)

Ah. I should've taken that as read, really.
• #### Re: (Score:3)

Don't know much about higher mathematics, but based on the post and the explanation of Shor's Algorithm from wikipedia, its not an issue of how easy it is to factor a small number or how practical. Its more of a benchmark for quantum computing. If the ideal success rate is 50%, then 48% is an indicator of how well the system is operating.

And besides, the quantum computer got a higher score on that math problem than the average American student. That's got to count for something.
• #### Re: (Score:2)

Don't know much about higher mathematics, but based on the post and the explanation of Shor's Algorithm from wikipedia, its not an issue of how easy it is to factor a small number or how practical. Its more of a benchmark for quantum computing. If the ideal success rate is 50%, then 48% is an indicator of how well the system is operating.

And besides, the quantum computer got a higher score on that math problem than the average American student. That's got to count for something.

Not really. 48% is plenty good enough, if you have a solid state quantum computing device that can use Shor's algorithm on larger numbers.

As mentioned above by other people, the way you'd use Shor's algorithm is use it to get the factors, then multiply them together using a conventional computer and see if you get the original number back. Multiplication is a pretty fast operation, compared to factorization, so the verification isn't really very costly. With a 50% success rate for Shor's algorithm, on ave

• #### Re: (Score:2)

Also, it's 48% for all the trials they did. The probability of getting heads when flipping a coin is 50% as well, but if you flip it 100 times, that doesn't mean that you'll end up with exactly 50 heads and 50 tails. All it means is that as you approach infinite trials the probabilty of getting heads tends towards 50%. So, depending on the number of trials they did, 48% is actually close enough to 50 that you can be assured that the algorithm is working just fine.
• #### Well heck, Intel might buy it. (Score:5, Funny)

by Anonymous Coward on Sunday August 26, 2012 @11:04AM (#41129677)

Historically, they're a bit more tolerant about that math thing.

• #### Re: (Score:2)

Historically, they're a bit more tolerant about that math thing.

Yes, they do show at least a qubit of interest in this.

• #### NSA likely already built one (Score:5, Interesting)

on Sunday August 26, 2012 @11:10AM (#41129719) Homepage

It seems that quantum computing has consistently been viewed as harder than it really is, judging by the ever-decreasing timescales between breakthroughs. Judging from the history of cryptography, and the military value of being able to break RSA, it's not unreasonable to expect that the NSA may have been trying to build such a chip for some time and could potentially have succeeded.

Some months ago James Bamford, who is the premier chronicler of the NSA and has a history of being given accurate leaks, claimed the NSA had made a "huge breakthrough" in its ability to break codes [wired.com] - and that the datacenter they're currently building is a part of the solution. The NSA denied everything of course. But if academics are now able to build a working implementation of Shors algorithm for small numbers, that strongly implies that a focussed team with practically infinite budgets could have already succeeded in building one that can handle crypto-sized numbers.

• #### Re:NSA likely already built one (Score:5, Insightful)

on Sunday August 26, 2012 @11:34AM (#41129849) Homepage

And before anyone freaks out and thinks that the NSA is reading their e-mail, keep in mind that they have to be very selective about how and when they use results from their quantum computer. This is similar to breaking ENIGMA--you want the enemy to think that their codes are secure, so you don't suddenly counter all of their plans perfectly. You certainly don't turn this on e.g. classical organized crime, as that could give away your capabilities on a considerably less valuable target.

• #### Re: (Score:3)

Nah, they just have to act "correctly" on the intel without it being statistically obvious.

• #### Re: (Score:2)

Also called 'don't worry, just a routine check'.
• #### Re: (Score:2)

Email mostly transits the backbone unencrypted, so no crypto breakthroughs are necessary to do that. All the evidence points towards huge data collection and mining operations by the NSA that are only getting bigger, so I'm pretty sure that yes, the NSA does "read" my mail (in the sense that it is probably run against a large list of regular expressions or something).
• #### Re: (Score:3)

And before anyone freaks out and thinks that the NSA is reading their e-mail, keep in mind that they have to be very selective about how and when they use results from their quantum computer. This is similar to breaking ENIGMA--you want the enemy to think that their codes are secure, so you don't suddenly counter all of their plans perfectly. You certainly don't turn this on e.g. classical organized crime, as that could give away your capabilities on a considerably less valuable target.

That's not much comfort, because there's a subtle distinction you blur. After cracking ENIGMA, they were aware of much more than they acted upon, in order to keep the breakable communication flowing. It doesn't mean they decided not to crack as much enemy communication as possible. Similarly, it doesn't mean they won't actually monitor "classical organized crime," but rather that they might not act upon the information they glean from monitoring it.

The only thing that will limit their reach is capacity. T

• #### Re: (Score:2)

It seems that quantum computing has consistently been viewed as harder than it really is, judging by the ever-decreasing timescales between breakthroughs. Judging from the history of cryptography, and the military value of being able to break RSA, it's not unreasonable to expect that the NSA may have been trying to build such a chip for some time and could potentially have succeeded.

Well, of course, they got it from the aliens at area 51 decades ago. They've just been spoonfeeding us the tech, bit by bit.

• #### Re: (Score:2)

or perhaps someone managed to sell them the idea that by using billion bucks they would then have that?

• #### 50% of the truth (Score:2, Interesting)

Could it be that the reason the algorithm is only supposed to get the rich answer 50% of the time is that there is a parallel universe out there where 5 x 3 is not 15???!?!?

• #### Huh? (Score:2)

I get the correct answer 99% of the time. Too bad I hit that remaining 1% during my entire period of elementary school :/

• #### Re: (Score:2)

A little offtopic, but your post reminds me of something I read not so long ago

"If religions say that life is eternal, why are they so worried about what you do in your first century?"

• #### The most important part is knowing the question. (Score:2)

It may sound cheesy, but if you are going to get the answer correct 50% of the time then the most important piece becomes knowing which question to ask, and being able to test whether your 50% answer is right. If not, rinse and repeat. Eventually you're going to get something interesting.
• #### What comes after? (Score:2)

If quantum computing is the end of encryption as we know it, then soon the internet as we know it will end too.

How will electronic communication be secured after quantum computing?

Someone call Al Gore: We need a new internet.

• #### Re: (Score:2)

Quantum computing threatens only public key crypto, secret key crypto is not affected. So how do you solve the key distribution problem if traditional algorithms are insecure? Either you use quantum key distribution or you base your public key crypto on a mathematical problem not affected by quantum computing.

In any case fundamentals of cryptography should be the least of your concerns as vulnerabilities are usually found in the implementation and usage.
• #### solid state quantum computer, since when? (Score:2)

I found it interesting that the summary mentioned a solid-state quantum computer, since I (apparently incorrectly) believed that it consisted of teasing a cloud of Rubidium atoms to standstill in a near-vacuum and then shining lasers at them.
Solid-state sounds a lot cheaper.
• #### Oh no! That's my public and private keys! (Score:2)

Crap! I knew it was only a matter of time before these new fanged quantum computers cracked my 4 bit RSA encryption key!

• #### Bourbon (Score:3)

on Sunday August 26, 2012 @01:45PM (#41130771) Homepage
"48% of the time, *finger snap* it works 100% of the time."
• #### New Math (Score:2)

Its sufficient to understand what you are doing. Never mind getting the right answer [youtube.com].

• #### Great! Congrats! (Score:5, Interesting)

on Sunday August 26, 2012 @03:58PM (#41131609) Journal

Disclaimer: I am a former researcher in the field, left to some other job.

What you can see at UCSB is what happens when a team of scientists which ae skilled in engineering, working as a team, and collaborating with everybody happens to have the right guy as the leader (with the right policy about co-authors on publications).

Everybody whom i met from this team was open, honest, and friendly; they have worked hard and long on it and they accumulated some of the best people.

They deserve the success they have now! I think there may be a small break now in their publications, since i have the ffeling they now may work on overcoming the next big roadblocks (but now they they have all the backing they could need for it).

I also have to state it will be a long long way to the first QC. While i believe that every step like this will be more than just replicated at the NSA, i believ that they wont be more than 10 years ahead, and i estimate 20y-30y until qc works better than classical qc (although I also hope and believe that breaktroughs are possible).

The person who's taking you to lunch has no intention of paying.

Working...