Quantum Algorithm

quantum-computing algorithms

Definition

Quantum Algorithm

A quantum algorithm is a predetermined sequence of quantum gates applied to a quantum register to perform a computational task. The algorithm specifies how the quantum state evolves from an initialised start state to a final state, from which classical information is extracted via measurement.

1. Quantum Parallelism: Algorithms exploit superposition to evaluate functions on multiple inputs simultaneously.
2. Interference: Amplitudes are manipulated constructively and destructively to amplify correct answers and suppress wrong ones.
3. Probabilistic Output: Measurement yields classical outcomes with probabilities determined by quantum amplitudes.

Structure

Input: Classical specification of the problem instance.

State Preparation: Initialise the quantum register to a known state, typically $|0{⟩}^{\otimes n}$.

Quantum Circuit: Apply a sequence of unitary transformations:

$$|{\psi }_{\text{final}}⟩=U_k\cdots U_2{U}_1|{\psi }_{\text{initial}}⟩$$

Measurement: Measure some or all qubits, obtaining classical bits with probabilities $|⟨x|{\psi }_{\text{final}}⟩{|}^2$.

Examples

Deutsch-Jozsa Algorithm: Determines whether a function is constant or balanced using only one query.

Grover’s Search: Searches an unsorted database of $N$ items in $O(\sqrt{N})$ time.

Shor’s Algorithm: Factors integers in polynomial time, providing exponential speedup over classical algorithms.