QAOA · Interference · IBM Quantum
Your choice of destinations gets rewritten as an Ising model and put through quantum interference. Amplitudes for bad itineraries cancel; amplitudes for good ones reinforce. The final act — 64 measurements that collapse the superposition — is left to bits that came out of real IBM quantum hardware.
1 — What you want. Tap to raise the weight (○○○ to ●●●)
Phase of the amplitudes (8 sampled points)
2 — Best of 64 shots
3 — What the 64 shots contained (top 10 by frequency)
4 — Comparison (lower is better)
If you only pick one place, you do not need a quantum computer. Take the highest-scoring one and you are done. The moment you combine places, it becomes a different problem. Choosing from 12 destinations gives 212 = 4,096 combinations. Twenty destinations is about a million; forty is over a trillion. Every place you add doubles the space.
And "a good itinerary" is not a sum of good parts. Kanazawa is good and Kyoto is good, but putting both in makes the travelling heavy. Including one changes what the other is worth — and because of that interaction, picking the best thing one at a time will not find you the best whole. Physics has a name for problems shaped like this: the Ising model, where spins pull on each other while the system looks for the arrangement that settles lowest.
Let xi be 1 if you go to destination i and 0 if you don't. What we want to minimise is:
Because x is only ever 0 or 1, x² = x holds, so expanding (Σx − k)² leaves nothing above second order. That shape is called a QUBO (quadratic unconstrained binary optimisation). Substitute x = (1 − z)/2 and a QUBO is an Ising model, which means it maps straight onto quantum hardware. A question about holidays turns into the same equation as a question about magnets. That is the part worth staring at.
All 4,096 itineraries are given a complex amplitude. At the start they are all the same size, all pointing the same way. Then two operations alternate.
Each itinerary's amplitude is rotated by an angle proportional to its cost. At this point the probabilities have not moved at all. The amplitudes keep their length; only their direction changes. That is the layer where the colours change in the picture above and the bars do not.
Each qubit is rotated slightly, which adds neighbouring itineraries' amplitudes together. This is where direction starts to matter. Amplitudes pointing the same way add up; amplitudes pointing opposite ways cancel out. Because layer 1 gave the low-cost itineraries a different direction, layer 2 makes only the low-cost ones grow.
That is interference. Randomness does not have this mechanism. A uniform random number treats all 4,096 itineraries as equals; it has no way to favour the good ones. The peak leaning left in the "after" picture is a record of probability actually moving.
Real quantum computers do not answer in one shot. They run the same circuit hundreds of times and count the bitstrings that come back. Interference builds a hill where good itineraries are more likely — it does not build a machine that always emits the optimum. When QAOA is used in practice, the answer returned is the best of the measured samples. This page does the same thing, pulling all 64 shots' worth of bits from the IBM pool in one request.
Look at section 3. Sixty-four shots typically produce around fifty different itineraries. That looks scattered, but all of them sit at the good end of the 4,096. Interference got you that far; picking the single winner is the classical step of "take the best one you measured". A lot of writing blurs these two together and says the quantum computer found the answer, so it is worth keeping them apart.
These 4,096 combinations are faster to just enumerate. This page enumerates all of them in the background for comparison — that is the "brute-force optimum" row. Today's quantum computers do not beat classical machines at this size. If a page tells you otherwise, be suspicious.
The interference is being computed by your browser. It holds a 12-qubit state vector — 4,096 complex numbers — and multiplies matrices through it. The mathematics is genuine; the machine running it is ordinary.
The hardware is only involved in the measurement. A job goes to IBM's quantum computers daily to stock a pool of bits, and those bits are what collapse the superposition here. When the pool runs dry it falls back to your device's cryptographic RNG and says so on screen. It is never swapped in quietly.
So why do it. Because it makes visible what interference is doing. The QAOA equations are in the papers, but watching the probability mass slide left is something you have to run to feel. And the same circuit still fits in forty qubits when there are forty destinations. You would not have to count a trillion combinations. That is where this might matter one day.
The code below submits the same circuit to IBM. It works on the free Open Plan, though the queue can be hours or days.
from qiskit_optimization import QuadraticProgram
from qiskit_ibm_runtime import QiskitRuntimeService, SamplerV2
from qiskit.circuit.library import QAOAAnsatz
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
qp = QuadraticProgram()
for s in spots:
qp.binary_var(s["id"])
qp.minimize(linear=h, quadratic=J) # the same H(x) as above
ansatz = QAOAAnsatz(qp.to_ising()[0], reps=3)
service = QiskitRuntimeService(channel="ibm_quantum_platform")
backend = service.least_busy(operational=True, simulator=False)
pm = generate_preset_pass_manager(target=backend.target, optimization_level=3)
# finding gamma and beta is the classical side's job. this is the part people mix up
job = SamplerV2(mode=backend).run([(pm.run(ansatz), best_params)], shots=4096)
print(job.result()[0].data.meas.get_counts())
The outer loop that searches for γ and β runs on a classical computer. The quantum side only answers "what happens at these angles". You often read that the quantum computer does the optimising. That is not accurate.
Prices assume two nights, one person, leaving from Tokyo Station, with travel and lodging added together roughly. Depending on the season and how you book, they can easily double. Use them to compare, not to budget. The per-destination scores (hot spring 5, sea 4, and so on) are my own opinion with nothing behind them. Moving the weights until the model matches your own taste is the intended way to use this.