This section contains some background to quantum computation, as well as discussion of various models of quantum computation. There are seperate subcategories for Quantum Algorithms, Quantum Error Correction and Physical Realisations
For a gentle introduction to quantum computation, see the tutorial What is Quantum Computation?. For a less gentle introduction see Basic concepts in quantum computation in our tutorials section
A quantum computer is any device for computation that makes direct use of distinctively quantum mechanical phenomena to perform operations on data. In a classical (or conventional) computer, the program's input is stored in classical bits and the computer performs operations on this bits; in a quantum computer, the input is stored in qubits, and the quantum computer manipulates the qubits during the computation. The reason people are excited about quantum computation is because we
can efficiently solve problems on a quantum computer which are believed to not be efficently solvable on a classical computer.
Experiments have already 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; see Quantum Information Science and Technology Roadmap for a sense of where the research is heading. Many national government and military funding agencies support quantum computing research, to develop quantum computers for both civilian and national security purposes, such as cracking public key cryptography. See for potential implementations of quantum computation.
Contents |
The power of quantum computers
Integer factorization is believed to be practically impossible with an ordinary computer for large numbers that are the product of two prime numbers of roughly equal size (eg. products of two 300-digit primes). By comparison, a quantum computer could solve this problem very quickly using Shor's factoring 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 find its factors. It can also solve a related problem called the discrete log problem. This ability would allow a quantum computer to break many of the cryptographic systems in use today. In particular, most of the popular public key ciphers could be quickly broken, including forms of RSA, ElGamal and Diffie-Hellman. These are used to protect bank transactions, in secure Web pages, encrypted email, and many other types of data. Breaking these would be significant.
Perhaps not as surprisingly, quantum computers could also be useful for running simulations of quantum mechanics. The speedup 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.
This dramatic advantage of quantum computers is currently known to exist for a number of problems: factoring, discrete log, quantum physics simulations and. However, there is no proof that the advantage is real: an equally fast classical algorithm may still be discovered (though this is considered unlikely). There is one other problem where quantum computers have a smaller, though significant (quadratic) advantage. It is quantum database search, and can be solved by Grover's search algorithm. In this case the advantage is provable. This establishes beyond doubt that (ideal) quantum computers are superior to classical computers.
Problems with quantum computing
One of the major obstacles of quantum computing is the problem of decoherence, which causes the unitary character (and more specifically, the invertibility) of quantum computational steps to be violated. Decoherence times for candidate systems, in particular the transverse relaxation time T2 (terminology used in NMR and MRI technology), typically range between nanoseconds and seconds at low temperature. Error rates are typically proportional to the ratio of operating time to decoherence time, hence any operation must be completed much quicker than the decoherence time. 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. An often cited (but rather arbitrary) figure for required error rate in each gate is 10−4. This implies that each gate must be able to perform its task 10,000 times faster than the decoherence time of the system.
Meeting this scalability condition is possible for a wide range of systems. However the use of error correction brings with it the cost of a greatly increased number of required qubits. The number required to factor integers using Shor's algorithm is still polynomial, and thought to be between L4 and L6, where L is the number of bits in the number to be factored. For a 1000 bit number, this implies a need for 1012 to 1018 qubits. Fabrication and control of this large number of qubits is non-trivial for any of the proposed designs.
Practical quantum computers
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
There are a number of practical difficulties in building a quantum computer, and thus far quantum computers have only solved trivial problems. 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.
Further information
- Quantum computing is part of quantum information processing.
- Good general reference:
- arXiv.org e-Print archive - a very complete online archive of research papers.
- Centre for Quantum Computation, University of Cambridge http://cam.qubit.org
- Institute for Quantum Computing, University of Waterloo
- QCL — A Programming Language for Quantum Computers
- Qwiki - A quantum physics wiki devoted to providing technical resources for practicing quantum information scientists.
- QIIC, Imperial College London, includes downloadable courses.
- Quantum computing related companies
- D-Wave Systems - Superconductor-based quantum computers
- id Quantique - Quantum cryptography and Random-number generators
- MagiQ - Quantum cryptography solutions
Articles in category "Quantum Computation"
There are 3 articles in this category.
