the universal quantum computer or universal quantum Turing machine (UQTM) is a theoretical machine that combines both Church-Turing and quantum principles.
A UQTM quantum computer would be able to do everything that our current computers can do and in addition the funky quantum capabilities.
The number of classical states encoded in a quantum register grows exponentially with the number of qubits. The power of quantum computers is the ability to compare 2 to the number of qubit states. So 12 entangled and coherent qubits could look at 2 ** 12 or 4096 states. So 50 entangled and coherent qubits could look at over a quadrillion states. 100 entangled and coherent qubits could look at quadrillion times a quadrillion states. For n=300, this is roughly 10**90, more numbers than there are atoms in the known universe.
Note: that ten physical qubits are needed to form one logical qubit and the physical qubits need to be able to perform multiple logic operations. We are currently counting logical qubits. It is the 2007 goal to form one logical qubit.
Another use of quantum computers is cracking the security used for finance and secrets. The Shor algorithm: if a number has n bits (is n digits long when written in the binary numeral system), then a quantum computer with just over 2n qubits can use Shor's algorithm to find its factors. The key length for a secure RSA transmission is typically 1024 bits. 512 bits is now no longer considered secure. For more security or if you are paranoid, use 2048 or even 4096 bits. Read more about cryptography and its importance here
From the wikipedia quantum computer (QC) entry:
Problems and practicality issues [to get to quantum computers]
There are a number of practical difficulties in building a quantum computer, and thus far quantum computers have only solved trivial problems. David DiVincenzo, of IBM, listed the following requirements for a practical quantum computer:
* scalable physically to increase the number of qubits
* qubits can be initialized to arbitrary values
* quantum gates faster than decoherence time
* Turing-complete gate set
* qubits can be read easily
To summarize the problem from the perspective of an engineer, one needs to solve the challenge of building a system which is isolated from everything except the measurement and manipulation mechanism. Furthermore, one needs to be able to turn off the coupling of the qubits to the measurement so as to not decohere the qubits while performing operations on them.
Reviewing some of the leading QC approaches:
The scaling to useful numbers of qubits is progressing among several architectures.
superconducting versions - Like dwave systems in vancouver. Seems like they should get a lot of qubits but that they are somewhat limited in the range of capabilities. They can do searches and they are not computers that can be be generally sold. Their solution is finicky and will need to be coddled by engineers and Phds at big facilities who will feed questions submitted for answers. Could be offered as a service starting in 2007 for 50+ and maybe 100 qubits.
Trapped ion quantum computers are a leading approach qo quantum computers. They appear to be very scalable and are usually built with semiconductors. This 2006 presentation by Carl Williams toutes the benefits of trapped ions and describes the proposed scalable to hundreds of qubits architecture. Recently 2D semiconductor ion traps have been developed They need to be adjusted to have ions that are better for manipulation.
This table from the 2004 Quantum computing roadmap gives a sense of the state of each approach. Ion traps seemed to have filled their gaps with item 1 and 3.
Green= a potentially viable approach has achieved sufficient proof of principle
Orange= a potentially viable approach has been proposed, but there has not been sufficient proof of principle
Red= no viable approach is known
The column numbers correspond to the following QC criteria:
#1. A scalable physical system with well-characterized qubits.
#2. The ability to initialize the state of the qubits to a simple fiducial state.
#3. Long (relative) decoherence times, much longer than the gate-operation time.
#4. A universal set of quantum gates.
#5. A qubit-specific measurement capability.
#6. The ability to interconvert stationary and flying qubits.
#7. The ability to faithfully transmit flying qubits between specified locations.
Magnetic liquid. Read by sensitive MRI. Up to about 12 qubits. Current qubit leader but limitations on scaling.
Magnetic bubbles could scale to 100's of qubits. Might be able to get going quickly. But has not actually delivered anything.
Scaling also possible by transmitting quantum effects via optical fiber and can transmit quantum effected ions and molecules (the quantum teleportation stuff). Can also already have quantum encrypted communication (military).
As we get smaller semiconductor features, better superconductors and metamaterials down to 10 nanometers or less and at better temperatures, I think the decoherence and robustness issues will be vastly improved.
It seems progress is going quite well on all of these factors and useful machines for larger quantum simulations (hundreds of qubits) and narrow sets of search and decryption purposes should be with us far sooner than the universal machines.
If it is 10 years to universal quantum computers and 1 or 2 years to useful but finicky quantum lab simulators as a commercial service. Probably in the 3-6 year range there will be fairly widespread, cheap and useful for pushing molecular manufacturing development with very powerful quantum simulators. Our understanding and mastery of the quantum world will vastly improve over this time.
Trends that are working for this. Constantly shrinking lithography and control of nanoscale materials, better understanding of quantum physics and superconductors, and better superconductors, better lasers.
I expect a lot of progress over the next ten years and beyond. A lot of the progress are virtually assured based on progressing enabling capabilities. But with the interacting effects there will at some point be some sudden leaps in capability when a bunch of things all come together at once past particular threshholds.
Magnetic bubbles could scale to 100's of qubits
Error checking for superconducting QC
Quick summary of the state of quantum computers
2004 quantum computing roadmap
Economist magazine on quantum computers
Berkeley Labs article on quantum computers