Quantum Algorithms

Quantum algorithms make use of superposition, interference and entanglement to solve certain problems faster than classical methods. This page summarises several influential algorithms and suggests simple circuits you can try on the Quantum Simulator (opens in a new tab).

Deutsch-Josza Algorithm

The Deutsch-Josza algorithm determines whether a function is constant or balanced using only one query, compared to $2^{n-1}$ queries classically. It prepares a superposition of all inputs, applies the function as a quantum oracle, and then performs a quantum Fourier transform to extract the result.

The circuit consists of a Hadamard gate on each input qubit, followed by a controlled operation that flips the output qubit based on the function's value. Finally, another round of Hadamard gates prepares the state for measurement. The result indicates whether the function is constant (all zeros) or balanced (one of the outputs is one).

Simon's Algorithm

Simon's algorithm solves the problem of finding a hidden period in a function with exponential speedup over classical methods. It prepares a superposition of inputs, applies the function as a quantum oracle, and then uses interference to extract the period.

The circuit begins with Hadamard gates on the input qubits to create a superposition. The function is applied as a controlled operation that encodes the hidden period into the output qubits. After another round of Hadamard gates, measuring the input qubits reveals linear equations that can be solved classically to find the hidden period.

Bernstein-Vazirani Algorithm

The Bernstein-Vazirani algorithm finds a hidden binary string using only one query, compared to $n$ queries classically. It prepares a superposition of all inputs, applies the function as a quantum oracle, and then performs a quantum Fourier transform to extract the hidden string.

The circuit consists of a Hadamard gate on each input qubit, followed by a controlled operation that encodes the hidden string into the output qubit. After another round of Hadamard gates, measuring the input qubits reveals the hidden string directly.

Phase Estimation

Phase estimation estimates the eigenvalue of a unitary operator by preparing a superposition of states, applying controlled rotations, and performing a quantum Fourier transform. It is a key subroutine in many quantum algorithms, including Shor's algorithm.

The circuit begins with a register of qubits in the state $|0\rangle$ and an auxiliary qubit in the state $|1\rangle$ . Hadamard gates create superpositions, followed by controlled rotations that encode the phase information. Finally, a quantum Fourier transform extracts the phase, which can be measured to obtain an approximation of the eigenvalue.

Shor's Factoring Algorithm

Shor's algorithm factors large integers in polynomial time. It combines classical pre‑ and post‑processing with a quantum routine that determines the period of a modular exponentiation function. The ability to factor efficiently threatens classical cryptographic schemes based on integer factorisation. Implementing Shor's algorithm requires a sizable number of qubits and precise control, but small instances illustrate how phase estimation and the quantum Fourier transform work together.

At a high level the algorithm computes the order $r$ of an integer $a$ modulo $N$ by preparing a superposition of all exponents, applying modular exponentiation controlled by those exponents and then performing a quantum Fourier transform. Measuring yields a value close to a multiple of $1/r$ , from which $r$ can be deduced using continued fractions.

Grover's Search Algorithm

Grover's algorithm finds a marked item within an unsorted database of size $N$ using only $O(\sqrt{N})$ queries. It iteratively amplifies the probability amplitude of the desired state using an oracle and a diffusion operation. On the Quantum Simulator you can construct a two‑qubit version of Grover's search to see amplitude amplification in action.

Each iteration consists of querying the oracle, which flips the phase of the marked element, followed by the diffusion operator that inverts amplitudes about their average. Repeating this about $\tfrac{\pi}{4}\sqrt{N}$ times rotates the state vector close to the marked basis state.

Grover's algorithm is a key component of the Quantum Amplification Algorithm, which uses a similar approach to find the ground state of a Hamiltonian.

Quantum Fourier Transform

The Quantum Fourier transform (QFT) is the quantum analogue of the discrete Fourier transform. It maps computational basis states to phase encoded superpositions and is a key component of algorithms such as Shor's and phase estimation. Efficient implementations of the QFT require only $O(n^2)$ gates for $n$ qubits and can be visualised step by step on the simulator.

The QFT maps computational basis states to phase encoded superpositions. For a single qubit the QFT is a Hadamard gate. For two qubits it applies a Hadamard to the first qubit, followed by a controlled phase rotation from the first to the second qubit, and then another Hadamard on the second qubit. This pattern continues for larger numbers of qubits, with controlled phase rotations decreasing in angle as the distance between qubits increases.

The QFT can be expressed as a unitary matrix that transforms the computational basis states into superpositions of all possible states with phases determined by their binary representations. The matrix for the QFT on $n$ qubits is given by

\mathrm{QFT}_{n} = \frac{1}{\sqrt{2^n}}\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & e^{2\pi i/2^n} & e^{2\pi i \cdot 2/2^n} & \cdots & e^{2\pi i \cdot (2^{n-1}-1)/2^n} \\ 1 & e^{2\pi i/2^n} & e^{2\pi i \cdot 2/2^n} & \cdots & e^{2\pi i \cdot (2^{n-1}-1)/2^n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & e^{2\pi i/2^n} & e^{2\pi i \cdot 2/2^n} & \cdots & e^{2\pi i \cdot (2^{n-1}-1)/2^n} \end{bmatrix}.

The QFT is particularly powerful because it can be implemented efficiently on a quantum computer, requiring only $O(n^2)$ gates for $n$ qubits. This is in contrast to the classical discrete Fourier transform, which requires $O(n \log n)$ time.

The QFT is a key component in many quantum algorithms, including Shor's algorithm for factoring and phase estimation. It allows quantum computers to perform frequency analysis on quantum states, enabling them to extract periodicities and other features that are difficult to compute classically.

The QFT is defined recursively for $n$ qubits as follows:

\mathrm{QFT}_{n} = H_1 \otimes \mathrm{QFT}_{n-1} + \sum_{k=2}^{n} R_{k-1} \otimes \mathrm{QFT}_{n-k+1},

where $H_1$ is the Hadamard gate on the first qubit and $R_{k-1}$ are controlled phase rotations that depend on the distance between qubits. The final step involves reversing the order of the qubits to restore the expected binary ordering.

The QFT is a powerful tool in quantum computing, enabling efficient manipulation of quantum states and serving as a foundation for many advanced algorithms.

For an $n$ ‑qubit input state $|x\rangle$ the QFT produces

\mathrm{QFT}|x\rangle=\frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}e^{2\pi i xy/2^n}|y\rangle.

The circuit uses a cascade of Hadamard and controlled phase rotations whose angles decrease exponentially. Reversing the order of qubits at the end restores the expected binary ordering.

Variational Algorithms

Noisy intermediate‑scale quantum devices often employ variational algorithms. Here a parameterised quantum circuit is optimised using classical feedback. Examples include the Variational Quantum Eigensolver for estimating molecular energies and the Quantum Approximate Optimisation Algorithm for combinatorial problems. These approaches are well suited to interactive exploration because the circuits are relatively small but depend on tunable parameters.

A cost function, such as the expectation value of a Hamiltonian, is estimated from repeated measurements of the circuit. A classical optimiser then updates the parameters to minimise this cost. The process iterates until convergence, blending quantum state preparation with classical optimisation.

HHL

The Harrow–Hassidim–Lloyd algorithm solves certain systems of linear equations exponentially faster than known classical methods, provided the system meets specific criteria. It uses phase estimation to encode the reciprocals of eigenvalues and controlled rotations to produce the solution state. While a full implementation requires many qubits, simplified versions demonstrate the principle of encoding solutions in quantum amplitudes.

The output is a quantum state proportional to the solution vector rather than the explicit coefficients. Subsequent measurements allow estimation of features of the solution, such as expectation values of observables, without constructing the vector explicitly.

These and many other algorithms demonstrate how quantum gates can be orchestrated to tackle problems that are currently intractable on classical hardware. Exploring small-scale versions on the Quantum Simulator helps build intuition for how each algorithm manipulates quantum states.

Quantum Circuits