A computer which makes explicit use of the rules of quantum mechanics. Pioneered by David Deutsch in 1985, it relies on quantum entanglement to achieve a highly parallel operation in which many manipulations are effectively processed simultaneously, offering greatly improved speed over conventional computers, including parallel computers, for certain types of calculation. Elementary calculations and simple logic circuits have been demonstrated, but a complete quantum computer has not yet been built.
A quantum computer is any device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. in a quantum computer, the data is measured by qubits. The basic principle of quantum computation is that the quantum properties of particles can be used to represent and structure data, and that quantum mechanisms can be devised and built to perform operations with these data.
Though quantum computing is still in its infancy, experiments have been carried out in which quantum computational operations were executed on a very small number of qubits. Research in both theoretical and practical areas continues at a frantic pace, and many national government and military funding agencies support quantum computing research to develop quantum computers for both civilian and national security purposes, such as cryptanalysis. (See Timeline of quantum computing for details on current and past progress.)
It is widely believed that if large-scale quantum computers can be built, they will be able to solve certain problems asymptotically faster than any classical computer. Quantum computers are different from other computers such as DNA computers and computers based on transistors, even though these may ultimately use some kind of quantum mechanical effect (for example covalent bonds). Some computing architectures such as optical computers may use classical superposition of electromagnetic waves, but without some specifically quantum mechanical resource such as entanglement, they do not share the potential for computational speed-up of quantum computers.
The basis of quantum computing
Unsolved problems in physics: Is it possible to construct a practical computer that performs calculations on qubits (quantum bits)?‹The template Unsolved has been proposed for deletion here.›
In quantum mechanics, the state of a physical system (such as an electron or a photon) is described by a vector in a mathematical object called a Hilbert space. As described in the article on quantum mechanics, this function has a probabilistic interpretation; of particular significance is that quantum states can be in a superposition of the basis states. A quantum computer maintains a vector of qubits. A quantum computer operates by manipulating those qubits, i.e. by transporting these bits from memory to (possibly a suite of) quantum logic gates and back.
Qubits for a quantum computer can be implemented using particles with two spin states: "up" and "down" (typically written and );
For discussion of foundational aspects of quantum computing, see the article on quantum circuits. In a quantum computer, however, the qubits can be in a superposition of all the classically allowed states.
For an n qubit quantum register, recording the state of the register requires 2 complex numbers (the 3-qubit register requires 2, more states than there are atoms in the known universe. The representation is also (for most practical cases) non-unique, since there is no way to physically distinguish between a particular quantum register and a similar one where all of the amplitudes have been multiplied by the same phase such as −1, i, or in general any number on the complex unit circle. An algorithm for a quantum computer must initialize this vector in some specified form (dependent on the design of the quantum computer).
Upon termination of the algorithm, the 8-dimensional complex vector stored in the register must be somehow read off from the qubit register by a quantum measurement. However, by the laws of quantum mechanics, that measurement will yield a random 3 bit string (and it will destroy the stored state as well). By repeated runs of the quantum computer and measurement of the output, the correct value can be determined, to a high probability, by majority polling of the outputs.
A quantum algorithm is implemented by an appropriate sequence of unitary operations.
For more details on the sequences of operations used for various algorithms, see universal quantum computer, Shor's algorithm, Grover's algorithm, Deutsch-Jozsa algorithm, quantum Fourier transform, quantum gate, quantum adiabatic algorithm and quantum error correction.
The power of quantum computers
Integer factorization is believed to be computationally infeasible with an ordinary computer for large numbers that are the product of two prime numbers of roughly equal size (e.g., products of two 300-digit primes). By comparison, a quantum computer could solve this problem relatively easily. 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. This ability would allow a quantum computer to "break" many of the cryptographic systems in use today, in the sense that there would be a relatively fast (polynomial time in n) algorithm for solving the problem. The only way to increase the security of an algorithm like RSA would be to increase the key size and hope that an adversary does not have the resources to build and use a powerful enough quantum computer. It seems plausible that it will always be possible to build classical computers that have more bits than the number of qubits in the largest quantum computer. If that's true, then algorithms like RSA could be made secure by ensuring that keylengths exceed the storage capacities of quantum computers.
There are some digital signature schemes that are believed to be secure against quantum computers.
Perhaps not as surprisingly, quantum computers could also be useful for running simulations of quantum mechanics. This idea goes back to Richard Feynman (1982) who observed that there is no known algorithm for simulating quantum systems on a classical computer and suggested to study the use of quantum computer for this purpose. The speedup achieved by quantum computers could be just as large as for factoring. This could be a great boon to physics, chemistry, materials science, nanotechnology, biology and medicine, all of which are limited today by the slow speed of quantum mechanical simulations. For example, some modern simulations that are taking IBM's Blue Gene supercomputer years, would take a quantum computer only a matter of seconds.
This dramatic advantage of quantum computers is currently known to exist for only those three problems: factoring, discrete logarithm, and quantum physics simulations. There is one other problem where quantum computers have a smaller, though significant (quadratic) advantage. This establishes beyond doubt that (ideal) quantum computers are superior to classical computers for at least one problem. The time for a quantum computer to solve this will be proportional to the square root of n. There are also more complicated methods for secure communication, such as using quantum cryptography.
Regardless of whether any of these problems can be shown to have an advantage on a quantum computer, they nonetheless will always have the advantage of being an excellent tool for studying quantum mechanical interactions, which of itself is an enormous value to the scientific community.
There are currently no other practical problems known where quantum computers give a large speedup over classical computers.
Problems and practicality issues
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 easilyTo 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.
Quantum decoherence
One major problem is keeping the components of the computer in a coherent state, as the slightest interaction with the external world would cause the system to decohere. This effect causes the unitary character (and more specifically, the invertibility) of quantum computational steps to be violated. If the error rate is small enough, it is possible to use quantum error correction, which corrects errors due to decoherence, thereby allowing the total calculation time to be longer than the decoherence time.
One approach to the stability-decoherence problem is to create a topological quantum computer with anyons, quasi-particles used as threads and relying on knot theory to form stable logic gates.
Candidates
There are a number of quantum computing candidates, among those:
Superconductor-based quantum computers (including SQUID-based quantum computers) Trapped ion quantum computer Electrons on helium quantum computers "Nuclear magnetic resonance on molecules in solution"-based "Quantum dot on surface"-based "Cavity quantum electrodynamics" (CQED)-based "Molecular magnet"-based Fullerene-based ESR quantum computer Solid state NMR Kane quantum computers Optic-based quantum computers (Quantum optics) Topological quantum computerIn 2005, researchers at the University of Michigan built a semiconductor chip which functioned as an ion trap. Such devices, produced by standard lithography techniques, may point the way to scalable quantum computing tools.
Quantum computing in computational complexity theory
This section surveys what is currently known mathematically about the power of quantum computers. It describes the known results from computational complexity theory and the theory of computation dealing with quantum computers.
The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time". Quantum computers only run randomized algorithms, so BQP on quantum computers is the counterpart of BPP on classical computers. A quantum computer is said to "solve" a problem if, for every instance, its answer will be right with high probability. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time.
An operator for a quantum computer can be thought of as changing a vector by multiplying it with a particular matrix. It has been shown that if a quantum computer could be designed with nonlinear operators, then it could solve NP-complete problems in polynomial time.
Although quantum computers are sometimes faster than classical computers, ones of the types described above can't solve any problems that classical computers can't solve, given enough time and memory (albeit possibly an amount that could never practically be brought to bear). A Turing machine can simulate these quantum computers, so such a quantum computer could never solve an undecidable problem like the halting problem. The existence of "standard" quantum computers does not disprove the Church-Turing thesis (Nielsen and Chuang 2000).
Very recently, Debabrata Goswami and others have begun to investigate the possibility of using quantum mechanics for hypercomputation - that is, solving undecidable problems. Centre for Quantum Computation, University of Cambridge http://cam.qubit.org Quantiki - Cambridge free-content resource in quantum information science Institute for Quantum Computing, University of Waterloo Quantum & NanoTechnology Group, Oxford University UK Quoxic meetings calendar, a list of upcoming and previous quantum information meetings in Oxford and London. QCL — A Programming Language for Quantum Computers Qwiki - Caltech quantum physics wiki devoted to providing technical resources for practicing quantum information scientists. QuantumInfo.Org, University of Leeds Quantum Information Group. Quantum Information Science Gateway The Physics Community's general reference on QIS. Introduction to Quantum Computation: The Temple of Quantum Computing, a quantum computing tutorial for everyone, including those who have no background in physics. "An Introduction to Quantum Computing for Non-Physicists". "A Physics-Free Introduction to the Quantum Computation Model". "Quantum Computation: A Computer Science Perspective". "Bulk Spin-Resonance Quantum Computation". (download) Other references "Bulk Spin Resonance Quantum Computation" Using quantum computers to simulate quantum systems: Feynman, R. Closing in on Quantum Chemistry - Calculating real properties of real quantum chemistry systems using a quantum computer Quantum cryptography: The first paper ever written on this: Wiesner, S. "Quantum Cryptography Based on Bell's Theorem". "Quantum cryptography, or unforgeable subway tokens". Advances in Cryptology: Proceedings of Crypto 82, August, Plenum Press, 267–275. A listing of a huge number of quantum cryptography papers, with some discussion of them, is at http://www.cs.mcgill.ca/~crepeau/CRYPTO/Biblio-QC.html Quantum Cryptography Universal quantum computer and the Church-Turing thesis: Deutsch, D. "Quantum Theory, the Church-Turing Principle, and the Universal Quantum Computer". Proc. "Algorithms for quantum computation: discrete logarithms and factoring". Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20–22 November. Jean-Pierre Seifert, "Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation", (download) IBM's announcement of the first actual execution of the algorithm, which also gives the history of the first quantum computers with 2, 3, 5, and 7 qubits. "A Fast Quantum Mechanical Algorithm for Database Search". Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, 212–219.. "Quantum time-space tradeoffs for sorting". Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, 69–76. — A MATLAB based quantum computer simulator libquantum — A library for quantum computer simulation QCL — Simulation of quantum computing with a quantum computing language Quantum::Entanglement — Quantum computation module for Perl. QCF — Quantum computation functions for matlab Fraunhofer Quantum Computing Simulator — A free web-based quantum simulator (31 qubits) and a collaborative workspace for the quantum computing community. QDENSITY — A MATHEMATICA based quantum computer simulator, oriented to Density Matrix A Quantum Cryptography Computer Simulator Fernando Lucas Rodriguez Linear Al - free software for research and education in quantum computation Quantum error correction: Simonite, Tom. (2006) New Scientist: Error-check breakthrough in quantum computing. "Scheme for reducing decoherence in quantum computer memory". "Decoherence free subspaces for quantum computation". of Mechanical Engineering, MIT), 1998, "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems", arXiv:quant-ph/9801041. The Quantum Computer — An Introduction. (Easy to understand explanation of quantum computing) Hayes, Brian (Jul-Aug 1995). (Logic gates in a quantum computer) David Deutsch (1997). Quantum computing related companies D-Wave Systems - Superconductor-based quantum computers id Quantique - Quantum cryptography and Random-number generators MagiQ - Quantum cryptography solutions Quantum computing related patents Some issued quantum computing-related patents Some published quantum computing-related patents Quantum Hoaxes Atom Chip Corp's QUANTUM-OPTICAL TECHNOLOGY Yet-to-be-categorized HP Cites Progress On Quantum Computer Similarly named miscellany: For the online service provider that was previously known as Quantum Computer Services, see America Online.
User Comments Add a comment…