🗺️ Before we begin — the hardest type of problem in computing

Imagine you're a delivery driver who needs to visit 20 cities and return to your starting point. You want the shortest possible route. How many possible routes are there? 20! ÷ 2 = about 1.2 quintillion. If you could check one route per nanosecond, it would take you 38 years to check them all.

This is the Travelling Salesman Problem (TSP) — one of the most famous NP-hard problems in computer science. It appears everywhere: logistics, circuit design, protein folding, supply chain optimisation. Classical computers can find approximate solutions but struggle with large instances.

QAOA (Quantum Approximate Optimisation Algorithm) is a quantum approach that uses interference to find good solutions much faster. It's one of the most promising near-term quantum algorithms — applicable to problems that are genuinely important in industry and government right now.

🌀 The billion-dollar optimisation problem

Every day, Amazon routes millions of delivery trucks, Indian Railways schedules thousands of trains, airlines route hundreds of planes, and hospitals schedule surgeries. Each is a massive optimisation problem. Classical computers find approximate solutions — but even a 1% improvement in routing efficiency across India's logistics sector would save thousands of crores annually. Quantum optimisation aims for better approximations, faster.

🗺️ Quantum Optimisation · Session 6 · Q17

QAOA Optimiser

From the Travelling Salesman Problem to India's railway network — see how QAOA uses quantum interference to find better solutions to combinatorial optimisation problems faster than classical algorithms.

🗺️ TSP Problem

⚡ QAOA Algorithm

🔁 Run Optimisation

🇮🇳 India Applications

🏆 Badge

🗺️

Combinatorial explosion

N cities → N! possible routes. For N=20, that's 10¹⁸ routes. No classical computer can check them all. Approximation algorithms exist but miss the optimal.

⚡

QAOA structure

Alternating cost and mixer operators on quantum hardware. Parameterised circuit finds approximate optimal with fewer evaluations than classical exhaustive search.

📊

Quantum advantage

QAOA can find better approximations faster, especially for problems with specific mathematical structure. Not exponential speedup — but meaningful practical improvement.

🇮🇳

India relevance

Indian Railways (world's largest employer), IRCTC booking optimisation, ISRO mission planning, logistics for e-commerce — all are large-scale optimisation problems.

🗺️

Wizzy · Quantum Guide

The Travelling Salesman Problem: given N cities with known distances, find the shortest round trip visiting each city exactly once. Classical computers use heuristics — they can't guarantee finding the optimum for large N. Click cities on the map to add them, then see how the problem scales!

Travelling Salesman Problem — Click to Add Cities

Cities

—

Possible routes

—

Classical check time

—

Current route dist

Click on the map to add cities. Watch how quickly the number of possible routes explodes!

⚡

Wizzy · Quantum Guide

QAOA works in two alternating steps: Cost operator (phase-kick states proportional to their cost — bad solutions get more phase), then Mixer operator (spread the amplitude around to explore nearby solutions). Like interference in the double slit — after enough layers, good solutions interfere constructively, bad ones destructively.

QAOA Structure

QAOA Circuit (p=2 layers)

            |+⟩ ── 
            Uc(γ₁)
             ── 
            Um(β₁)
             ── 
            Uc(γ₂)
             ── 
            Um(β₂)
             ── M
          

Cost operator Uc(γ)

Encodes the optimisation objective. Applies phase proportional to route length. Bad routes (long) get large negative phase — destructive interference amplifies against them.

Mixer operator Um(β)

Spreads amplitude to neighbouring solutions. Like diffusion in Grover's algorithm — prevents the algorithm from getting stuck in local optima. Enables exploration.

Key insight: QAOA is essentially amplitude amplification (from Grover's) applied to optimisation problems. Cost operator marks bad solutions. Mixer operator amplifies good ones. With more layers, the approximation improves.

⚡

Wizzy · Quantum Guide

Watch QAOA find better and better routes! The classical random search (red) and QAOA (purple) both start from random solutions. Watch which finds a shorter route faster. QAOA uses interference to focus on promising regions of the solution space.

Classical vs QAOA Optimisation

🎲 Classical random search

Distance: —

⚡ QAOA

Distance: —

Improvement over iterations

Generate a problem and run both algorithms to see the comparison.

🇮🇳

Wizzy · Quantum Guide

Optimisation problems are everywhere in India's economy. Indian Railways alone manages 13,000 trains, 8,000 stations, and 25 million daily passengers — one of the world's most complex optimisation problems. Quantum algorithms could find more efficient schedules, routes, and resource allocations than any classical approach.

QAOA Applications in India

🚂

Indian Railways

Schedule 13,000 trains across 67,000km of track. Reduce delays, optimise platform use, minimise empty seat journeys. Potential savings: thousands of crores annually.

📦

E-commerce Logistics

Flipkart, Amazon, Meesho route millions of daily deliveries. Better routing = lower fuel costs, faster delivery. 1% improvement = hundreds of crores saved.

💡

Power Grid

India's power grid serves 1.4 billion people. Optimal load balancing, transmission routing, and renewable integration require solving massive optimisation problems in real time.

🏥

Healthcare Scheduling

Schedule surgeries, allocate hospital beds, route ambulances. AIIMS and government hospital networks face complex multi-constraint scheduling problems daily.

⚡

Wizzy · Quantum Guide

🎊 You've understood quantum optimisation — one of the most commercially relevant near-term quantum applications! Optimisation problems underpin every major industry. QAOA is already being tested on real optimisation problems in finance, logistics, and energy by companies worldwide.

🧠 What you actually learned today

Combinatorial optimisation problems like TSP have N! possible solutions — exhaustive search is impossible for N>20. Classical heuristics approximate but don't guarantee the optimal.
QAOA uses alternating cost operators (phase-kick bad solutions) and mixer operators (amplify exploration) to concentrate amplitude on good solutions through interference.
QAOA is parameterised by angles (γ, β) per layer, optimised classically. More layers (higher p) → better approximation ratio, but more quantum circuit depth.
QAOA is a hybrid algorithm — quantum hardware evaluates objective function expectations; classical optimiser tunes parameters. Works on today's NISQ hardware.
India's largest optimisation challenges: Indian Railways, e-commerce logistics, power grid, healthcare scheduling — all are priority targets for quantum optimisation.

⚡

QAOA Optimiser Badge!

You understand quantum optimisation — from TSP to Indian Railways!

Optional. Stays on this device only — not sent to WhizzStep.

⚡ WhizzStep Quantum Lab

Activity completion card for

Student Name

has explored QAOA — Quantum Approximate Optimisation Algorithm

This records completion of a browser activity only. It is not an accredited certificate or proof of mastery.

QAOA Expert

TSP

Quantum Optimisation

📖 Quantum Vocabulary

QAOA KEY

Quantum Approximate Optimisation Algorithm. Hybrid quantum-classical algorithm for combinatorial problems. Alternates cost and mixer operators to find approximate optimal solutions.

NP-hard NEW

A class of problems for which no polynomial-time classical algorithm is known. Includes TSP, graph colouring, protein folding. Classical computers can only approximate; quantum computers may do better.

Like finding a needle in a haystack that grows faster than exponentially.

Cost operator NEW

The QAOA component that encodes the objective function. Applies phase proportional to solution quality — amplifying bad solutions' destructive potential.

Mixer operator

The QAOA component that explores the solution space. Spreads amplitude to neighbouring solutions — preventing local-optima trapping and enabling exploration.

Approximation ratio

How close an algorithm gets to the optimal solution. QAOA with p layers achieves a provable approximation ratio. Higher p = better ratio but deeper circuit.

Combinatorial explosion

When the number of possible solutions grows faster than any polynomial. TSP: N! routes. Protein folding: 3ᴺ configurations. Quantum algorithms aim to navigate this space more efficiently.

Key Concepts from Q17

QAOA

⚡ Parameterised interference

QAOA is Grover's amplitude amplification generalised to optimisation. Cost operator creates the oracle; mixer operator does the diffusion. More layers = better approximation.

Hybrid

🔄 Quantum-classical

Classical optimiser finds best γ, β parameters. Quantum hardware evaluates objective function expectation. Same NISQ-friendly hybrid approach as VQE — works on today's hardware.

NP-hard

🧩 Hard problem class

TSP, Max-Cut, portfolio optimisation, scheduling are all NP-hard. Quantum algorithms may provide polynomial speedup for some — a genuinely open question in complexity theory.

India impact

🇮🇳 Crore-scale savings

Indian Railways, logistics, grid management — 1% efficiency improvement across India's logistics sector equals thousands of crores. Quantum optimisation is a clear economic priority.

About this lab

Q-17 Emerging Applications Classes 8-12 15 min Applied

Learning objective: Use a toy optimisation problem to explore a hybrid quantum-classical algorithm. This does not establish practical quantum advantage.

What this simplifies: This is a local browser simulation, not access to real quantum hardware.

Privacy: No learner input leaves the device.

Teacher prompt: Ask the class why this simulation might mislead someone who takes it too literally.

Reflect: What is one thing this activity showed you that you did not expect?

← Quantum Drug Discovery Back to All Labs Quantum Machine Learning →

Bring this learning to my school →