Make your paper interactiveCreate

Text from the interactive explanation

Quantum Algorithms for Wireless Communications

Panagiotis Botsinis, Dimitrios Alanis, Zunaira Babar, Hung Nguyen, Daryus Chandra, Soon Xin Ng, Lajos Hanzo

Original paper

Quantum algorithms for wireless communications · a tutorial survey, 2018

When many phones share the airwaves, the tower has to work out which combination of signals they sent, and the list of possibilities explodes. Botsinis, Alanis, Babar, Nguyen, Chandra, Ng and Hanzo survey how quantum algorithms could search such lists in far fewer steps. Below, a simulated quantum search is already running.

Preparing the register…

1 · The problem

The crowded airwaves

Your phone sends data as a stream of symbols . In a common scheme called QPSK, each symbol is one of four “directions”, ↗ ↖ ↙ ↘, so each one carries two bits.

To fit in more users, next-generation networks plan to let several phones transmit on the same frequency at the same time ( non-orthogonal multiple access , or NOMA). The tower then hears only the sum: each phone’s symbol, stretched and turned by its own radio path (its channel ), plus noise.

Try it. The ✦ is what the tower heard. Every dot is what it would have heard, without noise, for one combination of symbols. Tap the dot you think the phones sent.

16 combinations to compare

Picking the closest dot is exactly what the optimal maximum-likelihood detector does: compare what was heard with every possible combination and take the closest. The trouble is how fast that list grows.

1,099,511,627,776combinations to compare

The tower can’t take its time, either: next-generation “ultra-reliable low-latency” links aim to finish their processing within a few OFDM symbols (an OFDM symbol is one time slot of a 4G/5G signal), a tiny fraction of a millisecond. Shortcuts exist, such as decoding the strongest phone first and subtracting it ( successive interference cancellation ), but they lose accuracy when the phones’ signals look alike. So the survey asks: could a quantum computer search the full list instead?

2 · The new ingredient

A register that holds every candidate at once

An ordinary bit is 0 or 1. A qubit can be in a superposition of both, written a|0⟩ + b|1⟩. The numbers a and b are its amplitudes . Picture the state as an arrow: its shadow on each axis is one amplitude.

When you measure a qubit you never see the arrow. You get a plain 0 or 1, with chances a² and b², and the arrow collapses onto what you saw.

Try it. Drag the arrow, then measure. A single reading is a coin toss; the tally of a hundred settles on the squared amplitudes.

Amplitudes can be negative: the arrow can point below the axis. A measurement can’t tell a from −a, since both square to the same chance. Quantum operations can tell them apart, and Grover’s search depends on that.

Put n qubits together and the register holds 2n amplitudes, one for every n-bit number. A Hadamard gate on each qubit spreads them evenly, so every entry gets the same amplitude. Applying an operation to the register then acts on all 2n entries together, which the paper calls quantum parallelism .

The catch: holding every candidate is not the same as finding the right one. Reading the register is like drawing one card at random from the deck. The trick is to tilt the odds before you look .

3 · The lever

Flip, reflect, repeat: Grover’s search

In 1996 Lov Grover found a way to tilt the odds. Start with all N entries equal, then repeat two moves:

The oracle , a circuit that can recognise the wanted entry, flips the sign of its amplitude. Nothing measurable changes yet.

The diffusion step reflects every amplitude about the average (the dashed line). The flipped entry sits far below the average, so it bounces far above it, while everything else shrinks a little.

Below is the paper’s own worked example (its Fig. 9), recomputed live: 32 entries, with the wanted one at index 18.

Predict first: how many rounds until reading entry 18 is almost certain?

Grover’s search needs about (π/4)·√N rounds; checking entries one by one needs about N/2 looks on average. For a million entries that is roughly 785 rounds instead of 500,000 looks, a quadratic saving, and Grover’s method is provably the best possible for an unsorted list.

Investigate. Does doubling N double the rounds? Mark four entries: what happens? Mark none: what does the search do? And keep pressing past the peak: the survey notes that too many rounds can drive the chance of success back towards zero.

That last point is Grover’s weakness: to know when to stop, it must know how many entries are marked, and it must be able to recognise the answer. A cell tower knows neither.

4 · The detector

Finding the best without knowing it in advance

Nobody can hand the tower’s oracle the right message; that is the very thing we are looking for. What the tower can do is score every candidate: how far is the signal it would have produced from the signal actually heard? The best candidate has the lowest score.

Two refinements of Grover’s search handle this:

BBHT search (Boyer, Brassard, Høyer and Tapp) copes with not knowing how many entries are marked. It tries a random number of rounds, checks what it read with an ordinary computer, and widens the range a little each time.

Dürr–Høyer search uses BBHT to find a minimum. Pick a candidate at random and make its score the bar to beat. The oracle marks every candidate that scores better. Search. Whenever a better one turns up, lower the bar and go again.

Watch it work on a real received signal from three phones (64 candidates). Lighter bars score better than the bar to beat; below, their amplitudes rise together while each attempt runs.

How often does the search land on the true best candidate, and at what cost?

Look at the cost: with just 64 candidates the quantum route spends roughly as many evaluations as checking all 64. So where is the win?

5 · The payoff

When does the shortcut pay off?

Each extra phone multiplies the list of combinations by 4, but its square root only by 2. Dürr–Høyer needs at most 22.5·√N Grover rounds (and at least 4.5·√N, when the first random guess is already the best), so the gap opens quickly.

Drag to 20 phones: over a trillion comparisons, against about 24 million Grover rounds. That is the kind of saving the survey is about: matching, or nearly matching, the optimal detector at a fraction of the cost. The paper reports that quantum-assisted multi-user detectors built this way approach the optimal detector’s performance.

6 · The bigger picture

The same lever, all over the network

Multi-user detection is one of seven problem families the survey examines. In each, a hard search sits somewhere inside the network, and Dürr–Høyer or another quantum algorithm takes the place of an exhaustive search or a classical rule of thumb. Choose one:

How fast do routes multiply?

Our count of loop-free routes from source to destination through any of the relays, when every node can reach every other. The survey’s Fig. 22 plots the same runaway growth up to 70 nodes, which is why exhaustive searches become hopeless and why each route must also be weighed on error rate, delay and power at once.

7 · The evidence

Inside the quantum detector, and what kind of evidence this is

The survey draws the quantum multi-user detector as nested shells: Grover’s circuit sits inside BBHT, which sits inside Dürr–Høyer, with an ordinary processor around it turning the result into the probabilities the decoders need. Each shell needs to know less about the answer. Tap a shell.

Tap a shell to see what each layer stops needing to know.

A tutorial survey

The paper explains quantum computing from scratch for communication engineers, using linear algebra and circuit diagrams. It walks through the main quantum algorithms (Deutsch, Simon, Shor, phase estimation, Grover and its relatives, quantum counting, HHL, quantum mean and weighted sum) and gathers the quantum-assisted solutions proposed for wireless problems.

Theory and simulation

No universal quantum computer existed, so the algorithms were demonstrated by simulating them on classical supercomputers , assuming such a computer is available. Comparisons with classical methods rest on the algorithms’ theoretical capabilities: at the time of writing, no quantum-assisted solution to a practical wireless problem had been demonstrated on real hardware.

Hardware in 2018

D-Wave’s 2000Q quantum annealer had 2,000 qubits; IBM’s gate-based Q Experience had 20, with a 50-qubit machine announced for 2020. Grover’s circuit could already be assembled with IBM’s tools, at least for a handful of qubits.

Deliberately out of scope

The authors focus on the algorithms, their performance gains and their complexity. Scalability, timing, the hardware required and how classical and quantum parts of a modem chip would work together are, they note, still to be considered.

“For a specific complexity budget, a performance gain is observed when the quantum algorithms are used. Similarly, by employing the quantum algorithms, a specific performance target may be reached at a lower computational complexity.”

1981 Feynman proposes a framework for simulating the evolution of quantum systems

1985 Deutsch: one question answers what classically needs two

1994 Shor: factoring; Simon: exponential speed-up for a black-box puzzle

1996 Grover’s quantum search; Dürr–Høyer minimum search

1998 BBHT search for an unknown number of answers

2000 Quantum counting; Hogg’s heuristic quantum search

2009 HHL: solving linear equations

2011–13 Quantum mean and weighted-sum algorithms, used in soft-output detectors

8 · Back to the tower

A tower with a quantum co-processor

The survey pictures base stations where classical and quantum processors work side by side, exchanging information. In the quantum detectors it reviews, an ordinary processor prepares scores and final decisions while the quantum search does the heavy searching. Its list of open problems sketches where that could go next:

Coordinated multi-point. A phone at the edge of a cell is served by several towers at once, which treat each other’s “interference” as useful information, multiplying the data to search.

Drone networks. Optimal routes for battery-limited, mission-critical drones, and where to place drones used as emergency base stations.

Proactive caching. Deciding which popular content to store in which node to cut delay and power, a multi-objective problem much like routing.

Quantum-aided neural networks , built from recently proposed quantum perceptrons.

Smarter searches. Candidate messages in multi-user detection share symbols, so neighbouring entries are related; Hogg’s heuristic quantum search could exploit that to cut the cost further.

A tower that weighs a trillion possibilities in a blink does not exist yet. But how it could work is already written down: flip, reflect, repeat.

↑ Back to the opening search

About the paper

Panagiotis Botsinis, Dimitrios Alanis, Zunaira Babar, Hung Nguyen, Daryus Chandra, Soon Xin Ng and Lajos Hanzo. “Quantum Algorithms for Wireless Communications.” IEEE Communications Surveys & Tutorials, 2018. School of Electronics and Computer Science, University of Southampton. Author-hosted PDF.

All visualisations on this page are original illustrations and simulations made for this explainer; none of the paper’s figures are reproduced. Results marked “simulated” are computed live in your browser from the algorithms the paper describes (Grover, BBHT and Dürr–Høyer search) using a simplified signal model; they illustrate the method and are not the paper’s reported results. The worked example in chapter 3 recomputes the paper’s Fig. 9 (32 entries, entry 18 marked). Complexity bounds and reported findings are taken from the survey.

Topics in this iPaper

Engineering
In this survey we investigate the employment of quantum computing for solving problems in wireless communication systems.

Abstract, page 1

Computer science
we describe the general problems and the high-level operation of the major quantum algorithms

Section II-B, page 8

Physics
we state the basic postulates of quantum mechanics and describe how quantum computing systems can be represented

Section II-A, page 4

quantum computing
we discuss the basics of quantum computing using linear algebra

Abstract, page 1

quantum search algorithms
Grover’s QSA succeeds in finding the desired entry with 100% probability of success after querying the database on the order of O(√N) times

Section II-B6, page 10

multi user detection
the DH QSA of Section II-B8 was employed in [56], [62], where it was demonstrated that it approaches the optimal performance

Section III-A3, page 19

wireless communications
potential applications in the field of wireless communications, which would benefit from using a quantum computer

Section III, page 16

non orthogonal multiple access
in the uplink of a NOMA system [5], [72]–[76] the users are allowed to simultaneously share the same frequency and time resources

Section III-A1, page 17

multi objective routing
the NDQO algorithm succeeds in identifying the entire set of Pareto-optimal routes at a complexity on the order of O(L√L)

Section III-D3, page 26

Quantum Algorithms for Wireless Communications — Interactive explanation | iPaper.ai