Quantum Algorithms

The Algorithms That Define Quantum Advantage

Quantum hardware is only as useful as the algorithms that run on it. A handful of breakthrough algorithms demonstrate quantum advantage. the ability to solve specific problems exponentially or quadratically faster than any known classical algorithm. These algorithms are the reason quantum computing is relevant to cryptography, optimization, and science.

Shor's Algorithm: Breaking RSA and ECC

Invented by Peter Shor in 1994, this algorithm can factor large integers in polynomial time. a task that is exponentially hard for classical computers. This directly threatens:

• RSA encryption. Security depends on the difficulty of factoring the product of two large primes
• Elliptic Curve Cryptography (ECC). Security depends on the discrete logarithm problem, which Shor's algorithm also solves
• Diffie-Hellman key exchange. Same vulnerability to the discrete logarithm attack

How Shor's Algorithm Works (Conceptually)

1. Reduce factoring to period-finding. Choose a random number a, and find the period r of the function f(x) = a^x mod N
2. Use quantum Fourier transform. Create superposition of all values, apply modular exponentiation, then use the Quantum Fourier Transform (QFT) to extract the period
3. Classical post-processing. Use the period to compute factors via the GCD

The quantum speedup comes from step 2: the QFT can extract periodicity from an exponentially large superposition in polynomial time.

Grover's Algorithm: Searching Faster

Published by Lov Grover in 1996, this algorithm provides a quadratic speedup for unstructured search problems. Where a classical computer needs O(N) operations to search N items, Grover's algorithm needs only O(√N).

Impact on Symmetric Cryptography

Algorithm	Classical Security	Post-Quantum Security (Grover)	Mitigation
AES-128	128 bits	64 bits	Upgrade to AES-256
AES-256	256 bits	128 bits	Already sufficient
SHA-256	256 bits (preimage)	128 bits	Consider SHA-384/512

The good news: Grover's speedup is "only" quadratic. Doubling key lengths is generally sufficient to maintain security against quantum attacks on symmetric algorithms.

Quantum Simulation

Richard Feynman's original insight (1982) was that simulating quantum systems requires quantum hardware. This remains one of the most promising near-term applications:

• Drug discovery. Simulating molecular interactions to design new pharmaceuticals
• Materials science. Discovering new catalysts, superconductors, and battery materials
• Chemistry. Accurately modeling chemical reactions at the quantum level

Variational Quantum Eigensolver (VQE) and QAOA

These hybrid quantum-classical algorithms are designed for near-term quantum hardware (NISQ devices):

• VQE. Finds the ground state energy of molecules using a parameterized quantum circuit optimized by a classical computer
• QAOA (Quantum Approximate Optimization). Tackles combinatorial optimization problems like routing, scheduling, and portfolio optimization

These algorithms tolerate higher error rates than Shor's algorithm, making them candidates for useful quantum computation before full fault tolerance is achieved.