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

Comments

There are some problems with this.

[Anonymous Coward]

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.

Re:There are some problems with this.

[john_many_jars]

It is my understanding of quantum computers that they harness the wave equations of the subatomic particles to solve problems. Using the Heisenberg (sp?) uncertainty principle to do work.

And you are right that factoring numbers and the Chinese Remainder Theorem is used in todays top notch crypto schemes. However, this is relatively new since the standard for encryption relies mainly on standard fsa's not to gerenrate large prime numbers but to obscure bit patterns. That's how D(igital) E(ncryption) S(tandard) works. Admittedly it is not the best, but it is still more difficult to solve than Caesar.

All that it would take to solve this problem would be to come up with an encryption technology that relies on the fact that the solution of a very difficult math/CS problem be solved (ie P?=NP) to break the encryption. If this is accomplished, then we move on to the next hard problem like determination of Godel numbers for Number Theory. The numbers exist, just almost impossible to find. It is just a matter of finding the trap door to these problems. The Chinese Remainder Theorem is the key to the trap door in strong crypto, today. (Note: I never said this was easy, but at no point is it impossible)

All encryption needs to do is apply a very difficult problem to maintain efficency. And according to Godel, these problems will always exist.

In other words, 1) [I believe anyway] quantum computer are not programmed, but involve a very difficult process of determining a wave equation that describes the problem or solution to a problem and the corresponding work to set up that wave equation in reality, 2) encryption is not just the application of solving the chinese remainder theorem, but merely the application of a known difficult problem that must be solved to encrypt the data (I can think of quite a few problems that are solveable but are extremely difficult), 3) maybe even quantum computers will finally enable perfect one-time pads to exist giving perfect encryption.

At no point did anyone say solving problems does not raise new ones. As a matter of fact, quite the opposite is true. For every rule there are x exceptions, x>=1. Even that rule has exceptions. Have to be exceptions if the rules describe anything interesting.

Also, remember necessity is the mother of invention. As long as hard problems exist (and they are guaranteed to exist-- you can always find Godel numbers, each one progressively more difficult to write down, let alone determine), encryption will advance.

Open Source Quantum Computing

[Ignatius]

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.

Re:Encryption

[BeBoxer]

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.

Will we be able to program in this way?

[K8Fan]

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?

Yes, and so much more!

[CausticPuppy]

It runs all possible operating systems simultaneously.

Qubit..

[deefer]

Wasn't Qubit a 3D platform game with a cute jumping sprite about 15 years ago?
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.

Re:A bit more detail for the curious ...

[yuriwho]

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.

Re:Anybody got a good explination of what this mea

[jejones]

Check out QED, a transcript of lectures by Feynmann on quantum electrodynamics. Particles evidently don't exactly travel in straight lines; in a way, they go every which way at once, and the path we see them take is the one of least resistance, the most likely path. If you remember your automata theory, they're reminiscent of nondeterministic machines, which can also be thought of as trying every possibility at once. If we have real live quantum computers, then, whether P=NP becomes a question of much less practical importance, because we'd all have NP capable hardware. Hence the concern in other messages on this thread about encryption, since public key cryptosystems count on NP complete problems being extremely tedious to solve.

(This is a lot of handwaving on my part, and corrections are welcomed!)

Moore's law of quantum computing.

[Claudius]

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.

Re:Multiple States?

[ptbrown]

schroedinger:~$ cat >box
bash: cat: command not found
schroedinger:~$ whereis cat
cat: /bin/cat /usr/man/man1/cat.1.gz
schroedinger:~$ echo $PATH
/usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/g ames
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: /bin/cat /usr/man/man1/cat.1.gz
schroedinger:~$ AAAARRRRRRRRGGGGHHHH!!!!!!

QC will [probably] not solve all problems in NP-C

[Signail11]

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.

Re:Can anyone paraphrase how it works?

[balbuzaro]

Okay, I found this explanation (link at the end): Quantum Computers

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 bit more detail for the curious ...

[Somnus]

As a physics major, I have experience with NMR experiments in junior lab; and "spin flipping" is critical to my research group's experiment. So, I'll take a stab at explaining the experiment in greater detail for interested parties who don't appreciate Wired's liberal use of jargon ...

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