Understanding Linear, Quadratic, and Exponential Growth

When discussing quantum computing and cryptography, you’ll often hear terms like “exponential speedup” or “quadratic advantage.” But what do these actually mean? Let’s break it down visually.

The Three Growth Types

Linear Growth: $O(n)$

Linear growth is the most intuitive. If you have 10 items and it takes 10 seconds to process them, then 20 items will take 20 seconds. Double the input, double the time.

$f(n) = c \cdot n$

Real-world example: Reading a book page by page. Twice as many pages = twice as long to read.

Quadratic Growth: $O(n^2)$

Quadratic growth accelerates faster. If you have 10 items and it takes 100 operations, then 20 items will take 400 operations - four times as many, not twice.

$f(n) = c \cdot n^2$

Real-world example: A round-robin tournament where every player must play every other player. Double the players = four times the matches.

Exponential Growth: $O(2^n)$

Exponential growth is where things get wild. Each additional input doubles (or more) the total work required. This is why brute-force attacks on cryptographic keys are infeasible.

$f(n) = c \cdot 2^n$

Real-world example: Guessing a password by trying every combination. Each additional character doubles the search space.

Interactive Comparison

Play with the graph below to see how these growth rates compare. Adjust the coefficients and see how quickly exponential growth dominates:

Why This Matters for Cryptography

Classical Security

Modern encryption relies on problems that require exponential time to solve by brute force. A 256-bit AES key has $2^{256}$ possible combinations - a number so large that checking every key would take longer than the age of the universe.

Quantum Advantage

This is where quantum computing changes the game:

Algorithm	Classical	Quantum	Speedup
Grover’s (search)	$O(2^n)$	$O(2^{n/2})$	Quadratic
Shor’s (factoring)	$O(e^{n^{1/3}})$	$O(n^3)$	Exponential

• Grover’s algorithm provides a quadratic speedup for search problems. This effectively halves the bit security of symmetric encryption (AES-256 becomes AES-128 equivalent).

• Shor’s algorithm provides an exponential speedup for factoring and discrete logarithms. This completely breaks RSA and ECC.

The Takeaway

• Quadratic speedup is significant but manageable - just double your key sizes
• Exponential speedup is catastrophic - no practical key size can compensate

This is why post-quantum cryptography focuses on problems that even quantum computers can only solve in exponential time.

Summary

Understanding growth rates helps you evaluate claims about quantum computing:

• “Quantum computers are faster” - How much faster matters enormously
• “We need bigger keys” - Only helps against quadratic speedups
• “RSA is broken” - True if large-scale quantum computers exist (exponential speedup)
• “AES is broken” - False, just use larger keys (only quadratic speedup)

The difference between “a bit faster” and “universe-breakingly faster” comes down to understanding these growth curves.