CoChat

Quantum Search Algorithms for Wireless Communications

Open access

The DOI matches its Crossref record; 203 of the 204 references it cites were found in a registry or an index.

Abstract

Faster, ultra-reliable, low-power, and secure communications has always been high on the wireless evolutionary agenda. However, the appetite for faster, more reliable, greener, and more secure communications continues to grow. The state-of-the-art methods conceived for achieving the performance targets of the associated processes may be accompanied by an increase in computational complexity. Alternatively, a degraded performance may have to be accepted due to the lack of jointly optimized system components. In this survey we investigate the employment of quantum computing for solving problems in wireless communication systems. By exploiting the inherent parallelism of quantum computing, quantum algorithms may be invoked for approaching the optimal performance of classical wireless processes, despite their reduced number of cost-function evaluations. In this contribution we discuss the basics of quantum computing using linear algebra, before presenting the operation of the major quantum algorithms, which have been proposed in the literature for improving wireless communications systems. Furthermore, we investigate a number of optimization problems encountered both in the physical and network layer of wireless communications, while comparing their classical and quantum-assisted solutions. Finally, we state a number of open problems in wireless communications that may benefit from quantum computing.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/comst.2018.2882385

Cites

203 of 203 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1 The structure of the paper.
Fig. 1 The structure of the paper.CC-BY · From the PDF
Fig. 2 The 2D representation of a qubit, when the amplitudes of its quantum states are real-valued.
Fig. 2 The 2D representation of a qubit, when the amplitudes of its quantum states are real-valued.CC-BY · From the PDF
Fig. 3 The generic 3D representation of a qubit using a Bloch sphere, when the amplitudes of its quantum states are complex-valued.
Fig. 3 The generic 3D representation of a qubit using a Bloch sphere, when the amplitudes of its quantum states are complex-valued.CC-BY · From the PDF
Fig. 4 The circuit representation of the Hadamard gate H , of the three Pauli gates X , Z and Y , as well as of the Controlled-NOT operation, of the general Controlled-U gate and of the Toffoli gate.
Fig. 4 The circuit representation of the Hadamard gate H , of the three Pauli gates X , Z and Y , as well as of the Controlled-NOT operation, of the general Controlled-U gate and of the Toffoli gate.CC-BY · From the PDF
Fig. 5 Timeline of quantum computing milestones.
Fig. 5 Timeline of quantum computing milestones.CC-BY · From the PDF
Fig. 6 The quantum circuit employed in Shor's algorithm for finding the period of the function in (29) [33].
Fig. 6 The quantum circuit employed in Shor's algorithm for finding the period of the function in (29) [33].CC-BY · From the PDF
Fig. 7 The quantum circuit of the Quantum Phase Estimation Algorithm, which estimates the eigenvalues of a unitary operator U , which corresponds to its eigenvector | φ 〉 , as described in (30) [48].
Fig. 7 The quantum circuit of the Quantum Phase Estimation Algorithm, which estimates the eigenvalues of a unitary operator U , which corresponds to its eigenvector | φ 〉 , as described in (30) [48].CC-BY · From the PDF
Fig. 8 Grover operator's quantum circuit including an Oracle, two n -qubit Hadamard gates H and an n -qubit phase shift gate P 0 . The HP 0 H operator forms the diffusion operator of the Grover operator G = HP 0 H · O [28].
Fig. 8 Grover operator's quantum circuit including an Oracle, two n -qubit Hadamard gates H and an n -qubit phase shift gate P 0 . The HP 0 H operator forms the diffusion operator of the Grover operator G = HP 0 H · O [28].CC-BY · From the PDF
Fig. 9 Example of Grover's QSA in a database with N = 32 entries, where the searched value exists only in the entry with index 18. Since there is only a single solution S = 1 in a database of size N = 32, we have to perform L opt = 4 Grover iterations. The red dashed lines indicate the mean value of the amplitudes after each Oracle operation.
Fig. 9 Example of Grover's QSA in a database with N = 32 entries, where the searched value exists only in the entry with index 18. Since there is only a single solution S = 1 in a database of size N = 32, we have to perform L opt = 4 Grover iterations. The red dashed lines indicate the mean value of the amplitudes after each Oracle operation.CC-BY · From the PDF
Fig. 10 Flowchart of the BBHT QSA. The colored box represents the operation of Grover's QSA's quantum circuit of Fig. 8, while the rest of the steps are performed in the classical domain. The value of λ remains constant throughout the operation, while m is always initialized to 1. When the maximum number of allowed iterations L max is at least 4 . 5 √ N , there is a ≈ 100% probability of success.
Fig. 10 Flowchart of the BBHT QSA. The colored box represents the operation of Grover's QSA's quantum circuit of Fig. 8, while the rest of the steps are performed in the classical domain. The value of λ remains constant throughout the operation, while m is always initialized to 1. When the maximum number of allowed iterations L max is at least 4 . 5 √ N , there is a ≈ 100% probability of success.CC-BY · From the PDF
Fig. 12 The quantum circuit of the Quantum Counting Algorithm [34]. It employs the quantum circuit of the QPEA shown in 7, where the U operator is the Grover operator G and the quantum function register is initialized to an equiprobable superposition of all states, which represents the eigenvector of Grover's operator.
Fig. 12 The quantum circuit of the Quantum Counting Algorithm [34]. It employs the quantum circuit of the QPEA shown in 7, where the U operator is the Grover operator G and the quantum function register is initialized to an equiprobable superposition of all states, which represents the eigenvector of Grover's operator.CC-BY · From the PDF
Fig. 13 The quantum circuit of the Quantum Mean Algorithm [55]. It employs the quantum circuit of the QPEA shown in 7, where the U operator is the function's operator U f = f ( x ) . The quantum function register is initialized to the superposition of states | Ψ 〉 , using n Hadamard gates and the operator A , which includes two operations of U f and a controlled rotation of the ( n + 1)th auxiliary qubit. The circuit estimates the mean value of the function's values a = ∑ N x =0 f ( x ) / N .
Fig. 13 The quantum circuit of the Quantum Mean Algorithm [55]. It employs the quantum circuit of the QPEA shown in 7, where the U operator is the function's operator U f = f ( x ) . The quantum function register is initialized to the superposition of states | Ψ 〉 , using n Hadamard gates and the operator A , which includes two operations of U f and a controlled rotation of the ( n + 1)th auxiliary qubit. The circuit estimates the mean value of the function's values a = ∑ N x =0 f ( x ) / N .CC-BY · From the PDF
Fig. 14 The quantum circuit of the Quantum Weighted Sum Algorithm [56]. It employs the quantum circuit of the QMA shown in 13, with the difference that the quantum function register is not equiprobably initiliazed. Rather, the initilization is performed based on unitary rotation gates, which rely on the weights of the desired weighted sum.
Fig. 14 The quantum circuit of the Quantum Weighted Sum Algorithm [56]. It employs the quantum circuit of the QMA shown in 13, with the difference that the quantum function register is not equiprobably initiliazed. Rather, the initilization is performed based on unitary rotation gates, which rely on the weights of the desired weighted sum.CC-BY · From the PDF
Fig. 15 The problem of Multi-User Detection in the uplink of a synchronous multiple access system.
Fig. 15 The problem of Multi-User Detection in the uplink of a synchronous multiple access system.CC-BY · From the PDF
Fig. 16 Inside a quantum multi-user detector.
Fig. 16 Inside a quantum multi-user detector.CC-BY · From the PDF
Fig. 17 System model of a joint channel estimation and multi-user detection receiver in the uplink of a multi-carrier NOMA system employing decisiondirected channel estimation.
Fig. 17 System model of a joint channel estimation and multi-user detection receiver in the uplink of a multi-carrier NOMA system employing decisiondirected channel estimation.CC-BY · From the PDF
Fig. 18 The problem of Multi-User Transmission in the downlink of a multiple access system.
Fig. 18 The problem of Multi-User Transmission in the downlink of a multiple access system.CC-BY · From the PDF
Fig. 19 The resultant legitimate constellation of each user layer, after applying a perturbation vector.
Fig. 19 The resultant legitimate constellation of each user layer, after applying a perturbation vector.CC-BY · From the PDF
Fig. 20 The design methodology for the vector perturbation precoding for MUT.
Fig. 20 The design methodology for the vector perturbation precoding for MUT.CC-BY · From the PDF
Fig. 21 Exemplified topology for routing optimization in a Heterogeneous Network (HetNet) [118].
Fig. 21 Exemplified topology for routing optimization in a Heterogeneous Network (HetNet) [118].CC-BY · From the PDF
Image 21
CC-BY · From the PDF
Fig. 23 The BBHT-QSA chain process used in [65], [66], [122], and [134] for identifying a single Pareto-optimal route.
Fig. 23 The BBHT-QSA chain process used in [65], [66], [122], and [134] for identifying a single Pareto-optimal route.CC-BY · From the PDF
Fig. 24 The indoors localization problem, where an accurate position of the user has to be estimated. (a) Uplink localization, where a mm-Wave anchor processes the received line of sight path, as well as the reflected paths. Based on the RSSI, the ToA and the AoA, the mm-Wave anchor may initially reduce the search space. Then, it may employ the fingerprinting methodology for comparing the received signals to those stored in a pre-calculated database. (b) Downlink localization using a VLC system, where each LED panel is switched on and off sequentially. The RSSI at the user by each LED access point is compared to a pre-calculated database, following the fingerprinting methodology. Quantum search may be employed for searching in the databases in both the downlink and the uplink localization methods.
Fig. 24 The indoors localization problem, where an accurate position of the user has to be estimated. (a) Uplink localization, where a mm-Wave anchor processes the received line of sight path, as well as the reflected paths. Based on the RSSI, the ToA and the AoA, the mm-Wave anchor may initially reduce the search space. Then, it may employ the fingerprinting methodology for comparing the received signals to those stored in a pre-calculated database. (b) Downlink localization using a VLC system, where each LED panel is switched on and off sequentially. The RSSI at the user by each LED access point is compared to a pre-calculated database, following the fingerprinting methodology. Quantum search may be employed for searching in the databases in both the downlink and the uplink localization methods.CC-BY · From the PDF
Image 24
CC-BY · From the PDF
Image 25
CC-BY · From the PDF
Image 26
CC-BY · From the PDF
Image 27
CC-BY · From the PDF
Image 28
CC-BY · From the PDF
Image 29
CC-BY · From the PDF
Image 30
CC-BY · From the PDF

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Items 201–203 of 203

Research works printed but not linked: 4

  1. jordan, 2011, Quantum Algorithm Zoo
  2. mosca, 2012, Quantum Algorithms, 2303
  3. verdu, 1998, Multiuser Detection
  4. 10.1109/JSAC.2015.2430520 · doi:10.1109/jsac.2015.2430520

Cited by

See all 159

Metadata

Authors
Botsinis, P., Alanis, D., Babar, Z., Nguyen, H. V., Chandra, D., Ng, S. X., & Hanzo, L.
Affiliations
University of Southampton (GB)
Venue
IEEE Communications Surveys & Tutorials
Published
2019
Volume
21
Issue
2
Pages
1209-1242
ISSN
  • 1553-877X (ISSN-L)
  • 2373-745X
OpenAlex
W2947173962
Cited by
149
References
204
Citations by year
2026: 11 · 2025: 19 · 2024: 30 · 2023: 30 · 2022: 20 · 2021: 21 · 2020: 14 · 2019: 4
FWCI
5.49
Type
journal article
Language
en
Open access
Locations
  • IEEE Communications Surveys & Tutorials (publishedVersion, cc-by)
  • ePrints Soton (University of Southampton) (submittedVersion)
Funders
Engineering and Physical Sciences Research Council (EP/L018659/1)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
Keywords
quantum search, quantum computing, wireless communication, quantum algorithms, optimization problems, physical layer, network layer, quantum-assisted optimization, computational complexity, low-power communication, secure communication

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.