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!
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
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.
Historically, they're a bit more tolerant about that math thing.
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.
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.
Then the summary was worded terribly.
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.
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.
They've done studies, you know. 48% of the time, it works every time.
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.
"48% of the time, *finger snap* it works 100% of the time."
sig: sauer
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).
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 ]
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});