Slashdot Mirror
Creeping Toward 10 Qbits: Atomic Computing
RetroGeek points to this "New York Times article about a computer using atoms as switches. Give me twenty atoms and I'll break the RC5 contest." Going from 7 atoms to 10 is the order of the year, and if this keeps up maybe soon we'll need some slightly longer encryption keys, thanks.
Belongs to the #$%&%^# NY Times that requires an atomic (sic.) password to log in. Only if atom is used in the Greek fashion.
I had too many atomic quantitities of C2H4Oh so do not blast me as a troll
Later
Frankly, it all depends.
How exactly do these quantum computers work? Are there wires involved? What about the processors? Are there transistors, etc... I am hopelessly uninformed, yet facinated.
virtual valery needs more AI , just imagine the possibilities ;)
--- Metamoderating abusive downgraders since my 300th post.
After years of being behind, it looks like this might be the equalizer in the neverending battle between those who write and those who break crypto. Now all we need to know is how many atoms need to be manipulated so that users won't put their passphrase on a Post-It(TM) note and stick it to their computer screen.
[Insert the usual disclaimer here]
Not only does the incredible computational power of quantum computing render current encryption keys useless, but it also will provide enough computing power to run windows 2000.
Someone you trust is one of us.
something i'm really looking forward to isn't the tiny tiny computers which will be possible with QC. it's the normal-sized computers which are, in actually, thousands of quantum processors working like mad in parallel. massively parallel systems making supercomputers possible in our toasters.
i'm gettin wet. i should go.
-- build a man a fire and he'll be warm all day. set a man on fire and he'll be warm for the rest of his life.
The powerful field is emanating from the supercooled superconducting magnets inside a tanklike machine called a nuclear magnetic resonance spectrometer.
;)
Might wanna warn Gordon about the possibility of a resonance cascade.
The One,
The Only,
--The Kid
the liberator who destroyed my property has realigned my perception
www.quantumheresy.com
I'm sure the Czech crew who released the PGP advisory this week would love the same kind of computing. (more historical codebreaking)
Seems entirely over my head (the level of computing obviously) but here would be some nice uses for this level of computing.
I wonder how old I'll be before a computer like this is something like what a c64 is in nowadays. Just think scientists where developing this starting in 1994 (from what I saw on NYTimes), imagine when the level of computing in 20 years, or would it all come crashing down. Scary thought. Anyone care to reply with links to basic quantum computing information you care to share?
Privacy Links
360 degrees of Karma
Yes, but will it provide enough power to factor large prime numbers...
According to this law, they will only have to get one more atom to dance every 18 months...
:)
Also, will the software industry be able to keep pace, writing bloated code to run on these things?
-Scott
So if I've understood the article correctly (possibly not, since it's 6am and I've been up all night), your QBIT (quantum bit) can be in 1 of 3 states:
1) up
2) down
3) dead kitten AND live kitten (superposition)
Does this mean that we'll use a new, post-boolean algebra on trinary computers, or will we be running a binary system which gets internally compiled down into operations involving QBITS?
Maybe the third state will be soaked up by the error correction mentioned in the article...
I actually think it would be cooler to have a binary computer, but the third state really did represent an unknown and mysterious simultaneously true and false state...
dim x as boolean
x=MyComplexMethod("goat",45,"all your base")
if x=true then
print "Yes- true"
else
if x=false then
print "No- false"
else
print "WTF is up with this?"
endif
endif
360 degrees of Karma
Introductory articles on quantum computation>
read on... quantum crypto
360 degrees of Karma
I don't mean to rain on anyone's parade. I really don't. Its just I think we may be getting a LITTLE ahead of ourselves, here. Contrary to a lot of posts on /., Quantum Computing is not so much a issue of EE as it is of good, old-fashioned AMO Physics - lasers (BIG lasers), nonlinear optics, RF Ion Traps and more lasers. This is not your granddad's transistor (which, even in its original form, probably could be safely operated at Johny and Susie's house in Peoria). From my experience as a research assistant in a quantum computing laboratory at a big academic institution, trapped-ion quantum computing is not the type of thing that'll be running your palm pilot 10, 30 or even 50 years down the road - the (absolutely crucial) electronics of the trap, alone, would make it insanely dangerous to have in your home, let alone your pocket (ions will still require the same EM containment fields 1,000 years down the road as they do now - its what makes 'em ions).
And no one has EVER gotten an Ion-Trap quantum computer to do ANYTHING. Not add two numbers. Not factor a number. Not multiply two numbers. The potential is there - the qubits - its just no one has ever tapped it in a feasible way.
I'm sure people said the same things about transistor based computer back in the day, but I really, really feel that the Ion Trapping method is not going to be the type of QC we'll see in practical use anytime down the road.
Just when we we getting worried about Moore's law failing, here comes someone getting ready to take the acceleration curve and golf it into warp drive.
Damn!
"It is a greater offense to steal men's labor, than their clothes"
The atom itself is not the qbit. The qbit is the quantum state of a 2P electron which makes transitions back and forth between a 1s state. The atom merely holds this electron (and only ONE such electron, per the exclusion principle.)
Ok, that's an overly inflammatory subject header. However, I once had a chat with a friend and we tried to work out what practical effect it would have on the world if you could solve NP problems reliably in polynomial time. I'm sure a lot of things would become slightly better, but neither of us could think of any revolutionary new applications that would become possible that weren't previously possible.
Remember that a lot of the problems that are in NP can be approximated pretty well. If you were actually routing travelling salesmen around the US, you might not mind a solution that's off by a few percent (particularly when there are going to be a whole pile of other sources of error; your salesmen getting stuck in traffic jams or dallying with housewives, etc.).
Can anyone offer some problem domains where quantum computing would offer more than an incremental improvement (discounting crypto, which seems to be a case of gain a little, lose a little)? I'm not claiming that such domains don't exist, btw. I'd be delighted if someone could point out a few.
Here is an article from Scientific American giving a good overview of the basics of quantum computing.
It's a bit dated (from 1998) but the principles are the same.
wouldn't be able to keep up with writing bloated code....unless they come up with a quantum computer to write the code for them....
"The good thing about Alzheimer's is that you can hide your own Easter eggs."
"People should be allowed to keep midgets as pets."
- Gov. Jesse Ventura
For more info on P vs. NP, see the classic Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson.
Note, by the way, that quantum computers are not generally thought able to solve NP-hard problems in P-time. They can solve in P-time a class of problems called QBP, which is believed to sit between P and NP in difficulty. Quantum computing suddenly got a lot of press when Peter Shor discovered that factoring is in QBP. However, factoring is probably not NP-hard.
Wasn't it bruce sterling who talked about a kind of organic based computer?
This will get really interesting when we have computing at a molecular level, but we can grow huge clusters of them like fruit or vines. Now that'll rock. Welcome to the next universe, baby!
Is this my idea or has anyone read about this organic computer idea somewhere before?
http://www.hyperpoem.net
hyperpoem.net
This work is impressive, but NMR-based quantum computers have some special scaling problems. The net spin polarization of these liquids at room temperature is very small- about one part in a thousand roughly. This means that the quantum computation is done with only the slightest of distinction between 0 and 1. That can be handled for small computations, but the signal to noise problem becomes severe for larger systems.
The current quantum error correction codes impose a large bit overhead (factor of three or so), which compounds the signal/noise difficulty of the NMR technique.
The nice thing about this method is that the nuclei are well-isolated inside the electron clouds and decohere slowly. However, my guess is that NMR-based quantum computing will be first out of the gates, but will lag behind other implementations before reaching the finish line.
Curtains for windows?
They were building structures measuring in the hundreds of cubits three thousand years ago.
--
What I gave was a *very* rough sketch of the mechanics behind it. I don't claim to be an expert on quantum information theory, nor on constructing ion traps. I can assure you however that the manipulation of the electron's quantum state involves much less "fumbling" than you described. These spin-spin manipulations are carried out with a finely tuned YAG laser which is optically doubled (a few times over) to the correct frequency for the desired transition (the laser is referenced to a rubidium cell, perhaps, as reference). I'm certainly not denying the potential of the types of QC's you mention - perhaps you might elaborate on the enhanced "computing power" you'd expect from nuclear-based quantum computers? As for evidence of the merits of these ion-trap QCs, I suggest articles by D. Wineland (NIST) and C. Monroe (Formerly of NIST, now at Univ. Michigan).
Grover's algorithm is O(n^0.5).
It's qubit, not qbit.
1. We might be soon approaching the point where we should need longer encryption keys due to the amount of computing power available to the researcher.
2. We all know that the NSA is de facto "a little bit" ahead in this subject, due to their obfuscation of their existance and all the matter of cryptology during the 70s.
3. The US government decided to "open up" to allow the use of "strong" encryption to the rest of the world.
1+2+3=> I'm seriously thinking that the NSA itself could have gained enough computing power (quantum computing? does it look less impossible now?) at the time they started opening the key-size barrier.
time will prove me wrong, hopefully.
-- There are two kind of sysadmins: Paranoids and Losers. (adapted from D. Bach)
Java runtime is also quite slow.
Personally, I think the major advances will happen once companies such as Intel begin to hit fundemental barriers in creating silicone chips. Then we'll see some real money being thrown at optical and quantum computing, by companies who work by results rather than by scientific interest.
This is kind of an informed guess, but:
- 7 to 10 years: Silicone begins to run out of steam
- 15 years: First useful optical computers
- 20 to 25 years: Silicone is gone, optical is mainstream
- 50 years: Quantum computers do something useful for the first time
- 75 years: Quantum computers begin to be used by large companies
- 100 years: Quantum computing is mainstream
Hopefully, I'll be around to see all of the above!
Anyone else care to reply with their own timescale?
Beg:
http://archive.nytimes.com/2001/03/27/science/27QU AN.html
Any former CS student from a decent school will probably have done some NP complete proofs. You remember these: you create an algorithm of order O(N^x) to transform from known NP complete problem (A) to NP open (B), proving that if A can be solved in polynomial time then B can to.
:-)
If QC is achieved these transformation algorithms will have practical importance. Yet another thing I learnt in school that seemed useless at the time but maybe isn't
http://rareformnewmedia.com/
3) dead kitten AND live kitten (superposition) and superposition of dead and live dog
The only reason you get superpositions is because you haven't measured the state yet, as when you have a kitten and a puppy (in separate sound proof boxes of course.)
Without looking in the boxes you can't tell whether the kitten or the puppy are dead or alive.
(obviously if you forgot to put holes in the box so they could breathe, they'd both be dead.)
By opening the box the kitten decides whether it is alive or dead and the same with the puppy.
Which asks the questions.
Can you use animals for quantum computing, or are the costs of feeding them too high?
and
If a tree is in a wood, and no one is around, is it still standing or is it falling down or is it in a supositioned state, until someone goes to look at it?
And of course then you have to ask if you don't know nothing about anything does anything exist?
I'm not a Troll i prefer to be called a Goblin.
You cretinous, cock-sucking, camel-kissing, crap-cuddling coward. Anyone with even a quarter a cerebral cortex could check the status bar of their browser and ken that this isn't a goatse.cx link. Fucking loser.
... or only 63 bits to break it in 2 "clock cycles". or 62 bits to break it in 4 "clock cycles". etc etc etc.
I'm speaking from 'gut feel' not knowledge here, but don't the Qbits need to be able to 'interact' with each other in order to solve the larger problem. If so you might need to be able to arrange 64^2 paths along which they could pairwise interact without interfering with their interaction with the other 62 Qbits? Even if they don't need pairwise interactions, but 'broadcast', you still need to get the 64 bits to be able to interact without interfering.
I've got a nasty feeling I haven't got a clue what I'm asking... Ooops!
THL
--
Keeping
Has anyone found a way to crack that with quantum computers?
Can anything be proven about the possibility of such a "quantum algorithm" existing if not?
AFAIK, there is still ongoing investigation into whether and how every one of our cells utilises the quantum nature of particles in DNA manipulation
Wow, I never knew Roger Penrose was an expert in DNA as well as neurology.
I've heard he's working on a theory that motor cars operate at the quantum level also.
Windows already uses quantum effects. Just looking at it will make it crash....
</Humor>
www.eFax.com are spammers
Could you imagine a beowulf cluster of qubits in Natalie Portman's pants, running Linux?!
And no one has EVER gotten an Ion-Trap quantum computer to do ANYTHING. Not add two numbers. Not factor a number. Not multiply two numbers. The potential is there - the qubits - its just no one has ever tapped it in a feasible way.
I'm confused; what sort of quantum system ran Shor's system or the basic quantum search algorithm?
Keys based on biometric security can be tens of thousands of bytes long, have nothing crackable about them and are entirely consistent. and much more secure.
They'll also need 64-bit hardware. Goodbye 32-bits and that other unportable OS won't make it there will it?
MSBPodcast.com The opinions expressed here are my own. If you don't like 'em... Think up your own stuff.
this article was posted on slashdot before; that where I learned 'bout it. It's well written and covers the theory and a bit of the mechanics. Worth a read (and a re-read) if you're interested.
.... will be needed to write a CSS Decoder?
What about conventional computers that connect to small quantum computers to perform small but frequent tasks? Isn't this a little more realistic and concrete goal in the near future?
Or are they completely incompatible?
Remember "Bring 'em on"? *sigh
It ISN'T NP-hard. Remember that an NP-hard problem is one where, even if you had a proposed solution, you can't verify the answer in polynomial time. Verifying a factorization answer is easy: just multiply. That's polynomial time, therefore factoring isn't NP-hard.
That's as opposed to Travelling Salesman where even if you have a proposed path, you'd have to check all possible paths to decide if yours was the minimum.
--
324006
The uber-paranoid may want to revoke their old private keys and issue new ones anyhow... According to this report on cryptome.org, a serious flaw was found in OpenPGP and its derivatives which leaves your private key vulnerable to attack.
Well, let's see:
10 atoms this year
20 atoms by early 2003
40 atoms by late 2004...
By the 22nd century, the entire universe will be a computer. Or is it already?
You are in a maze of twisty little passages, all alike.
Rather than depend upon a single 2048 bit key I'd rather use my pocket atomic encryption computer. It's...no, that's some lint...that's a pebble, some sand, dried mud -- wait, that will work. A little water and I put it in this message encrypter to make a cup of really hot tea...
"Nobody will ever need more than 640KB RAM." -- Bill Gates.
Maybe he meant 'more than 640 atoms' or 'more than 640KB RSA'?
[
This sure does promising enough. Another alternative using an identical technology is coupling two SQUIDs - Superconducting QUantum Interference Devices. SQUIDs.
;-)
;-)
These devices have excellent magnetic sensitivity. And when two of these thingies are coupled, you have your information travelling between one another through insulators at awesome speed (in these, even the superconducting electrons tunnel through).
Incidentally, I'm also working on SQUIDs, although on a theoretical basis. Getting to make a SQUID is, well, a little tough... So we are trying to find guys who'd give us Liquid Helium for free
Another interesting thing to do would be to quantumly couple 2 SQUIDs!!! And imagine building a Beowulf cluster of *those* !!!
"...Fear the people who fear your computer"
Usually I'm enthralled when new technology comes along. Organic LEDs? Cool! New ways to squeeze transistors onto a chip? Great! Super-fast wireless networks? Hubba hubba!
Yet. Quantum computers. There's one technology I hope never comes real in my lifetime. Looks like I'll be disappointed, I had no idea they had come this far.
Why? Because it will mean an end to public-key cryptography forever. Even if we manage to restore secure communication through quantum cryptography, digital signature technology will be lost.
I had great hopes for digital signatures. Here was a technology that gave the truth an edge over lies. Imagine a digital videocamera with a tamper-resistant chip wired into it that signs the video data regularly. Then connect it to a UMTS mobile or a satelite phone, give it to a brave man and send him to say Palestine. Make it so that it can't easily be turned on and off. You have a pretty damn good witness.
The loss for crypto is also sad. Today if I e-mail with a teacher at Birzeit, we can use crypto to aid in his safety. If the adversary, in this case Israel, gets a QC they can easily intercept this mail, kill him and create credible faked reports supporting their case. And if QC's become a reality, states will get it first, and possibly the public will never get it.
Public-key cryptography seemed to provide an antidote to big-brother type scenarios. But in a world where states have QC's we will be back were we was most of the 20th century: where you can never know very much about what's truth and what's propaganda, and the best you can do is support "your side". The best I can think of is praying.
Better suggestions are welcome.
xkcd is not in the sudoers file. This incident will be reported.
If it works out that Q-Comps are both *incredibly* more powerful in raw capacity (likely) and require special facilities (also likely), then we'll see a return to the architectures of the 70's and 80's, when Iron was Big and the Glass House was king.
In such an architecture, distributed platforms would be used to handle UI and interpretation, and the processor time to brute-force the calculations would be rented. A lot of the paradigm we've come to take for granted is very recent, and would have to be rethought in such an environment. Just as an example: Q-Comps could have the raw power to accurately simulate the physics of an FPS with hundreds of simulataneous players down to a microscopic level. Then an abstract of that could be transmitted to the players. Welcome to the Holodeck, boys.
--Dave Rickey
the NYT is now officially slashdotted. :-)
This article would lead you to believe that Quantum computing will provide a linear speed up to most algorithms. In fact only a very limited set of algorightms actually benefit from Quantum Paralellism. Peter Shor's algorithm for fatoring large numbers is significant not becasue it's terribly useful, but because at the time it was the only thing useful that had yet been devised for a quantum computer. Quantum computers are massively parallel, but because of some of the tricky laws of quantum mechanics, you can only read one result from the parrallel computation (The whole bit about observation causing wave functions to collapse.).
If you're really wantining to read more on Quantum Computing and Quantum Mechanics in general check out the Oxford Centre for Quantum Computation (David Deutch and Artur Ekert have done some really significant stuff) and read In Search of Schrodinger's Cat by John Gribben.
I'm currently doing research in a subset of quantum algorithms (and have worked as a research assistant in another area of quantum mechanics). They're pretty cool, but you shouldn't get your hopes up for them making the latest kernal hack run faster.
Once again we have someone who misunderstands the complexity theory but decides to post anyway. So, let's present some definitions.
P is a class of problems that can be decided by a deterministic turing machine in polynomial time.
NP is a class of problems that can be decided by a non-deterministic turing machine in polynomial time. NP stands for nondeterministic polynomial(*)
So, by definition, NP-complete problems can be solved in polynomial time. You just need to implement a non-deterministic turing machine to do that. The big question in computer science is whether NP-complete problems can also be solved in polynomial time by a deterministic turing machine (i.e. does P = NP?). The answer at this point is "probably not". Here is the most informative post on the subject I've seen so far, btw.
Anyway, back to the story: it looks (well, to me at least) like quantum computer is an implementation of NTM, but as others have pointed out, some researchers have doubts about that. If it is indeed an NTM, then presto -- you have poly-time solutions to all NP-complete problems. Assuming you can ever build one of these suckers, of course ;-)
(*) One other (and more commonly used) way to define class NP is as a class of all problems that can be verified by a deterministic turing machine in polynomial time. That is really only a subset of the definition.
___
___
If you think big enough, you'll never have to do it.
with even a quarter a cerebral cortex could check the status bar of their browser and ken that this isn't a goatse.cx link
Except if the URL looks benign but links to a page that contains a mirror of goatse.cx's content.
Will I retire or break 10K?
They'll also need 64-bit hardware. Goodbye 32-bits and that other unportable OS won't make it there will it?
64 bits can be emulated. The x87 architecture has had instructions to deal with 64-bit double-precision floating-point values since the 8087. And how else do you think the 32-bit PC emulates the 64-bit Nintendo 64 console?
"Bits" without context are meaningless. For example, the measure (data bus width) that makes Sega Genesis's MC68000 a 16-bit CPU makes the Super NES's 65816 CPU 8-bit. Sega liked to call its Saturn console 96-bit because it had three parallel 32-bit (ALU width) CPUs.
Will I retire or break 10K?