Text from the interactive explanation
Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection
Jingjing Cui, Yifeng Xiong, Soon Xin Ng, Lajos Hanzo
Original paperTomorrow’s networks will crowd ever more antennas into the same airwaves. The receiver that is guaranteed to make the fewest mistakes has to check every possible message, and that list doubles with each extra antenna. Researchers at the University of Southampton asked whether a quantum algorithm built for today’s small, noisy quantum computers could do the checking instead.
The live cube is a simulated quantum detector decoding a three-antenna link in real time. Each glowing corner is one possible message; watch the glow gather on the one that best explains the received signal.
Two antennas talk at once. What does the receiver hear?
A mast with several antennas can send several bits at the same instant; this is called MIMO , short for multiple-input, multiple-output. Here each antenna sends one bit as a pulse that is either positive (↑, written +1) or negative (↓, −1). On the way, the pulses mix: each receiving antenna picks up a different blend of both, plus random noise.
The receiver knows how the air mixes signals (the channel), so for each of the four possible messages it can work out the expected echo it would hear without noise. Then a noisy reading arrives. Which message was it?
1 · Choose the message to send
2 · Mystery signal: can you beat the detectors?
A hidden message is sent. Tap the expected echo you think it came from, or use these buttons.
Maximum-likelihood (ML) detection simply picks the expected echo closest to the reading. When the noise is random and bell-shaped, the closest echo is the most likely message, so no other detector makes fewer mistakes. Switch on ML regions: every point on the map belongs to its nearest echo.
A cheaper, common shortcut, the MMSE detector (minimum mean-squared error), “un-mixes” the reading with one fixed formula and rounds each bit. Switch on MMSE regions: its boundaries are straight lines, and where they disagree with ML (striped) it guesses wrong more often. Try New channel to find links where the two echoes in the middle crowd together.
Every extra antenna doubles the list of suspects
With two antennas there are 4 possible messages. Each new antenna can be ↑ or ↓, so the list doubles: 8, 16, 32… Picture each message as a corner of a cube : neighbouring corners differ by flipping a single bit. One antenna gives a line, two a square, three a cube, four a “hypercube”, and so on. ML detection has to visit every corner.
illustrationThe checking time assumes, for illustration only, a machine testing one billion messages per second. The paper states the general rule: the work of exact ML detection grows as 2N with the number of transmit antennas N, and the problem is known to be NP-hard (no known shortcut avoids this blow-up in the worst case).
The best guess is the lowest valley
The paper’s first step is a translation. Give each transmitted bit its own qubit , a quantum bit that, like a tiny magnet, can point up or down. Then write a rulebook for the magnets’ energy (physicists call it a Hamiltonian ) so that each arrangement’s energy equals how badly that message fits the reading. Every pair of magnets is linked (the lines in the triangle), with a strength set by how much the two antennas’ signals overlap. Each magnet is also nudged by what was received (the small arrows).
The best-fitting message becomes the arrangement with the lowest energy , the ground state. Flip the magnets and see.
For binary symbols sk = ±1 sent through channel H, the ML detector solves (paper eq. 2–4)
Swapping each sk for the qubit operator σz(k) gives the problem Hamiltonian (eq. 7; constants dropped in eq. 34):
Its energy levels are exactly the mismatches of the 2N candidate messages (Proposition 1), so the mismatch shown above is always 2 × energy + a constant shared by every guess. Each pair of antennas contributes one coupling, so the qubits form a fully connected graph (paper Fig. 1).
Start somewhere easy, then change the rules very slowly
A quantum computer does not have to visit the corners one by one. Its qubits can sit in a superposition , an in-between state that carries a share of every message at once. The easiest such state to prepare puts equal weight on all eight; it is the lowest-energy state of a simple “mixing” rulebook.
The adiabatic theorem says: blend that easy rulebook into the problem rulebook slowly enough and the qubits stay in the lowest-energy state all the way, ending on the answer. The lines below are the eight energy levels as the blend τ goes from 0 (easy) to 1 (problem). What counts as slowly is set by the narrowest squeeze between the lowest two levels, the minimum gap .
Predict, then run
How long must the slide last to land on the answer most of the time? Pick a duration and run it.
simulationExact quantum evolution of the same toy three-antenna link, with energies rescaled for display. In the paper’s own examples the minimum gap was 1.94 (one qubit) and 1.93 (two qubits), and the run time needed grows like 1/g² (eq. 19–20).
The catch: on a gate-based quantum computer, a long, smooth slide must be chopped into a very long sequence of operations, and today’s noisy machines lose their quantum state long before such a sequence finishes.
QAOA: a few big kicks with tunable dials
The quantum approximate optimization algorithm (QAOA) keeps the idea of the slide but uses only a few steps. Each round applies two kicks:
● Problem kick (angle γ): every corner’s quantum phase (the cyan comet) turns at a speed set by its energy. Nothing moves yet, but the corners fall out of step. ● Mixer kick (angle β): weight flows along the cube’s edges between messages that differ by one bit. Corners that are in step reinforce each other; corners out of step cancel. That interference is what can pile weight onto the answer.
The kick strengths are dials . An ordinary computer turns them, the quantum device reports the average energy, and the loop repeats: a hybrid quantum–classical algorithm (paper Fig. 2).
Notice the map is a field of hills and valleys, not a single bowl. The paper found the same for its level-1 circuits (Fig. 5): the energy landscape is non-convex , with several local valleys, and it gets bumpier as antennas and rounds are added. A tuner that only walks downhill can get stuck, which is why the authors restart their optimiser (COBYLA) from many random starting points.
More rounds, closer to the slow slide
With more rounds, p, there are 2p dials and the kicks can imitate a gentle slide. Choose p and watch the tuned schedule: the problem kicks grow while the mixer kicks shrink, just like the blend τ going from 0 to 1.
Starting from the equal superposition |ψ(0)⟩ = |+⟩⊗N (one Hadamard gate per qubit), a level-p QAOA prepares (eq. 37)
and a classical optimiser searches for the 2p angles that minimise the measured average energy Fp = ⟨ψp|Hf|ψp⟩ (eq. 38–39). For one qubit the authors derive F1 = b sin(2β) sin(2bγ) (eq. 40), plus closed forms for two and three qubits. Each level needs (N + 1)N/2 gates for the problem kick and N for the mixer.
On this page the energies are rescaled to lie between 0 and 1, and the mixer is written with the opposite sign so that the starting state is its lowest-energy state; both choices leave the physics unchanged. The depth chart uses schedules tuned to minimise average energy, as QAOA does.
In simulation, the quantum detector matched the best classical one
The authors simulated QAOA circuits on an ordinary computer (with IBM’s Qiskit Aer simulator, noise-free) for links with one, two and three transmit antennas. For each signal-to-noise level they ran 40,000 random channels and counted bit errors .
Bit error rate: errors per bit sent
from the paperValues read from Fig. 6 and replotted. Lower is better. The quantum-based detector (QML) lies on top of classical ML (CML); for three antennas it drifts very slightly above at the highest signal-to-noise ratios, because its answer is picked from a finite number of measurements. Both beat MMSE.
Approximation ratio: how close the average answer gets
from the paperValues read from Fig. 7(d) and replotted (signal-to-noise 10 dB, best of 2,000 optimiser restarts). A ratio of 1 means QAOA’s average energy equals the true best answer. Gaps in a line are depths the authors did not run.
Race the detectors yourself
Below, random three-antenna messages stream through random channels. Each column is one transmission; each row is one detector; red marks a wrong message. The quantum detector is a simplified re-enactment: an eight-round QAOA whose dials are tuned to minimise average energy, measured 8 times, keeping the best-fitting reading, as in the paper.
simulationA small in-browser re-enactment with its own noise convention; its numbers are not the paper’s measurements, but the ordering (ML ≈ QAOA, MMSE behind) is the pattern the paper reports.
What would it take for a real network?
The paper also counts the cost. A QAOA circuit for N antennas and p rounds needs about (N + 5)·N·p / 2 quantum gates, which grows gently. Simulating it on an ordinary computer is another matter: just writing down the quantum state of N qubits takes 2N+3 bytes, and a full operator takes 22N+3. A real quantum device would hold that state physically instead.
Bars use a logarithmic scale. The paper’s estimate: a 16 GB computer can simulate about 15 qubits when it must store the operators, or about 30 when it only stores the state.
“In our future research we would test the QAOA on large-scale MIMO systems, using the results derived in this treatise as a springboard.”
So, can a quantum state pick out the right message from the crowd? For two- and three-antenna links in noise-free simulation, the answer was yes: QAOA-based detection came within a whisker of the optimal classical detector and beat the common MMSE shortcut. The paper also maps the road ahead. Bigger links mean a fully connected web of qubits, more rounds (for three antennas the approximation ratio was still climbing at 20 rounds), more dials to tune on a bumpy landscape, and real, noisy hardware instead of simulation. The authors present this as the first application of QAOA to maximum-likelihood detection in wireless communications, and as a way to open “new avenues of optimization” for the crowded networks to come.
↑ Back to the Answer Cube
The paper
Jingjing Cui, Yifeng Xiong, Soon Xin Ng and Lajos Hanzo , “Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection”, IEEE Transactions on Communications, vol. 70, no. 8, pp. 5386–5400, 2022. School of Electronics and Computer Science, University of Southampton.
This page is based on the authors’ accepted manuscript: southampton.ac.uk/~sxn/paper/2022_qaoa_ml_acc.pdf. A preprint is also available as arXiv:2107.05020.
The charts in Chapter 6 replot values read by eye from the paper’s Figs. 6 and 7(d), so they are approximate. Everything else (the Answer Cube, the antenna map, the hypercube, the spin triangle, the energy-level slide, the dial map and the detector race) is an original illustration or a live simulation of small toy links built from the paper’s equations, with energies rescaled for display. The cube picture of the candidate messages is our visual device for the paper’s 2N-state description.
Topics in this iPaper
Engineering
Consider a MIMO system and transmitting binary symbols over an Mr × Mt channel matrix
Section II (System Model), page 3
Physics
the quantum system can smoothly evolve from a known ground state of Hamiltonian H(0) to an unknown ground state of Hamiltonian H(T)
Section III-B (The Adiabatic Theorem), page 4
Computer science
finding the optimal solution is exponentially hard using classical computers
Abstract, page 1
quantum approximate optimization algorithm
we apply the QAOA for the ML detection by encoding the problem of interest into a level-p QAOA circuit having 2p variational parameters
Abstract, page 1
maximum likelihood detection
we consider the maximum likelihood (ML) detection problem of binary symbols transmitted over a multiple-input and multiple-output (MIMO) channel
Abstract, page 1
multiple input multiple output
having Mt transmit antennas (TA) as well as Mr receive antennas (RA)
Section II (System Model), page 3
adiabatic quantum computation
we assume that the quantum system starts from a known ground state HB and evolves to an unknown ground state Hf
Section IV-A (The Adiabatic Evolution), page 5
ising model
Then, we have the Ising Hamiltonian associated with (4) as follows
Section III-A, page 4
variational quantum algorithms
Following the VQE principle, the QAOA creates a parameterized state in terms of γ and β on the quantum computer
Section V-B and Fig. 2, pages 7-8
bit error rate
Observe from Fig. 6 that the QAOA based ML detector approaches the BER of classical ML detector
Section VII and Fig. 6, pages 10-11