The programming model of quantum algorithms base on qubit which are states in a quantum-mechanic; a two-dimensional state. Todays classical bit are one-dimensional, it is on or off. If the qubit gets measured it will return the classical bit, with bit probability. The state space grows exponentially in the number of qubits n and that in general the number of basis vectors is 2^n.
A quantum algorithm can be thought of as three steps:
- encoding of the data into the probabilistic states
- a sequence of quantum gates applied
- measurements of one or more of the qubits
The two quantum mechanical effects that quantum algorithms can exploit to outperform classical algorithms are superposition of states and entanglement:
- Superposition refers to the fact that before measurement each qubit is in both basis states simultaneously.
- Entanglement as the effect that a change in one quit also affects the connected other(s).
Quantum algorithms are often grouped into
- number-theory-based,
- oracle-based and,
- quantum simulation algorithms.
Instead they could also be grouped by application areas:
- inverse function computation,
- number-theory applications,
- algebraic applications,
- graph applications,
- learning applications and,
- quantum simulation.