Three classic NP-Hard problems where brute-force is infeasible — and why quantum computing offers hope.
Problem Setup
Press "Run Brute Force" to find the optimal route
720
Total Permutations
0
Routes Checked
—
Best Distance
O((n-1)!/2)
Complexity
What's happening? The TSP asks: given N cities, find the shortest route visiting each exactly once.
Brute force tries (n-1)!/2 unique routes. With 6 cities = 60 routes. With 20 cities = 60,822,550,204,416,000 routes. With 50 cities, even at 1 billion checks/second it would take longer than the age of the universe.
Quantum advantage: Grover's algorithm gives a quadratic speedup (√N), and quantum annealing can explore the energy landscape to find near-optimal solutions exponentially faster.
HP Lattice Model — Hydrophobic-Polar Protein Folding
SEQUENCE:
H Hydrophobic P Polar
—
Possible Conformations
—
Best Energy Score
O(2ⁿ)
Search Space
~3ⁿ
Real-world (3D)
What's happening? Protein folding determines a protein's 3D shape, which determines its function.
Even in a simplified 2D grid model (HP model), the search space is ~3ⁿ (each residue turns left, right, or straight).
For a 100-residue protein: ~5 × 10⁴⁷ conformations. This is why DeepMind's AlphaFold was revolutionary — it uses ML to bypass brute force.
Quantum advantage: D-Wave's quantum annealer frames protein folding as a QUBO (Quadratic Unconstrained Binary Optimization) problem, naturally mapping onto qubit interactions to find minimum energy states.
Job-Shop Scheduling Problem
Press "Optimize" to find minimum makespan
—
Possible Schedules
—
Makespan (time units)
O((n!)ᵐ)
Brute-force Complexity
—
= This Many Routes
What's happening? We need to assign J jobs across M machines in optimal order to minimize total time (makespan).
The search space is (n!)ᵐ — with 5 jobs on 4 machines that's 1,728,000 combinations.
With 10 jobs on 6 machines: over 1.3 × 10²⁰.
This underpins real logistics: airline scheduling, chip manufacturing, supply chain, hospital OR scheduling.
Quantum advantage: Quantum approximate optimization algorithms (QAOA) can find near-optimal schedules by encoding constraints as Hamiltonians and finding the ground state — potentially exponential speedup over classical methods.
Complexity Growth Comparison
Classical vs Quantum
n
Brute O(n!)
Grover O(√n)
Speedup
Key Insight
Classical computers must check solutions sequentially. Even with parallelism, the exponential wall is insurmountable.
Quantum computers use superposition to explore many states simultaneously, and interference to amplify correct answers.
For NP-Hard problems, this isn't just faster — it's a fundamentally different computational paradigm.