Quantum Computing

: "In a quantum computer, the fundamental unit of information (called a quantum bit or qubit), is not binary but rather more quaternary in nature. This qubit property arises as a direct consequence of its adherence to the laws of quantum mechanics which differ radically from the laws of classical physics. A qubit can exist not only in a state corresponding to the logical state 0 or 1 as in a classical bit, but also in states corresponding to a blend or superposition of these classical states. In other words, a qubit can exist as a zero, a one, or simultaneously as both 0 and 1, with a numerical coefficient representing the probability for each state. This may seem counterintuitive because everyday phenomenon are governed by classical physics, not quantum mechanics -- which takes over at the atomic level." - http://www.cs.caltech.edu/~westside/quantum-intro.html

What makes computing with qubits so interesting is that when you have 2 qubits in one entangled system, there are 4 possible simultaneous states (8 for 3, etc.) and performing a binary operation on a superposed state (such as the state with all combinations having equal wieght) is equivaluent to performing the operation simultaneously on each of those states, this performing 2^n computations at once. The trick is coming up with quantum algorithms that produce a useful answer when a single random one of the possible binary number outputs is read out at the end.

: If "Computable" means "Doable on a TuringMachine," and if it turns out that you can't simulate QuantumComputing on a TuringMachine, then QuantumComputing is... well, uncomputable. That would be fun.

Yes, that would be fun. Unfortunately, we already know that we can simulate QuantumComputing on a TuringMachine. It might not be possible efficiently, but it is possible to do it slowly. There are actually already programs which simulate QuantumComputing. See http://rugth30.phys.rug.nl/compphys0/qce.htm, but I did not take a look at it.

But why would one not be able to simulate QC on a Turing Machine? A quick search finds:

Quantum Computing Reports on Progress in Physics, vol 61, pp 117-173 (1998): A. M. Steane

Which states that

: ...we know that classical computers can simulate, by their computations, the evolution of any quantum system . . . with one reservation: no classical process will allow one to prepare separated systems whose correlations break the Bell inequality. It appears from this that the EPR-Bell correlations are the quintessential quantum-mechanical property (Feynman 1982).

So, a problem that could only be solved using non-locality would satisfy our need for something computable, but not Turing computable.

It seems as if, so far, what quantum computers do is, mostly, tame certain problems for which no efficient classical solution is known. However, While Shor's factoring algorithm for quantum computers is impressive, factorization is probably not an NP-hard problem. There are currently no known quantum algorithms that can solve NP-complete problems in polynomial time. There's a little more discussion over in NpComplete.

See: http://www.qubit.org/

Quantum computing could be used to implement a CellularAutomaton:

"One way to make the cells would be using structures called quantum-dots, which are also know as 'artificial atoms'. A simulation showing how the cellular architecture works is available .." as applet on

http://cm-th.physics.ox.ac.uk/SimonB/circuit/simulator.html

And for an example that does some arithmetic: context see: http://elais.physics.ox.ac.uk/SimonB/adder/implement.html

This looks like it might be quite interesting. Needs some more context, though. Preferably in the form of text on a Wiki page.Possibly not this one.

I'm seeing "Server not found" for http://cm-th.physics.ox.ac.uk . Is that server no longer in commission, or is my DNS lookup misbehaving?

If QuantumComputing can solve factoring routinely this will cause problems for many trusted software and networking encryption schemes which rely on the fact that large numbers cannot be factored easily.

However, the same technology can provide new encryption schemes which will let the communicating parties know if any bits have been intercepted. Thus, we won't all suddenly have no information security.

Encryption will be broken in two ways. First, if the first quantum computers are hyper-expensive (as most breakthrough tech is), then we'll have a time that only large governments and corporations will have quantum computers. Secondly, once everybody has quantum computers, they won't be able to break encryption on live data streams, but any encrypted data they retrieved previously in the old classic computing days would suddenly be crackable.

[From the interviews I've read, large search-space computations will generally take a square root as much space and time as they would on a regular machine. That is, the 2^N computations is an ideal case that simply doesn't apply to most quantum algorithms. A square root corresponds to halving the number of bits in your encryption key. This is a major hit, granted, but one that can be tackled by using bigger keys.]

And some advances on the entanglement front: http://physicsweb.org/articles/news/11/1/11/1