Computer engineers typically describe a
modern computer's operation in terms of
classical electrodynamics. In these "classical" computers, some components (such as
semiconductors and
random number generators) may rely on quantum behavior; however, because they are not
isolated from their environment, any
quantum information eventually quickly
decoheres. While
programmers may depend on
probability theory when designing a
randomized algorithm, quantum-mechanical notions such as
superposition and
wave interference are largely irrelevant in
program analysis.
Quantum programs, in contrast, rely on precise control of
coherent quantum systems. Physicists
describe these systems mathematically using
linear algebra.
Complex numbers model
probability amplitudes,
vectors model
quantum states, and
matrices model the operations that can be performed on these states. Programming a quantum computer is then a matter of
composing operations in such a way that the resulting program computes a useful result in theory and is implementable in practice. As physicist
Charlie Bennett describes the relationship between quantum and classical computers,
Quantum information Just as the bit is the basic concept of classical information theory, the
qubit is the fundamental unit of
quantum information. The same term
qubit is used to refer to an abstract mathematical model and to any physical system that is represented by that model. A classical bit, by definition, exists in either of two physical states, which can be denoted 0 and 1. A qubit is also described by a state, and two states, often written |0\rangle and |1\rangle, serve as the quantum counterparts of the classical states 0 and 1. However, the quantum states |0\rangle and |1\rangle belong to a
vector space, meaning that they can be multiplied by constants and added together, and the result is again a valid quantum state. Such a combination is known as a
superposition of |0\rangle and |1\rangle. A two-dimensional
vector mathematically represents a qubit state. Physicists typically use
bra–ket notation for quantum mechanical
linear algebra, writing |\psi\rangle for a vector labeled \psi. Because a qubit is a two-state system, any qubit state takes the form \alpha|0\rangle+\beta|1\rangle, where |0\rangle and |1\rangle are the standard
basis states, and \alpha and \beta are the
probability amplitudes, which are in general
complex numbers. If either \alpha or \beta is zero, the qubit is effectively a classical bit; when both are nonzero, the qubit is in superposition. Such a
quantum state vector behaves similarly to a (classical)
probability vector, with one key difference: unlike probabilities, probability are not necessarily positive numbers. Negative amplitudes allow for destructive wave interference. When a qubit is
measured in the
standard basis, the result is a classical bit. The
Born rule describes the
norm-squared correspondence between amplitudes and probabilitieswhen measuring a qubit \alpha|0\rangle+\beta|1\rangle, the state
collapses to |0\rangle with probability |\alpha|^2, or to |1\rangle with probability |\beta|^2. Any valid qubit state has coefficients \alpha and \beta such that |\alpha|^2+|\beta|^2 = 1. As an example, measuring the qubit 1/\sqrt {2}|0\rangle+1/\sqrt{2}|1\rangle would produce either |0\rangle or |1\rangle with equal probability. Two particularly important superposition states are the plus state |+\rangle = 1/\sqrt{2}|0\rangle + 1/\sqrt{2}|1\rangle and the minus state |-\rangle = 1/\sqrt{2}|0\rangle - 1/\sqrt{2}|1\rangle. While both yield outcomes 0 and 1 with equal probability upon standard basis measurement, they behave differently under operations such as the
Hadamard gate—which maps |0\rangle \leftrightarrow |+\rangle and |1\rangle \leftrightarrow |-\rangle—demonstrating that relative phase differences carry meaningful quantum information. Each additional qubit doubles the
dimension of the
state space. As an example, the vector represents a two-qubit state, a
tensor product of the qubit with the qubit . This vector inhabits a four-dimensional
vector space spanned by the basis vectors , , , and . In general, the vector space for an -qubit system is -dimensional, and this makes it challenging for a classical computer to simulate a quantum one: representing a 100-qubit system requires storing classical values.
Unitary operators The state of this 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 modeled with
matrix multiplication. Thus : X|0\rangle = |1\rangle and X|1\rangle = |0\rangle. The mathematics of single-qubit gates can be extended to operate on multi-qubit quantum memories in two important ways. One way is simply to select a qubit and apply that gate to the target qubit while 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
controlled NOT (CNOT) gate can then be represented using the following matrix: \operatorname{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, \operatorname{CNOT}|00\rangle = |00\rangle, \operatorname{CNOT}|01\rangle = |01\rangle, \operatorname{CNOT}|10\rangle = |11\rangle, and \operatorname{CNOT}|11\rangle = |10\rangle. In other words, the CNOT applies a NOT gate (X from before) to the second qubit if and only if the first qubit is in the state |1\rangle. If the first qubit is |0\rangle, nothing is done to either qubit. In summary, quantum computation can be described as a network of quantum logic gates and measurements. However, any
measurement can be deferred to the end of quantum computation, though this deferment may come at a computational cost, so most
quantum circuits depict a network consisting only of quantum logic gates and no measurements.
Quantum parallelism Quantum parallelism is the heuristic that quantum computers can be thought of as evaluating a function for multiple input values simultaneously. This can be achieved by preparing a quantum system in a superposition of input states and applying a unitary transformation that encodes the function to be evaluated. The resulting state encodes the function's output values for all input values in the superposition, enabling the simultaneous computation of multiple outputs. This property is key to the speedup of many quantum algorithms. However, "parallelism" in this sense is insufficient to speed up a computation, because the measurement at the end of the computation gives only one value. To be useful, a quantum algorithm must also incorporate some other conceptual ingredient.
Quantum programming There are multiple
models of computation for quantum computing, distinguished by the basic elements in which the computation is decomposed.
Gate array from
more primitive gates|upright=1.15 A
quantum gate array decomposes computation into a sequence of few-qubit
quantum gates. A quantum computation can be described as a network of quantum logic gates and measurements. However, any measurement can be deferred to the end of quantum computation, though this deferment may come at a computational cost, so most quantum circuits depict a network consisting only of quantum logic gates and no measurements. Any quantum computation (which is, in the above formalism, any
unitary matrix of size 2^n \times 2^n over n qubits) 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, since a computer that can run such circuits is a
universal quantum computer. 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. Implementation of Boolean functions using the few-qubit quantum gates is presented here.
Measurement-based quantum computing A
measurement-based quantum computer decomposes computation into a sequence of
Bell state measurements and single-qubit
quantum gates applied to a highly entangled initial state (a
cluster state), using a technique called
quantum gate teleportation.
Adiabatic quantum computing An
adiabatic quantum computer, based on
quantum annealing, decomposes computation into a slow continuous transformation of an initial
Hamiltonian into a final Hamiltonian, whose ground states contain the solution.
Neuromorphic quantum computing Neuromorphic quantum computing (abbreviated 'n.quantum computing') is an unconventional process of computing that uses
neuromorphic computing to perform quantum operations. It was suggested that quantum algorithms, which are algorithms that run on a realistic model of quantum computation, can be computed equally efficiently with neuromorphic quantum computing. Both traditional quantum computing and neuromorphic quantum computing are physics-based unconventional computing approaches to computations and do not follow the
von Neumann architecture. They both construct a system (a circuit) that represents the physical problem at hand and then leverage their respective physics properties of the system to seek the "minimum". Neuromorphic quantum computing and quantum computing share similar physical properties during computation.
Topological quantum computing A
topological quantum computer decomposes computation into the braiding of
anyons in a 2D lattice.
Quantum Turing machine A
quantum Turing machine is the quantum analog of a
Turing machine.
one-way quantum computation, adiabatic quantum computation, and topological quantum computation—have been shown to be equivalent to the quantum Turing machine; given a perfect implementation of one such quantum computer, it can simulate all the others with no more than polynomial overhead. This equivalence need not hold for practical quantum computers, since the overhead of simulation may be too large to be practical.
Noisy intermediate-scale quantum computing The
threshold theorem shows how increasing the number of qubits can mitigate errors, yet fully fault-tolerant quantum computing remains "a rather distant dream". Scientists at
Harvard University successfully created "quantum circuits" that correct errors more efficiently than alternative methods, which may potentially remove a major obstacle to practical quantum computers. The Harvard research team was supported by
MIT,
QuEra Computing,
Caltech, and
Princeton University and funded by
DARPA's Optimization with Noisy Intermediate-Scale Quantum devices (ONISQ) program.
Quantum cryptography and cybersecurity Digital cryptography enables communications to remain private, preventing unauthorized parties from accessing them. Conventional encryption, the obscuring of a message with a key through an algorithm, relies on the algorithm being difficult to reverse. Encryption is also the basis for digital signatures and authentication mechanisms. Quantum computing may be sufficiently more powerful that difficult reversals are feasible, allowing messages relying on conventional encryption to be read. Quantum cryptography replaces conventional algorithms with computations based on quantum computing. In principle, quantum encryption would be impossible to decode even with a quantum computer. This advantage comes at a significant cost in terms of elaborate infrastructure, while effectively preventing legitimate decoding of messages by governmental security officials. == Communication ==