Quantum algorithms - a very brief introduction
A very brief introduction to quantum algorithms.
Quantum Algorithms
Algorithms that use quantum phenomena to solve certain problems exponentially faster than classical computers.
What Makes Quantum Computing Different
Classical computers process bits as 0 or 1. Quantum computers use qubits, which can exist in superposition — multiple states simultaneously. This allows quantum computers to evaluate many computational paths at once, with probability amplitudes overlapping to efficiently converge on solutions.
Important caveat: Quantum parallelism isn't a free lunch. Clever algorithm design is required to harness it — you can't just "run everything in parallel."
Devising a Quantum Algorithm
Building a quantum algorithm follows a three-step process:
1. Find a Problem with Quantum Advantage
Quantum systems excel where the solution space grows exponentially with input size. Good candidates include:
- Protein folding — classical MD simulations require O(3ⁿ) coordinates for N atoms → quantum advantage candidate
- Option pricing — limited state evolution → better suited for classical Fourier methods
2. Problem Encoding
Convert the problem into a quantum system by defining a Hamiltonian (an "energy" function) where minimising it gives the solution. For example, in the Travelling Salesman Problem, a Hamiltonian is defined over distances and binary route variables — a quantum annealer physically maps qubits to this Hamiltonian and naturally evolves toward the minimum energy (optimal) solution.
For gate-based systems, variational quantum algorithms like QAOA can be used instead.
Circuit Construction
Quantum circuits are built from:
| Component | Role |
|---|---|
| Cost operator | Penalises bad solutions |
| Mixer operator | Shuffles solutions to explore new possibilities |
| Measurement | Reads out the result |
The loop: start with all possibilities → apply cost operator → entangle qubits → apply mixer operator → run circuit → adjust parameters → repeat until good solution found.
3. Parameter Tuning
Classical computers are used to optimise the quantum circuit's parameters — a hybrid approach that forms the basis of most practical quantum algorithms today.
Key Examples
Shor's Algorithm
Purpose: Integer factorization — with applications in breaking RSA encryption.
Steps:
- Classical preprocessing — select a random integer
aand compute GCD(a, N). If > 1, N is already factored. - Find period r of the modular function
f(x) = aˣ mod N— the smallest positive integer whereaʳ mod N = 1. - Quantum shenanigans:
- Prepare a superposition over all possible values of x
- Apply modular exponentiation to entangle input and output registers
- Apply the Quantum Fourier Transform (QFT) to extract periodicity information
- Measure to yield an integer related to r
- Classical postprocessing — use r to compute GCD(aʳ/² − 1, N) and GCD(aʳ/² + 1, N). One yields a non-trivial factor of N.
Grover's Algorithm
Purpose: Searching unstructured databases or solving Boolean problems — finding an input x₀ such that f(x₀) = 1 across a database of size N = 2ⁿ.
Steps:
- Prepare an n-qubit register in superposition over all possible states
- Apply the Oracle operator — marks the correct solution by flipping its phase
- Apply the Diffusion operator — amplifies the marked state while suppressing others
- Repeat for ~√N iterations
- Measure to yield the solution with high probability
Provides a quadratic speedup over classical search.
Key Techniques
| Technique | Description |
|---|---|
| Quantum Fourier Transform (QFT) | Quantum analogue of the classical DFT. Used in Shor's algorithm, phase estimation, and the hidden subgroup problem. Implemented via Hadamard gates and controlled phase gates. |
| Amplitude Amplification | Amplifies probability of measuring "good" outcomes. Provides quadratic speedup. Core to Grover's search and fault detection. |
| Phase Estimation | Estimates the phase of a unitary operator's eigenvalue. Used in Shor's algorithm, quantum simulation, and linear systems. |
| Quantum Walks | Quantum analogues of classical random walks, using superposition, interference, and unitary evolution. Two types: discrete-time (shift operators) and continuous-time (graph Laplacians). |
| Hybrid Quantum-Classical Algorithms | Combine quantum and classical computing — quantum handles specific subproblems, classical handles the rest. Examples: VQE, QAOA. |
Originally published as a whitepaper by @Brendan_In_Byte
Attached files