User:Jaydavidmartin/Quantum computing

Foundations (Quantum Computing)

The prevailing model of quantum computation describes the computation in terms of a network of quantum logic gates that operate on qubits, the quantum analogue to bits.

Qubits

Main article: Qubit

The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers.

Just as the bit is the basic unit of information in classical computation, the quantum bit or qubit is the basic unit of information in quantum computation. In the theory of computation, qubits are represented as mathematical objects, which allows a theory of quantum computation to be constructed independently of the physical realization of quantum bits.

Single qubit

A qubit is represented as a unit vector in the two-dimensional complex Hilbert space ${\textstyle \mathbb {C} ^{2}}$. In particular, it is represented as a linear superpositions of two particular orthonormal basis states, represented in bra–ket notation as $|0\rangle ={\bigl [}{\begin{smallmatrix}1\\0\end{smallmatrix}}{\bigr ]}$ and $|1\rangle ={\bigl [}{\begin{smallmatrix}0\\1\end{smallmatrix}}{\bigr ]}$, corresponding to the two classical bit states 0 and 1, respectively. Hence, the state $|\psi \rangle$ of a qubit is represented mathematically as:

$|\psi \rangle =\alpha |0\rangle +\beta |1\rangle ={\bigl [}{\begin{smallmatrix}\alpha \\\beta \end{smallmatrix}}{\bigr ]}$

where $\alpha$ and $\beta$ are complex probability amplitudes. More precisely, the squares of $\alpha$ and $\beta$ correspond to the probabilities of measuring the qubit to have value 0 or 1. Because of the Born rule, the quantum state of a qubit cannot be precisely measured—that is, the values of $\alpha$ and $\beta$ cannot be precisely determined. Rather, when a qubit is measured the result of the measurement is always 0, with probability $|\alpha |^{2}$, or 1, with probability $|\beta |^{2}$. Because the squares correspond to probabilities, the qubit's state is normalized to length 1, i.e. $|\alpha |^{2}+|\beta |^{2}=1$. What this all means is that unlike a classical bit, which must have state 0 or 1, a qubit can exist in a continuum of states between $|0\rangle$ and $|1\rangle$—at least until the qubit is observed, at which point the qubit is always measured as having either value 0 or 1, with probabilities $|\alpha |^{2}$ and $|\beta |^{2}$, respectively.

Multiple qubits

The single-qubit representation can be extended to multiple qubits using the tensor product. More precisely, the state of ${\textstyle n}$ qubits is a unit vector in the ${\textstyle 2^{n}}$-dimensional Hilbert space ${\textstyle (\mathbb {C} ^{2})^{\otimes n}}$. For example, consider a two-qubit system. This system has four basis states: $|00\rangle$, $|01\rangle$, $|10\rangle$, and $|11\rangle$, where $$|00\rangle =|0\rangle \otimes |0\rangle ={\biggl [}{\begin{smallmatrix}1\\0\\0\\0\end{smallmatrix}}{\biggl ]};\quad |01\rangle =|0\rangle \otimes |1\rangle ={\biggl [}{\begin{smallmatrix}0\\1\\0\\0\end{smallmatrix}}{\biggr ]};\quad |10\rangle =|1\rangle \otimes |0\rangle ={\biggl [}{\begin{smallmatrix}0\\0\\1\\0\end{smallmatrix}}{\biggr ]};\quad |11\rangle =|1\rangle \otimes |1\rangle ={\biggl [}{\begin{smallmatrix}0\\0\\0\\1\end{smallmatrix}}{\biggr ]}.$$

A pair of qubits existing in a superposition of these states is then represented as the state vector:

$|\psi \rangle =\alpha _{00}|00\rangle +\alpha _{01}|01\rangle +\alpha _{10}|10\rangle +\alpha _{11}|11\rangle$.

where ${\textstyle \alpha _{00},\alpha _{01},\alpha _{10},\alpha _{11}}$ are the probability amplitudes.

Compare this to a multiple-bit classical system. For ${\textstyle n}$ classical bits, each state is a binary string in ${\textstyle \{0,1\}^{n}}$ (for example, in a three-bit system the possible states are: 000, 001, 010, 011, 100, 101, 110, and 111). That is, precisely defining the state of an ${\textstyle n}$-bit system requires a state space of dimensionality ${\textstyle n}$, whereas the state of a multiple-qubit requires a state space of dimensionality $2^{n}$. In other words, whereas the dimensionality of the state space corresponding to classical bits grows linearly, the dimensionality of the state space corresponding to quantum bits grows exponentially. More concretely, this means that the number of classical bits required to store the state of an ${\textstyle n}$-qubit system is ${\textstyle 2^{n}}$ (since ${\textstyle n}$ bits have ${\textstyle 2^{n}}$ possible states). This number grows quickly—for ${\textstyle n=500}$, the number of classical bits required to store the state of the 500-qubit system is larger than the estimated number of atoms in the universe.

Quantum logic gates

Main article: Quantum logic gates

Just as classical computation is often described as a network of logic gates operating on bits, so too is quantum computation described as a network of quantum logic gates operating on qubits (as well as a series of measurements). Just as qubits are abstracted as vectors, quantum logic gates are abstracted as unitary matrices.

Any measurement can be deferred to the end of a quantum computation, though this deferment may come at a computational cost. Because of this possibility of deferring a measurement, most quantum circuits depict a network consisting only of quantum logic gates and no measurements.

Single qubit gates

The state of a one-qubit quantum memory can be manipulated by applying quantum logic gates, analogous to how classical memory can be manipulated with classical logic gates. One important gate for both classical and quantum computation is the NOT gate, which can be represented by a matrix $$X:={\begin{pmatrix}0&1\\1&0\end{pmatrix}}.$$ Mathematically, the application of such a logic gate to a quantum state vector is modelled with matrix multiplication. Thus ${\textstyle X|0\rangle =|1\rangle }$ and ${\textstyle X|1\rangle =|0\rangle }$.

The mathematics of single qubit gates can be extended to operate on multiqubit quantum memories in two important ways. One way is simply to select a qubit and apply that gate to the target qubit whilst leaving the remainder of the memory unaffected. Another way is to apply the gate to its target only if another part of the memory is in a desired state. These two choices can be illustrated using another example. The possible states of a two-qubit quantum memory are $$|00\rangle :={\begin{pmatrix}1\\0\\0\\0\end{pmatrix}};\quad |01\rangle :={\begin{pmatrix}0\\1\\0\\0\end{pmatrix}};\quad |10\rangle :={\begin{pmatrix}0\\0\\1\\0\end{pmatrix}};\quad |11\rangle :={\begin{pmatrix}0\\0\\0\\1\end{pmatrix}}.$$ The CNOT gate can then be represented using the following matrix: $$CNOT:={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}}.$$ As a mathematical consequence of this definition, ${\textstyle CNOT|00\rangle =|00\rangle }$, ${\textstyle CNOT|01\rangle =|01\rangle }$, ${\textstyle CNOT|10\rangle =|11\rangle }$, and ${\textstyle CNOT|11\rangle =|10\rangle }$. In other words, the CNOT applies a NOT gate (${\textstyle X}$ from before) to the second qubit if and only if the first qubit is in the state ${\textstyle |1\rangle }$. If the first qubit is ${\textstyle |0\rangle }$, nothing is done to either qubit.

Multiple qubit gates

Any quantum computation can be represented as a network of quantum logic gates from a fairly small family of gates. A choice of gate family that enables this construction is known as a universal gate set. One common such set includes all single-qubit gates as well as the CNOT gate from above. This means any quantum computation can be performed by executing a sequence of single-qubit gates together with CNOT gates. Though this gate set is infinite, it can be replaced with a finite gate set by appealing to the Solovay-Kitaev theorem.

Quantum algorithms

Main article: Quantum algorithms

More information can be found in the following articles: universal quantum computer, Shor's algorithm, Grover's algorithm, Deutsch–Jozsa algorithm, amplitude amplification, quantum Fourier transform, quantum gate, quantum adiabatic algorithm and quantum error correction.