Slashdot Mirror
First 7-qubit Quantum Computer Developed
AllynKC wrote: "Wired News has this story on the developments in quantum computing. Federal researchers have developed the worlds first 7-qubit quantum computer.
Interesting stuff; but even Wired's toned-down version is, quite honestly, beyond me at some points. Still, the concept of a fully functioning quantum computer intrigues me."
Also, does it have a USB port?
> "There is no spoon"-Neo, The Matrix Neo said no such thing. - Captain Nitpick.
Your first problem is that you're asking a bunch of geeks. My god man... use your head.
> Furthermore, the NSA has generally led civilian scientists by a couple decades in cryptography work.
In crypto theory, sure. Their hardware these days is pathetic tho.
heh, sorry, when I said "factoring primes" I meant trying to find a prime factorization of a number, sorry.
Paranoid thought: what if the NSA already has production quantum computing systems, crunching away at the world's keys while they laugh at distributed.net?
Optimistic thought: think about running Seti@home clients at these, super-imposing all the parameter space searches they do in each work unit.
please don't post at them anymore, thanks.
The people who get it first are highly dependent on those very banks. If they knock some pillars, they cut themselves down at the knees.
Ludite.
> Random observation: we're seeing e-everything nowadays. Tomorrow will we start seeing q-everything?
Hopefully.
Then e can resume its role as the fifth letter of the alphabet.
. . . the obvious question.
... does it run Linux?
thank you.
Cryptography will evolve to a level that can deal with faster computers! Think about what you are saying. Technology is a wonderful thing, it is rarely ever static. Necesity is the mother of all invention. When the CIA needs to hide its mail from the rest of us they will find a better encription algorithm for their office e-mail system.
Is there a quake port yet?
This is all well and good, but the window between the introduction of quantum computing and the adoption of new methods of cryptography is too dangerous to be so blithely ignored. If new methods of cryptography are possible, fine, but research into quantum computing needs to be stopped until they are in place.
dude, if anyone here knew the answer... he wouldn't be here!
a Beowulf cluster of Palm Pilots?
> factoring prime numbers.
No, but the NFS (Number Field Sieve) can be used
for factoring AND solving discrete log problems.
Also - don't be so sure that noone can read
the state of a particle without changing it.
This is 'insightful'? The guy has no clue what quantum computing is really about.
A quantum computer does far more than run the same algorithms faster than a conventional computer. Given a quantum computer with sufficient qubits to represent any single input to an algorithm, you can run that algorithm on all inputs in parallel. So instead of having to spend O(N) time searching a key space with N keys, you only have to spend O(1) time. So no matter how big you make your keys, a quantum computer exists with at least as many qubits as your key has bits will be able to break your encryption in the same time it takes to test a single key.
I think if we were to consult a NINJA, he would say:
"Goliath was said to be 7 span and 6 qubits."
- A Ninja
Good..Microsoft will be releasing a version of Windows for it in 3 weeks.
Who wants to bet on how long before the words, "trans-crotonic acid" show up in a Star Trek Voyager episode. Maybe they already have?
Wasn't Noahs arc 40 qubits!?!?!?! :o)
Well, fine, it will be harder to eavesdrop on communications. But what about spoofing connections, or decrypting encrypted data, however obtained?
I Recall someone making a similar statement concerning all computers a few decade ago. "I see a market for about ten computers in the whole world." Wasn't that the boss at IBM about fifty years ago?
Wow, if you thought that that computer is sweet, check out this link:
http://xlem.hypermart.net
That's dumb. Society will never be reformed. We need stronger crypto.
Actually, quantum computation has the ability for massive quantum parallelism. While Moore's law says computers will get faster exponentially, that's nothing compared to what quantum computers are capable of because the algorithms each machine is capable of are totally different. Lets say you have a Moore's Law box running a 1 GHz and you need to execute 1 million lines of code to get the solve a problem. Now a quantum computer might only operate a 1 MHz, but it turns out that if the problem you are interested in is to factor a very larger number, then a quantum computer could do that in maybe only 1000 lines of code. You see the advantage. While the classical computer can execute more instructions in a certain amount of time, the quantum computer is able to take advantage of the massive parallelism of quantum mechanics so it needs to execute far fewer instructions to solve the same problem. This isn't true for every problem, but it turns out that factoring is one that behaves this way.
Well, assuming you (eventually) get a quantum CPU... IO and other resources might not like being accessed simultaneously by multiple OSes...
I wouldn't get too worried - it doesn't appear that the current research of is any use but for testing theories.
This is why it needs to be stopped at this stage. But if there's always going to be that window of lawlessness and anarchy between the development of quantum computing and the implementation of quantum encryption, we'd probably be better off ceasing research and just plain not resuming it. If the choice is between not researching quantum computing and the destruction of some substantial portions of the pillars of our civilization, I know what I'd pick.
I only hope I live to see that day . . .
Quantum computers would certainly compromise RSA-based public key cryptosystems, but not all public key cryptosystems are automatically rendered useless by the advent of quantum computers. For instance, elliptic curve cryptosystems are immune to
attacks by blindingly fast integer factorization techniques.
Research into the quantum computer area must be enhanced.
My bad. I was thinking with my cock again.
I've recently looked at Quantum Computing and have put together a web page with some information and links at http://www.rpi.edu/~bonanj/qcomp/
A good point. Moderate this guy up! Oh yeah, and I'm serious about this question. I NEED TO GET LAID!
Just like the digital processor cycle!
I CANT WAIT TO RUN WINDOWZ ON MY NEW QUANTUM COMPUTER!!!!
Not PC cpmpatible == niche market == few sales == higher costs == eventual bankruptcy.
the quantum computer wouldn't play a mean game of chess. It would, however play ALL POSSIBLE mean games of chess at once. Truly, Kasparov would have trouble here...
The encryption stuff is nice and all, but will it run Windows?
If you are going to be that anal, you may as well say "factor large positive composite integers into primes".
getting ph1rst p05t will make you suave and sexy beyond human reckoning.
"That first-poster is one smooth mutha..."
"Shut yo' mouth!"
"I'm just talkin' 'bout Gritsboy!"
"We can dig it!"
Damn right.
We will never discover how to time travel/dimension jump because every time someone figures it out and comes to the realization of how bad it is, they jump back and prevent it from ever being discovered. ;)
the new computer modertate this post down to a -1?
I can't try it at home, I already microwaved my furby >:)
PS: A "full blown" cpu of all quantum hardware might not be as good a thing as some ppl might think... Qubits are good at figuring out some things and not so good at figuring out others; It's like the difference between a RISC and a CISC ... a chip with MMX would be better at multimedia than a RISC, but the RISC would be better at database ops or sorting and such. Quantum is just another technology, it isn't THE be-all-end-all next technology. yet.
Espically if you first post for Scooby Doo! ( It works, I know! )
... a Beowulf cluster of these?
thank you.
Rendering our current encryption schemes worthless would not be a bad thing. For example, people being able to draw funds from the accounts of others and miltary units getting bogus orders from who knows where. However, there are other safeguards. The overdependence on computers and insecure networks for many things will eventually be realized not only because of such security issues but because of how this affects people's lives. Some information should be personal and doesn't belong in a global information network where it can be accessed by others. So-called security is a bogus issue because it already is breached by the very people who claim to be protecting it - governments, large corporations, etc. Information which should be confidential or restricted to certain use is freely traded by so-called "trusted" entities every day, on every single one of us. This information doesn't belong in such networks at all. For example, military units should receive their orders in person from commanders or on secure physical networks which are totally separated from the internet and civillian networks where the only way to protect such communiations is cryptography. Right now they use the same networks and channels as posters to Slashdot, so anyone can, in theory, send bogus orders to a miitary unit or even start a war from anywhere in the world! Networks (including the internet) which transcend corporate boundaries should be for free communication and education only, and information derived from such networks like the internet should not be the basis of world economies. Financial and other sensitive transactions should use (physically) separate channels of communication. Of course this would bring an end to E commerce, but E commerce is a bad thing. Yes, personal contact and "snail mail" is necessary and useful sometimes, and the need for more of that will soon be realized when those who have come to depend on global eletronic networks understand fully that this inevitably leads to the concentration of money and power into the hands of a smaller and smaller group of people or even worse impersonal corporate and governemental entities. Another way of putting this is that remote access on open networks like the internet should not allow update privilidges. Persons could still send information or post it, though. Updating the information being viewed or read would have to be done through other, physically separate channels where cryptography is not an issue. This means that to update your own web page you might need to hand carry the information to your ISP or use a private hookup to the site. Of course all financial transactions over such open networks like the internet should be held null and void. Again, the danger is not so much from so-called hackers as from the very people who claim to be safeguarding our rights and our financial security - governements and corporations. The loss of privacy is just the tip of the iceberg.
I pour trans-croutonic acid on my salad.
(Vinaigrette! Mmmm....)
linux> dog bash: dog: not found linux> whereis dog dog: /usr/bin/dog /usr/man/man1/dog.1 linux> /usr/bin/dog | cat catfood & cat: MEOWWWWWWWW!!!!!!! cat: SIGKILL recieved Segmentation Fault Core Eaten linux> Dog process exited with code 1 linux>
I don't know much about quantum computing... But isn't quantum mechanics the only truly random thing in the universe?
Over all possible combinations of states, one of those combinations must represent a portion of the linux kernel, and another another, etc ;)
Just like a transcendental number! (well, maybe not exactly like a transcendental number, since the total number of possible states is finitely fixed by the # of qubits... but still, The WHOLE linux source and all binaries can be represented by combinations (with replacement) of the qubits of a non-zero qubit machine!!
8)
how about a beowolf of these quantum computers? -Tanga!
the ninja troll is a retard. that shit is played out punk. why don't you click your heels together and go back to kansas bitch. sincerely, gordon liu
One of the things that quantum computing brings to the table is a new type of encryption.
If you firmly believe that the powers that be won't take advantage of quantum encryption...well, then I can see where you get your paranoia.
Besides, all information wants to be free...
>;)
'Nuff said.
Ok, now I'm really confused...
From a chemist's point of view, this is what I know of the NMR part of the work at read at Wired. NMR lines up quantum spin states of molecules in solution sort of like flies stuck to a sheet of fly paper all in the same orientaions. If you fire RF electromagnetic energy at these lined up molecules at the magic or "resonance" frequency, you can knock these nuclei to the next spin state. YOu can detect the transistion with an appropriate detector. That's the basiscs of what chemists use oit for, though I imagine the work done at Los Almos by these gentlmen is far more cutting edge. As for the "mysterious" liquid. I imagine it's nothing special that they synthsized. They probaly chose it because it gave clearly interpretable spectum or some other technical reason. You could probably buy it at a general chemical supply house for about $5 per kilogram.....just my wo bits on the basics .......
Not all modern cryptography is based on the difficulty of factoring large numbers. There are encryption algorithms based on the Discrete Logarithm problem such as the ElGamal cryptosystem. These algorithms have nothing to do with factoring prime numbers. I don't know much about Quantum computing, so I don't know if this problem is also "vulnerable" to quantum computers :).
Also, one-way hash functions, such as MD5, are also not based on factoring large prime numbers.
Anyways, sorry about the nitpick!
I wish people would stop finding ways to solve these intractible problems!
that was QBert :)
"There is no spoon"-Neo, The Matrix
"SPOOOOOOOOON!"-The Tick, The Tick
There are a lot of issues to be worked out about quantum gates and transistors before anyone can build a working quantum device of any complexity. First of all, there are issues with the nuclear weak force. Experiments have found that complex quantum circuitry just isn't terribly reliable because the weak force tends to break the connections between the quantum components. There are also timing issues, since at that scale there can be relativistic effects related to the speed at which signals are passing back and forth. You can actually have a signal that seems to arrive before it was sent, which plays all sorts of hell with the logic, as you can image if you know anything about programming. Some theorists have suggested that modern lazy functional programming languages such as Haskell may be best suited for programming quantum computers precisely because of this problem; it's already possible today to write Haskell code where information seems to go backwards in time due to lazy evaluation interactions. But anyway, I think quantum computers, if they ever become viable, won't appear for at least twenty to fifty years. People get so optimistic sometimes about their latest successes that they forget how much left there is to do, and how little a piece of the puzzle they've really solved, and that it isn't valid to assume that just because you've solved 10% of the problem in N years, you'll be able to solve the remaining 90% in 9N years. It's not a linear situation.
As an NMR (nuclear magnetic resonance) jock with some knowledge of the systems and methods used for these approaches to quantum computing, I tend to be 'cautiously optimistic' about the future of q-comp, like most. But I do have to comment on the embarrassingly poor reporting in that Wired article, at least as far as the description of NMR methods goes. Admittedly, it's difficult to distill the details of many scientific research techniques into layman's terms, even without the copy length restrictions of most publishing outlets, but this one was pretty bad. In this case the blame should probably be shared equally by the writer and the source, Laflemme ("needles with bulldozers"?!). The comment about 15 qubits being a practical limit for the NMR qcomp approach is probably the only valid detail, barring some new developments in relaxation-cancellation methods (which are not out of the question, given the recent advances in NMR methods for structural biology).
WWJD? JWRTFM!!!
What, your qubix kernel doesn't want to run in supervisor mode either?
Does that count as an observer?
Damn you Heisenberg, and your Uncertainty Principle!
Oh well. I think it already runs QNX...
---
pb Reply or e-mail; don't vaguely moderate.
pb Reply or e-mail; don't vaguely moderate.
Why did the Wired article describe NMR as a specialized version of MRI? If anything, it's the other way around.
"... nuclear NMR spectromotor, which is a specialized version of the imaging devices commonly used in hospitals."
Also, "nuclear NMR" is, like " ATM machine", redundant.
Is it just me or does this sound a heck of a lot more like a register than a computer?
... I'm sure this should be refered to as a computer.
It's quite a leap from a simple register type device to even the most primitive ALU
"There's no secret. You just press the accelerator to the floor and keep turning left." -- Bill Vukovich
(think Bill Cosby)
--
John Kramer
John Kramer
God may be my co-pilot, but the devil is my backseat driver.
The problem is not that it isn't a law, it's that fast new processors get dropped on Intel/AMD every 18 months. They get dropped on me something like every four years....
~luge
IAAL,BIANLY
Apparently I'm not the only fossil around here : )
(remember the part about changing the sex of one of the elephants?)
I see even classic Slashdot is now pretty much unusable on dial up anymore.
Within hours, Intel announced plans for a 14 qubit processor backwards compatable with x86 instructions.
MS claims they will have a version of windows ready for its release, although its rumored to be months behind schedule.
Its already running linux.
Know what I like about atheists? I've yet to meet one that believes God is on their side.
These people mangle chemistry. It's trans-crotic acid. Just like it's not a spectromotor but a spectrometer.
Dennis
Maybe it's just because I know what's involved with this experiment on a practical level that makes me think that something really big is going to need to happen before q-computing makes any significant dent in anything.
The experiment is done in an NMR, which is completely impractical for any kind of device for widespread use. Any extension to higher qbits involving the same type of experiment seems to me to be of very limited value.
Conceptually it's interesting, but until the principle can be demonstrated completely at room temperature (the sample is at RT, but the magnets in the NMR are liquid nitrogen and liquid helium cooled), I don't think it's going anywhere.
Dennis
"Actually, a Qubit is the distance from your elbow to the tips of your fingers."
Isn't that a `cubit'?
Kwoobit....
-rozzin.
Okay, so is it mere coincidence that the numbers here are 2^3-1=7 and 2^4-1=15? I can't imagine that powers of two would impact qubits, but the question seems worth asking.
Also, things like the MD5 digest might be invertable faster using a quantum computer than a conventional one. Also, if it turns out quantum computers can solve NP problems in polynomial time, a lot of fundamental assumptions in even symmetric cryptography are going out the window.
On the other hand, we'll always have one-time-pads. (assuming you use them right, the two time pad is a poor form of encryption)
- From an application-level standpoint, there's nothing to distinguish a quantum computer from an electronic one except for speed
- IIRC, encryption speed scales linearly with key length while (brute force) decryption speed scales exponentially; this means that it will always be far more difficult to break a given key length than it is to encrypt that same key. Advances in technology help both sides of the equasion.
The advantage of quantum computers is not just that they're faster (in fact, they aren't), but that because of the way they work, they can solve some problems with a better asymptotic running time (that is, in fewer steps), than a conventional computer.For example, RSA encryption assumes like you said that factoring a product of primes scales much worse than just multiplying numbers. This is true on a conventional computer, a quantum computer does not need exponential time to factor numbers, it can do it in polynomial time.
Even brute force quantum computers can do faster (but not a lot faster, just a factor of N^2 faster).
>Well, assuming you (eventually) get a quantum
>CPU... IO and other resources might not like
>being accessed simultaneously by multiple OSes...
Well, obviously we'd have to have some level of virtualization going on... some underlying arbitrator of resources.
We do this now with stuff like VMWare, I don't see why it's such a reach to assume that we couldn't do the same thing with quantum processing.
-LjM
So, in 5 years a quantum computer will triple todays fastest computers in performance?
But according to moores law (or not really, because that's all about transisitors...) processors double in power every 18 months... so:
if todays fastest computers are 5's, then quantum computers 5 years from now will be (5*3) 15's, while regular super computers will be (5*2*2*2) 40's... Doesn't sound very exciting to me in that time frame.
The port was relatively painfree...
.sig: Join AMSAT
note "relatively"
but the simultaneous crash/noncrash superpositions of states. And the blue flash of Cerenkov radiation... Omigawd! it's running a Win OS!
My new
If you can go to bed, knowing you did a valuable thing today, you're very lucky. If you can't... it's not bedtime
"Adding more of the same" works only for building bigger classical computers. A 32-bit register can be constructed from 32 individual isolated bits. But for a useful 32-qubit register, you must be able to maintain quantum coherence over the whole ensemble. 32 individual qubits will not suffice.
David
Good explanation, but there's a couple things that are missing. For a somewhat longer explanatory article, people can look at one from Scientific American a few years back.
The importance of the 7 qubits is mainly just the same as the importance of bits in a classical computer: this is essentially the memory capacity of the quantum computer. It is also very important to have extra bits since, as you say, you can use redundancies to keep your computer from decohering (becoming non-quantum). But I remember a talk by a guy using chloroform as the molecule (CHCl3, for 2 qubits), and talking about using Shur's factoring algorithm (the quantum algorithm to factor numbers very quickly) to factor a number like 4. Not very exciting from a mathematical standpoint.
The cute thing about using NMR with organic molecules this way is that different frequencies "talk" to different atoms in the molecule. So you can set or manipulate different qubits using different frequencies. The qubits talk to neighboring qubits as well, through the atomic interactions: this is actually a good thing- it's most of how your calculation gets done (the NMR is essentially I/O). Unfortunately, there's a problem with this approach: there's a physical limit to the size of these molecules (and thus the number of qubits). I think this is where the 15 bit limit came from. It is hard to imagine how you can find arbitrarily large organic molecules where each nuclear spin has an appreciably different resonance frequency, and where the atoms are spaced so that they only talk with
There may be some breakthrough with this latest announcement, but it looks to me like a straightforward extension of previous results.
Luckily there are some other approaches to quantum computers that (if they work) should scale up much more easily.
Surprisingly, there are collaborating groups around the world (e.g. Australia) that are in the process of designing building working prototypes of some of these weird and wonderful machines. The problem is that we still don't really have a good grasp of what commercially useful domain will drive the need for mass demand. I suppose it was the same electronically in that early boards were more toys until people mastered the assembly of megagates into useful building blocks. Peole like Pen rose have speculated on physiological process underlying a given thought that may initially involve a number of superposed quantum states. I hope there are some really smart guys out there who can take some of the ideas through to the next stage. Now if someone could come up with decent quantum algorithms for massive parallel search and comparisons of multiple genetic strands databases, they'd make a killing. LL
Alright quantum computing is becoming more and more of a reality, is anyone working on encryption especially public/private key encryption that can withstand quantum factoring?
"Sometimes it's hard to tell the dancer from the dance." --Corwin Of Amber in CoC
Or "factor large positive composite integers as products of prime integers"
^Z
www.timcoleman.com is a total waste of your time. Never go there.
Or perhaps "factor large numbers into primes"?
^Z
www.timcoleman.com is a total waste of your time. Never go there.
...Thinking Machines Corp would still be around, and Danny Hillis wouldn't be wasting his time dicking around with a huge dumb clock.
If Mr. Hillis is the genius you say he is, then perhaps he has a better idea of what might be important in the future than you or I.
Personally I think he realized that there might be more important problems facing Humans than the speed of database queries.
Hotnutz.com - Funny
Try:
http://www.qubit.org
There are some good tutorials there.
Haha--so much for the alleged proofread that I did of my post. As you so adroitly pointed out, it should be "factor large number."
Perhaps you can sell me a deep hole in which to stash my growing embarrassment?
It's more meaningful, therefore, to think of the number of qubits in a quantum computer as its memory size, not its addressing capacity. A 30-qubit quantum computer isn't nearly analagous to a 32-bit von Neumann machine; it's much closer to one with 4 *bytes* of RAM!
I disagree with this statement. If 30 qubits are placed into a coherent superposition, then the number of accessible states is 2^30, (about 1 billion states). This exponentiation of accessible states is part of the charm of quantum computing. To quote an article from the journal Science, A register of say 1500 qubits, if it could be placed in superposition, could access more states than there are particles in the universe. (Peter Knight, Science 2000 January 21; 287: 441-442)
I'll grant, however, that the number quoted is misleading, and hundred-qubit machines will probably be needed to factor extremely large numbers: In order to do quantum error correction (i.e., making sure the bath of states doesn't lose coherence through interactions with the outside world), then each logical qubit would need to be encoded into 5 physical qubits (minimum). In essence, if Moore's Law holds, then you will have to wait another 3 years or so for such a machine.
An advantage quantum computers have over their classical counterparts is that a qubit can be in a superposition between states |1> and |0>. In principle, each qubit can be in an infinity of possible states in between the "pure" |1> and |0> states. Like any quantum mechanical wavefunctions, these qubit states can be made to interfere with each other, which is one of the features of quantum computers that is expoited in quantum algorithms. (Interference is not strictly necessary in a quantum computer calculation, but it is a useful feature of qubits that has no classical counterpart, and it illustrates some of the power of quantum computation). By cleverly packing data into wavefunctions and then interfering wavefunctions with themselves, a quantum computer can perform calculations that would be prohibitive otherwise. As an example, by taking advantage of the quantum mechanical properties of qubits Grover's algorithm allows an unordered database to be searched in O[sqrt(N)] time rather than the O[N] time required by a classical computer.
Well, for what it's worth Alan Kay and the rest of the Smalltalk designers are there, too, and they've always been trying to change the world. Disney seems to be collecting brilliant people and letting them play on Disney's buck, without too much concern for whether they do anything useful. AFAIK, none of them do any real work for the company. (Hillis is what, 'Head Imagineer'? Sounds important ;-)
Rather, it appears to be the move of a man who found that his doctoral work was not wanted by the market.
Geeze, you made him sound kinda pathetic.
I had the 'real' Q-Bert for my C-64... didn't have a Spectrum 48, tho...
"It's tough to be bilingual when you get hit in the head."
I still wish they had never called it a 'law'... though that certainly is more catchy than "Moore's Trend" or "Moore's Guestimate on Human Advancement in Semiconductors"... If it were a law, we wouldn't need the companies to work on things for us, Nature would drop fast new processors on us every 18 months. Kinda like that skittles commercial.....
"It's tough to be bilingual when you get hit in the head."
no it means each register can have n states.
where n is how many quantum states you can distinguish. so this one bit could store 5000 bits of information simultaniusly. one ion of hardware for 16megs of data - yup.
go talk to bill joy.
the future is scary.
there is no guarantee of parity between encryption being easy and decription being hard. there is no guarantee of me not being hit by a bus tomorrow.
there is no guarantee of an asteroid not hitting the earth tomorrow. etc..
worry. sound the alarm. perhaps develop another scheme for security - like a courier. don't panic. it won't solve any problems
Sigh. There is no largest prime number.
Apart from that, I'm imagining your hyper-computer, and I'm seeing something a lot dumber than a centipede.
The halting problem is impossible. It doesn't matter how much computing power you throw at it.
This is totally different from things like factorization, which are merely impractical because they take so darn long. It's these kinds of problems that QC may help solve.
--
Patrick Doyle
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
Maybe there isn't much difference though, at least to the average person, except that Q-Bert is more fun (unless you are a cryptographer).
I understand the idea of using quantum computers to simulate a NFA, and such. But what I don't understand is, how? I mean, how do we encourage the quantum computer to resolve to a solution state?
Does anybody have a link to a good introductory article on quantum computing?
--
Fourth law of programming: Anything that can go wrong wi
There should be no real concern about encryption, except in regard to existing encrypted messages. Quantum computing reduces the number of operations necessary to brute-force crack a public key encrypted message to the square root of the number of operations necessary to brute-force on a standard computer. Doubling the number of bits in the key of a public key encryption squares the number of operations necessary to brute-force crack an encrypted message.
The upshot of this is that even if we get production quality quantum computers, just double the length of your encryption key and you have as much protection as you had before.
I haven't seen anyone mention this explicitly...
If I understand the idea behind qubits, then it should be possible to build a computer that can implement a nondeterministic finite automata. An NFA would permit the solution of a class of problems that are considered NP complete -- they can only be solved in exponential time (prime number factorization being only one application of this). This quantum computer would then be able to solve NP-Complete problems in polynomial time.
Some examples of these types of problems are planning and routing, Operations Research generally, and general search.
Many techniques explored in AI have that NP-completeness characteristic, which AI researchers try hard to control/avoid. Could quantum computing be more important for AI/MI than for anything else? (Once we have enough bits to work with, that is...)
Hmmm......
No, 30 q-bits might be useful. You do not need to store any instructions in the memory, just the numbers you need to keep in a super position, as the instructions are imposed on the computer from the MRI machine, i.e. we would use it like a reprogramable circut, not like a universal turing machine.
If the computer is really good and you do not need any error correction then you could factor a 16 digit number very fast, but more likely you would need serious error correction (might leave you with 4 q-bits if you were lucky; quantum error corrections was pretty expencive as I recall).
The Christian religion has been and still is the principal enemy of moral progress in the world. -- Bertrand Russell
Actually I read an article a while ago that implied there was a very high probability that the molecular ion channels in the axons can have quantum resonances. Proving that any such resonance has an effect on the neruo transmitters would be a huge breakthrough. Who knows, perhaps our brains are already quantum computers.
So the Traveling Salesman is dead?
I found Q-Bert on PC once and was immensely disappointed. I later found its speccy clone and my disappointment continuted.
:(
It is a poor ripoff of the original Speccy game "PI-BALLED". I played this for months on end. Probably the highlight was that I called the frog guy "IRS", but later found out his name was "JAS" and they just used such a pissy small font that it was impossible to tell the difference.
I don't have pi-balled on my spec em tho
30 qubits would not be nearly enough to factor a large number (whether prime or not ;-). Quantum computers store their entire state in the quantum register. This includes not merely data that is currently being operated on (as with traditional computer registers), but also all other state information. The current "instruction" or step is coded in the quantum register, as are all "variables" (including ones that no longer need use; quantum theory prevents us from doing nifty things like "let a = b", which actually makes it harder to reuse register space).
It's more meaningful, therefore, to think of the number of qubits in a quantum computer as its memory size, not its addressing capacity. A 30-qubit quantum computer isn't nearly analagous to a 32-bit von Neumann machine; it's much closer to one with 4 *bytes* of RAM!
In reality, it's been estimated that before we can factor reasonably large numbers, we'll need quantum machines possessing hundreds of bits. Quantum programmers of tomorrow will get their kick out of squeezing as much as possible out of their half-kilobyte of register space.
Random observation: we're seeing e-everything nowadays. Tomorrow will we start seeing q-everything?
http://www.openqubit.org/index.shtml
I thought it was five for birds...
Quantum computer is still way way out there.
even without the problems of quantum error correction and instruction registers, my copy of MATLAB can factor any 30 bit number in between 0.05 and 0.3 seconds (primes took the longest).
also, the poster hanging on my wall suggests that it will take "hundreds+" of qubits to make a quantum factoring engine. somewhat arbitrary, but perhaps as reasonable a guess as anyone on slashdot is likely to make.
cheers,
sh_
Interested in learning Chinese or Japanese? check out Chinese/Japanese-English Dictiona
ha! these are exactly the two sites i have linked off my own homepage
great minds think alike (so, apparently, do ours)
cheers,
sh_
Interested in learning Chinese or Japanese? check out Chinese/Japanese-English Dictiona
That [locking 30 NSA Ph.D.s in a secret room] is not likely to work. Progress on this type of computing is likely to take a lot of new ideas and development to actually reduce to practice. It will take a lot of people, working in parallel on different techniques to see if/how this can be made to work.
/., I'll simply say "think of the scientific process as open-source. Your idea is closed-source."
There are a lot more than 30 Ph.D.-level people working on this problem around the world, most of whom are probably talking to each other in conferences every year, and their progress is relatively slow.
Sure, once a technology is mature (i.e., you actually know it works and how it is done) NSA could put a lab in their basement full of quantum computers. But those 30 hypothetical NSA guys are probably NOT going to get a practical quantum computer working any sooner than the community at large. Furthermore, 30 Ph.D.'s can probably advance NSA's agenda much more efficiently by working on something much more practical.
Since this is
I find it unbelievable that there's already a 7-qubit quantum computer, even if it is NMR. But what would impress me more is if one or two of the existing algorithms for various problems were implemented on it successfully. Obviously it doesn't take much skill to prime factor the numbers between 0 and 127. But it would still be a quite remarkable advance.
On a side note, the only thing quantum encryption and quantum computers have in common is the use of the word "quantum". The similarities between the two are the same as the similarities between electrical engineering and mechanical engineering. Try http://www.qubit.org for basic tutorials on quantum computers, etc.
"Still, quantum computers may never be general-purpose computing devices and are more likely to be targeted at massive number-crunching problems like encryption and decryption, searches of huge databases and simulations of quantum physical states."
Isn't that what they said about the first computers in the 60s? Just a thought.
Yea... I definitly disagree... 1. With faster more efficient description comes faster, more power encription, yes? 2. It's not like these type of computers will hit the market at $1k a piece and every 16 year old will drag their dady to buy one for them just so they can be the next big hacker? By the time the price comes down to affordable consumer levels like it did with current computers, all the important encription will be changed accordingly...
Just a thought.
This is a freaky/cool coincidence... where the subjecyt is quantum computers dilbert: I've invented a quantum computer, capable of interacting with matter from other universes to solve complex equations. Dogbert: According to chaos theory, your tiny cyhange to another universe will shift its destiny, possibly killing every uinhabitant. Dilbert: Shift Happens dogbert: Fire it up
"And how can this be? For he is the
Strong data typing is for those with weak minds.
Strong data typing is for those with weak minds.
Another very important point to remember is that we are talking about the atomic level here, .18 micron is like trying to make a CPU with house wire. It'll be a while before anything useful comes out of it.
Most work in CS will also be in setting up problems, all the time of a program will be organizing data to be processed, since the processing will be close to instant, at least in theory.
Someone else asked about Solution States, well as I said above, you run a solver on here and you get every solution at once. Pretty fun stuff.
Hope this helps.
If large QCs ever become operational, then our current computer cryptosystems will need to be scrapped immediately. You don't outdo a QC, you have to change the rules instead.
For example, neither digital or quantum computer algorithms can break a private code. If your group creates a codebook where "The moon is in the 7th house" actually means "Let's order pepperoni for dinner", and so on with random phrases, then all the quantum power in town won't figure it out. That sort of thing requires actual human beings to break.
Of course, codebooks won't work for e-commerce and secure internet connections... The only way to protect that stuff would be to switch to quantum crypto (a different technology altogether).
Quantum computers, sort of?. Is there any articles on this? One interesting thing...
Some people have tried to argue that the human brain is strictly more powerful than Turing machines by using Godel's incompleteness theorem and derivatives (e.g. Roger Penrose). i.e. AI will not accomplish what we can do, if we do it on computers in its present form.
Is there any light on this issue with quantum computers? Is it "strictly more powerful" than Turing machine, or is it just a faster and smaller (no matter how faster and smaller) version of what we already have now?
I don't think you and the person you quote necessarily mean the same thing when you say "today's fastest computers". If I understand the implications of the technology correctly, quantum computing has the potential (in five years) to be three times as fast as any computer currently on the planet. While personal computers will be eight times as fast five years from now as they are today, they won't be eight times as fast as the current high end supercomputers.
value:
On the off chance that this isn't a troll, here's a short list of reasons why this technology won't lead to a new dark ages at least not by itself.
AlphabetSoup agencies and other power groups will find new ways to keep secrets, and there will always be a rough balance between what can/can't be protected.
Govt.'s secret and open have way more resources than individuals. Order will be maintained.
who gets these things first?
humanity will adapt, transparency is good.
I've been hearing stories on how quantum computers will do this and do that and all.. Being a curious person (and having not taken my advanced physics lessons yet) I'd like to get some kind of background information .. popularization, if you like. Any pointers to sites with good information?
Today's cryptography is based on the theory that factoring large numbers is so slow, that the information in the message would be redundant by the time decrypting it would be complete.
What to do next is to find what Quantum Computers are not so good at. I understood the main advantage of Quantum technology was its ability to perform parallel calculations. How could we outdo that advantage? Suggestions?
There's some very intelligent people on the loose out there.
One of them will probably come up with a quantum-safe crypo when they get their hands on a couple of quantum-computers.
/.Mattsson - My native language is not English, so please don't whine over linguistic errors. (That's lame anyway...)
Basically, think of it this way. Rather than having two states available for computers to work with (on/off or 1/0) you can parallize groups of atoms (or better yet ions) together so that you have simultaneous 1/0 combinations (corresponding to each spin state +0.5/-0.5 or up/down) providing faster computational capabilities.
I doubt the NSA has the scientific prowess to build a quantum computer ahead of the mainstream scientific community. However, think of this likely scenario:
Quantum computers turn out to be extremely expensive. There may be only a few on the planet. Whoever holds these can unlock any encryption. Since, no one else can, this gives the holders of
the quantum computer incredible powers. The NSA would almost certainly have it. It's hard for anyone else to make, since it involves quite a bit of scientific knowledge, and certainly some specialized and expensive equipment.
The conclusion is unmistakable. The quantum computer is the new atom bomb.
As Niels Bohr (one of the fathers of quantum mechanics) said: "anyone who can contemplate quantum mechanics without getting dizzy has not understood it". The points made about today's most advanced cryptographic techniques being useless in the quantum computer era are well founded. An effective quantum computer will make today's super-computers look like a broken abacus. It has been argued that the current laws of mathematics may forbid the timely factoring of huge numbers. The only solution is the brute force attack and the use of quantum computers. While Bell Labs have described how this might be done the equipment needed is not yet available but when it is it may be possible to factor numbers so super huge (greater than the number of atoms in the known universe) in days, maybe hours and eventually minutes or seconds. For an vision of quantum computing see David Deutsch's 1985 paper (Poss Oxford Achive). Thankfully quantum cryptography already exists thanks to the original ideas and experiments (1799) of Thomas Young at Cambridge, England, into the theory of light. Further work was done by Stephen Weisner, a graduate student at the University of Columbia but he was so far ahead of his time that no-one appreciated the implications of his paper. Fourteen years later Bennett and Brassard excited the cryptographic community with the potential of 'absolutely secure cryptography'. In 1988 Bennett witnessed the first (publically announced) quantum cryptographic exchange over a distance of 30cm. In 1995 the University of Geneva achieved 23Km using optical fibre. Although there are still arguments between quantum theorists about the explanation of the quantum effect of light Superposition of States exists for photons (and other sub-atomic particles) and can be measured. See Erwin Schroedinger's (Nobel Prize for Physics 1933) 'Schroedinger's Cat' explanation of superposition. I can't see Joe Public having access to 'Pretty Good Quantum Privacy' (PGQP) any time soon!
And who says we won't find encryptions that the gov't can't break? ;-]
Like most technology, the military/gov't might try to keep such technology for themselves, sooner or later the public sector will either get ahold of it by leak, by accident, or by re-inventing the same thing (especially if they already know it exists...)
TangoChaz
"It's not enough to be on the right track -- you have to be moving faster than the train." -- Rod Davis, Editor of Seahorse Mag.
TangoChaz
--------------------
Wise men talk because they have something to say, fools because the
i read the other article, and had the same question... i have read a little on quantum theory, but cant say i know anything about it. and yes, we have all heard of schroedinger's cat, which is neither dead nor alive, but both simultaneously.
but how, if we cant tell which state something is in, can we use that to manipulate information? its not like you can set the bit to on or off, instead you have all this randomness per bit that you cant control or even really measure.
.sigs are dumb!
Correct me if I am wrong here.
:-)
The NSA has a large number of mathematicians and other type hardcore science people working for them.
This is their forte and what they are mainly compromised of.
They can focus these resources very easily.
Example:I want 30 of you guys with Ph.D's in maths go in this room. You cannot come out until you have figured out how to do xyz. We will slide pizza under the door.
Tell me how the public scientific community can compete with something like that?
NSA has untold amounts of money and who knows what the hell they are really doing. They have their own FAB.
Anyone who reads slashdot regularly knows all this stuff tho. My point is they have immeasuable scientific prowess since no one is 'really' sure.
Jeremy
Thanks, That makes more sense than my comment :-)
ja
You're probably thinking of Q-Bert.
What the hell does that mean? You quote Einstein and think you've made some kind of point..
Sure, but the worst case analysis isn't orders of magnitude greater than for a digital machine. From what I understand, the only real gains are for cryptography (anyone performing an experiment -- ie, trying to read your data -- would corrupt it due to quantum entanglement); and in solving the Traveling Salesman way faster since you can bust out factorial mathematical keys very fast (also related to encryption). Searching would be almost instant (if you count the data's load time as a scalar) since you could load all the possible values into quantum states (eigenvalues) and perform a single experiment -- sorting, I believe, would still be difficult (perhaps more difficult due to corruption?). The good news: quantum entanglement allows for fast-as-light calculations (some of those O(n)+b problems shrink to O(1)). I guess you'd really have to ask yourself: How are dictionary operations changed? How do these changes affect fundamental data types? And how do we make these data types work within our algorithms? I think it'll most likely depend on who gets what to function -- people are using trapped ions, liquids, and Univ. of Oregon is trying to use light. Depending on how the properties of each work, we'll get different upper bounds on different operations. Disclaimer: I'm not a physicist, I'm a computer scientist.
"Thank you. Please spellcheck your genitalia references though.
OUCH! My brain is melting...
"Never teach a cat to say 'Tuna,' its all he'll ever want to talk about!" - BEAR
All the discussions about quantum computers seem to center around Shor's algorithm and other esoteric methods for doing things most people aren't interested in doing. Are there any algorithms for doing tasks that are actually common on desktop computers and of interest to average users?
Now imagine what that computer could do. Could decode genomes, could crack codes, could find the largest prime number, could discover the smallest form of measurement, could map out the entire universe, or could even cure the most deadly diseases.
There's the practical uses. Now let's look at the quantum theory. Remember the "Time travel theory". Recently reading the book Timeline by Michael Crichton I was introduced more indepth into the thereom itself. It deals wiuth the fact that time doesn't exist, but an infinite number of realities or instances exist. Thus not making timetravel possible, but dimension jumps possible. Thus making reality no longer defined, but confused.
So now what do we consider. Who's hands this technology will get into. This would be the ultimate code breaker along with the ultimate weapon. Imagine one person being able to change all of history or to be able to get into any computer they want to. The world itself would become a non-existant entity.
Ignore the "p2p is theft" trolls, they're just uninformed
The number of qubits will double and the cost will halve every fifteen minutes.
Good god, I just read an article (Wired?) that was raving that they managed to entangle 4-qubit systems.
Welcome to the new reality.
blog |
Federal researchers say they've created the most robust quantum computer ever...
And so the article goes. And so goes this discussion, focused primarily on how it works and what it could do.
Does anyone know of a quantum computer actually computing anything, be it problem-solving or adding two integers?
You just take one quantum computer, shift it into 50 different quantum states simultaniously, and voila! you have a one-machine Beowulf cluster!
I hereby release this sig to Public Domain
Since computer scientists, like birds and cavemen, only count up to three (whoops, I mean "many"), this means that quantum computing has really definitively entered the realm of "many." Pulling this off is pretty huge, not just because it brings practical quanutm computers that much closer. It's also a pretty impressive achievement in experimental physics and engineering to get that kind of precise control over individual quantum systems.
Neo did so say "ther is no spoon" there at the endf when he's tie-ing that rope thinging to his waist so trinity can get out of the helicopter. I think.
If Mr. Edison had thought smarter he wouldn't sweat as much. --Nikola Tesla
"If the trend of increasing performance continues, a quantum computer that triples today's fastest computers could be built in five years [...]"
Reality:
If the trend of increasing performance continues according to Moore's law, a personal computer that octuples today's fastest computers could be built in five years.
--
Have fun: Join D.N.A. (National Dyslexics Association)
The increase in factoring speed POTENTIALLY (it has not yet been done) gained by employing quantum factoring is easily compensated for by using larger keyspaces. There is a great deal of writing on this subject available, including some very clear articles by Shamir.
My simplistic understanding is that instead of using a transistor to store bits they use certain quantum attributes of atomic particles to store bits of info. One advantage would be that they are very small.
Damn, What a big step, i wanna see one of these things in action. I would really like to see cracking some DES on this baby. By the way, what is a qubit? lol
How much faster? Well if conventional techniques need 2^64 operations to factor something, QC needs 2^32 to do the same thing. Therefore, to regain the same level of security you would have to double the length of the keys you use. This isn't particularly difficult (encryption and decryption would run more than twice as slowly, but Moore's law soon sorts that out.)
NO NEW SCHEMES ARE REQUIRED! (well mostly...)
If you want to know more, do a google search, there's a large range of articles on it.
-WolfWithoutAClause
"Gravity is only a theory, not a fact!"Hi,
Could you post a reference to the L^3 Knapsack problem.
I'm interested in the general NP space (:)), because of machine learning problems are generally in here. My reading of the QC stuff is that it is generally over-hyped.
They can't solve SAT can they, and worse, supervised machine learning is 2^2^n...
Cheers,
Winton
I have to disagree. History has proven over and over that whenever a new technology comes out, it benefits both criminals AND the ones fighting it. An optimist like myself would argue the possibilites quantum computers could bring to better store, access, and safe guard important information.
---------------
---------------
JavaScript tutorials scripts
obviously software would have to been rewritten for these types of computers, but would all hardware change or would just the main boards (cpu, motherboard, etc..) change? would these sorts of machines be backwards compatible or not?
No wireless. Less space than a nomad. Lame. - Initial
I'm not sure why it's useful to have a q-bit to be a 0 and 1 at the same time. Does that simply mean there are three state for each register, 0, 1 and 1-0?
I wouldn't get too worried - it doesn't appear that the current research of is any use but for testing theories.
You should read up on Quantum Cryptography - there are numerous theoretical discussions of crypto models based on quantum computing technology that would be much more advanced than the standard crypto models we currently use.
I once read what I thought was an excellent explanation of the Quantum Processing theory, I'll try to reproduce it here.
- -----------------|
- -LO--------------|
Imagine an office building in which there is a single briefcase in one of the offices. It is not known which one.
In order to find the briefcase you would have to search room by room until it was found.
This is the way that modern computer systems work.
Now imagine if you were to temporarily produce clones of yourself whose count match the exact number of rooms in the building. Each of them could stand outside a room and all of them enter their room simultaneously. Then cause all of the clones that did not find the briefcase to disappear leaving only the clone with the find.
This is how I understand Quantum Computer to work.
The quantum states of n qubits are combined to produce 2^n unique simultaneous results. Then only the result that is correct is caused to remain.
Now for a Practical Application besides code breaking.
What about a memory system? If it was a 64 qubit system the following could take place:
Determine the address of the memory location by masking out the high order (HO) double word (dw)of the system, thereby determining the address in the low order (LO) dw, and mask out the LO dw to retrieve the instruction or data in the HO dw stored at that address.
Pardon my ascii art.
|-------------------------------64-------------
|---------------HO---------------||------------
|-------Instruction / Data---------||------------Address-----------|
If my understanding of the qubit system is correct then the only limit on the amount of memory in the system would be the address bus of the CPU. There would be no need for an array of memory cells ('chips') a single qubit register would provide all of the memory locations needed.
This assumes that the CPU processes 32 bit data and uses 32 bit addresses.
Turing's Halting Problem comes to mind. And fun stuff too:
NO TOUCH MONKEY!
And, of course it runs NetBSD
The Wired article refers to the Los Alamos group on quantum computation.
Raymond Laflamme's home page (his name is mentioned in article)
http://qso.lanl.gov/~laf/
Quantum Crypto & Computation at Los Alamos
http://qso.lanl.gov/qc/
The 7-qubit computation does not seem to be mentioned yet on the experiments page, but odds are it will be up soon.
A very essential point is being left out in all this quantum computing- that the BASIC Theory of mechanics is considred shaky by some very prominent thinkers. Quantum Comptuing is based on the current theory of quantum mechanics. If you have no foundation your house will fall. "God does not play dice with the Universe" Einstien
For a small fee, I will gladly factor any large prime number you give me, assuming of course that you can assure me that it truly is prime.
----------------------------
Quantum effects are the very phenomenon that stand the greatest chance of STOPPING Moore's Law in its tracks - and yet it is these same effects quantum computers use to do their work. Which means two things: eventually conventional computing must hit a quantum wall, and on the other side of that wall, quantum computing takes over.
That said, I still have some doubts about quantum technology - it sounds to me too much like nondeterminism, and I can't help but wonder where you're going to find people who understand it well enough to develop the technology without doing it "by cookbook" as many COBOL programmers do today. But the technology is there, it seems to work, so what the hey.
~ radiographite: art by john shepard
There are a lot of problems where it is much easier to verify an answer than it is to figure out what the answer should be. For instance if I ask you to factor 221, you may have some trouble. If I tell you that 13 is a factor of 221, it is easy for you to test that.
Well the basic idea of quantum computing applied to factoring would be to set up an experiment that is like trying to divide 221 by every possible number at once. But the trick is that instead of coming back with "yes/no" you would try to cause the no answers to cancel themselves out, so that what an experimenter would see would almost certainly be something that came back with a yes.
Of course this is easier said than done...
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
If quantum computers are available to the code-breakers, that means that they are also available to the code-makers
Yes but it's not very egalitarian anymore, is it? The people you're hiding your message from can afford the quantum computers, but not those just wanting to send encrypted email.
I've finally had it: until slashdot gets article moderation, I am not coming back.
The only problem i have with the second sentance is moore's law - current technology will have doubled in speed twice and be well on it's way to doubling again by the time he triples it, so, why bother if you're just gonna be playing catch up?
This is just like television, only you can see much further.
Second sentence:
if the trend of increasing performance continues, a quantum computer that triples today's fastest computers could be built in five years, according to physicist Raymond Laflamme
Last sentence:
"On my optimistic days I think we will have quantum computers in 20, 30, 40 years maybe," he said. "On my pessimistic days, I think quantum computing is crazy."
Still, it's cool. Personally, I think that ten years is the most likely timeframe, but that the uneducated guess of an uninformed amateur.
The Wired article talks about using a spectromotor is this just a dumb typo for spectrometer and if not what is a spectromotor?
You can try this link http://www.imsa.edu/~matth/cs299/. This is introductory stuff - which equates to 'nearly incomprehensible' for us normal humans. I think I've made it through 3 sections.
You never really know how close to the edge you can go until you fall off.
Can anybody provide a link to an intermediate level description of what exactly a quantum computer does? I'm unclear about how they use this mysterious tube of liquid, and large magnets to perform the three basic steps of computing (input, proccessing, output). I'm interrested in how they feed information into the system, how they perform operations (either simple [i would say atomic, but that has a double meaning] operations like addition, division, etc..., or whatever the fundimental operations that they _can_ perform are...), and how they read/verify the results.
---
Play Six Pack Man. I
The path of advancement in computer hardware has been so simple that it can be stated in one sentence -- Add more of the same.
Even the most advanced silicon coming out of Intel, et al., are nothing but very advanced adders. Once you have the basic adder, the rest is a problem in manufacturing and packaging (how can we make it smaller, and then how do we keep it cool, supply power, etc)
I predict (with all the authority I can muster) that quantum computers will follow the same path, only faster (since we've already solved many of the problems before). Once the scientist are able to manipulate a few bits, it will be a very fast progression to manipulating a lot of bits. It's just a matter of doing the same. Of course, they have to move out of the realm of "moving pins with bulldozers" first 8*)
Aah, change is good. -- Rafiki
Yeah, but it ain't easy. -- Simba
Possibly true, but his day job is at Disney. Hard to see that working for Disney offers much opportunity to change the world. Rather, it appears to be the move of a man who found that his doctoral work was not wanted by the market. The "Long Now Foundation" and it's big clock is an interesting experiment in pyramid building, but the learn a little about the history of the pyramids to see just how pointless it is trying to build anything less rugged than a huge stone pile.
"How perfectly Goddamn delightful it all is, to be sure" Charles Crumb
as i (poorly) understand it a quantum bit can store far more data than a regular bit. if we ever start building gates based on quantum physics we should be able to send many signals through the same gate, at the same time, without interfering with each other. ie. a full adder should be able to execute 1, or 2^16 add operations at the same time. the ultimate in parallel processing.
a full blown pentium, could run linux, windows, be, and bsd simultaniusly with no sharing. each operating system executing on it's own quantum level, with access to the full functionality of the machine.
a looong way of, but very very cool.
Hmmm....database queries are among the easiest sorts of algorithms to parallelize. In fact, I had the pleasure of working on a parallel database supercomputer built by NCR in the early nineties. If you've got 256 nodes, for example, you can come pretty close to finding a key 256 times as fast as on a single node. (There is a lot of overhead, of course, but it was per node, note per record.)
This was a pretty cool machine, built entirely out of 486 and pentium boards with standard hard drives, all running ATT Unix. Cool stuff. Not quite "massively parallel", though, in that I think it only went up to something like 128 or 256 nodes.
It was really cool to work on. It was fun being able to create a 100 gigibyte table. (Though it is getting less and less cool. Bear in mind that at the time I only had a 100 mb drive on my PC.)
The cake is a pie
Huh? I thought if you "solved" one problem in NP-Complete, you automatically solved them all.
("Solving" meaning creating an algorithm that runs in polynomial time instead of exponential time)
--
The shareholder is always right.
A quantum bit (qubit) can still only store one piece of information... a bit. A regular bit can either be 1 or 0.
The thing about a qubit is that it is both 1 and 0, simultaneously. This is called superposition of states-- the qubit exists in all possible states at the same time. If you have a system of 4 qubits, with each bit having 2 superimposed states, then you get 16 possible states at the same time.
It gets a bit more complicated with quantum logic gates though... but here's one possible application: decryption.
Today, you have to brute force a key, one at a time, until you find a winner.
Theoretically, a quantum computer could test ALL POSSIBLE KEYS in one fell swoop, and blammo, the correct one pops right out.
I'm simplifying this to a sickening excess, but you get the point.
I believe the first real application of quantum logic gates will be in the upcoming Bit Boys' Glaze3D video chip, which is due to be released 6 months from any given date. (/sarcasm)
-CausticPuppy "Of all the people I know, you're certainly one of them." -Somebody I don't know
You can always search for "quantum computing" in a search engine, but here ya go.
Quantum Computing - Lov Grover
If you want a good book on quantum mechanics but you're not a real physicist, try The Dancing Wu-Li Masters, by somebody whose name I forget. Search for it on Amazon, read the reviews, and then (of course) buy it elsewhere.
-CausticPuppy "Of all the people I know, you're certainly one of them." -Somebody I don't know
Now step back and think about who has the most to gain from them. Furthermore, the NSA has generally led civilian scientists by a couple decades in cryptography work.
It makes me wonder how far along they are with this type of computer.
Best regards,
SEAL
Actually, brute-force decryption that scales linearly, rather than exponentially, is exactly what quantum computers promise to do that conventional computers can't.
Many other posters have provided better links and explanations than I could.
"You can't get something for nothing." - my grandfather, on the stock market and Reaganomics.
That's generally true, baring details about semantics and Karp reductions, but nobody has ever shown that factoring or the RSA problem is in NP-Complete! If somebody could demonstrate this, it would be quite a breakthrough in our understanding of the computational complexity of this problem and others related to the RSAP, like the DLP.
Actually, QC will make factoring large composites much easier than by a mere square root. Decomposition of large composites into primes can be done in NP-time; a QC will enable us to factor these composites in strictly polynomial time, whereas the best current factoring algorithms (NFS for general numbers, ECM for many medium sized factors) take subexponential time. The square root reduction applies to *conventional* symmetric encryption algorithms in the case of a brute force attack.
Knapsack PKC=based on knowing which subset of values in a given set will sum exactly to a certain fixed value (the size of the knapsack)
L^3 algorithm=Lenstra-Lenstra-Lovasz Lattice reduction algorithm; guaranteed to find a basis for a lattice with elements of length not more than a certain [theoretically exponential, but in practice only superpolynomial] length longer than the shortest basis for such a lattice. Used for reducing the lattice formed when inverting many knapsack PKC into a more easily handled size.
Check out these sites for more info on quantum computing
Qubit.org
Quantum computing and information at IBM
If quantum computers are available to the code-breakers, that means that they are also available to the code-makers. From an application-level standpoint, there's nothing to distinguish a quantum computer from an electronic one except for speed -- the quantum computer would be able to execute the same tasks several orders of magnitude faster. While key lengths of 128 (2^7) bits are secure today, in a world with quantum computers you would need key lengths of (for example) 16K bits (2^14) to get an equivilent level of security. It's not practical to use 16Kbit encryption TODAY, because it would take too long to encrypt somthing to that level; however, with a quantum computer kilobit-length encryption keys become as feasable as 128 bit keys are today. IIRC, encryption speed scales linearly with key length while (brute force) decryption speed scales exponentially; this means that it will always be far more difficult to break a given key length than it is to encrypt that same key. Advances in technology help both sides of the equasion.
"The axiom 'An honest man has nothing to fear from the police'
Why is it that the proponents of "one nation under God" are so eager to get rid of "liberty and justice for all"?
See www.qubit.org for some interesting introductory articles.
This is very interesting - yet another new scientific frontier to explore. Yet, as always, we must be cautious here - new frontiers bring new dangers. And the danger here is very readily apparent.
Right now, the world depends on good, strong cryptography. It's how banks, militaries, stock exchanges, and governments communicate securely and reliably. If the cryptography safeguarding these communications were to disappear overnight, what would we have? Global anarchy, as anyone could draw whatever funds they wanted from banks, military units could be given bogus orders, and any communication not done in person would be impossible to authenticate. Not a pretty situation, right?
Yet this is exactly the set of circumstances that the quantum computer would bring upon us! It's well known that these computers are much faster at factoring large numbers (the basis of all modern cryptography) than conventional computers, and would render our current encryption schemes absolutely worthless. I don't believe that this is something we can allow to happen, at least not until we've taken the time - most likely several decades - to reform our society to the point where we can accept this. Research into this area must be halted immediately.
And if you disagree with me, just think about the alternative.
As part of my master thesis, I've developed a programming language for quantum computers. While the interpreter is still somewhat experimental, it works under Linux and the best part of it: it's Open Source (GPL). So if you want to play around with quantum algorithms and can't afford the real hardware, you might want to give it a try.
Reading about this, I can't help thinking about the brilliant and doomed Connection Machine. It was a hypercube of ~65000 processors engineered by Danny Hillis, a genius engineer in the same class as Cray.
But they never sold well enough, not because of the cost, but because there were few programmers who could imagine how to break a problem down so it could be run efficiently on all these processors. Other than real-time ray-tracing and weather simulations (astonishing particle systems) people couldn't figure it out.
If someone had managed to figure out how to perform a database queries efficiently with this type of massively parallel machine, they would have sold like very expensive hotcakes, Thinking Machines Corp would still be around, and Danny Hillis wouldn't be wasting his time dicking around with a huge dumb clock.
Given that we didn't know what to do with a machine that could deliver ~65,000 answers at once, what do we expect to do with one that can deliver all possible answers at once?
"How perfectly Goddamn delightful it all is, to be sure" Charles Crumb
It runs all possible operating systems simultaneously.
-CausticPuppy "Of all the people I know, you're certainly one of them." -Somebody I don't know
And before anyone gets to it....
I guess a Beowulf cluster of these things is/is not possible!!!
Strong data typing is for those with weak minds.
Strong data typing is for those with weak minds.
Actually trans-crotonic acid (with 4 carbon 13 isotopes) is the quantum computer. It has 7 magnetically nonequivalent nuclei that have spin -/+ 1/2 and interact strongly. When you selectively flip the spin of one nucleus, it affects the neighbouring nuclei through coupling.
CH3-CH=CH-CO2H
the three H's in the CH3 are equivalent and are considered collectively as a bit. the two H's on the double bond are two more bits and all of the carbons are bits.
I think the max limit of 15 relates to the fact that coupling typically only works across 4 bonds max and thus nobody has yet been able to think of a molecule with more than 15 magnetically distinct atoms that are all within 4 bonds of each other. Its a neat puzzle to try and think of one of these, symmetry keeps fusking things up making atoms magnetically equivalent.
no sig.
(This is a lot of handwaving on my part, and corrections are welcomed!)
You can read some more information about the work of the Los Alamos scientists at http://www.lanl.gov/w orldview/news/releases/archive/00-041.html. Curiously, Moore's Law seems to hold for quantum computers as well, since it was nearly 18 months since the same researchers intoduced the first 3 qubit quantum computer (using nuclear magnetic resonance and a trichloroethylene molecule). To quote the article: Of course, if Moore's Law is at work here," Laflamme added, "then we could have a 30-qubit quantum computer in less than five years." A 30 qubit machine could perform certain tasks (such as Shor's algorithm or a variant for factoring large primes) many times faster than even the most powerful present-day supercomputers.
The following is a short summary of the effect that quantum computing will have on cryptography by type of cryptographic primitive, as is currently accepted by a consensus of cryptographers:
public key cryptosystems based on factoring or extracting discrete logs over a prime field- practical quantum computing will make these systems essentially useless, since the sender of the messages will have no inherent computational advantage over the attacker
public key cryptosystems based on discrete logs over eliptic curve- not much research has been done in this area, but it is not immediately apparent that quantum computing will nesessarily create a trivial break of this problem
public key cryptosystems based on knapsack problem- pretty much obselete already thanks to the L^3 lattice reduction algorithm; not much to worry about
public key cryptosystems based on calculations in a truncated polynomial ring modulo different small primes (ie. NTRU)- probably not much to worry about, as there is no apparent reduction from factoring to converting between different ring representations of a polynomial (the main attack is via the L^3 algorithm)
symmetric algorithms- square root reduction in brute force time
hash functions- theoretical square root reduction in time to find collisions; it isn't clear how to achieve this, though
general NP problems - surprisingly, recent results show that quantum computers may not be able to solve general problems in the space NP-Hard. Search on xxx.lanl.gov for a preprints about the (surprising relative lackof) Hamiltonian nonlinearity properties in quantum wave functions.
A qubit, as the article says, is a quantum bit. All this means is that there is some quantum system/subsystem where some quality, like spin or energy, can be decomposed into precisely to two states. An ananology would Fourier's theorem: Broadly speaking, it says that you can decompose any "nice" function into an infinite sum of sines and cosines. The quantum world is cool because often, just two basis functions, up and down, are needed to completely (a pun, for you math people) describe a space in which that numerical quality resides.
Such is the case here. The scientists, if I am not mistaken, are manipulating spin. Spin is a fundamental quantity in "classical" quantum mechanics; the spin quality of spin 1/2 particles, like electrons, can be wrestled out of special relativity (first finagled by Dirac); arbitrary spin falls out of special relativity + quantum field theory (if you know group theory, it's pretty simple :-).
Now, I think this experiment uses spin 1/2 particles, i.e. particles whose total "intrinsic angular momentum" is equal to h/(4*pi), where h is Planck's constant. The cool thing about spin 1/2 particles is that their space is completely described by two components, up and down. This is because h/(2*pi) is the smallest angular momentum quantum you can have, so in order for the possible states to be "legal," the differences between any pair of them must be a multiple of h/(2*pi). But since spin 1/2 particles have a total spin of h/(4*pi), the only possible states are -h/(4*pi) and +h/(4*pi).
So what's the deal with NMR? Well, NMR is nothing more than a method for manipulating/measuring spins/magnetic states using electromagnetic radiation. So, if the molecules in question are placed in a magnetic field, then there will be an energy difference between the up, down, and "mixed" states contingent on the alignment of spins w.r.t. to the direction of the magnetic field. This is as if it were possible for a compass to get stuck in the "south" position -- there's some potential energy caught up in there. In the quantum world, one can shoot a photon a system in the "north," or up, state and have it jump to "south," or down, or high-energy state. The simple requirements for the photon: It must have an energy equal to the difference in energy of the two states; and, it must carry the appropriate amount of angular momentum, important for more complex situations. So, these scientists have been able to manipulate bits by shooting radio waves at'em.
So why are 7-qubit systems important? Because, in addition to the "external" or ambient magnetic field, each little particle that has a magnetic moment also generates a magnetic field. Having a "strongly interacting" multi-qubit system gives you a much more reliable bit, because when some flip due to a photon, the stragglers are more likely to flip as well. This will help avoid the dreaded mixed states that can screw with your data in untraceable ways. As noted by Wineland of NIST, this cute strategy has sharply diminishing returns past 15.
The "trans-crotonic" acid is probably just some acid which is transparent to the NMR frequencies they're working at, and is nice all around for refractions, etc.
There is a simple, but informative page at UCSD that has pretty pictures showing what I've been blabbering about ...
I hope I've been helpful w/o being condescending!
*** Proven iconoclast, aspiring epicurean ***