Shor's algorithm, Grover's search

Quantum Algorithms

Discover quantum algorithms that provide exponential speedups over classical computation

Grover's Search Algorithm

Grover's algorithm provides a quadratic speedup for searching unsorted databases. It can find a marked item in O(√N) steps compared to O(N) classically.

Interactive Grover's Search Demo

Find the marked item (red) in the database:

Complexity Comparison (16 items):
Classical: O(N) = 8 steps average
Quantum: O(√N) = 4 steps

Shor's Factorization Algorithm

Shor's algorithm can factor large integers exponentially faster than the best known classical algorithms, threatening current RSA encryption.

Factorization Demo

Enter a number to factor (or use examples):

15
Time Complexity:
Classical: O(e^(n^(1/3))) - Exponential
Shor's: O(n³) - Polynomial

Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum analog of the discrete Fourier transform and is a key component in many quantum algorithms.

QFT Visualization

The QFT transforms quantum states in the computational basis to the Fourier basis:

1. Apply Hadamard gates to create superposition
2. Apply controlled phase rotations
3. Reverse the order of qubits
4. Result: Fourier transformed state

Quantum Random Walk

Quantum random walks show quadratic speedup over classical random walks and are used in various quantum algorithms.

Random Walk Comparison
Hitting Time Comparison:
Classical Random Walk: O(N)
Quantum Random Walk: O(√N)

Quantum Advantages

  • Exponential: Shor's algorithm
  • Quadratic: Grover's search
  • Polynomial: Quantum simulation
  • Constant: Deutsch-Jozsa

Key Algorithms

  • Shor's: Integer factorization
  • Grover's: Database search
  • QFT: Fourier transform
  • VQE: Variational quantum eigensolver
  • QAOA: Quantum optimization

Applications

  • Cryptography
  • Optimization
  • Machine Learning
  • Chemistry Simulation
  • Financial Modeling

Next Topics

Quantum Entanglement Quantum Cryptography Back to Fundamentals