10.1109/TQE.2020.DOI

This work received funding from the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (Grant
agreement No. 819819) and the European Union’s Horizon Europe programme (ERC
PoC, Grant agreement No. 101112697). It has also received funding from the
European Union HORIZON programme under iSEE-6G GA No. 101139291.

Corresponding author: Ioannis Krikidis (email: krikidis@ucy.ac.cy).

# MIMO with $1$-bit Pre/Post-Coding Resolution: A Quantum Annealing Approach

IOANNIS KRIKIDIS1  Department of Electrical and Computer Engineering,
University of Cyprus, Cyprus (email<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the problem of digital pre/post-coding design in
multiple-input multiple-output (MIMO) systems with $1$-bit resolution per
complex dimension. The optimal solution that maximizes the received signal-to-
noise ratio relies on an NP-hard combinatorial problem that requires
exhaustive searching with exponential complexity. By using the principles of
alternating optimization and quantum annealing (QA), an iterative QA-based
algorithm is proposed that achieves near-optimal performance with polynomial
complexity. The algorithm is associated with a rigorous mathematical framework
that casts the pre/post-coding vector design to appropriate real-valued
quadratic unconstrained binary optimization (QUBO) problems. Experimental
results in a state-of-the-art D-WAVE QA device validate the efficiency of the
proposed algorithm. To further improve the efficiency of the D-WAVE quantum
device, a new pre-processing technique which preserves the quadratic QUBO
matrix from the detrimental effects of the Hamiltonian noise through non-
linear companding, is proposed. The proposed pre-processing technique
significantly improves the quality of the D-WAVE solutions as well as the
occurrence probability of the optimal solution.

###### Index Terms:

MIMO, quantum computing, quantum annealing, alternating optimization, D-WAVE,
pre/post-coding, $1$-bit.

=-15pt

##  I Introduction

Afundamental enabling technology for future 6G wireless communication systems
is massive/large multiple-input multiple-output (MIMO) systems [1]. By
exploiting the spatial degrees of freedom associated with the antenna arrays
and through appropriate signal processing, MIMO systems are able to support
the extremely high requirements of capacity, throughput and reliability.
However, as the number of antennas increases, the implementation
complexity/cost of conventional digital MIMO in terms of radio frequency (RF)
chains, digital-to-analogue converters (DACs) and/or analogue-to-digital
converters (ADCs), base-band signal processing etc. becomes a bottleneck for
practical applications [2]. To address this challenge, analogue/digital hybrid
MIMO architectures which split the processing into digital and analogue domain
to balance the trade-off between performance and implementation
complexity/cost have emerged as a promising solution [2]. Other relevant
techniques consider analogue-only signal processing where low-resolutions
phase shifters are used to implement analogue pre/post-coding (mainly suitable
for high frequency bands e.g., millimeter wave), or the employment of low-
resolution DACs/ADCs [3, 4].

In contrast to existing approaches, in this work, we study a basic (digital)
point-to-point MIMO system with low-resolution pre/post-coding processing;
specifically, we assume that both the transmitter and receiver employ $1$-bit
signal processing resolution ($1$-bit per complex dimension) in order to
extremely reduce complexity and power consumption111It is worth noting that
although $1$-bit processing at the transmitter is similar to $1$-bit DAC, the
assumption of $1$-bit processing at the receiver is fundamentally different to
conventional $1$-bit ADC; this assumption, makes the considered architecture
different from the existing $1$-bit DAC/ADC MIMO architectures [4].. This new
MIMO architecture is promising for future low-power/low-computation devices in
the era of the Internet of Things. Due to the complex-valued binary resolution
of the new MIMO architecture, the design of pre/post-coding vectors becomes an
NP-hard problem; it can be solved optimally through exhaustive search (ES)
over all the possible transmit/receive configurations corresponding to an
exponential complexity. To the best of the author’s knowledge, the considered
MIMO design problem is reported for the first time in this paper.

Adiabatic quantum computing is a promising tool to solve NP-hard problems by
using the principles of the Adiabatic Theorem [5]. Specifically, if a quantum
system is initially in the ground state (quantum state with the lowest energy)
of an initial Hamiltonian and the system evolves/changes slowly (gradually),
it will converge to the ground state of the final Hamiltonian. By encoding the
final Hamiltonian to the desired problem, the Adiabatic evolution can be used
to solve complex combinatorial optimization problems which are represented as
instances of the Ising model (equivalent to quadratic unconstrained binary
optimization (QUBO) problem) [6]. D-WAVE is a commercial analogue quantum
device that implements a noisy approximation of the quantum Adiabatic
algorithm called quantum annealing (QA) [5, 7]. This quantum device has
received considerable interest lately due to the high number of available
qubits (more than $5,000$ qubits in latest hardware architectures) and its
friendly interface for remote access. It is worth noting that in QA, instead
of analyzing the computation time/complexity of a given algorithm, we mainly
study the trade-off between time and the probability that the output is
correct.

D-WAVE QA is introduced as a promising computation tool to solve complex (NP-
hard) combinatorial problems in wireless communication system [8]. The
associated literature mainly focuses on the solution of the maximum-likelihood
detection problem in large multi-user MIMO systems [9, 10]; recent research
studies employ D-WAVE QA in other wireless communication problems such as
channel decoding (polar codes) [11], passive beamforming design in intelligent
reflecting surfaces [12], configuration selection in reconfigurable/fluid-
antenna systems [13], beam assignment in satellite systems [14] etc.. The
integration of D-WAVE QA in the design of wireless communication systems is a
new research area of paramount importance.

In this paper, we extend our work in [15] towards the design of $1$-bit
digital (complex-valued) pre/post coding vectors. Specifically, we solve the
problem of pre/post-coding design in a MIMO system with $1$-bit resolution per
complex dimension. We focus on the maximization of the received signal-to-
noise ratio (SNR) which due to the complex binary assumption relies to the
solution of an NP-hard complex-valued combinatorial problem. By using the
principles of alternating optimization and the computation capabilities of the
D-WAVE QA, an iterative algorithm is proposed which solves appropriate QUBO
instances at each iteration to gradually compute the pre/post-coding vectors.
An appropriate mathematical framework that converts the original complex-
valued combinatorial problem to real-valued QUBO instances is investigated.
Experimental results in a state-of-the-art D-WAVE QA device show that the
proposed iterative algorithm achieves near-optimal performance (similar to ES)
while ensuring polynomial complexity.

To further improve the quality of the returned distinct D-WAVE QA solutions, a
new pre-processing technique that preserves the quadratic QUBO matrix from the
detrimental effects of the Hamiltonian noise is proposed. The proposed pre-
processing technique is motivated by the non-uniform compression in pulse code
modulation (PCM) communication systems. Specifically, motivated by the
experimental observation that small magnitude elements ($\approx 0$) of the
quadratic matrix are more sensitive to the Hamiltonian noise [16] (similar to
quantization noise in PCM [17]), a non-linear companding ($\mu$-law) pre-
processing is proposed to boost small-magnitude elements without qualitatively
affecting the structure of the original QUBO problem. Experimental results
show that the proposed pre-processing technique improves the quality of the
D-WAVE solutions (we have less distinct solutions of higher quality) and
increases the probability of the optimal solution.

The remainder of this paper is organized as follows. The system model and the
problem formulation are described in Section II. Section III presents the
proposed QA-based iterative algorithm for the design of the $1$-bit pre/post-
coding vectors. The QUBO pre-processing technique that improves the efficiency
of the D-WAVE QA is presented in Section IV. Pertinent experimental examples
are presented in Section V. Finally, concluding remarks are discussed in the
last section.

Figure 1: $N_{R}\times N_{T}$ MIMO channel with $1$-bit pre/post-coding
vectors.

Notation: Boldface letters refer to vectors (lower case) or matrices (upper
case); $(\cdot)^{T}$, $(\cdot)^{H}$, $\|\cdot\|$, and $\|\cdot\|_{\max}$
denote transpose, complex conjugate transpose, Euclidean norm, and max-norm,
respectively; $\textrm{diag}(\boldsymbol{x})$ denotes a diagonal matrix whose
main diagonal is $\boldsymbol{x}$; $j=\sqrt{-1}$ is the imaginary unit;
$\mathcal{R}(\cdot)$ and $\mathcal{I}(\cdot)$ return the real and imaginary
part of their complex arguments, respectively; $\boldsymbol{x}(k:n)$ refers to
the vector with elements $x_{k},x_{k+1},\ldots,x_{n}$; the space of $x\times
y$ complex matrices is denoted by $\mathbb{C}^{x\times y}$, $\mathbbm{1}$
denotes an all-ones column vector of appropriate dimension;
$\textrm{sgn}(\cdot)$ denotes the sign function;
$\mathcal{CN}(\mu,\sigma^{2})$ denotes complex Gaussian distribution with mean
$\mu$ and variance $\sigma^{2}$.

##  II Problem formulation

We consider a point-to-point MIMO system consisting of $N_{T}$ and $N_{R}$
transmit and receive antennas, respectively [18]. Let
$\boldsymbol{H}\in\mathbbm{C}^{N_{R}\times N_{T}}$ denote the MIMO channel
matrix, where entries correspond to the channels between the transmit and and
receive antennas i.e., $h_{i,j}$ is the channel coefficient between the $j$-th
transmit antenna and the $i$-th receive antenna. Without loss of generality,
we assume normalized Rayleigh block fading channels i.e.,
$h_{i,j}\sim\mathcal{CN}(0,1)$.

The MIMO system operates in the beamforming mode [18] (single data flow) to
maximize the received SNR and thus digital pre/post- processing vectors are
adjusted accordingly. To reduce complexity and power consumption, both the
transmitter and the receiver employ vector processing of $1$-bit resolution
(i.e., $1$-bit for the real part and $1$-bit for the imaginary part). Fig. 1
schematically presents the system model.

Let $\boldsymbol{f}\in\mathcal{S}^{N_{T}\times 1}$ and
$\boldsymbol{g}\in\mathcal{S}^{N_{R}\times 1}$ denote the (unnormalized)
complex $1$-bit pre-coding and post-coding vectors, respectively, taking
values in the quantized complex set $\mathcal{S}\triangleq\\{\pm 1\pm 1j\\}$;
the normalized pre/post-coding vectors are given by
$\boldsymbol{f}/\|\boldsymbol{f}\|=\boldsymbol{f}/\sqrt{2N_{T}}$ and
$\boldsymbol{g}/\|\boldsymbol{g}\|=\boldsymbol{g}/\sqrt{2N_{R}}$,
respectively. We assume a perfect channel state information at both the
transmitter and the receiver. The received SNR is given by

$\displaystyle\rho(\boldsymbol{g},\boldsymbol{f})=\frac{P|\boldsymbol{g}^{H}\boldsymbol{H}\boldsymbol{f}|^{2}}{4N_{T}N_{R}\sigma^{2}},$
(1)

where $\sigma^{2}$ is the variance of the additive white Gaussian noise, $P$
is the transmit power, while the extra terms in the denominator are due to the
power normalization of the pre/post-coding vectors. Since the objective of the
MIMO system is to maximize the received SNR, we introduce the following design
problem

$\displaystyle\max_{\boldsymbol{f}\in\mathcal{S}^{N_{T}\times
1},\;\boldsymbol{g}\in\mathcal{S}^{N_{R}\times
1}}\;|\boldsymbol{g}^{H}\boldsymbol{H}\boldsymbol{f}|^{2}$ (2a)
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\Rightarrow\max_{\boldsymbol{f}\in\mathcal{S}^{N_{T}\times
1},\;\boldsymbol{g}\in\mathcal{S}^{N_{R}\times
1}}\;\boldsymbol{f}^{H}(\boldsymbol{H}^{H}\boldsymbol{g}\boldsymbol{g}^{H}\boldsymbol{H})\boldsymbol{f}$
(2b)
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\Rightarrow\max_{\boldsymbol{f}\in\mathcal{S}^{N_{T}\times
1},\;\boldsymbol{g}\in\mathcal{S}^{N_{R}\times
1}}\;\boldsymbol{g}^{H}(\boldsymbol{H}\boldsymbol{f}\boldsymbol{f}^{H}\boldsymbol{H}^{H})\boldsymbol{g}.$
(2c)

Due to the binary nature of the complex pre/post-coding vectors, the above
combinatorial problem is NP-hard; the optimal solution requires ES over all
the possible pre/post-coding vectors.

###  II-A Exhaustive search (ES)- Benchmark

The ES scheme evaluates the SNR expression in (1) for all the possible
pre/post-coding vectors and returns the solution with the maximum SNR. It is
obvious that the ES requires $2^{2N_{T}}\times 2^{2N_{R}}=2^{2(N_{T}+N_{R})}$
computations (complex valued vectors) and therefore its complexity becomes
exponential with the number of transmit/receive antennas. A more intelligent
ES scheme can take into account the computation symmetry embedded in (1) i.e.,
$\rho(\boldsymbol{g},\boldsymbol{f})=\rho(\pm\boldsymbol{g},\pm\boldsymbol{f})=\rho\big{(}-\mathcal{I}(\boldsymbol{f})+\mathcal{R}(\boldsymbol{f})j,+\mathcal{I}(\boldsymbol{g})-\mathcal{R}(\boldsymbol{g})j\big{)}=\rho\big{(}\mathcal{I}(\boldsymbol{f})-\mathcal{R}(\boldsymbol{f})j,-\mathcal{I}(\boldsymbol{g})+\mathcal{R}(\boldsymbol{g})j\big{)}$
corresponding to six equivalent computations and therefore the total number of
ES computations decreases to $2^{2(N_{T}+N_{R})}/6$; for both ES schemes, the
implementation is prohibited for large-scale MIMO topologies.

Algorithm 1 QA-based $1$-bit pre/post-coding design.

Input: $\boldsymbol{H}$, $\boldsymbol{g}_{l}^{(0)}\in\mathcal{S}^{N_{R}}$,
$\boldsymbol{f}_{l}^{(0)}\in\mathcal{S}^{N_{T}}$ with $l=1,\dots,L$, relative
tolerance $\delta$, $L$, $K$,
$\rho_{\textrm{old}_{l}}=\rho(\boldsymbol{g}_{l}^{(0)},\boldsymbol{f}_{l}^{(0)})$,
$k\leftarrow 0$.

1:for $l=1,2,\ldots,L$ do

2: repeat

3: $k\leftarrow k+1$

4: if $k>1$ then

5: Let $\rho_{\textrm{old}_{l}}=\rho_{\textrm{new}_{l}}$

6: end if

7: [D-WAVE] Solve
$\boldsymbol{b}_{f}^{*}\\!\\!=\\!\\!\arg\min_{\boldsymbol{b}_{f}}\boldsymbol{b}_{f}^{T}(-\boldsymbol{V}_{n})\boldsymbol{b}_{f}$
for $\boldsymbol{g}_{l}^{(k-1)}$.

8: Convert $\boldsymbol{b}_{f}^{*}$ to spin vector $\boldsymbol{f}_{l}^{(k)}$.

9: [D-WAVE] Solve
$\boldsymbol{b}_{g}^{*}\\!=\\!\arg\min_{\boldsymbol{b}_{g}}\boldsymbol{b}_{g}^{T}(-\boldsymbol{R}_{n})\boldsymbol{b}_{g}$
for $\boldsymbol{f}_{l}^{(k)}$.

10: Convert $\boldsymbol{b}_{g}^{*}$ to spin vector
$\boldsymbol{g}_{l}^{(k)}$.

11: Let
$\rho_{\textrm{new}_{l}}=\rho(\boldsymbol{g}_{l}^{(k)},\boldsymbol{f}_{l}^{(k)})$.

12: until
$|\rho_{\textrm{new}_{l}}-\rho_{\textrm{old}_{l}}|/|\rho_{\textrm{old}_{l}}|<\delta$
or $k\geq L$

13: Obtain
$(\boldsymbol{g}_{l},\boldsymbol{f}_{l})=(\boldsymbol{g}_{l}^{(k)},\boldsymbol{f}_{l}^{(k)})$.

14:end for

Output:
$(\boldsymbol{g}^{\textrm{qa}},\boldsymbol{f}^{\textrm{qa}})=\arg\max_{\boldsymbol{g}_{l},\boldsymbol{f}_{l}}\rho(\boldsymbol{g}_{l},\boldsymbol{f}_{l})$.

##  III QA-based $1$-bit pre/post-coding vector design

We propose a new algorithm that incorporates a QA solver in the design of the
$1$-bit complex pre/post-coding vectors. By taking into account the binary
combinatorial structure of the problem, we introduce an alternating
optimization algorithm that solves a QUBO problem at each iteration. The QUBO
formulations are solved through a state-of-the-art D-WAVE QA device [7]. More
specifically, based on the equivalent expression in (2b), we firstly fix the
vector $\boldsymbol{g}$ (by using a random solution in the initial step) and
we study the following combinatorial problem with respect to the pre-coding
vector $\boldsymbol{f}$ i.e.,

$\displaystyle\max_{\boldsymbol{f}\in\mathcal{S}^{N_{T}\times
1}}\;\boldsymbol{f}^{H}(\boldsymbol{H}^{H}\boldsymbol{g}\boldsymbol{g}^{H}\boldsymbol{H})\boldsymbol{f}.$
(3)

Given that the involved matrices/vectors in (3) are complex valued (which it
is not compatible with current QA solvers), we transform the problem in (3) to
an equivalent real-valued form

$\displaystyle\max_{\boldsymbol{f}_{r}\in\mathcal{P}^{2N_{T}\times
1}}\boldsymbol{f}_{r}^{T}(\boldsymbol{J}^{T}\boldsymbol{J})\boldsymbol{f}_{r},$
(4a)
$\displaystyle\boldsymbol{f}_{r}=\left[\begin{array}[]{c}\mathcal{R}(\boldsymbol{f})\\\
\mathcal{I}(\boldsymbol{f})\end{array}\right],\;\boldsymbol{g}_{r}=\left[\begin{array}[]{c}\mathcal{R}(\boldsymbol{g})\\\
\mathcal{I}(\boldsymbol{g})\end{array}\right],$ (4f)
$\displaystyle\bar{\boldsymbol{H}}=\left[\begin{array}[]{cc}\mathcal{R}(\boldsymbol{H})&\mathcal{I}(\boldsymbol{H})\\\
-\mathcal{I}(\boldsymbol{H})&\mathcal{R}(\boldsymbol{H})\end{array}\right],\;\boldsymbol{q}=\boldsymbol{g}_{r}^{T}\bar{\boldsymbol{H}},$
(4i)
$\displaystyle\boldsymbol{J}=\left[\begin{array}[]{cc}\boldsymbol{q}(1:N_{R})&-\boldsymbol{q}(N_{R}+1:2N_{R})\\\
\boldsymbol{q}(N_{R}+1:2N_{R})&\boldsymbol{q}(1:N_{R})\end{array}\right],$
(4l)

where $\mathcal{P}\triangleq\\{+1,-1\\}$ denotes the spin set. Then, we
convert the pre-coding vector $\boldsymbol{f}_{r}$ (containing spin variables
$\\{+1,-1\\}$) to the binary vector $\boldsymbol{b}_{f}$ (with entries in the
set $\\{0,1\\}$) by using the transformation [9]
$\boldsymbol{b}_{f}=\frac{1}{2}(\boldsymbol{f}_{r}+\mathbbm{1})$ and thus the
problem in (4a) is converted to a standard QUBO formulation

$\displaystyle\max_{\boldsymbol{f}_{r}\in\mathcal{P}^{2N_{T}\times
1}}\boldsymbol{f}_{r}^{T}(\boldsymbol{J}^{T}\boldsymbol{J})\boldsymbol{f}_{r}=\max_{\boldsymbol{f}_{r}\in\mathcal{P}^{2N_{T}\times
1}}\boldsymbol{f}_{r}^{T}\boldsymbol{V}\boldsymbol{f}_{r}$ (5)
$\displaystyle=\max_{\boldsymbol{b}_{f}}\;4\boldsymbol{b}_{f}^{T}\boldsymbol{V}\boldsymbol{b}_{f}-2\boldsymbol{b}_{f}^{T}\boldsymbol{V}\mathbbm{1}-2\mathbbm{1}^{T}\boldsymbol{V}\boldsymbol{b}_{f}$
$\displaystyle=\max_{\boldsymbol{b}_{f}}\;\boldsymbol{b}_{f}^{T}\bigg{(}4\boldsymbol{V}-4\textrm{diag}(\boldsymbol{V}\mathbbm{1})\bigg{)}\boldsymbol{b}_{f}$
$\displaystyle=\max_{\boldsymbol{b}_{f}}\;\boldsymbol{b}_{f}^{T}\boldsymbol{V}_{0}\boldsymbol{b}_{f}.$
(6)

The last mathematical step transforms the above (symmetric) quadratic matrix
$\boldsymbol{V}_{0}$ to a form that is compatible with the D-WAVE QA solver
[10]; we normalize the matrix such as all its entries take values in the range
$[-1,+1]$. The calibrated matrix is written by
$\boldsymbol{V}_{n}=\frac{\boldsymbol{V}_{0}}{\|\boldsymbol{V}_{0}\|_{\max}}$
and thus the D-WAVE compatible QUBO problem is written as

$\displaystyle\min_{\boldsymbol{b}_{f}}\;\boldsymbol{b}_{f}^{T}(-\boldsymbol{V}_{n})\boldsymbol{b}_{f}.$
(7)

The returned binary vector $\boldsymbol{b}_{f}$ is converted back to the spin
vector $\boldsymbol{f}$. By using the principles of alternating optimization,
we then fix $\boldsymbol{f}$ (by using the previous solution), and we solve
the equivalent problem in (2c) i.e.,

$\displaystyle\max_{\boldsymbol{g}\in\mathcal{S}^{N_{R}\times
1}}\;\boldsymbol{g}^{H}(\boldsymbol{H}\boldsymbol{f}\boldsymbol{f}^{H}\boldsymbol{H}^{H})\boldsymbol{g},$
(8)

which is transformed to an equivalent real-valued spin form

$\displaystyle\max_{\boldsymbol{g}_{r}\in\mathcal{P}^{2N_{T}\times
1}}\boldsymbol{g}_{r}^{T}(\boldsymbol{Z}^{T}\boldsymbol{Z})\boldsymbol{g}_{r}$
(9a)
$\displaystyle\hat{\boldsymbol{H}}=\left[\begin{array}[]{cc}\mathcal{R}(\boldsymbol{H})&-\mathcal{I}(\boldsymbol{H})\\\
\mathcal{I}(\boldsymbol{H})&\mathcal{R}(\boldsymbol{H})\end{array}\right],\;\boldsymbol{z}=\hat{\boldsymbol{H}}\boldsymbol{f}_{r},$
(9d)
$\displaystyle\boldsymbol{Z}=\left[\begin{array}[]{cc}\boldsymbol{z}(1:N_{T})&\boldsymbol{z}(N_{T}+1:2N_{T})\\\
-\boldsymbol{z}(N_{T}+1:2N_{T})&\boldsymbol{z}(1:N_{T})\end{array}\right]^{T}.$
(9g)

The above spin-variable formulation is converted to a QUBO formulation by
using similar analytical steps like before

$\displaystyle\max_{\boldsymbol{g}_{r}\in\mathcal{P}^{2N_{T}\times
1}}\boldsymbol{g}_{r}^{T}(\boldsymbol{Z}^{H}\boldsymbol{Z})\boldsymbol{g}_{r}\;=\max_{\boldsymbol{g}_{r}\in\mathcal{P}^{2N_{T}\times
1}}\boldsymbol{g}_{r}^{T}\boldsymbol{R}\boldsymbol{g}_{r}$ (10)
$\displaystyle=\min_{\boldsymbol{b}_{g}}\;\boldsymbol{b}_{g}^{T}(-\boldsymbol{R}_{n})\boldsymbol{b}_{g},$
(11)

where $\boldsymbol{b}_{g}$ is the binary representation of the vector
$\boldsymbol{g}$, while the normalized matrix $\boldsymbol{R}_{n}$ is defined
similar to $\boldsymbol{V}_{n}$.

The above alternating optimization process is repeated until convergence or a
maximum number of iterations ($K$ iterations) is achieved. Due to the
discrete/binary nature of the problem, the final solution is sensitive to the
initial conditions (i.e., initial vector $\boldsymbol{g}^{(0)})$ which could
result in convergence to a local maximum (SNR objective function). To overcome
this limitation and facilitate the iterative algorithm to escape local maxima
and get closer to the optimal solution, we introduce $L$ independent execution
of the algorithm by using different initial conditions
($\boldsymbol{g}_{l}^{(0)}$ with $l=1,\ldots,L$); from the $L$ returned
solutions, we keep the one corresponding to the maximum SNR objective
function. The pseudocode of the QA-based iterative algorithm is given in
Algorithm 1.

The time complexity of the Algorithm 1 mainly refers to the number of anneals,
which is a system parameter that is tuned empirically. Obviously, as the size
of the problem increases, the number of anneals should also increase (in a
polynomial way) in order to successfully determine the optimal solution.
Specifically, the time complexity of the proposed QA scheme can be written as
$K\times L\times(2\times N_{a})\times T_{a}$ (time-units) where $N_{a}$ is the
number of anneals, $T_{a}$ is the anneal time, while the factor $2$ is due to
the fact that we solve two QUBO problems at each basic algorithmic iteration.
It is obvious that the time complexity of the proposed scheme is polynomial
with respect the main system parameters and thus much lower than the
exponential time complexity of the classical ES scheme.

Figure 2: $\mu$-law compander characteristic function; $\mu=255$ is considered
in our experimental studies (commercial PCM). Figure 3: QUBO pre-processing
technique to combat Hamiltonian/ICE noise. Figure 4: [top] D-WAVE performance
for conventional QUBO (without pre-processing), [bottom] D-WAVE performance
for companded QUBO (with pre-processing); QUBO problem of dimension $24$, ES
benchmark (dashed line).

##  IV Pre-processing- companded QUBO

In this section, we study a new pre-processing QA technique that converts the
quadratic QUBO matrix in a form that is more robust to Hamiltonian noise [19].
Due to the interaction of the D-WAVE QA device with the external environment
as well as due to hardware limitations, the QA process suffers from noise
effects that decrease the quality of the solution. These noise effects are
collectively represented by the term integrated control errors (ICE) which
captures all the sources of solution infidelity (e.g., cross-talk with
adjacent qubits, temperature fluctuations, flux noise, quantization/precision,
bandwidth of the analogue circuits etc.). An informative overview of the ICE
sources is given in [16, Ch. 3]. Due to the ICE effects, the QA device solves
a slightly altered QUBO problem given by

$\displaystyle\underbrace{\min_{\boldsymbol{b}}\;\boldsymbol{b}^{T}\boldsymbol{Q}\boldsymbol{b}}_{\text{original
QUBO}}\;\rightarrow\;\underbrace{\min_{\boldsymbol{b}}\;\boldsymbol{b}^{T}\big{(}\boldsymbol{Q}+\boldsymbol{E}\big{)}\boldsymbol{b}}_{\textrm{noisy/ICE
QUBO}},$ (12)

where $\boldsymbol{Q}$ is the original symmetric quadratic QUBO matrix, while
the random matrix $\boldsymbol{E}$ represents the Hamiltonian/ICE noise in the
bias and couplers coefficients (the elements of the matrix $\boldsymbol{E}$
are random variables e.g., coloured Gaussian distribution [16]). Therefore, it
is obvious that the QA device solves a modified/noisy problem whose ground
state may be different that the one of the original QUBO problem. The
associated literature mainly focuses on the characterization of the noise by
using statistical signal processing tools [19] or the investigation of
heuristic post-processing techniques that improve the quality of the returned
solution [20]. In practice, to combat the noise/ICE effects and overcome
potential local minima, the same QUBO instance is solved multiple times (each
execution is called anneal) in a row and the best solution among all the
anneals is adopted222It is worth noting that this concept is very similar to
retransmission techniques (e.g., repetition code) in wireless communications
systems, where the same information signal is transmitted multiple times
through independent noisy channels to achieve diversity and increase
reliability [21, Ch. 3]..

From the modified QUBO problem in (12), it is obvious that the elements of the
original matrix $\boldsymbol{Q}$ with small values/magnitudes ($\approx 0$)
are more sensitive to noise effects. Our proposed pre-processing QUBO
technique converts the $\boldsymbol{Q}$ matrix elements with small magnitude
to higher values without affecting the qualitative interconnection between the
qubits (i.e., the sign and the order in the strength of the bias/couplers
coefficients remain the same). Specifically, inspired by the non-uniform
quantization process in PCM systems which boosts the lower amplitudes and
reduces the dynamic range of the input speech signal [17, Ch. 7], we introduce
a nonlinear compression block (named compander by using the terminology from
PCM systems) to pre-process $\boldsymbol{Q}$ elements before the D-WAVE QA
operation. Without loss of generality, we consider the $\mu$-low (logarithmic)
compander which is used in PCM systems in the United States and Canada,
defined as follows [17, Ch. 7]

$\displaystyle
C(x)=\frac{\log(1+\mu|x|)}{\log(1+\mu)}{\textrm{sgn}(x)},\;\;\;\textrm{with}\;-1\leq
x\leq 1.$ (13)

The positive parameter $\mu$ controls the amount of compression. Fig. 2 plots
the characteristic function of the $\mu$-law for various values of $\mu$; it
can be seen that as the $\mu$ parameter increases, the low magnitude elements
are mapped to much higher values. In our experimental studies (without loss of
generality), we consider $\mu=255$ which is the value that is used in
commercial PCM systems. After QUBO pre-processing, the D-WAVE QA device solves
the following noise-robust QUBO problem

$\displaystyle\min_{\boldsymbol{b}}\;\boldsymbol{b}^{T}\bigg{(}C(\boldsymbol{Q})+\boldsymbol{E}\bigg{)}\boldsymbol{b}.$
(14)

Fig. 3 schematically presents the proposed QA pre-processing technique to
combat ICE effects; it is worth noting, that the proposed approach is generic
and be used with other physics/quantum-inspired heuristic solvers (e.g.
coherent Ising machines).

##  V Experimental evaluation

Experimental results in a state-of-the-art D-WAVE QA device are carried-out in
order to validate the efficiency of the proposed techniques.

###  V-A D-WAVE setting

For our D-WAVE QA experiments, we use the D-WAVE Leap interface with the
Advantage_system1.1 quantum processing unit [7]. For each QUBO instance, we
use $1,000$ anneals with $1\mu$sec anneal time and a ferromagnetic coupling
parameter equal to $\bar{J}_{F}=3$. For the minor embedding, we adopt the
heuristic algorithm minorminer which is included in the Ocean software
development kit by default [6, 7]; in this case, a majority vote is applied to
broken chains.

###  V-B Companded QUBO

In Fig. 4, we study the efficiency of the proposed QUBO pre-processing
technique. As an indicative example, we consider a QUBO problem (see eq. (12))
of dimension $24$ where the elements of the QUBO symmetric matrix
$\boldsymbol{Q}$ are random variables of normal Gaussian distribution with
variance one (a normalization in the range $[-1,+1]$ is also applied
$\boldsymbol{Q}/\|\boldsymbol{Q}\|_{\max}$). In Fig. 4[top], we plot the
performance of the conventional QUBO (without pre-processing); specifically,
we plot the original QUBO matrix as an array of coloured cells, the returned
solutions over $1,000$ anneals which are ordered in descending order of their
objective function values as well as the associated occurrence probabilities.
As it can be seen, the D-WAVE solver returns almost $270$ distinct solutions
and the optimal solution (equivalent to ES scheme) occurs with a probability
$\approx 0.08$. We also note that the considered QUBO problem requires $24$
logical variables corresponding to (average) $80$ physical qubits for the
minor embedding.

In Fig. 4[bottom], we show the performance of the proposed companded QUBO.
Firstly, we plot the companded QUBO matrix $C(\boldsymbol{Q})$; it can be seen
the low magnitude elements of the original matrix $\boldsymbol{Q}$ are
converted to higher values. As for the efficiency of the pre-processing
process, it can be seen that the D-WAVE device returns only $9$ (high quality)
solutions while the optimal solution (equivalent to ES) occurs with a
probability $\approx 0.8$. The obtained results show that the proposed pre-
processing technique preserves the quadratic QUBO matrix from the Hamiltonian
noise and increases the efficiency of the D-WAVE solver. The fact that the
probability of the optimal solution increases by a factor $10$ could decrease
the required number of the total anneals, making the D-WAVE QA solver more
attractive for real-time (delay-sensitive) applications.

Figure 5: [D-WAVE] Average SNR performance versus transmit power $P$ for
different MIMO configurations; Algorithm 1/D-WAVE results (markers), ES
benchmark (dashed line), RQ-M algorithm [15] (dashdotted line). Figure 6:
Median TTS ($99$% confidence level) for a single D-WAVE iteration, versus the
size of the MIMO topology with $N_{T}=N_{R}$.).

####  V-B1 Minimum spectral gap

To further demonstrate the efficiency of the proposed pre-processing
technique, we study the minimum spectral (eigenvalue) gap of the QA adiabatic
evolution for some indicative problem instances. Specifically, the quantum
Hamiltonian that drives the D-WAVE QA process is given by

$\displaystyle H(s)$
$\displaystyle=-\frac{A(s)}{2}\bigg{(}\sum_{i}\hat{\sigma}_{x}^{(i)}\bigg{)}+\frac{B(s)}{2}\bigg{(}\sum_{i}h_{i}\hat{\sigma}_{z}^{(i)}$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+\sum_{i<j}J_{i,j}\hat{\sigma}_{z}^{(i)}\hat{\sigma}_{z}^{(j)}\bigg{)},$
(15)

where $\hat{\sigma}_{x,z}^{(i)}$ are the Pauli matrices operating on a qubit
$q_{i}$, the coefficients $h_{i}$ and $J_{i,j}$ are the linear biases and
quadratic couplers of the equivalent Ising problem, respectively, $s\in[0\;1]$
denotes the anneal fraction, $A(s)$ and $B(s)$ represent the anneal schedules
(adiabatic path). The values of $A(s)$ and $B(s)$ for each value of the anneal
fraction are available for the latest D-WAVE quantum processors in [22]; this
allows us to simulate the Hamiltonian evolution (with an accuracy $30\%$ [22])
of the quantum system and characterize the minimum spectral gap that governs
its efficiency [5]. We recall that the the minimum spectral gap is defined as
the minimum of the energy difference between the first excited energy and the
ground energy as a function of the time i.e.,

$\displaystyle g=\min_{s\in[0,\;1]}\lambda_{1}(s)-\lambda_{0}(s),$ (16)

where $\lambda_{i}(s)$ denotes the $i$-th eigenvalue of the Hamiltonian $H(s)$
at the time fraction $s$ with
$\lambda_{0}\leq\lambda_{1}\leq\ldots\leq\lambda_{2^{n}}$, where $n$ is the
number of qubits in the quantum system.

In Fig. 7, we plot the spectral gap versus the anneal fraction, for an Ising
problem with $n=8$ qubits where the parameters $h_{i},J_{i,j}$ are distributed
according to a Gaussian normal distribution with variance one (normalized to
the range $[-1,\;+1]$). It can be seen that the proposed companded pre-
processing technique ensures a higher minimum spectral gap (i.e., $g=2,11$
against $g=1,25$ without pre-processing for the considered example), which
validates its robustness against the Hamiltonian noise. It is also worth
noting that a higher minimum spectral gap can minimize the overall computation
anneal time, since the appropriate anneal duration is proportional to
$T_{a}\sim 1/g^{2}$.

In Table I, we study the efficiency of the pre-processing technique in terms
of average minimum spectral gap $\mathbbm{E}(g)$ over $10,000$ independent
Rayleigh fading channel realizations. It can be seen that the proposed pre-
processing technique achieves a higher average minimum spectral gap for all
scenarios considered while it ensures a high efficiency (i.e., pre-processing
efficiency denotes the probability that the minimum spectral gap (with pre-
processing) is higher than this one without pre-processing).

Figure 7: [left] Ising matrix, [right] Spectral minimum gap versus the anneal fraction.  TABLE I: Average minimum spectral gap $\mathbbm{E}(g)$. | $n=5$ | $n=8$ | $n=10$
---|---|---|---
Without pre-processing | $0,8906$ | $0,8221$ | $0,7750$
With pre-processing | $1,2377$ | $1,2469$ | $1,2612$
Pre-processing efficiency ($\%$) | $77,56$ | $75,67$ | $76,21$

###  V-C MIMO $1$-bit pre/post-coding design

We study the performance of the proposed QA-based $1$-bit pre/post-coding MIMO
design. We consider a symmetric MIMO setup with $N_{T}=N_{R}$, $\sigma^{2}=1$,
$K=8$, $L=8$, $\delta=0.01$. In Fig. 5, we plot the average SNR performance of
the proposed algorithm (Algorithm 1) versus the transmit power $P$; we
consider $1,000$ channel realizations while the ES solution and the RQ-M
algorithm [15] (classical heuristic which is based on the Rayleigh quotient)
are used as performance benchmarks. It can be seen, that the proposed QA-based
iterative algorithm achieves the optimal ES performance for all cases. The
RQ-M scheme provides a suboptimal performance mainly due to the discretization
of the complex-valued solution (quantization noise) [15]. It is worth noting
that as the number of antennas increases, ES can not be applied since the
total number of computations becomes practically prohibited e.g., $6,87\times
10^{10}$ computations per channel realization for the scenario with
$N_{T}=N_{R}=9$. The MIMO topologies considered have high practical interest
for the upcoming communication systems and are sufficient to demonstrate the
efficiency of the proposed QA-based framework.

In Fig. 6, we plot the median time-to-solution (TTS) versus the size of the
MIMO topology for a single D-WAVE iteration (find $\boldsymbol{f}$ or
$\boldsymbol{g}$). The TTS is defined as the time needed for the D-WAVE solver
to find the ground state of the problem with $99\%$ success probability i.e.,
$\textrm{TTS}=T_{\text{run}}\log(0.01)/\log(1-p)$ where $t_{\text{run}}$ is
the total annealing time ($1\mu sec$ for $1,000$ anneals) and $p$ is the
success probability. We observe that as the MIMO size increases, a higher TTS
is required to find the optimal pre/post coding vectors; TTS increases by a
factor $10$, as we move from a $3\times 3$ MIMO to a $9\times 9$ MIMO
topology.

Figure 8: D-WAVE indicative results for a single channel and single iteration
to compute $\boldsymbol{f}_{l}^{(k)}$; SNR performance of the returned
solutions (in descending order) and the associated occurrence probabilities;
ES benchmark (dashed line), $N_{R}=N_{T}=4$, $P=18$ dB. [left] conventional
QUBO (without pre-processing), [right] proposed companded QUBO (with pre-
processing). Figure 9: D-WAVE indicative results for a single channel and
single iteration to compute $\boldsymbol{g}_{l}^{(k)}$; SNR performance of the
returned solutions (in descending order) and the associated occurrence
probabilities; ES benchmark (dashed line), $N_{R}=N_{T}=4$, $P=18$ dB. [left]
conventional QUBO (without pre-processing), [right] proposed companded QUBO
(with pre-processing).

In Figures 8, 9, we focus on a single iteration of the proposed algorithm
(Algorithm 1) for a single channel realization for a setup with
$N_{T}=N_{R}=4$, $P=18$ dB. Specifically, Fig. 8[left] deals with the design
of the pre-coding vector $\boldsymbol{f}_{l}^{(k)}$ (given a post-coding
vector $\boldsymbol{g}_{l}^{(k-1)}$) without QUBO pre-processing. Firstly, we
observe that the D-WAVE returns almost $\approx 190$ solutions while the
optimal solution (with the maximum SNR) occurs with a total probability
$0.09$; it is worth noting that the first four (in the order) solutions are
equivalent in terms of SNR performance, due to the computation symmetry of the
problem (see Section II-A). In Fig. 8[right], we adopt the proposed QUBO pre-
processing technique and we show the performance of the D-WAVE in terms of SNR
for the returned solutions as well as the associated occurrence probabilities.
The results validate our previous main observations i.e., the companded pre-
processing QUBO approach improves the quality of the returned solutions (only
$18$ high quality solutions are returned), while the optimal solution occurs
with a probability $\approx 0.37$.

Fig. 9 deals with the next step of the iterative algorithm which refers to the
design of the post-coding vector $\boldsymbol{g}_{l}^{(k)}$ given the post-
coding vector from the previous step. The results are inline with our previous
remarks; the D-WAVE solver achieves the optimal ES performance while the
companded QUBO pre-processing improves the quality of the returned solutions
and slightly increases the occurrence probability of the optimal solutions. It
is also worth noting that the achieved maximum SNR increases at the end of the
second step in comparison to the SNR output of the previous algorithmic step.

##  VI Conclusion

In this paper, we studied a new low-complexity digital MIMO architecture with
$1$-bit (processing) resolution per complex dimension. The design of pre/post-
coding that maximizes the received SNR relies to an NP-hard combinatorial
problem with exponential complexity for the optimal ES scheme. An iterative
D-WAVE QA-based algorithm that solves appropriate real-valued QUBO instances
at each iteration is proposed; the iterative scheme gradually achieves near-
optimal (similar to ES) performance while ensuring polynomial complexity. To
further boost D-WAVE efficiency, a pre-processing non-linear companding
technique that transforms the quadratic matrix to a form that is more robust
to Hamiltonian/ICE noise is also investigated. Experimental results show that
the new pre-processing technique improves the quality of the D-WAVE solutions
and could decrease the required number of the total anneals.

## References

  * [1] Z. Wang, J. Zhang, H. Du, D. Niyato, S. Cui, B. Ai, M. Debbah, K. B. Letaief, and H. V. Poor, “A tutorial on extremely large-scale MIMO for 6G: fundamentals, signal processing, and applications,” IEEE Commun. Surv. Tut., (to appear), 2024.
  * [2] A. Li, C. Masouros, A. L. Swindlehurst, and W. Yu, “1-bit massive MIMO transmission: Embracing interference with symbol-level precoding,” IEEE Comm. Mag., vol. 59, pp. 121–127, May 2021.
  * [3] J. M. B. da Silva, A. Sabharwal, G. Fodor, and C. Fischione, “1-bit phase shifters for large-antenna full-duplex mmWave communications,” IEEE Trans. Wireless Commun., vol. 19, pp. 6916–6931, Oct. 2020.
  * [4] A. Lozano, “$1$-bit MIMO for Terahertz channels,” in Proc. Int. ITG Work. Smart Antennas, French Riviera, France, Nov. 2021.
  * [5] C. C. McGeoch, Adiabatic quantum computation and quantum annealing, Morgan & Claypool Publ., 2014.
  * [6] S. Kasi, P. A. Warburton, J. Kaewell, and K. Jamieson, “A cost and power feasibility analysis of quantum annealing for nextG cellular wireless networks,” IEEE Trans. Quantum Eng., vol. 4, pp. 1–17, Oct. 2023.
  * [7] D-WAVE, Getting started with D-WAVE solvers, https://docs.ocean.dwavesys.com/en/stable/getting_started.html, 2021.
  * [8] M. Kim, S. Kasi, P. A. Lott, D. Venturelli, J. Kaewell, and K. Jamieson, “Heuristic quantum optimization for 6G wireless communications,” IEEE Networks, vol. 35, pp. 8–15, July 2021.
  * [9] M. Kim, D. Venturelli, and K. Jamieson, “Leveraging quantum annealing for large MIMO processing in centralized radio access networks,” in Proc. ACM Special Interest Group Data Commun., Beijing, China, Aug. 2019, pp. 241–255.
  * [10] A. K. Singh, D. Venturelli, and K. Jamieson, “Perturbation-based formulation of maximum likelihood MIMO detection for coherent ising machines,” in Proc. IEEE Global Commun. Conf., Rio de Janeiro, Brasil, Dec. 2022, pp. 2523–2528.
  * [11] S. Kasi, J. Kaewell, and K. Jamieson, “A quantum annealer-enabled decoder and hardware topology for nextG wireless polar codes,” IEEE Trans. Wireless Commun., (to appear), 2023.
  * [12] C. Ross, G. Gradoni, Q. J. Lim, and Z. Peng, “Engineering reflective metasurfaces with Ising Hamiltonian and quantum annealing,” IEEE Trans. Antennas Propag., vol. 70, pp. 2841–2854, April 2022.
  * [13] I. Krikidis, C. Psomas, A. K. Singh, and K. Jamieson, “Optimizing Configuration Selection in Reconfigurable-Antenna MIMO Systems: Physics-Inspired Heuristic Solvers,” IEEE Trans. Commun., (submitted), Jan. 2024.
  * [14] T. Q. Dinh, S. H. Dau, E. Lagunas, and S. Chatzinotas, “Efficient Hamiltonian reduction for quantum annealing on Satcom beam placement problem,” in Proc. IEEE Int. Conf. Commun., Rome, Italy, May 2023, pp. 2668–2673.
  * [15] I. Krikidis, “MIMO with analogue 1-bit phase shifters: A quantum annealing perspective” IEEE Wireless Commun. Lett.(to appear), 2024.
  * [16] D-WAVE, Technical description of the D-WAVE quantum processing unit, User manual, Feb. 2023.
  * [17] J. G. Proakis and M. Salehi, Fundamentals of Communication systems, Pearson Prentice Hall, 2005.
  * [18] J. R. Hampton, Introduction to MIMO communications, Cambridge, 2014.
  * [19] T. Zaborniak and R. de Sousa, “Benchmarking Hamiltonian noise in the D-WAVE quantum annealer,” IEEE Trans. Quantum Eng., vol. 2, No. 3100206, Jan. 2021.
  * [20] J. E. Dorband, “Improving the accuracy of an adiabatic quantum computer”, https://arxiv.org/abs/1705.01942, 2017.
  * [21] D. Tse and P. Viswanath, Fundamentals of wireless communication, Cambridge, 2005.
  * [22] https://docs.dwavesys.com/docs/latest/doc_physical_properties.html

|  Ioannis Krikidis (F’19) received the diploma in Computer Engineering from
the Computer Engineering and Informatics Department (CEID) of the University
of Patras, Greece, in 2000, and the M.Sc and Ph.D degrees from École Nationale
Supérieure des Télécommunications (ENST), Paris, France, in 2001 and 2005,
respectively, all in Electrical Engineering. From 2006 to 2007 he worked, as a
Post-Doctoral researcher, with ENST, Paris, France, and from 2007 to 2010 he
was a Research Fellow in the School of Engineering and Electronics at the
University of Edinburgh, Edinburgh, UK. He is currently a Professor at the
Department of Electrical and Computer Engineering, University of Cyprus,
Nicosia, Cyprus. His current research interests include wireless
communications, quantum computing, 6G communication systems, wireless powered
communications, and intelligent reflecting surfaces. Dr. Krikidis serves as an
Associate Editor for IEEE Transactions on Wireless Communications, and Senior
Editor for IEEE Wireless Communications Letters. He was the recipient of the
Young Researcher Award from the Research Promotion Foundation, Cyprus, in
2013, and the recipient of the IEEEComSoc Best Young Professional Award in
Academia, 2016, and IEEE Signal Processing Letters best paper award 2019. He
has been recognized by the Web of Science as a Highly Cited Researcher for
2017-2021. He has received the prestigious ERC Consolidator Grant for his work
on wireless powered communications.
---|---