Basis
A classical computer has a
memory made up of
bits, where each bit is represented by either a one or a zero. A quantum computer maintains a sequence of
qubits. A single qubit can represent a one, a zero, or any
quantum superposition of those two
qubit states;
[13]:13–16 a pair of qubits can be in any quantum superposition of 4 states,
[13]:16 and three qubits in any superposition of 8 states. In general, a quantum computer with
{\displaystyle n}
qubits can be in an arbitrary superposition of up to
{\displaystyle 2^{n}}
different states simultaneously
[13]:17 (this compares to a normal computer that can only be in
one of these
{\displaystyle 2^{n}}
states at any one time). A quantum computer operates on its qubits using
quantum gatesand
measurement (which also alters the observed state). An
algorithm is composed of a fixed sequence of
quantum logic gates and a problem is encoded by setting the initial values of the qubits, similar to how a classical computer works. The calculation usually ends with a measurement, collapsing the system of qubits into one of the
{\displaystyle 2^{n}}
pure states, where each qubit is zero or one, decomposing into a classical state. The outcome can therefore be at most
{\displaystyle n}
classical bits of information (or, if the algorithm did not end with a measurement, the result is an unobserved quantum state). Quantum algorithms are often probabilistic, in that they provide the correct solution only with a certain known probability.
[14] Note that the term non-deterministic computing must not be used in that case to mean probabilistic (computing), because the term
non-deterministic has a different meaning in computer science.
An example of an implementation of qubits of a quantum computer could start with the use of particles with two
spin states: "down" and "up" (typically written
{\displaystyle |{\downarrow }\rangle }
and
{\displaystyle |{\uparrow }\rangle }
, or
{\displaystyle |0{\rangle }}
and
{\displaystyle |1{\rangle }}
). This is true because any such system can be mapped onto an effective
spin-1/2 system.
Principles of operation
A quantum computer with a given number of qubits is fundamentally different from a classical computer composed of the same number of classical bits. For example, representing the state of an
n-qubit system on a classical computer requires the storage of 2
n complex coefficients, while to characterize the state of a classical
n-bit system it is sufficient to provide the values of the
n bits, that is, only
n numbers. 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 is measured, they will only be found in one of the possible configurations they were in before the measurement. It is generally incorrect to think of a system of qubits as being in one particular state before the 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.
Qubits are made up of controlled particles and the means of control (e.g. devices that trap particles and switch them from one state to another).[15]
To better understand this point, consider a classical computer that operates on a three-bit
register. If the exact state of the register at a given time is not known, it can be described as a probability distribution over the
{\displaystyle 2^{3}=8}
different three-bit strings
000, 001, 010, 011, 100, 101, 110,
and
111. If there is no uncertainty over its state, then it is in exactly one of these states with probability 1. However, if it is a
probabilistic computer, then there is a possibility of it being in any
one of a number of different states.
The state of a three-qubit quantum computer is similarly described by an
eight-dimensional vector
{\displaystyle (a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7})}
(or a one dimensional vector with each vector node holding the amplitude and the state as the bit string of qubits). Here, however, the coefficients
{\displaystyle a_{k}}
are
complex numbers, and it is the sum of the
squares of the coefficients'
absolute values,
{\displaystyle \sum _{i}|a_{i}|^{2}}
, that must equal 1. For each
{\displaystyle k}
, the absolute value squared
{\displaystyle \left|a_{k}\right|^{2}}
gives the probability of the system being found after a measurement in the
{\displaystyle k}
-th state. However, because a complex number encodes not just a magnitude but also a direction in the complex plane, the phase difference between any two coefficients (states) represents a meaningful parameter. This is a fundamental difference between quantum computing and probabilistic classical computing.[16]
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 =
{\displaystyle |a_{0}|^{2}}
, the probability of measuring 001 =
{\displaystyle |a_{1}|^{2}}
, etc.). Thus, measuring a quantum state described by complex coefficients
{\displaystyle (a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7})}
gives the classical probability distribution
{\displaystyle (|a_{0}|^{2},|a_{1}|^{2},|a_{2}|^{2},|a_{3}|^{2},|a_{4}|^{2},|a_{5}|^{2},|a_{6}|^{2},|a_{7}|^{2})}
and we say that the quantum state "collapses" to a classical state as a result of making the measurement.
An eight-dimensional vector can be specified in many different ways depending on what
basis 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 operator.
Ket notation is often used to make the choice of basis explicit. For example, the state
{\displaystyle (a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7})}
in the computational basis can be written as:
{\displaystyle a_{0}\,|000\rangle +a_{1}\,|001\rangle +a_{2}\,|010\rangle +a_{3}\,|011\rangle +a_{4}\,|100\rangle +a_{5}\,|101\rangle +a_{6}\,|110\rangle +a_{7}\,|111\rangle }
where, e.g.,
{\displaystyle |010\rangle =\left(0,0,1,0,0,0,0,0\right)}
The computational basis for a single qubit (two dimensions) is
{\displaystyle |0\rangle =\left(1,0\right)}
and
{\displaystyle |1\rangle =\left(0,1\right)}
.
Using the eigenvectors of the Pauli-x operator, a single qubit is
{\displaystyle |+\rangle ={\tfrac {1}{\sqrt {2}}}\left(1,1\right)}
and
{\displaystyle |-\rangle ={\tfrac {1}{\sqrt {2}}}\left(1,-1\right)}
.
