Slashdot Mirror
Solid State Quantum Computer Finds 15=3x5 — 48% of the Time
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."
Sometimes 2+2=5, give the thing a break!
50% of the time.
To be fair, it could have been either until we looked.
(And you could have posted either here or at the correct story.)
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?
"Lame" - Galaxar
If I calculate 135257x15643 in my head, the correct answer is found pretty close to zero in five attempts. Is that good?
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.
I am TheRaven on Soylent News
Close enough for government work.
No brain, no pain.
Why isn't getting the correct answer 48% of the time impractical?
systemd is Roko's Basilisk.
Historically, they're a bit more tolerant about that math thing.
It was both a moon and a space station at the same time.
To the jerk who modded the parent down:
Read up on schroedinger's cat you doofus.
Then you can have your geek card back.
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 - 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.
Because once you get the (maybe wrong) answer, you can easily check whether it's right, and try again if it's wrong.
Try to factor 15, and machine tells you something like 15=8*4. Multiply 8 times 4 and see whether you get 15. Yes => done. No => run 15 through machine again. 50% accurate means you only have to try twice on the average. 1% right means you have to try 100 times. Each try might take a few seconds, or a few minutes, or a few hours, say, for a 500 digit number. Even if you have to try 1000 times (on multiple machines in parallel, perhaps), that's nothing compared to the millions of years it would take to factor a 500 digit number conventionally.
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???!?!?
I am Slashdot. Are you Slashdot as well?
I get the correct answer 99% of the time. Too bad I hit that remaining 1% during my entire period of elementary school :/
If Pandora's box is destined to be opened, *I* want to be the one to open it.
Why not? It could be used to count ballots. Couldn't be any sloppier than what we have now. Considering who's running, it may as well be a coin toss anyway
“He’s not deformed, he’s just drunk!”
As I said two posts above yours, it's not practically useful because factorising 4-bit numbers on a classical computer is already easy. Factoring larger numbers is hard, but requires more entangled qubits.
I am TheRaven on Soylent News
As others have said the real issue isn't the success rate they have. The real question is can they make it scale to bit counts where it is actually useful while maintaining a tolerable success rate? That means increasing the number of bits dramatically.
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
I don't understand how this isn't of practical use.
Size. In order to attack larger problems, you need more entangled qubits. For some mixture of engineering and physics reasons that I am deeply unqualified to discuss, building systems capable of keeping qubits in their proper state seems to get increasingly hairy as the number of qubits you need grows.
That's why '15' is a popular number to factorize in quantum computing experiments. It's really small. Since classical computers are far more mature, and a great deal cheaper, the problems that very small quantum computers are capable of attacking are also solvable in minimal time by ordinary means. Only if you can build a fairly large quantum computer do you get to the point where the extreme efficiency(for certain purposes) of the quantum computations can be applied to problems sufficiently large that you can't just steamroller them with cheap silicon.
No acceptable compiler refactors math equations in a way that breaks numerical accuracy, unless the user explicitly requests it (gcc's -funsafe-math-optimizations comes to mind). Optimizing compilers are useless if they give the wrong answers for the most compute-intensive problems.
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.
I do not respond to cowards. Especially anonymous ones.
IIRC, the Pentium gave correct answers 0% of the time.
We make compromises for accuracy all the time in computation. The use of floating point numbers is one such case. Simple numbers such as 0.1 can't even be accurately represented in binary floating point but we use binary floating point over decimal floating point for many tasks simply because it runs faster, and the answers it gives us is "close enough"
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
Great, now some financier is going to get the brilliant idea to start using this to calculate my paycheck each week.
because-- we haven't 'gotten there' with the higgs yet-- still may NEVER..
every day http://en.wikipedia.org/wiki/Special:Random
I agree. The AC's comment which is blatantly wrong is more specific:
High-performance numerical algorithms are written with the expectation of a well-behaved compiler which will not attempt to refactor mathematical expressions on the basis that it may change the numerical error. The mathematicians who write these algorithms understand how the error accumulates, so their order-of-operations will be tailored accordingly.
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.
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.
To be, or not to be: isn't that quite logical, Slashdot Beta?
Crap! I knew it was only a matter of time before these new fanged quantum computers cracked my 4 bit RSA encryption key!
"48% of the time, *finger snap* it works 100% of the time."
sig: sauer
Without having studied this particular issue, I'm guessing that that is why the answer is correct only 50% of time under ideal circumstances. It can be 5x3=15 or 3x5=15 (so it could've been either). Perhaps someone more involved with quantum algorithms can correct me on this?
Am I the only one interested in what the quantum computation returned the OTHER 52% of the time?
Its sufficient to understand what you are doing. Never mind getting the right answer.
Have gnu, will travel.
still better than most humans
Schrödinger wrote about the cat idea in order to demonstrate how ridiculous that particular model of quantum physics is; he'd be rolling in his grave if he knew that people were taking it as truth...
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).
I'm no expert. But Shor's algorithm has you choose a value A and find the period of f(x) = a**x mod n.. If r ends up being odd or a**r/2 = -1 mod n, you have to start over.. (If I understand it correctly, if r/2 = -1, you just showed 15x1 = 15 which isn't useful..
Perhaps some more knowledgeable could comment on this?
That explains why some programmer's hate C++'s operator overloading.
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
Consider the "use quantum computing to get an answer, use regular computing to verify answer" post higher in this thread.
While it's computationally intensive to factor number, it's absolutely trival to check factors' prdocut against target number.
Yes, it's possible that the quantum computer will give a false positive half of the time like "13 = 3 x 5"
On the other hand, it's quite trivial to see that 3 x 5 make 15 and not 13 and thus this was a false positive.
It can be a viable pre-filtering technique. Currently, factoring large numbers is awfully resource intensive. You basically have to recursively build a table of prime numbers up to sqrt(n)
Now with a quantum computer, you might only need to do multiplications to check the things that the quantum unit is spitting, and keep doing this until you have a big enough confidence of the result.
Depending on the implementation (specially the hardware implementation of the quantum unit), you might get a sufficient enough answer in a much shorter time frame than with a classic computer (where the time frame might be more like "universe heat death")
As you said the problem currently is successfully making a quantum computing units that can work on anything bigger than a trivially small number of qubit.
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
Good luck breaking RSA.
Yup.
for a 4096 bit key, it would give the correct numbers only a very tiny fraction of the time. But that's still better than zero.
consider that to mutliply the factors to verify the answer is trivial.
if the speed of the quantum unit is high enough and it spits answers at a sufficient rate, even if it only spits the correct answer at a very low rate, by veryfying constantly the result of the quantum unit, after a while you may end up with the correct result with a sufficiently high confidence.
if the answer-spitting-rate is high enough compared to the correct-answer-rate this "after a while" might be better than the time necessary to brute-force-factorise the numbers with current technology.
Yes you can't have nice things (for free).
But quantum is the kind of weird technology which can give lots of *shitty* things (for free).
Okay, these things are *shitty* and not *nice*, but you still get them for free.
And you can still try putting them in a big pile, light them on fire and use the heat to cook a nice dinner. And a dinner is *nice*.
maybe the production rate is forced to scale badly compared to the true-positive rate and they cancel each other exactly the same way a perpetual motion machine always ends up having an output energy of zero or worse.
but that not a reason to not even try proving *that*. we need to at least understand quantum computing well enough to be able to see if this 50% vs 48% difference will become an obstacle in the long term or not. we have to test and prove your predictions.
maybe cooking dinner over quantum virtual shit is not worth it, but at least we have to prove it.
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
That case happens rarely. The case you're actually looking for is values of a where the function has even period.
The reasoning behind it is this:
Suppose that N has at least two distinct prime factors. (If it isn't, then N is either prime or a perfect power of a prime. There are efficient algorithms for detecting the latter case.) Further suppose that the function f(x) = a^x mod N has minimum period 2r for some r. (That is, f(x+2r) = f(x), but f(x+q) f(x) for any q < 2r.)
In this case, a^(2r) is congruent to 1 modulo N, but a^r is NOT congruent to 1 modulo N. That is, a^r is a square root of unity modulo N, but it isn't congruent to 1. If it also isn't congruent to -1 (which is the case that you mentioned), then it's a nontrivial square root of unity.
Now consider the number d = gcd(a^r-1, N). If d=N, then N is a factor of a^r-1, that is, a^r is congruent to 1 modulo N. This is a contradiction (since we eliminated this case above), so it can't happen. Similarly, if d=1, then a^r is congruent to -1 modulo N, which is the other case that we eliminated above. (Exercise: prove this!)
So d is a divisor of N (because it's the gcd of N with some other number), but it isn't 1 or N. Therefore, it's a nontrivial factor of N.
Of course, it's not obvious that there should be an a for which f has even period, but that's where the hardcore analysis comes in.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
Does this have something to do with PvsNP problem? Its solution provides a perfect algorithm for facturing numbers i guess
The computer really didn't want to give an answer after being asked so many times, but was forced to take a side.
Computers with natural attitudes.
There are only 379,501,200 (54!5) combinations in Texas. With a few hundred thousand dollars spent on unique combinations, your probability of winning is rather higher than 0.0001%. Your problem there is going to be finding the people and time to get all those dots filled in.
If you want to try playing with a simulation of Quantum Computing, you can check out my tutorial that shows you how to do Gover's Algorithm using QCF on Octace.
But you can't tell which way he's rolling without opening his coffin.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Getting the right answer quickly 50% of the time (and being able to quickly verify that it's correct) is much faster than getting the right answer 100% of the time if the calculations take longer than you're willing to wait (e.g. crypto problems where you can pick a key size for which cracking requires a computer the size of the planet to run for billions of years.)
And knowing that somebody else can guess the right answer 50% of the time, instead of having to wait arbitrarily long times, affects your choice of algorithms. This is why cryptographers are really concerned about quantum computers - they're the only significant threat to modern cryptography (except for special cases like differential power analysis when the attacker has physical access to your computer, or sloppiness like bad random number generators or protocols that leak information.) So while factoring "15" is obviously not a hard problem, if the methods used to do it can be extended to crack longer keys, and don't hit some kind of Heisenberg limit (Planck's constant is about 150 bits), then it's interesting.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks