Quantum Lab Session 6 Simulation Q17
๐Ÿ—บ๏ธ 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!
๐ŸŒ€ Why this problem is so hard
TSP is NP-hard โ€” there's no known polynomial-time classical algorithm. The best classical approximation algorithms can guarantee being within 1.5ร— of optimal (Christofides algorithm). But for exact optimum with N=50 cities, even the world's fastest supercomputer would take longer than the age of the universe. Quantum algorithms aim to close this gap.

Travelling Salesman Problem โ€” Click to Add Cities

0
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 is parameterised interference
Each QAOA layer has two angles: ฮณ (cost mixing strength) and ฮฒ (exploration strength). These are tuned by a classical optimiser โ€” again, a hybrid quantum-classical algorithm like VQE. With more layers (higher depth p), QAOA finds better solutions. At infinite depth, it finds the exact optimum.

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!

โšก WhizzStep Quantum Lab
This certifies that
Student Name
has mastered QAOA โ€” Quantum Approximate Optimisation Algorithm
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.