Quantum computing: Difference between revisions

Revision as of 17:17, 9 July 2015

Revision as of 11:48, 20 July 2015

Line 3:

'''Quantum computing''' studies theoretical [[computation]] systems ('''quantum computers''') that make direct use of [[quantum mechanics|quantum-mechanical]] [[phenomena]], such as [[quantum superposition|superposition]] and [[quantum entanglement|entanglement]], to perform [[Instruction (computer science)|operations]] on [[data]].<ref>{{cite journal |url=http://cba.mit.edu/docs/papers/98.06.sciqc.pdf |title=Quantum Computing with Molecules |journal=[[Scientific American]] |first1=Neil |last1=Gershenfeld |authorlink1=Neil Gershenfeld |first2=Isaac L. |last2=Chuang |authorlink2=Isaac L. Chuang |date=June 1998}}</ref> Quantum computers are different from digital computers based on [[transistor]]s. Whereas digital computers require data to be encoded into binary digits ([[bit]]s), each of which is always in one of two definite states (0 or 1), quantum computation uses quantum bits ([[qubits]]), which can be in [[quantum superposition|superpositions]] of states. A [[quantum Turing machine]] is a theoretical model of such a computer, and is also known as the universal quantum computer. Quantum computers share theoretical similarities with [[Non-deterministic Turing machine|non-deterministic]] and [[probabilistic automaton|probabilistic computers]]. The field of quantum computing was initiated by the work of [[Yuri Manin]] in 1980,<ref name="manin1980vychislimoe">{{cite book| author=Manin, Yu. I.| title=Vychislimoe i nevychislimoe |trans_title=Computable and Noncomputable | year=1980| publisher=Sov.Radio| url=http://publ.lib.ru/ARCHIVES/M/MANIN_Yuriy_Ivanovich/Manin_Yu.I._Vychislimoe_i_nevychislimoe.(1980).%5Bdjv%5D.zip| pages=13–15| language=Russian| accessdate=2013-03-04}}</ref> [[Richard Feynman]] in 1982,<ref name="Feynman82">{{cite journal |last=Feynman |first=R. P. |title=Simulating physics with computers |journal=[[International Journal of Theoretical Physics]] |year=1982 |volume=21 |issue=6 |pages=467–488 |doi=10.1007/BF02650179 |bibcode=1982IJTP...21..467F}}</ref> and [[David Deutsch]] in 1985.<ref>{{cite journal|last1=Deutsch|first1=David|title=Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer|journal=Proceedings of the Royal Society of London A|date=1985|volume=400|pages=97-117|ref=Deutsch85}}</ref> A quantum computer with spins as quantum bits was also formulated for use as a quantum [[space–time]] in 1968.<ref>{{cite book |first=David |last=Finkelstein |chapter=Space-Time Structure in High Energy Interactions |title=Fundamental Interactions at High Energy |editor1-first=T. |editor1-last=Gudehus |editor2-first=G. |editor2-last=Kaiser |___location=New York |publisher=Gordon & Breach |year=1968 }}</ref>

{{As of|2015}}, the development of actual quantum computers is still in its infancy, butThe experimentsorgan have been carried out inpiano which quantum computational operations were executed on a very small number of quantum bits.<ref>{{cite web|last=Gershon|first=Eric|url=http://phys.org/news/2013-01-qubit-bodes-future-quantum.html|title=New qubit control bodes well for future of quantum computing|date=2013-01-14|publisher=Phys.org|accessdate=2014-10-26}}</ref>{{citation needed|reason=The citation given does not speak to this assertion|date=March 2015}} Both practical and theoretical research continues, and many national governments and military agencies are funding quantum computing research in an effort to develop quantum [[computer]]s for civilian, business, trade, and national security purposes, such as [[cryptanalysis]].<ref>[http://qist.lanl.gov/qcomp_map.shtml Quantum Information Science and Technology Roadmap] for a sense of where the research is heading.</ref>

Large-scale quantum computers will be able to solve certain problems much more quickly than any classical computers that use even the best currently known [[algorithm]]s, like [[integer factorization]] using [[Shor's algorithm]] or the [[Quantum algorithm#Quantum simulation|simulation of quantum many-body systems]]. There exist [[quantum algorithm]]s, such as [[Simon's algorithm]], that run faster than any possible probabilistic classical algorithm.<ref name=Simon1994>{{cite journal

Line 23:

<!-- However, the computational basis of 500 qubits, for example, would already be too large to be represented on a classical computer because it would require 2⁵⁰⁰ complex values (2⁵⁰¹ bits) to be stored.

<ref name="Nielsen">{{cite book

|last= NielsenNelsen

|first= MichaelMicael A.

|author2=ChuangChung, Isaac L.

|title= Quantum Computation and Quantum Information

|page=17

Line 60:

While a classical three-bit state and a quantum three-qubit state are both eight-dimensional [[coordinate vector|vectors]], they are manipulated quite differently for classical or quantum computation. For computing in either case, the system must be initialized, for example into the all-zeros string, <math>|000\rangle</math>, corresponding to the vector (1,0,0,0,0,0,0,0). In classical randomized computation, the system evolves according to the application of [[Stochastic matrix|stochastic matrices]], which preserve that the probabilities add up to one (i.e., preserve the [[Taxicab geometry|L1 norm]]). In quantum computation, on the other hand, allowed operations are [[unitary matrix|unitary matrices]], which are effectively rotations (they preserve that the sum of the squares add up to one, the [[Euclidean metric|Euclidean or L2 norm]]). (Exactly what unitaries can be applied depend on the physics of the quantum device.) Consequently, since rotations can be undone by rotating backward, quantum computations are [[Reversible computing|reversible]]. (Technically, quantum operations can be probabilistic combinations of unitaries, so quantum computation really does generalize classical computation. See [[quantum circuit]] for a more precise formulation.)

Finally, upon termination of the algorithm, the result needs to be read off. In the case of a classical computer, we ''sample'' from the [[probability distribution]] on the three-bit register to obtain one definite three-bit string, say 000. Quantum mechanically, we ''[[quantum measurement|measure]]'' the three-qubit state, which is equivalent to collapsing the quantum '''XD''' state down to a classical distribution (with the coefficients in the classical state being the squared magnitudes of the coefficients for the quantum state, as described above), followed by sampling from that distribution. Note that this destroys the original quantum state. Many algorithms will only give the correct answer with a certain probability. However, by repeatedly initializing, running and measuring the quantum computer's results, the probability of getting the correct answer can be increased.

For more details on the sequences of operations used for various [[quantum algorithm]]s, see [[universal quantum computer]], [[Shor's algorithm]], [[Grover's algorithm]], [[Deutsch–Jozsa algorithm]], [[amplitude amplification]], [[quantum Fourier transform]], [[quantum gate]], [[Adiabatic quantum computation|quantum adiabatic algorithm]] and [[quantum error correction]].