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."
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.
The Russians/Soviets have been using one time pads for low volume (text) traffic for over 60 years. The one time pad can't be cracked by a quantum computer (or conventional computer) if properly generated. It's a pain to use but it is provably secure.
Mea navis aericumbens anguillis abundat
Read up some... The only thing that Quantum Computing has that relates to Quantum Encryption is the fact that they both have Quantum in their name. They're two completely separate technologies... Quantum computing theoretically could render most of todays cryptography useless, but it won't enable Quantum Encryption...
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.
Quantum cryptography is (assuming quantum theory is correct) an unbreakable cryptosystem. A basic primer of Q Cypto is here. This also gives details of how to implement Q. Crypto - test of quantum encrypted links of over 1km have already been demonstated: a far cry from "you can't develop [it] until you solve some general problems".
We need an "I am not a scientist" label (like IANAL) for posts like that one.
FWIW, the arguments I've seen along these line have been pretty bogus. Unless quantum effects play a significant role in the operation of neurons, you could simulate a brain to the necessary exactitude with a TM. (Even if QM plays a role, it most likely randomizes certain interactions and you'd just need a TM with a /dev/random hooked up to, say, diode noise.) Douglas Hofstadter takes this to an interesting conclusion in "A Conversation With Einstein's Brain", which can be found in The Mind's I (highly recommended reading). (I think "A Conversation..." was originally in Godel, Escher, Bach, but I haven't gotten through that yet - maybe I'll make it my summer project.)
I would think that the theoretical version of a quantum computer would be a Turing machine with nondeterminism, which doesn't buy you anything over a vanilla TM in terms of computability.
Tom Swiss | the infamous tms | my blog
You cannot wash away blood with blood
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
Yeah, does it mean you'll get an answer like "The answer might be 3.476 or it might be 3.475?"
---
DO NOT DISTURB THE SE
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
Bah.... thanks for the ludite argument.
These things wont be available to "anyone" for
quite a long time. Noone except HUGE corperations
and governments will be building them within the
next 10 years or even more. Plenty of time.
Research is important. Science for the sake of
science I say. Human society will adapt. Maybe
a few eggs will have to break in the process...
but in the end we get a good omlet.
Like any good tool, such things can be used for
either good or evil. I think we should continue
as we always have with technology...keep going
forward and seal with the social raminifcations
as we go.
No system is so sacred and important that it
shouldn't be torn down and rebuilt from scratch.
"I opened my eyes, and everything went dark again"
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.
Let me start with the disclaimer that I am not an expert in either quantum mechanics or number theory. That said, there is a fundamental difference between public and private key crypto. Public key is all based upon various problems which are considered to be "trapdoor" problems. This means that they are easy to compute in one direction, and "hard" to compute in the other. The classic one (which RSA is based upon) is factoring. It is easy to multiply two prime numbers together. It is "hard" to factor the resulting number to get the original primes back. I put "hard" into quotes because no one has ever proven that these problems are actually hard. It's just that no one has ever figured out an efficient algorithm for solving them, at least not with classical computers. The quantum computers, it appears, will be able to brute force these problems by just trying all possible answers at once. This works for factoring because one answer is provably right, and the others are provably wrong.
On the other hand, private key does not suffer from this problem. The reason being that you can't prove which answer is the correct one. In the most extreme form, we have the one time pad. This is a provably secure encryption method, the reason being that given a ciphertext of a certain size, there exists a key which will decrypt that ciphertext into any possible plaintext of the same size with equal probablility. So, even if you did try every possible key, the results would be every possible plaintext with no way to tell which one is correct. Even the practical private key systems that we use (DES, Blowfish, IDEA), a successful cryptanalysis relies upon there being patterns or detectable traits in the plaintext so that we can distinguish the "junk" produced by bad keys from the correct answer. This is very different from the public-key case where you can mathematically prove that you have the correct answer.
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.
schroedinger:~$ cat >box /bin/cat /usr/man/man1/cat.1.gz g ames /bin/cat /usr/man/man1/cat.1.gz
bash: cat: command not found
schroedinger:~$ whereis cat
cat:
schroedinger:~$ echo $PATH
/usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/
schroedinger:~$ cat >box
bash: cat: command not found
schroedinger:~$ ls
GNUstep News
Mail box
schroedinger:~$ cat >box
bash: cat: command not found
schroedinger:~$ whereis cat
cat:
schroedinger:~$ AAAARRRRRRRRGGGGHHHH!!!!!!
Any sufficiently advanced civilization is indistinguishable from Gods.
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.
The memory of a classical computer is a string of 0s and 1s, and a classical computer can do calculations on only one set of numbers at once. The memory of a quantum computer is a quantum state which can be in a superposition of many different numbers at once. A classical computer is made up of bits, and a quantum computer is made up of quantum bits, or qubits. A quantum computer can do an arbitrary reversible classical computation on all the numbers simultaneously, and also has some ability to produce interference, constructive or destructive, between various different numbers. By doing a computation on many different numbers at once, then interfering the results to get a single answer, a quantum computer has the potential to be much more powerful than a classical computer of the same size.
The most famous example of the extra power of a quantum computer is Peter Shor's algorithm for factoring large numbers. Factoring is an important problem in cryptography; for instance, the security of RSA public key cryptography depends on factoring being a hard problem. Despite much research, no efficient classical factoring algorithm is known.
Shor actually solved a related problem, the discrete log. Suppose we take a number x to the power r and reduce the answer modulo n (i.e., find the remainder r after dividing xr by n). This is straightforward to calculate. It is much more difficult to find the inverse - given x, n, and y, find r such that xr = y (mod n). For factoring, all we need to do is consider y=1 and find the smallest positive r such that xr = 1 (mod n). Shor's quantum algorithm to do this calculates xr for all r at once. Since xl+r = xl (mod n), this is a periodic function with period r. Then when we take the Fourier transform, we will get something that is peaked at multiples of 1/r. Luckily, there is an efficient quantum algorithm for the Fourier transform, so we can then find r.
There are many proposals for how to build a quantum computer, with more being made all the time. The 0 and 1 of a qubit might be the ground and excited states of an atom in a linear ion trap; they might be polarizations of photons that interact in an optical cavity; they might even be the excess of one nuclear spin state over another in a liquid sample in an NMR machine. As long as there is a way to put the system in a quantum superposition and there is a way to interact multiple qubits, a system can potentially be used as a quantum computer. In order for a system to be a good choice, it is also important that we can do many operations before losing quantum coherence. It may not ultimately be possible to make a quantum computer that can do a useful calculation before decohering, but if we can get the error rate low enough, we can use a quantum error-correcting code to protect the data even when the individual qubits in the computer decohere.
http://qso.lanl.gov/~gottesma/QComputers.html
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 ***