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:

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:

1. Classical preprocessing — select a random integer a and compute GCD(a, N). If > 1, N is already factored.
2. Find period r of the modular function f(x) = aˣ mod N — the smallest positive integer where aʳ mod N = 1.
3. 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
4. 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:

1. Prepare an n-qubit register in superposition over all possible states
2. Apply the Oracle operator — marks the correct solution by flipping its phase
3. Apply the Diffusion operator — amplifies the marked state while suppressing others
4. Repeat for ~√N iterations
5. Measure to yield the solution with high probability

Provides a quadratic speedup over classical search.

---

Key Techniques

---

Originally published as a whitepaper by @Brendan_In_Byte