Text from the interactive explanation
Quantum Search Algorithms, Quantum Wireless, and a Low-Complexity Maximum Likelihood Iterative Quantum Multi-User Detector Design
Panagiotis Botsinis, Soon Xin Ng, Lajos Hanzo
Original paperAn airport. Ten thousand phones. One base station.
When thousands of phones transmit at once, their signals land on top of each other. The perfect receiver, called maximum likelihood , untangles them by testing every combination of what everyone might have sent. At the paper's airport (10,000 users, 64-QAM) that is 6410000 combinations. Botsinis, Ng and Hanzo ask whether quantum search could make that perfect receiver affordable.
The detector race
Every tick on the ring is one possible combination. The amber arm checks them one by one. The cyan needles are a quantum search tilting the odds toward the best one. One clock tick = one evaluation.
A new burst of signals arrives. Both receivers start searching.
N = 4⁴ = 256 combinations
Predict: with just 2 BPSK users (4 combinations), who wins? Then try 10 or 12 users.
classical check
quantum amplitude
sign flipped by the oracle
how well a combination explains the signal
marked: beats the current best
Simulated in your browser on an illustrative signal model (Gold codes, fading, noise). Following the paper, one quantum oracle call is assumed to take as long as one classical evaluation.
Chapter 1 · Everyone talks at once
A crowd is a search problem
In the paper's system (DS-CDMA, the code-division scheme behind 3G phones), each phone multiplies its bits by its own fast “spreading code” so the base station can tell users apart. But the codes overlap a little, so every user leaks into the others. That is multi-user interference .
Here two users each send +1 or −1. The base station hears one point on this plane: what it picked up for user 1 (across) and for user 2 (up). The four dots are where that point would land with no noise, one for each pair the users might have sent. Noise blurs it.
The best receiver scores every candidate pair by how well it explains what was heard. That score is the paper's cost function , f(x) = exp(−‖y − Rx‖² / 2σ²): the closer the candidate dot, the more likely. A simpler receiver judges each user on its own, by which side of the dashed axis the point falls.
Try this: press “Send a new pair” and guess what was sent before looking. Then raise the code overlap: the coloured regions, where the best-match receiver picks each pair, twist away from the simple quadrants.
Illustrative two-user model of y = Rx + noise (paper Eq. 1 and 4).
With overlapping codes, only a receiver that compares whole combinations gets it right. That is multi-user detection . Its optimal form, the maximum-likelihood (ML) detector, has to score every combination.
Chapter 2 · The exponential wall
Every new user multiplies the work
With K users each choosing one of M symbols, the base station faces MK combinations. Two users sending ±1: 4. Four users with QPSK (4 symbols each): 256. Each tile in the grid is one combination, and each new user splits every tile into M smaller ones.
The paper points out that this explosion is what keeps the optimal detector out of real networks. Practical systems settle for cheaper, imperfect detectors instead.
Try this: add users, switch to 64-QAM, then press the airport button.
← the scale of a quantum search
A search needing only about √N looks instead of N would turn 256 into about 16, and a million into about a thousand. Quantum search promises exactly that square-root scaling.
Chapter 3 · One box, every key
Superposition is not yet a shortcut
The paper explains quantum computing with a box and eight keys, only one of which opens it (its Fig. 1). A serial computer tries the keys one after another. A parallel computer builds eight boxes and tries them all at once. A quantum computer tries all eight keys in a single box.
It can, because its unit of information, the qubit , can be 0 and 1 at the same time: “like a spinning coin in a box” that only becomes heads or tails when someone looks. Three qubits hold all 8 key numbers at once, and one quantum evaluation of the lock (the oracle ) acts on all of them together.
Try this: open the quantum box several times.
Illustration of the paper's Fig. 1 metaphor; outcomes are sampled from an equal superposition of 8 states.
Looking, a measurement , shows just one key, and every key is equally likely. Holding everything at once only pays off if the odds can be tilted toward the right key before looking. That tilting is Grover's algorithm.
Chapter 4 · Two reflections make a rotation
How Grover's search pumps up the answer
Each possible answer carries an amplitude : a number whose square is the chance of seeing that answer when you look. At the start they are all equal.
One Grover step makes two moves. Oracle: flip the sign of the answer's amplitude. Its bar turns magenta and points down, and its probability is unchanged. Diffusion: reflect every bar about their average, the dashed line. The flipped bar sat far below the average, so it rebounds far above it while the others shrink a little.
Seen geometrically (paper Fig. 11), the two reflections add up to a rotation by a fixed angle, from “not the answer” toward “the answer”. That angle is 2φ, where sin φ = √(S/N) for S answers among N items.
Exact statevector simulation of Grover's algorithm.
About (π/4)·√N steps bring the state close to the answer: 25 steps for 1,024 items, where a classical search averages about 512 looks. Keep going and the rotation carries past the answer, so the probability falls and later rises again, the waves of the paper's Figs. 13–14. In the paper's own example (4 items, searching for the cost value 0.38), a single step reaches the answer with certainty.
Chapter 5 · Searching for the best without knowing what it looks like
The Dürr–Høyer trick: keep raising the bar
Grover's oracle must recognise the answer. A receiver doesn't know in advance what the best combination's score will be. It only knows how to compare two candidates.
BBHT (Boyer, Brassard, Høyer and Tapp) copes with an unknown number of answers. It picks a random number of Grover steps and looks. If that fails, it allows a few more steps next time: the range grows by a factor of 6/5.
Dürr–Høyer turns this into a minimum-finder. Start from a guess (the paper uses the simple one-user-at-a-time decision). Let the oracle mark every combination that explains the signal better than the current best. Search, look, and if the result is better, make it the new bar. When a long search (4.5·√N oracle calls) finds nothing better, stop. The bar is the maximum-likelihood answer.
Try this: watch the white (marked) bars dwindle as the bar rises. Switch to 256 combinations and compare the oracle calls with the 256 an exhaustive search needs. Then start from a random guess.
Statevector simulation of the paper's Algorithms 1 and 2 on an illustrative DS-CDMA signal.
What the paper found (simulations, hard decisions)
In the paper's simulations of 4, 6 and 8 QPSK users, the Dürr–Høyer detector made the same decisions as the ML detector, so its error rate matched ML. It needed far fewer cost-function evaluations on average:
ML: all MK combinations Dürr–Høyer: average reported
The final stretch, when nothing is marked any more, is the price of certainty. It is why Dürr–Høyer always spends at least about 4.5√N calls, and why it wins only when N is large.
Chapter 6 · Not just an answer, but a confidence
Reading a sum with a quantum ruler
Modern receivers work in rounds. The detector hands the error-correcting decoder not just bits but a confidence for each one, a log-likelihood ratio (LLR). Positive means “probably 0”, negative means “probably 1”, and the bigger the number, the surer. The decoder sends refined beliefs back, and they repeat (paper Fig. 3).
An LLR is the logarithm of a ratio of two sums: the cost function, weighted by prior beliefs, summed over every combination in which the bit is 0, and again where it is 1. Each sum has MK/2 terms, so the exponential wall is back.
The paper's new Quantum Weighted Sum Algorithm (QWSA) prepares a quantum state whose chance of raising a “yes” flag equals the sum a. That turns the sum into an angle θ, with a = sin²θ. Then amplitude estimation reads the angle off a ruler with 2l marks, using l control qubits. The cost depends on l, not on how many users there are.
Try this: read the ruler at l = 3, 5 and 8. Then untick the normalization box.
Paper's example size: 2 users, QPSK, 8 terms per sum. Readings are sampled from the amplitude-estimation outcome distribution.
More qubits make a finer ruler. Tiny sums fall into the blind zone and read as zero. The paper avoids this by first running Dürr–Høyer to find the best combination and dividing every score by that best score (its Eq. 81), which keeps the sums readable. Together the two algorithms make the paper's soft-output quantum detector , one that can plug into an iterative receiver.
Chapter 7 · The evidence
Does the quantum receiver match the perfect one?
The authors simulated complete receivers, with spreading codes, fading radio channels, error-correcting codes and iterative decoding. The quantum algorithms themselves were simulated on a classical computer.
When does it pay off?
Matching performance is half the story. The other half is cost. Using the paper's complexity formulas (its Eq. 79–80), the chart counts cost-function evaluations per time slot. The ML detector needs MK. The quantum-assisted detector needs a fixed amount per bit for the QWSA (2l+3 per bit, per decoding round J), plus Dürr–Høyer work that grows like √(MK).
Beyond 10 QPSK users , or 6 8-PSK users , the quantum-assisted detector is cheaper (l = 11, J = 4).
With about 4 million evaluations per slot, it supports 33 BPSK users instead of 22.
For 64-QAM with 5 users , it costs about 0.25% of ML.
Using an ant-colony search instead of Dürr–Høyer for the normalization, 30 QPSK users cost roughly 10−12 of ML. Performance then depends on that search finding the true best.
For just 2 users with 8-PSK , the quantum-assisted detector can need up to 393,446 evaluations against ML's 64. The advantage belongs to big systems.
ML DHA-QWSA (worst–best case) ACO-QWSA budget
Curves computed from the paper's complexity formulas. The DHA-QWSA band spans Dürr–Høyer's worst case (22.5√N) and best case (4.5√N).
Back to the airport
What this brings closer
Checking every combination is hopeless for a big crowd. This paper charts a route to the perfect receiver's answers at a fraction of the work. A search that grows like √N (Dürr–Høyer) finds the most likely combination, and confidence estimates whose cost does not grow with the crowd (QWSA) feed the decoder. In the authors' simulations, the result matched the optimal detector.
The larger motivation, set out in the paper's introduction, is capacity. A single link's capacity grows only logarithmically with transmit power. If many superimposed parallel streams (users, antennas, frequencies) could be detected with low-complexity full-search techniques, throughput could grow linearly instead, pointing toward power-efficient, “green” wireless systems. Low-complexity detection also means less power drawn by handsets and base stations.
The quantum steps sit inside an otherwise ordinary receiver: its inputs and outputs stay classical (paper Fig. 2), so the quantum detector can slot into today's iterative designs.
What was shown, and how
The paper proposes the algorithms and evaluates them by computer simulation . The quantum operations were simulated, assuming one quantum oracle call takes as long as one classical evaluation. No quantum hardware was involved. The gains belong to large systems with many users and dense symbol alphabets. In small ones the classical detector is cheaper.
Source
Panagiotis Botsinis, Soon Xin Ng and Lajos Hanzo. “Quantum Search Algorithms, Quantum Wireless, and a Low-Complexity Maximum Likelihood Iterative Quantum Multi-User Detector Design.” IEEE Access, vol. 1, pp. 94–122, 2013. doi:10.1109/ACCESS.2013.2259536
Figures 20, 21, 22 and 25 are reproduced from this article, published open access under a Creative Commons Attribution (CC BY) license. They are cropped from the original figures, with captions rewritten.
All other visuals are original and drawn in your browser. The detector race, the Grover and Dürr–Høyer labs and the amplitude-estimation dial simulate the paper's algorithms on an illustrative signal model. The two-user plane and the key box are illustrations. Reported numbers come from the paper.
Topics in this iPaper
Engineering
demonstrate its application using the design example of a direct-sequence code division multiple access system
Abstract, page 94
Computer science
we employ a QSA that finds the minimum of a function in order to perform optimal hard MUD with a quadratic reduction in the computational complexity
Abstract, page 94
multi user detection
We propose a soft-input soft-output quantum-assisted MUD (QMUD) scheme, which is the quantum-domain equivalent of the ML MUD.
Abstract, page 94
grover s algorithm
It was shown in [53] that it succeeds in finding the solution after O(√N) CF evaluations
Section VI-A, page 108
quantum amplitude estimation
Employ l qubits and the Quantum Amplitude Estimation (QAE) algorithm [51] to estimate the probability
Section VII, page 114
code division multiple access
a direct-sequence code division multiple access system employing bit-interleaved coded modulation relying on iterative decoding
Abstract, page 94
exit chart
Both our extrinsic information transfer charts and bit error ratio curves show that the performance of the proposed QMUD and that of the optimal classic MUD are equivalent
Abstract, page 94
quantum computing
This is where Quantum Computing may be employed in the above-mentioned systems for reducing the complexity
Section I-B, page 97