Solving the Traveling Salesman Problem with Quantum Computing: A QAOA Journey
Think about the classic Traveling Salesman Problem (TSP) for a second. It sounds easy at first: start at one city, visit all the others exactly once, and get back to where you started, all while covering the least possible distance. But under the hood, it’s a monster. The number of possible routes blows up as I add cities. By twenty cities, I’m looking at around 60 quadrillion possible paths. Even supercomputers get overwhelmed. And this isn’t just some theoretical exercise. Whether it’s FedEx, United Airlines, or my favorite food delivery service, businesses run into TSP-like issues every day. Getting a better handle on this problem isn’t just academic. It could save money, reduce emissions, and make whole industries more efficient.
Now, let me talk about quantum computing. Not too long ago, quantum computers were little more than a scientific curiosity. These days, I can actually use a real quantum machine, and even if it’s not perfect, it’s more than just hype. One of the most promising quantum algorithms in the optimization space is the Quantum Approximate Optimization Algorithm (QAOA), created by Farhi, Goldstone, and Gutmann back in 2014. What happens when I put QAOA to work on TSP? That’s what this journey is about, and why the final product was surprisingly more exciting than it sounds on paper.
Cracking the Traveling Salesman Problem
To see what makes TSP so tough, I need to think about how computers tackle problems. Most problems scale in a manageable way. Double the input, double the work (that’s O(n)). Some are trickier and grow as the square or cube of the input. But TSP? It’s in a league of its own. It’s NP-hard.
Here’s the kicker: checking a solution is simple. Someone gives me a route, I add up the distance, make sure every city is included, and that’s it. But finding that best route, the really shortest loop? I would have to check a galaxy of possibilities, (n-1)!/2 routes, to be exact, for n cities.
This is where quantum computing starts to matter. Unlike regular computers, quantum machines use strange physics, things like superposition and entanglement, to explore many routes at once. Suddenly, an impossible search space becomes something I might actually navigate.
The Basics of QAOA
QAOA works because it’s a hybrid. It lets quantum and classical computers take turns. I set it up by expressing my optimization problem in quantum language, called a Hamiltonian. For TSP, that means encoding the “visit each city once” rule and the goal of minimizing distance, all within this framework.
In practice, I create a quantum circuit with two types of operators. The first represents the problem Hamiltonian. The second remixes the solution space for better exploration. Each operator uses angles or parameters that need tuning for the best results.
Now, the quantum circuit doesn’t figure these parameters out on its own. That’s where the classical computer steps in. It tries out different parameter values (using an optimizer like COBYLA), runs the quantum circuit, and evaluates the quality of the result. It loops this process, inching closer and closer to a decent solution.
Will QAOA always find the perfect answer? No. But it finds good ones, fast, and with the tech I’ll have in the future, it might soon beat classical approaches for big, seemingly unsolvable problems.
Architecture Breakdown: Frontend Meets Backend
To really make this work, I need a two-part system.
Backend (Python, Qiskit): This is where the heavy lifting happens. The backend gets city coordinates from the user, transforms TSP into something quantum computers can handle (a QUBO problem), spins up the QAOA circuit, and solves it, first using quantum simulators, since real hardware is still finicky. When IBM Quantum’s hardware grows up and stabilizes, I can plug right in.
Frontend (React/Next.js): The frontend is where people actually interact. A user picks city locations, either by hand or from templates. These are displayed on a map, routes are drawn, and statistics pop up: route length, circuit complexity, computation time, and more. It needs to feel lively, not like a black box. Progress bars, visuals, and clear feedback when the quantum engine is churning.
The two pieces talk via a REST API, with data zipping back and forth as JSON.
Implementation: Stuff I’ll Wrestle With
This project isn’t just plug-and-play.
Encoding the Problem: TSP doesn’t magically fit quantum algorithms, so I need to recast it into a binary optimization format, like a QUBO. Every possible route becomes a string of bits. The Hamiltonian enforces route rules and rewards shorter distances.
Designing the Circuit: Quantum circuits can’t be too deep. Adding more layers means more room for errors. But more depth also means better (potentially) solutions. Striking the right balance is an art.
Classical Optimization: The whole process hinges on how well the classical optimizer picks parameters. COBYLA is a favorite because it works without gradients, but different algorithms and settings can give better results.
Scaling Up: Simulators let me test up to around 8 cities quickly. More than that gets slow and painful. This limitation actually illustrates the need for quantum hardware, even simulations are tough for medium-sized TSP instances.
TSP and Beyond, Where Else Does This Apply?
While TSP is the headline act, the same tools extend far beyond that.
Logistics: Delivery companies tweak routes daily. Quantum solutions could mean faster deliveries and lower carbon footprints.
Circuit Design: Laying out wires on a chip is just another kind of TSP.
Finance: Building a portfolio often feels like picking a route through thousands of investment options, a quadratic optimization problem for qubits.
Drug Discovery: Exploring millions of molecular options is another space tailor-made for quantum algorithms.
QAOA isn’t just about TSP, it’s ready for anything structured as a binary quadratic problem: from graph coloring to scheduling to constraint satisfaction.
How Quantum Compares to Classical
Let me be blunt. Quantum solutions aren’t magic, at least not yet.
Simple classical algorithms, like the nearest-neighbor trick, give me fast but rough answers. Advanced ones, genetic algorithms, simulated annealing, run longer but do better.
Get Justen Visva’s stories in your inbox
Join Medium for free to get updates from this writer.
Right now, QAOA on simulators lands between the quick-and-dirty and heavy-duty classical approaches, both in speed and solution quality, for small cases. Is that disappointing? Not at all. The point is, as quantum hardware grows, that trade-off will shift. If I frame my project as a serious exploration, honoring quantum’s current limits and its crazy potential, I’ll be speaking the truth.
Building the Interface, Making Quantum Approachable
A polished interface turns a cool algorithm into a tool people actually care about.
I’ll want:
A way for users to punch in cities, load up presets, or play with demos.
A dynamic map or graph that makes routes obvious, different colors for quantum and classic, clear sequences, intuitive visuals.
A panel with all the stats: route order, total distance, quantum circuit layers, classical iterations, time taken.
Head-to-head comparisons, side-by-side quantum and classical solutions, turn results into stories.
Solid feedback while waiting, disable the button, spin an animation, show the quantum circuit crunching away.
Don’t overdo the design. Clean lines, whitespace, easy-to-read fonts, and a pro color scheme go further than flashy gimmicks. Tools like Tailwind CSS make this easier than ever.
Deploying and Sharing
The magic of a web app? Just drop a link and everyone can try it.
Frontends fly on Vercel, just link GitHub and I’m rolling. Python backends need Heroku, Railway, AWS, or similar. To start, I might run the backend locally while the UI is live, but for real production, I should deploy both.
That’s how quantum becomes accessible, no installs, no confusion, just a shared interactive tool that anyone can use.
Understanding Performance, the Real-World Bumps
As I build, I’ll hit quantum reality checks.
Classically simulating quantum circuits works for 4–6 cities in seconds, but it scales horribly. 8 takes half a minute, 10 can take several minutes or more.
On real hardware, things get trickier. Qubits are noisy, they don’t last long, and I don’t have many of them. Right now, the best machines have maybe 50–1000 qubits, but only a small, error-prone handful are usable simultaneously.
These aren’t “failures”, they’re where quantum tech stands today. Recognizing, explaining, and working around these limits isn’t an admission of defeat. It shows I actually get the field and know how to innovate within real-world constraints.
The Bigger Picture, Why This Matters
So why bother with quantum at all?
Because I’m at the tail end of Moore’s Law. Chips won’t double forever. Quantum isn’t just “faster classical”, it’s a different road entirely, one with brand new possibilities.
I’m living in what’s called the “Noisy Intermediate-Scale Quantum” (NISQ) era. Qubits are imperfect, small in number, and error-prone. But I can experiment, real research, solving meaningful problems, even if they’re small.
Building a TSP QAOA web app puts me right at the center of this new wave. I’m not just learning new code, I’m testing technologies that could drive the next ten years of computing.
How to Get Started
- Install Qiskit: pip install qiskit qiskit-optimization qiskit-algorithms
- Work through Qiskit’s QAOA and optimization tutorials for a hands-on intro.
- Prototype QAOA for a four-city problem in a Jupyter notebook, start simple, understand every step.
- Build the Python backend API to expose my QAOA solver over HTTP.
- Set up the frontend using React, Next.js, or my framework of choice.
- Connect the pieces, refine the interface, and test with real data.
- Deploy and put it to the test in the wild.
Wrapping Up
The Traveling Salesman Problem may date back nearly a century, but it’s as relevant as ever, challenging businesses and scientists alike. Quantum computing, particularly through QAOA, offers a new lens for tackling such ancient puzzles.
Building a complete TSP QAOA web app brings theory to life. It demands quantum savvy, optimization know-how, software development skills, and a sense for design. At the end, I don’t just have code. I have a proof that I can bridge tomorrow’s technology with today’s business needs.
And who knows? The proof-of-concept I build today, limited as it is, might turn into a critical business tool as quantum hardware finally matures. If I jump in now, I’ll be ahead of the curve, and honestly, that’s what makes all the sweat worth it.
