A

**quantum computer** is a device for

computationComputation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

that makes direct use of quantum mechanical phenomena, such as

superpositionQuantum superposition is a fundamental principle of quantum mechanics. It holds that a physical system exists in all its particular, theoretically possible states simultaneously; but, when measured, it gives a result corresponding to only one of the possible configurations.Mathematically, it...

and

entanglementQuantum entanglement occurs when electrons, molecules even as large as "buckyballs", photons, etc., interact physically and then become separated; the type of interaction is such that each resulting member of a pair is properly described by the same quantum mechanical description , which is...

, to perform operations on

dataThe term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...

. Quantum computers are different from traditional computers based on

transistorA transistor is a semiconductor device used to amplify and switch electronic signals and power. It is composed of a semiconductor material with at least three terminals for connection to an external circuit. A voltage or current applied to one pair of the transistor's terminals changes the current...

s. The basic principle behind quantum computation is that quantum properties can be used to represent data and perform operations on these data. A theoretical model is the

quantum Turing machineA quantum Turing machine , also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum...

, also known as the universal quantum computer. Quantum computers share theoretical similarities with non-deterministic and

probabilistic computersIn mathematics and computer science, the probabilistic automaton is a generalization of the non-deterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix or stochastic matrix. Thus, the probabilistic...

, like the ability to be in more than one state simultaneously. The field of quantum computing was first introduced by

Richard FeynmanRichard Phillips Feynman was an American physicist known for his work in the path integral formulation of quantum mechanics, the theory of quantum electrodynamics and the physics of the superfluidity of supercooled liquid helium, as well as in particle physics...

in 1982.

Although 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 (quantum bits). Both practical and theoretical research continues, and many national government and military funding agencies support quantum computing research to develop quantum

computerA computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...

s for both civilian and national security purposes, such as

cryptanalysisCryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...

.

Large-scale quantum computers could be able to solve certain problems much faster than any classical computer by using the best currently known algorithms, like

integer factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

using

Shor's algorithmShor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...

or the simulation of quantum many-body systems. There exist quantum algorithms, such as

Simon's algorithmSimon's algorithm, conceived by Daniel Simon in 1994, is a quantum algorithm which solves a black-box problem exponentially faster than any classical algorithm, including probabilistic algorithms...

, which run faster than any possible probabilistic classical algorithm. Given unlimited resources, a classical computer can simulate an arbitrary quantum algorithm so quantum computation does not violate the

Church–Turing thesisIn computability theory, the Church–Turing thesis is a combined hypothesis about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically computable...

. However, in practice infinite resources are never available and 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

^{500} complex values to be stored.

Nielsen and Chuang point out that "Trying to store all these complex numbers would not be possible on any conceivable classical computer."

## Basis

A classical computer has a memory made up of

bitA bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...

s, where each bit represents either a one or a zero. A quantum computer maintains a sequence of

qubitIn quantum computing, a qubit or quantum bit is a unit of quantum information—the quantum analogue of the classical bit—with additional dimensions associated to the quantum properties of a physical atom....

s. A single qubit can represent a one, a zero, or, crucially, any

quantum superpositionQuantum superposition is a fundamental principle of quantum mechanics. It holds that a physical system exists in all its particular, theoretically possible states simultaneously; but, when measured, it gives a result corresponding to only one of the possible configurations.Mathematically, it...

of these; moreover, a pair of qubits can be in any quantum superposition of 4 states, and three qubits in any superposition of 8. In general a quantum computer with

qubits can be in an arbitrary superposition of up to

different states simultaneously (this compares to a normal computer that can only be in

*one* of these

states at any one time). A quantum computer operates by manipulating those qubits with a fixed sequence of

quantum logic gateIn quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...

s. The sequence of gates to be applied is called a

quantum algorithmIn quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a...

.

An example of an implementation of qubits for a quantum computer could start with the use of particles with two

spinIn quantum mechanics and particle physics, spin is a fundamental characteristic property of elementary particles, composite particles , and atomic nuclei.It is worth noting that the intrinsic property of subatomic particles called spin and discussed in this article, is related in some small ways,...

states: "down" and "up" (typically written

and

, or

and

). But in fact any system possessing an

observableIn physics, particularly in quantum physics, a system observable is a property of the system state that can be determined by some sequence of physical operations. For example, these operations might involve submitting the system to various electromagnetic fields and eventually reading a value off...

quantity

*A* which is

*conserved* under time evolution and such that

*A* has at least two discrete and sufficiently spaced consecutive eigenvalues, is a suitable candidate for implementing a qubit. This is true because any such system can be mapped onto an effective spin-1/2 system.

## Bits vs. qubits

A quantum computer with a given number of qubits is fundamentally different than a classical computer composed of the same number of classical bits. For example, to represent the state of an n-qubit system on a classical computer would require the storage of 2

^{n} complex coefficients. Although this fact may seem to indicate that qubits can hold exponentially more information than their classical counterparts, care must be taken not to overlook the fact that the qubits are only in a probabilistic superposition of all of their states. This means that when the final state of the qubits are measured, they will only be found in one of the possible configurations they were in before measurement. Moreover, it is incorrect to think of the qubits as only being in one particular state before measurement since the fact that they were in a superposition of states before the measurement was made directly affects the possible outcomes of the computation.

For example: Consider first a classical computer that operates on a three-bit

registerIn computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...

. The state of the computer at any time is a probability distribution over the

different three-bit strings

`000, 001, 010, 011, 100, 101, 110, 111`. If it is a deterministic computer, then it is in exactly one of these states with probability 1. However, if it is a

probabilistic computerIn mathematics and computer science, the probabilistic automaton is a generalization of the non-deterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix or stochastic matrix. Thus, the probabilistic...

, then there is a possibility of it being in any

*one* of a number of different states. We can describe this probabilistic state by eight nonnegative numbers

*a*,

*b*,

*c*,

*d*,

*e*,

*f*,

*g*,

*h* (where

*a* = probability computer is in state

`000`,

*b* = probability computer is in state

`001`, etc.). There is a restriction that these probabilities sum to 1.

The state of a three-qubit quantum computer is similarly described by an eight-dimensional vector (

*a*,

*b*,

*c*,

*d*,

*e*,

*f*,

*g*,

*h*), called a

ketBra-ket notation is a standard notation for describing quantum states in the theory of quantum mechanics composed of angle brackets and vertical bars. It can also be used to denote abstract vectors and linear functionals in mathematics...

. However, instead of adding to one, the sum of the

*squares* of the coefficient magnitudes,

, must equal one. Moreover, the coefficients are

complex numberA complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...

s. Since the probability amplitudes of the states are represented with complex numbers, the phase between any two states is a meaningful parameter, which is a key difference between quantum computing and probabilistic classical computing.

If you measure the three qubits, you will observe a three-bit string. The probability of measuring a given string is the squared magnitude of that string's coefficient (i.e., the probability of measuring

`000` =

, the probability of measuring

`001` =

, etc..). Thus, measuring a quantum state described by complex coefficients (

*a*,

*b*,...,

*h*) gives the classical probability distribution

and we say that the quantum state "collapses" to a classical state as a result of making the measurement.

Note that an eight-dimensional vector can be specified in many different ways depending on what

basisIn linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...

is chosen for the space. The basis of bit strings (e.g., 000, 001, ..., 111) is known as the computational basis. Other possible bases are

unit-length, orthogonal vectors and the eigenvectors of the

Pauli-x operatorThe Pauli matrices are a set of three 2 × 2 complex matrices which are Hermitian and unitary. Usually indicated by the Greek letter "sigma" , they are occasionally denoted with a "tau" when used in connection with isospin symmetries...

.

Ket notationBra-ket notation is a standard notation for describing quantum states in the theory of quantum mechanics composed of angle brackets and vertical bars. It can also be used to denote abstract vectors and linear functionals in mathematics...

is often used to make the choice of basis explicit. For example, the state (

*a*,

*b*,

*c*,

*d*,

*e*,

*f*,

*g*,

*h*) in the computational basis can be written as:

- where, e.g.,

The computational basis for a single qubit (two dimensions) is

and

.

Using the eigenvectors of the Pauli-x operator, a single qubit is

and

.

## Operation

While a classical three-bit state and a quantum three-qubit state are both eight-dimensional

vectorIn linear algebra, a coordinate vector is an explicit representation of a vector in an abstract vector space as an ordered list of numbers or, equivalently, as an element of the coordinate space Fn....

s, 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,

, 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 matricesIn mathematics, a stochastic matrix is a matrix used to describe the transitions of a Markov chain. It has found use in probability theory, statistics and linear algebra, as well as computer science...

, which preserve that the probabilities add up to one (i.e., preserve the

L1 normTaxicab geometry, considered by Hermann Minkowski in the 19th century, is a form of geometry in which the usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their coordinates...

). In quantum computation, on the other hand, allowed operations are

unitary matrices, which are effectively rotations (they preserve that the sum of the squares add up to one, the 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

reversibleReversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be...

. (Technically, quantum operations can be probabilistic combinations of unitaries, so quantum computation really does generalize classical computation. See

quantum circuitIn quantum information theory, a quantum circuit is a model for quantum computation in which a computation is a sequence of quantum gates, which are reversible transformations on a quantum mechanical analog of an n-bit register...

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 distributionIn probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....

on the three-bit register to obtain one definite three-bit string, say 000. Quantum mechanically, we

*measure* the three-qubit state, which is equivalent to collapsing the quantum 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, the probability of getting the correct answer can be increased.

For more details on the sequences of operations used for various

quantum algorithmIn quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a...

s, see universal quantum computer,

Shor's algorithmShor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...

,

Grover's algorithmGrover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....

,

Deutsch-Jozsa algorithmThe Deutsch–Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998...

,

amplitude amplificationAmplitude amplification is a technique in quantum computing which generalizes the idea behindthe Grover's search algorithm, and gives rise to a family ofquantum algorithms.It was discovered by Gilles Brassard andPeter Høyer in 1997,...

,

quantum Fourier transformIn quantum computing, the quantum Fourier transform is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform...

,

quantum gateIn quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...

,

quantum adiabatic algorithmAdiabatic quantum computation relies on the adiabatic theorem to do calculations. First, a complex Hamiltonian is found whose ground state describes the solution to the problem of interest. Next, a system with a simple Hamiltonian is prepared and initialized to the ground state. Finally, the...

and

quantum error correctionQuantum error correction is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault-tolerant quantum computation that can deal not only with noise on stored quantum...

.

## Potential

Integer factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of few

prime numberA prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

s (e.g., products of two 300-digit primes). By comparison, a quantum computer could efficiently solve this problem using

Shor's algorithmShor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...

to find its factors. This ability would allow a quantum computer to decrypt many of the

cryptographicCryptography is the practice and study of techniques for secure communication in the presence of third parties...

systems in use today, in the sense that there would be a polynomial time (in the number of digits of the integer) algorithm for solving the problem. In particular, most of the popular public key ciphers are based on the difficulty of factoring integers (or the related

discrete logarithmIn mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

problem, which can also be solved by Shor's algorithm), including forms of RSA. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would have significant ramifications for electronic privacy and security.

However, other existing cryptographic algorithms do not appear to be broken by these algorithms. Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the

McEliece cryptosystemIn cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process...

based on a problem in

coding theoryCoding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

.

Lattice based cryptosystemsLattice-based cryptography is the generic term for asymmetric cryptographic primitives based on lattices.-History:Lattices were first studied by mathematicians Joseph Louis Lagrange and Carl Friedrich Gauss. Lattices have been used recently in computer algorithms and in cryptanalysis...

are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the

dihedralIn mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...

hidden subgroup problemThe hidden subgroup problem is a topic of research in mathematics and theoretical computer science.-Problem statement:Given a group G, a subgroup H ≤ G, and a set X, we say a function f : G → X hides the subgroup H if for all g1, g2 ∈ G,f = f if and only if g1H = g2H for the cosets of...

, which would break many lattice based cryptosystems, is a well-studied open problem. It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires roughly 2

^{n/2} invocations of the underlying cryptographic algorithm, compared with roughly 2

^{n} in the classical case, meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search (see Key size).

Quantum cryptographyQuantum key distribution uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages...

could potentially fulfill some of the functions of public key cryptography.

Besides factorization and discrete logarithms, quantum algorithms offering a more than polynomial speedup over the best known classical algorithm have been found for several problems, including the simulation of quantum physical processes from chemistry and solid state physics, the approximation of

Jones polynomials, and solving

Pell's equationPell's equation is any Diophantine equation of the formx^2-ny^2=1\,where n is a nonsquare integer. The word Diophantine means that integer values of x and y are sought. Trivially, x = 1 and y = 0 always solve this equation...

. No mathematical proof has been found that shows that an equally fast classical algorithm cannot be discovered, although this is considered unlikely. For some problems, quantum computers offer a polynomial speedup. The most well-known example of this is

*quantum database search*, which can be solved by

Grover's algorithmGrover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....

using quadratically fewer queries to the database than are required by classical algorithms. In this case the advantage is provable. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.

Consider a problem that has these four properties:

- The only way to solve it is to guess answers repeatedly and check them,
- The number of possible answers to check is the same as the number of inputs,
- Every possible answer takes the same amount of time to check, and
- There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.

An example of this is a

password crackerPassword cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password...

that attempts to guess the password for an

encryptedIn cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...

file (assuming that the password has a maximum possible length).

For problems with all four properties, the time for a quantum computer to solve this will be proportional to the square root of the number of inputs. That can be a very large speedup, reducing some problems from years to seconds. It can be used to attack symmetric ciphers such as

Triple DESIn cryptography, Triple DES is the common name for the Triple Data Encryption Algorithm block cipher, which applies the Data Encryption Standard cipher algorithm three times to each data block....

and

AESAdvanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...

by attempting to guess the secret key.

Grover's algorithmGrover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....

can also be used to obtain a quadratic speed-up over a brute-force search for a class of problems known as

NP-completeIn computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

.

Since chemistry and nanotechnology rely on understanding quantum systems, and such systems are impossible to simulate in an efficient manner classically, many believe

quantum simulationA universal quantum simulator is a quantum computer proposed by Richard Feynman in 1982.Feynman showed that a classical Turing machine would presumably experience an exponential slowdown when simulating quantum phenomena, while his hypothetical universal quantum simulator would not. David Deutsch...

will be one of the most important applications of quantum computing.

There are a number of technical challenges in building a large-scale quantum computer, and thus far quantum computers have yet to solve a problem faster than a classical computer. 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;
- universal gate set;
- qubits can be read easily.

### Quantum decoherence

One of the greatest challenges is controlling or removing

quantum decoherenceIn quantum mechanics, quantum decoherence is the loss of coherence or ordering of the phase angles between the components of a system in a quantum superposition. A consequence of this dephasing leads to classical or probabilistically additive behavior...

. This usually means isolating the system from its environment as interactions with the external world causes the system to decohere. This effect is irreversible, as it is non-unitary, and is usually something that should be highly controlled, if not avoided. Decoherence times for candidate systems, in particular the transverse relaxation time T

_{2} (for

NMRNuclear magnetic resonance is a physical phenomenon in which magnetic nuclei in a magnetic field absorb and re-emit electromagnetic radiation...

and MRI technology, also called the

*dephasing time*), typically range between nanoseconds and seconds at low temperature.

These issues are more difficult for optical approaches as the timescales are orders of magnitude shorter and an often-cited approach to overcoming them is optical pulse shaping. Error rates are typically proportional to the ratio of operating time to decoherence time, hence any operation must be completed much more quickly than the decoherence time.

If the error rate is small enough, it is thought to be 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 figure for required error rate in each gate is 10

^{−4}. This implies that each gate must be able to perform its task in one 10,000th of 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

*L* and

*L*^{2}, where

*L* is the number of bits in the number to be factored; error correction algorithms would inflate this figure by an additional factor of

*L*. For a 1000-bit number, this implies a need for about 10

^{4} qubits without error correction. With error correction, the figure would rise to about 10

^{7} qubits. Note that computation time is about

or about

steps and on 1 M

HzThe hertz is the SI unit of frequency defined as the number of cycles per second of a periodic phenomenon. One of its most common uses is the description of the sine wave, particularly those used in radio and audio applications....

, about 10

secondThe second is a unit of measurement of time, and is the International System of Units base unit of time. It may be measured using a clock....

s.

A very different approach to the stability-decoherence problem is to create a

topological quantum computerA topological quantum computer is a theoretical quantum computer that employs two-dimensional quasiparticles called anyons, whose world lines cross over one another to form braids in a three-dimensional spacetime . These braids form the logic gates that make up the computer...

with

anyonIn physics, an anyon is a type of particle that occurs only in two-dimensional systems. It is a generalization of the fermion and boson concept.-From theory to reality:...

s, quasi-particles used as threads and relying on

braid theoryIn topology, a branch of mathematics, braid theory is an abstract geometric theory studying the everyday braid concept, and some generalizations. The idea is that braids can be organized into groups, in which the group operation is 'do the first braid on a set of strings, and then follow it with a...

to form stable logic gates.

## Developments

There are a number of quantum computing

*models*, distinguished by the basic elements in which the computation is decomposed. The four main models of practical importance are

- the
*quantum gate array*In quantum information theory, a quantum circuit is a model for quantum computation in which a computation is a sequence of quantum gates, which are reversible transformations on a quantum mechanical analog of an n-bit register...

(computation decomposed into sequence of few-qubit quantum gateIn quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...

s),
- the
*one-way quantum computer*The one-way or measurement based quantum computer is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it...

(computation decomposed into sequence of one-qubit measurements applied to a highly entangled initial state (cluster stateIn quantum information and quantum computing, a cluster state is a type of highly entangled state of multiple qubits. Cluster states are generated in lattices of qubits with Ising type interactions. A cluster C is a connected subset of a d-dimensional lattice, and a cluster state is a pure state of...

)),
- the
*adiabatic quantum computer*Adiabatic quantum computation relies on the adiabatic theorem to do calculations. First, a complex Hamiltonian is found whose ground state describes the solution to the problem of interest. Next, a system with a simple Hamiltonian is prepared and initialized to the ground state. Finally, the...

(computation decomposed into a slow continuous transformation of an initial HamiltonianIn quantum mechanics, the Hamiltonian H, also Ȟ or Ĥ, is the operator corresponding to the total energy of the system. Its spectrum is the set of possible outcomes when one measures the total energy of a system...

into a final Hamiltonian, whose ground states contains the solution),
- and the topological quantum computer
A topological quantum computer is a theoretical quantum computer that employs two-dimensional quasiparticles called anyons, whose world lines cross over one another to form braids in a three-dimensional spacetime . These braids form the logic gates that make up the computer...

(computation decomposed into the braiding of anyonIn physics, an anyon is a type of particle that occurs only in two-dimensional systems. It is a generalization of the fermion and boson concept.-From theory to reality:...

s in a 2D lattice)

The

*Quantum Turing machine*A quantum Turing machine , also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a very simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum...

is theoretically important but direct implementation of this model is not pursued. All four models of computation have been shown to be equivalent to each other in the sense that each can simulate the other with no more than polynomial overhead.

For physically implementing a quantum computer, many different candidates are being pursued, among them (distinguished by the physical system used to realize the qubits):

- Superconductor-based quantum computers (including SQUID
A SQUID is a very sensitive magnetometer used to measure extremely weak magnetic fields, based on superconducting loops containing Josephson junctions....

-based quantum computers) (qubit implemented by the state of small superconducting circuits (Josephson junctions))
- Trapped ion quantum computer (qubit implemented by the internal state of trapped ions)
- Optical lattice
An optical lattice is formed by the interference of counter-propagating laser beams, creating a spatially periodic polarization pattern. The resulting periodic potential may trap neutral atoms via the Stark shift. Atoms are cooled and congregate in the locations of potential minima...

s (qubit implemented by internal states of neutral atoms trapped in an optical lattice)
- electrically-defined or self-assembled quantum dot
A quantum dot is a portion of matter whose excitons are confined in all three spatial dimensions. Consequently, such materials have electronic properties intermediate between those of bulk semiconductors and those of discrete molecules. They were discovered at the beginning of the 1980s by Alexei...

s (e.g. the Loss-DiVincenzo quantum computerThe Loss-DiVincenzo quantum computer is a scalable semiconductor-based quantum computer proposed by Daniel Loss and David P. DiVincenzo in 1997. The proposal was to use as qubits the intrinsic spin-1/2 degree of freedom of individual electrons confined to quantum dots...

or ) (qubit given by the spin states of an electron trapped in the quantum dot)
- Quantum dot
A quantum dot is a portion of matter whose excitons are confined in all three spatial dimensions. Consequently, such materials have electronic properties intermediate between those of bulk semiconductors and those of discrete molecules. They were discovered at the beginning of the 1980s by Alexei...

charge based semiconductor quantum computer (qubit is the position of an electron inside a double quantum dot)
- Nuclear magnetic resonance
Nuclear magnetic resonance is a physical phenomenon in which magnetic nuclei in a magnetic field absorb and re-emit electromagnetic radiation...

on molecules in solution (liquid-state NMR) (qubit provided by nuclear spins within the dissolved molecule)
- Solid-state NMR Kane quantum computer
The Kane quantum computer is a proposal for a scalable quantum computer proposed by Bruce Kane in 1998, then at the University of New South Wales. Often thought of as a hybrid between quantum dot and NMR quantum computers, the Kane computer is based on an array of individual phosphorus donor atoms...

s (qubit realized by the nuclear spin state of phosphorusPhosphorus is the chemical element that has the symbol P and atomic number 15. A multivalent nonmetal of the nitrogen group, phosphorus as a mineral is almost always present in its maximally oxidized state, as inorganic phosphate rocks...

donorAn electron donor is a chemical entity that donates electrons to another compound. It is a reducing agent that, by virtue of its donating electrons, is itself oxidized in the process....

s in siliconSilicon is a chemical element with the symbol Si and atomic number 14. A tetravalent metalloid, it is less reactive than its chemical analog carbon, the nonmetal directly above it in the periodic table, but more reactive than germanium, the metalloid directly below it in the table...

)
- Electrons-on-helium
Helium is the chemical element with atomic number 2 and an atomic weight of 4.002602, which is represented by the symbol He. It is a colorless, odorless, tasteless, non-toxic, inert, monatomic gas that heads the noble gas group in the periodic table...

quantum computers (qubit is the electron spin)
- Cavity quantum electrodynamics
Cavity quantum electrodynamics is the study of the interaction between light confined in a reflective cavity and atoms or other particles, under conditions where the quantum nature of light photons is significant...

(CQED) (qubit provided by the internal state of atoms trapped in and coupled to high-finesseIn contract bridge and similar games, a finesse is a technique which allows one to promote tricks based on a favorable position of one or more cards in the hands of the opponents....

cavities)
- Molecular magnet
- Fullerene
A fullerene is any molecule composed entirely of carbon, in the form of a hollow sphere, ellipsoid, or tube. Spherical fullerenes are also called buckyballs, and they resemble the balls used in association football. Cylindrical ones are called carbon nanotubes or buckytubes...

-based ESRElectron paramagnetic resonance or electron spin resonance spectroscopyis a technique for studying chemical species that have one or more unpaired electrons, such as organic and inorganic free radicals or inorganic complexes possessing a transition metal ion...

quantum computer (qubit based on the electronic spin of atoms or molecules encased in fullerene structures)
- Optics-based quantum computer (Quantum optics
Quantum optics is a field of research in physics, dealing with the application of quantum mechanics to phenomena involving light and its interactions with matter.- History of quantum optics :...

) (qubits realized by appropriate states of different modesA normal mode of an oscillating system is a pattern of motion in which all parts of the system move sinusoidally with the same frequency and with a fixed phase relation. The frequencies of the normal modes of a system are known as its natural frequencies or resonant frequencies...

of the electromagnetic fieldAn electromagnetic field is a physical field produced by moving electrically charged objects. It affects the behavior of charged objects in the vicinity of the field. The electromagnetic field extends indefinitely throughout space and describes the electromagnetic interaction...

, e.g.)
- Diamond-based quantum computer (qubit realized by the electronic or nuclear spin of Nitrogen-vacancy center
The nitrogen-vacancy center is one of numerous point defects in diamond. Its most explored and useful property is photoluminescence, which can be easily detected from an individual N-V center...

s in diamond)
- Bose–Einstein condensate-based quantum computer
A Bose–Einstein condensate is a state of matter of a dilute gas of weakly interacting bosons confined in an external potential and cooled to temperatures very near absolute zero . Under such conditions, a large fraction of the bosons occupy the lowest quantum state of the external potential, at...

- Transistor-based quantum computer – string quantum computers with entrainment of positive holes using an electrostatic trap
- Rare-earth-metal-ion-doped inorganic crystal based quantum computers (qubit realized by the internal electronic state of dopant
A dopant, also called a doping agent, is a trace impurity element that is inserted into a substance in order to alter the electrical properties or the optical properties of the substance. In the case of crystalline substances, the atoms of the dopant very commonly take the place of elements that...

s in optical fiberAn optical fiber is a flexible, transparent fiber made of a pure glass not much wider than a human hair. It functions as a waveguide, or "light pipe", to transmit light between the two ends of the fiber. The field of applied science and engineering concerned with the design and application of...

s)

The large number of candidates demonstrates that the topic, in spite of rapid progress, is still in its infancy. But at the same time, there is also a vast amount of flexibility.

In 2005, researchers at the

University of MichiganThe University of Michigan is a public research university located in Ann Arbor, Michigan in the United States. It is the state's oldest university and the flagship campus of the University of Michigan...

built a semiconductor chip that functioned as an

ion trapAn ion trap is a combination of electric or magnetic fields that captures ions in a region of a vacuum system or tube. Ion traps have a number of scientific uses such as mass spectrometery and trapping ions while the ion's quantum state is manipulated...

. Such devices, produced by standard

lithographyLithography is a method for printing using a stone or a metal plate with a completely smooth surface...

techniques, may point the way to scalable quantum computing tools. An improved version was made in 2006.

In 2009, researchers at

Yale UniversityYale University is a private, Ivy League university located in New Haven, Connecticut, United States. Founded in 1701 in the Colony of Connecticut, the university is the third-oldest institution of higher education in the United States...

created the first rudimentary solid-state quantum processor. The two-

qubitIn quantum computing, a qubit or quantum bit is a unit of quantum information—the quantum analogue of the classical bit—with additional dimensions associated to the quantum properties of a physical atom....

superconducting chip was able to run elementary algorithms. Each of the two artificial atoms (or qubits) were made up of a billion aluminum

atomThe atom is a basic unit of matter that consists of a dense central nucleus surrounded by a cloud of negatively charged electrons. The atomic nucleus contains a mix of positively charged protons and electrically neutral neutrons...

s but they acted like a single one that could occupy two different energy states.

Another team, working at the

University of BristolThe University of Bristol is a public research university located in Bristol, United Kingdom. One of the so-called "red brick" universities, it received its Royal Charter in 1909, although its predecessor institution, University College, Bristol, had been in existence since 1876.The University is...

, also created a

siliconSilicon is a chemical element with the symbol Si and atomic number 14. A tetravalent metalloid, it is less reactive than its chemical analog carbon, the nonmetal directly above it in the periodic table, but more reactive than germanium, the metalloid directly below it in the table...

-based quantum computing chip, based on

quantum opticsQuantum optics is a field of research in physics, dealing with the application of quantum mechanics to phenomena involving light and its interactions with matter.- History of quantum optics :...

. The team was able to run

Shor's algorithmShor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...

on the chip.

Further developments were made in 2010.

Springer publishes a journal ("Quantum Information Processing") devoted to the subject.

A team of scientists from Australia and Japan have finally made a breakthrough in

quantum teleportationQuantum teleportation, or entanglement-assisted teleportation, is a process by which a qubit can be transmitted exactly from one location to another, without the qubit being transmitted through the intervening space...

. They have successfully transferred a complex set of quantum data with full transmission integrity achieved. Also the qubits being destroyed in one place but instantaneously resurrected in another, without affecting their superpositions.

In 2011,

D-Wave SystemsD-Wave Systems, Inc. is a quantum computing company, based in Burnaby, British Columbia. On May 11, 2011, D-Wave System announced D-Wave One, labeled "the world's first commercially available quantum computer," and also referred to it as an adiabatic quantum computer using quantum annealing to...

announced the first commercial quantum annealer on the market by the name D-Wave One. The company claims this system uses a 128 qubit processor chipset. On May 25, 2011 D-Wave announced that

Lockheed MartinLockheed Martin is an American global aerospace, defense, security, and advanced technology company with worldwide interests. It was formed by the merger of Lockheed Corporation with Martin Marietta in March 1995. It is headquartered in Bethesda, Maryland, in the Washington Metropolitan Area....

Corporation entered into an agreement to purchase a D-Wave One system. The week of October 28th, 2011 USC became the first academic institution to house a commercial quantum computer. The D-Wave One Adiabatic Quantum Computer is housed at the USC Viterbi Information Sciences Institute in Marina del Rey. The $10-million computer was purchased by Lockheed Martin Corporation and hopes are to harness the technology to solve relevant problems that are hard to address through established methods in a "cost-effective" manner.

During the same year, researchers working at the

University of BristolThe University of Bristol is a public research university located in Bristol, United Kingdom. One of the so-called "red brick" universities, it received its Royal Charter in 1909, although its predecessor institution, University College, Bristol, had been in existence since 1876.The University is...

created an all-bulk optics system able to run an iterative version of

Shor's algorithmShor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...

. They successfully managed to factorize 21.

## Relation to computational complexity theory

The class of problems that can be efficiently solved by quantum computers is called

BQPIn computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...

, for "bounded error, quantum, polynomial time". Quantum computers only run probabilistic algorithms, so BQP on quantum computers is the counterpart of BPP ("bounded error, probabilistic, polynomial time") on classical computers. It is defined as the set of problems solvable with a polynomial-time algorithm, whose probability of error is bounded away from one half. A quantum computer is said to "solve" a problem if, for every instance, its answer will be right with high probability. If that solution runs in polynomial time, then that problem is in BQP.

BQP is contained in the complexity class

*#P*In computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...

(or more precisely in the associated class of decision problems

*P*^{#P}), which is a subclass of

PSPACEIn computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...

.

BQP is suspected to be disjoint from

NP-completeIn computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

and a strict superset of

PIn computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...

, but that is not known. Both

integer factorizationIn number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.

Possibilities of the quantum computer to accelerate classical algorithms has rigid limits — upper bounds of quantum computation's complexity. The overwhelming part of classical calculations cannot be accelerated on the quantum computer. A similar fact takes place for particular computational tasks, like the search problem, for which Grover's algorithm is optimal.

Although quantum computers may be faster than classical computers, those described above can't solve any problems that classical computers can't solve, given enough time and memory (however, those amounts might be practically infeasible). A

Turing machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

can simulate these quantum computers, so such a quantum computer could never solve an

undecidable problemIn computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....

like the

halting problemIn computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...

. The existence of "standard" quantum computers does not disprove the

Church–Turing thesisIn computability theory, the Church–Turing thesis is a combined hypothesis about the nature of functions whose values are effectively calculable; in more modern terms, algorithmically computable...

. It has been speculated that theories of

quantum gravityQuantum gravity is the field of theoretical physics which attempts to develop scientific models that unify quantum mechanics with general relativity...

, such as

M-theoryIn theoretical physics, M-theory is an extension of string theory in which 11 dimensions are identified. Because the dimensionality exceeds that of superstring theories in 10 dimensions, proponents believe that the 11-dimensional theory unites all five string theories...

or

loop quantum gravityLoop quantum gravity , also known as loop gravity and quantum geometry, is a proposed quantum theory of spacetime which attempts to reconcile the theories of quantum mechanics and general relativity...

, may allow even faster computers to be built. Currently,

*defining* computation in such theories is an open problem due to the

*problem of time*, i.e. there currently exists no obvious way to describe what it means for an observer to submit input to a computer and later receive output.

## See also

- Normal mode
A normal mode of an oscillating system is a pattern of motion in which all parts of the system move sinusoidally with the same frequency and with a fixed phase relation. The frequencies of the normal modes of a system are known as its natural frequencies or resonant frequencies...

- Chemical computer
A chemical computer, also called reaction-diffusion computer, BZ computer or gooware computer is an unconventional computer based on a semi-solid chemical "soup" where data is represented by varying concentrations of chemicals. The computations are performed by naturally occurring chemical...

- DNA computer
- Photonic computing
Today's computers use the movement of electrons in-and-out of transistors to do logic. Optical or Photonic computing is intended to use photons or light particles, produced by lasers or diodes, in place of electrons...

- Post-quantum cryptography
Post-quantum cryptography refers to research on cryptographic primitives that are not breakable using quantum computers...

- Quantum bus
A quantum bus is a device which can be used to store or transfer information between independent qubits in a quantum computer, or combine two qubits into a superposition. The concept was first demonstrated by researchers at Yale University and the National Institute of Standards and Technology in...

- Timeline of quantum computing
-1970s:* 1970 – Stephen Wiesner invents conjugate coding.* 1973 – Alexander Holevo publishes a paper showing that n qubits cannot carry more than n classical bits of information . Charles H. Bennett shows that computation can be done reversibly.* 1975 – R. P...

- List of emerging technologies
- Quantum gate
In quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...

### General references

}}

- David P. DiVincenzo (2000). "The Physical Implementation of Quantum Computation".
*Experimental Proposals for Quantum Computation*. Table 1 lists switching and dephasing times for various systems.
- David P. DiVincenzo (2000). "The Physical Implementation of Quantum Computation".
*Experimental Proposals for Quantum Computation*. .
- Sam Lomonaco Four Lectures on Quantum Computing given at Oxford University in July 2006
- C. Adami, N.J. Cerf. (1998). "Quantum computation with linear optics". .