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."
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 ***