1-bit RIS-aided Index Modulation with Quantum Annealing

1 1-bit RIS-aided Index Modulation with Quantum Annealing Ioannis Krikidis, Fellow, IEEE, Constantinos Psomas, Senior Member, IEEE, and Gan Zheng, Fellow, IEEE Abstract—In this paper, we investigate a new index modulation (IM) scheme for reconfigurable intelligent surface (RIS)-assisted communications with 1-bit RIS phase resolution. In addition to the traditional modulated symbols, extra bits of information are embedded in the binary RIS phase vector by indexing the cardinality of the positive phases shifts. To maximize capacity, the IM-based RIS vector is selected so as to maximize the signal-to-noise ratio at the receiver. The proposed IM design requires the solution of a quadratic binary optimization problem with an equality constraint at the transmitter as well as a quadratic unconstrained binary optimization (QUBO) problem at the receiver. Since commercial solvers cannot directly handle constraints, a penalty method that embeds the equality constraint in the objective function is investigated. To overcome the empirical tuning of the penalty parameter, an iterative Augmented Lagrangian optimization technique is also investigated where a QUBO problem is solved at each iteration. The proposed design and associated mathematical framework are tested in a real-world quantum annealing device provided by D-WAVE. Rigorous experimental results demonstrate that the D-WAVE heuristic efficiently solves the considered combinatorial problems. Furthermore, theoretical bounds on the average capacity are provided. Both experimental and theoretical results show that the proposed design outperforms conventional counterparts. Index Terms—Reconfigurable intelligent surface, index modulation, 1-bit, QUBO, Ising model, quantum annealing, optimization, D-WAVE. I. INTRODUCTION 6G communication systems introduce new engineering requirements such as data rates up to 1Tbps, extremely high connectivity, ultra reliability and energy efficiency, as well as air-interface latency 10×lower than current 5G deployments [1]. To satisfy these requirements, industry and academia focus on new emerging technologies and communication paradigms such as, reconfigurable intelligent surfaces (RISs), THz frequency bands, integrated sensing and communications, advanced modulation techniques such as index modulation (IM), low-bit-resolution signal processing, etc. Specifically, RISs refer to intermediate passive, active or hybrid devices that scatter the incident radio signals intelligently to control the wireless channel [2]. By jointly adjusting their reflection coefficients, I. Krikidis is with the Department of Electrical and Computer Engineering, University of Cyprus, Cyprus (e-mail: [email protected]). C. Psomas is with the Department of Computer Science and Engineering, European University Cyprus, Cyprus (e-mail: [email protected]). G. Zheng is with the School of Engineering, University of Warwick, Coventry, CV4 7AL, UK (e-mail: [email protected]). This work was supported by the European Research Council (ERC) under the Horizon Europe programme (Grant No. 101241675, PoC QUARTO), the EU Horizon-JU SNS programme (Grant No. 101192080, 6G-LEADER), and the Cyprus Research & Innovation Foundation (Grant No. DUAL USE/0922/0031). Part of this work was also supported by the UK Engineering and Physical Sciences Research Council (EPSRC) grant EP/X04047X/2 for TITAN Telecoms Hub. they can enhance the signal-to-noise ratio (SNR), achieving higher data rates and/or multi-user interference mitigation. Moreover, due to their quasi-passive nature and the reduced number of RF chains required for their operation, RISs are both cost-effective and energy-efficient [3]. On the other hand, IM is a modulation technique that conveys information by varying the index of transmission, such as transmit antennas, subcarriers or precoding matrices, rather than altering the amplitude/phase/frequency of the transmitted sinewave as in conventional modulation schemes [4]. The additional information conveyed through the IM indices increases the spectral efficiency and provides robust communications in challenging environments. Furthermore, the simplicity of IM leads to reduced implementation and hardware complexity as well as improved overall energy efficiency. Finally, low-bit-resolution communication systems that utilize only one or a few bits for signal encoding, are introduced to balance the trade-off between performance and implementation complexity [5], [6]. Due to the potential benefits arising from their implementation, both RIS and IM technologies have been extensively studied in the literature. See [2], [4] and references within. Hence, as expected, there are also works that investigate the synergy of these two technologies [7]. In [8], the author proposes two schemes, namely, an RIS-aided space shift keying scheme and an RIS-aided spatial modulation scheme. The two schemes use the IM concept at the receiver’s antennas and exploit the RIS to maximize the received signal at the selected antenna. The work in [9] follows a similar approach with the consideration of Alamouti space-time code. The proposed technique transmits the coded information through the RIS to the targeted receive antenna. The IM principles have also been utilized at the RIS side. In particular, the work in [10] investigates a reflection pattern modulation, where the RIS activates a subset of its elements to convey additional information. A similar design is studied in [11] focusing on visible light communications. The authors of [12] provide a technique with two RISs and propose a beam-IM scheme, ideal for millimeter wave communications. The aforementioned works consider RISs with continuous phase shifts, i.e., infinite resolution. However, RISs with low resolution phase shifts, e.g., 1-bit phase shifters, are more practical, more cost-effective and of lower complexity [13]. To the best of our knowledge, low-bit resolution RIS communications with IM techniques has not been addressed yet in the literature. In fact, the design and optimization of IMbased RIS-aided communications with discrete phase shifts require a complete different approach, mainly due to the combinatorial nature of the resulting setup. What is more, all these technological breakthroughs considerably enhance computational demands and necessitate computing resources arXiv:2509.18932v1 [cs.IT] 23 Sep 2025 2 with exceptionally high capabilities. Unfortunately, traditional silicon-based Von Neumann computing architectures can not be further advanced since transistors have reached their atomic limits [14]. Quantum computing emerges as a promising alternative to address this computational challenge, offering a suitable platform for advanced wireless technologies. The integration of quantum computing architectures and algorithms within wireless communication systems represents a crucial and emerging field of research [15], [16]. Quantum computing exploits quantum mechanics and relies on the principles of quantum tunneling, superposition and entanglement, encompassing two primary models: gatebased quantum computing and single-purpose quantum annealing (QA) model. The gate-based model operates discretely, utilizing programmable logic gates (unitary and reversible transformations) that act on qubits, resembling classical digital architectures. By sequentially interconnecting these basic logic gates, a variety of quantum algorithms e.g., Grover search, Deutsch, Shor, quantum Fourier transform, quantum approximate optimization algorithm etc., can be implemented, often achieving a computational speedup compared to classical counterparts [17]. For instance, the quadrature speed-up of the Grover’s algorithm (quantum search in an unsorted database) has been already proposed in the literature to solve several physical layer problems in wireless communication systems [18]. A first effort to combine IM with gate-based model quantum computing is presented in [19]; the proposed technique applies adaptive Grover search and simulation results are presented by using IBM Qiskit. However, gate-based quantum devices are highly susceptible to quantum decoherence, limiting the number of qubits and logic gates that can be effectively utilized. In contrast, the QA model is analog and grounded in the adiabatic principle of quantum mechanics (Adiabatic Theorem) [20], [21]. This model is particularly effective for addressing NP-hard combinatorial optimization problems, which are formulated as instances of the Ising model (spin-glass) which is equivalent to the quadratic unconstrained binary optimization (QUBO) problem. By leveraging the system’s adiabatic evolution, it gradually evolves to a final Hamiltonian (i.e., energy function representing the objective function to be minimized) whose ground state (lowest energy level) embeds the solution of the optimization problem considered. D-WAVE is a commercial analog quantum device that performs a noisy version of QA using advanced superconducting integrated circuits (niobium loops) [22]. Recently, it has gained significant attention for its impressive computational capabilities, including a high number of qubits, and its user-friendly cloudbased programming interface for real-time remote access. The current D-WAVE Advantage system features a quantum processing unit with over 5,000 flux qubits, while the forthcoming D-WAVE architectures are anticipated to incorporate more than 7,000 flux qubits with larger qubit connectivity. Although there is not any theoretical result/proof about the performance/speed-up of the D-WAVE QA, experimental results show quantum advantages against classical heuristics for particular instances. D-WAVE QA has been used to various traditional NP-hard problems (e.g., set cover problem, Knapsack, portfolio optimization, etc.) and experimental results show significant performance benefits [23], [24], [25], [26]. QA has been utilized to solve a wide range of problems in wireless communications. Early works mainly focus on addressing the maximum-likelihood signal detection problem in large-scale multiple-input multiple-output (MIMO) systems [28]. Experimental results show significant performance benefits in comparison to conventional solutions as well as limitations due to the number of qubits available and the noise effects (integrated control errors) [29]. QA has been also used to address other design problems of combinatorial nature in wireless communication systems such as beam assignment for satellite systems [30], design of RIS phases shifts in RISassisted communications [31], multi-user detection for nonorthogonal multiple access [32], decoding for polar codes [33], antenna configuration selection in fluid-antenna MIMO systems [34], etc. In our recent work, D-WAVE QA has been also used to design pre/post coding vectors for MIMO point-to-point MIMO systems with 1-bit analogue [35] and digital resolution [36], respectively. The results show that D-WAVE QA is a promising solver/heuristic for low-bitresolution signal processing techniques that are represented by QUBO instances. It is also worth noting that QA has been employed as an essential block to speed-up the training process in machine-learning models, which has potential interest in the design of wireless communication systems [37], [38]. In contrast to the discussed literature, this paper investigates a novel 1-bit RIS signal processing technique, which merges RIS-aided communication with IM. Specifically, the new IM design embeds information bits in the binary RIS phase vectors by indexing the cardinality of their distinct phases shifts. Then, the RIS chooses the vector that also maximizes the received SNR. The proposed IM scheme requires the solution of a binary optimization problem with an equality constraint at the transmitter and a QUBO problem at the receiver, which are solved in a real-world D-WAVE QA machine by using an appropriate mathematical framework. Specifically, the major contributions of the paper are summarized as follows: •A new RIS-based IM technique is proposed in which index information is embedded in the phase beamforming vectors that are used by the RIS. By taking into account the binary resolution {+1,−1}of the phase shifts, additional information bits are conveyed by using the cardinality of ±1entries in the RIS vectors as IM information. To maximize capacity, the RIS vector (with a given number of ±1phase shifts) that maximizes the SNR is selected for the IM process. Numerical results show that the proposed scheme outperforms conventional passive beamforming with binary phase shifts, while the performance advantages increase as the number of RIS elements increases. •The proposed RIS-based IM scheme is represented by a combinatorial binary problem with a single equality constraint at the transmitter side, as well as a conventional QUBO problem at the receiver side. To tackle the equality constraint, we firstly study the penalty method which embeds the constraint into objective function by using an auxiliary penalty parameter. An iterative technique 3 that iterates over different penalty parameters is also considered. To avoid the empirical tuning of the penalty parameter, we investigate the Augmented Lagrangian (AL) method, which combines Lagrangian optimization with the penalty method; this iterative method solves a QUBO problem at each iteration, while it converges to the solution faster and in a more smooth way due to the additional free variable. •Theoretical expressions are derived for the average SNR achieved by the proposed RIS-based IM scheme, characterizing how the cardinality of ±1entries in the RIS vector affects the received signal power. The proposed scheme performs close to conventional beamforming (in terms of SNR) when the numbers of +1 and −1phase shifts are equal (or approximately equal) and, for a sufficiently large number of RIS elements, the two schemes have similar performance. Moreover, we derive an upper bound on the average capacity. Our results show that the RIS-based IM technique outperforms conventional beamforming in terms of average capacity. •To solve the considered QUBO problems, we employ a real-world state-of-the art QA device i.e., D-WAVE Advantage System6.4. Rigorous experimental results show that the proposed RIS-based IM design can be efficiently solved through QA. Due to the low resolution of the quantum hardware, the AL technique seems to outperform the penalty method for large RIS configurations, since it handles the equality constraint in a more numerically robust manner. Notation: Lower and upper case bold symbols denote vectors and matrices, respectively; the superscripts (x x x)T,(x x x)Hdenote transpose and conjugate transpose of the vector x x x, respectively; E (·)denotes the statistical expectation; 1 1 1is a full-ones column vector of appropriate dimension, ℜ(·)returns the real part of its complex argument, diag(x x x)denotes a diagonal matrix whose main diagonal is x x x,I I Iis the identity matrix of appropriate dimension, CN×Mdenotes the set of complex-valued N× Mmatrices, and CN(µ, σ2)represents the complex Gaussian distribution with mean µand variance σ2. The remainder of the paper is organized as follows: Section II introduces the system model and provides some useful background. Section III presents the proposed RIS-aided IM scheme with the associated optimization problems and theoretical framework, whereas Section IV focuses on the solution of the combinatorial problems considered by using the D-WAVE solver. Numerical simulation results are provided in Section V. Our conclusions are discussed in Section VI. II. SYSTEM MODEL We assume a simple RIS-aided communication setup consisting of a single-antenna transmitter, a single-antenna receiver, and a passive RIS with Nreflecting elements. Suppose that the channel between the transmitter and the RIS is denoted by h h h∈CN×1, while the channel between the RIS and the receiver is given by g g g∈CN×1(standard cascaded RIS channel model). Due to obtacles and deep shadowing, a line of sight (LOS) link does not exist and communication between the !"# !$%$&$'() *+ g g g !+ h h h {+1,−1} Fig. 1. The system model consisting of one transmitter, one receiver, and a passive RIS with Nreflecting elements and 1-bit resolution. transmitter and the receiver is performed through the RIS [8], [9]. We assume independent and identically distributed (i.i.d.) Rayleigh fading, so that the entries of h h hand g g gare independent circularly symmetric complex Gaussian random variables with zero mean and unit variance. To reduce power consumption and signalling, the phase shifts of the RIS have binary resolution and thus can take two discrete values i.e., +1 and −1corresponding to the phase shifts 0and π, respectively. If Ptis the transmit power, the received SNR can be written as Γ = Pt|g g gHdiag(x x x)h h h|2 N0 , =Pth h hHdiag(x x xT)g g gg g gHdiag(x x x)h h h N0 =Ptx x xTdiag(h h hH)g g gg g gHdiag(h h h)x x x N0 =Ptx x xTR R Rx x x N0 ,(1) where R R R= diag(h h hH)g g gg g gHdiag(h h h),x x x= [x1, x2, . . . , xN]T denotes the binary RIS phase shift vector, with each element xi∈ {+1,−1}representing a discrete phase shift of 0or π, respectively, imposed by the i-th RIS element, and N0is the variance of the additive white Gaussian noise (AWGN) at the receiver. Global channel state information (CSI) is assumed at both the transmitter and the receiver, which can be acquired using techniques such as those proposed in [39], [40]. Maximizing the received SNR directly increases the achievable Shannon capacity, since the capacity expression C= log2(1 + SNR)is a strictly increasing function of SNR under Gaussian signaling. Fig. 1 schematically depicts the system model. A. Preliminaries: Ising-to-QUBO Transformation The optimization problems encountered in this work naturally arise in the Ising formulation, since the RIS phase shift variables are constrained to the spin set {+1,−1}. This representation closely reflects the physical nature of the system and aligns with the native spin-based variables used in quantum annealing hardware, which operates according to the Ising spin-glass model. The standard Ising form is given by (Ising problem) min x x xX i uixi+X i<j Ji,jxixj,(2) 4 where the real coefficients uiand Ji,j denote the linear (bias) and the quadratic (coupler strength) terms, respectively, xiare spin variables taking values in the set {+1,−1}. To reformulate the problem in a form suitable for our computational framework, we adopt the equivalent QUBO formulation by applying the transformation xi→2bi−1[28] i.e., (QUBO problem) min b b bX i Gi,ibi+X i<j Gi,jbibj = min b b bb b bTG G Gb b b, (3) where bi∈ {0,1}are binary variables, Gi,j = 4Ji,j and Gi,i = 2ui−2Pk<i Jk,i −2Pi<k Ji,k. QUBO/Ising problems belong to NP-hard complexity class. Due to the equivalence between NP-hard problems, many optimization problems can be represented as QUBO/Ising e.g., traveling salesman, nurse scheduling, max-cut, etc.. Although the Ising and QUBO formulations are mathematically equivalent, the QUBO representation is more commonly supported by commercial solvers, allows for easier embedding of constraints, and is more directly supported by the D-WAVE Ocean SDK and its associated tools (the quantum annealing platform used in our experimental results). For these practical reasons, we adopt the QUBO form in our study, while still referring to the Ising model where it offers clearer physical or theoretical insight (e.g., in the context of adiabatic quantum evolution in Section IV-A). To facilitate the reformulation process, we now present four key lemmas that convert Ising-type terms (both objective functions and constraints) into equivalent QUBO representations. Lemma 1. The quadratic Ising term x x xTJ J Jx x x, where x x xis a spin vector with elements in {+1,−1}, and J J Jis a hermitian N×Nmatrix, is equivalent to the quadratic binary expression b b bTJ J J′b b b+C, where b b bis a binary vector, J J J′= ℜ(4J J J−4 diag(J J J1 1 1)) and Cis a real-valued constant. Proof. The proof is given in Appendix A. Lemma 2. The linear Ising term x x xTa a a, where x x xis a spin vector with elements in {+1,−1}, and a a ais a real-valued vector, is equivalent to the binary quadratic expression b b bTdiag(−2a a a)b b b+ C, where b b bis a binary vector and Cis a real-valued constant. Proof. The proof is given in Appendix B. Lemma 3. The linear equality x x xTa a a=c, where x x xis a spin vector with elements in {+1,−1},a a ais a real-valued vector, and c > 0is a constant, is equivalent to the binary quadratic equality b b bTJ J Jb b b+C= 0, where b b bis a binary vector, J J J= 4a a aa a aT+ 4(c−a a aT1 1 1) diag(a a a)and C=c(c−2a a aT1 1 1). Proof. The proof is given in Appendix C. Lemma 4. The quadratic equality x x xTJ J Jx x x=c, where x x xis a spin vector with elements in {+1,−1},J J Jis hermitian matrix and c > 0is a constant, is equivalent to the binary quadratic equality b b bTJ J J′b b b+Cwhere b b bis a binary vector, J J J′= 4(ℜ(J J J)− c NI I I)−4 diag((ℜ(J J J)−c NI I I)1 1 1) and Cis a real-valued constant. Proof. The proof is given in Appendix D. III. RIS-AIDED INDEX MODULATION In this section, we present the conventional passive beamforming solution with binary phase shifts and the proposed RIS-based IM scheme. The associated QUBO problems are introduced and theoretical expressions for the average received signal power and average capacity are provided. A. Conventional beamforming The conventional beamforming scheme with binary phase shifts, designs the phase shift vector to maximize the SNR at the receiver. It corresponds to the solution of the following quadratic (Ising) unconstrained optimization problem max x x x∈{+1,−1}Nx x xTR R Rx x x= min x x x∈{+1,−1}Nx x xT(−R R R)x x x. (4) By using the expression in Lemma 1, the problem in (4) can be written as QUBO i.e., (P1) min b b b∈{0,1}Nb b bTℜ−4R R R+ 4 diag(R R R1 1 1)b b b = min b b b∈{0,1}Nb b bTQ Q Qb b b, (5) where Q Q Q=ℜ−4R R R+ 4 diag(R R R1 1 1)and the constant terms can be ignored from the optimization. B. IM-based beamforming The proposed technique combines the conventional RISbased passive beamforming with IM. Specifically, in addition to the conventional modulation which is employed at the transmitter, we use the number (cardinality) of +1s in the phase vector to convey extra bits of information by using the principles of IM. One could also consider the number of −1s in the phase vector, which is equivalent due to the symmetry in the SNR expression i.e., |g g gHdiag(x x x)h h h|2=|− g g gHdiag(x x x)h h h|2. As such, the distinct beamforming vectors can have k∈ {0,1,...,⌊N/2⌋} phase shifts equal to +1. Hence, the transmitter can adjust the index kaccording to the input information, thus conveying log2(⌊N/2⌋+1) extra bits at each transmission time. To further boost the performance, the RIS vector that maximizes the SNR at the receiver and has kvalues equal to +1 is selected. It is worth noting that the IM squeezes the space dimension of the passive beamforming from 2N−1 to N kvectors at each transmission. Therefore, even though the performance of the passive beamforming is reduced, it is compensated by the IM performance gain. The proposed IMbased design corresponds to the following constrained binary optimization problem min x x x∈{+1,−1}Nx x xT(−R R R)x x x(6) subject to x x xT1 1 1 = 2k−N, (7) where the objective function is the SNR at the receiver, the constraint in (7) refers to the IM that enforces kRIS elements with phase shift +1 and thus N−kelements with phase shift −1i.e., x x xT1 1 1 = PN i=1 xi= (+1)×k+(−1)×(N−k)=2k− N, where k∈ {0,1,...,⌊N/2⌋}. By applying the expressions in Lemmas (1) and (3), the above optimization problem can 5 be converted to an equivalent binary form, where both the objective and the constraint are quadratic binary functions i.e., (P2) min b b b∈{0,1}Nb b bTQ Q Qb b b s.t. b b bTT T Tb b b+C= 0,(equivalent to b b bT1 1 1+C′= 0),(8) where T T T=41 1 11 1 1T+8(k−N)I I I, and C= (2k−N)(2k−3N). We note also that the constraint in (8) can be written in a linear binary form as b b bT1 1 1+C′= 0, where C′=k−N. To be able to detect the IM information, the receiver should have a mechanism to extract the RIS beamforming vector x x x (and thus the parameter k) from the received signal. Since the receiver can measure the received SNR and given that a global CSI is assumed, IM detection corresponds to the solution of the following quadratic equation with respect to the spin vector x x x Pt N0 x x xTR R Rx x x= Γm,(9) where Γmdenotes the measured SNR at the receiver; in this work, we assume perfect SNR estimation (Γm= Γ). It is also worth noting that distinct RIS phase vectors correspond to distinct SNR values, thus ensuring that the equation has a unique solution1. The above equation can be written as a feasibility problem i.e., min x x x∈{+1,−1}N0(10) s.t. x x xTR R Rx x x= Γ′ m,(11) where Γ′ m= ΓmN0/Pt. By taking into account Lemma 4, the feasibility problem into (10) can be written in an equivalent binary form (P3) min b b b∈{0,1}N0(12) s.t. b b bTW W Wb b b= 0,(13) where W W W=ℜ4[J J J−Γ′ m NI I I]−4 diag([J J J−Γ′ m NI I I]1 1 1). The feasibility problem (P3) can be converted to a simple QUBO problem (by using the penalty method that will be discussed in Section IV-B) i.e., (P4) min b b b∈{0,1}Nb b bTW W Wb b b. (14) The above problem has similar structure to (P1). Therefore, although our experimental results concerns (P1), the methodology and key observations also hold for (P4). We emphasize that, in the proposed scheme, decoding the IM index does not require demodulating the conventional symbol. The receiver only estimates the received SNR, which (under global CSI) maps uniquely to the RIS vector and thus to k, enabling index recovery via a feasibility-type QUBO problem. As such, the IM layer operates independently of signal demodulation 1Two distinct configurations x x x=±x x x′yield the same SNR if and only if |v v vHx x x|2=|v v vHx x x′|2with v v v= diag(h h hH)g g g. For a fixed pair (x x x,x x x′), this is one real equation in the 2Nreal parameters of v v v, so the solution set is a (2N−1)-dimensional surface inside the 2N-dimensional space. With i.i.d. continuous fading (e.g., Rayleigh), the channel vector v v vis drawn from a continuous distribution, so the probability of lying exactly on such a surface is zero. Thus, exact SNR collisions occur with probability zero (i.e., almost surely), although they can arise for particular deterministic channels. and remains decodable even when the signal component is weak or unreliable. This provides a form of robust auxiliary communication, particularly useful in low-SNR or energyconstrained scenarios. C. Capacity bounds Here, we provide theoretical bounds on the average Shannon capacity achieved by the proposed technique and compare the performance with the conventional beamforming scheme. Assuming the transmitted IM information is equiprobable, the average capacity can be written as C=1 ⌊N/2⌋+ 1 ⌊N/2⌋ X k=0 E(log2(1 + Γ∗ k)) + log2(⌊N/2⌋+ 1), (15) where Γ∗ kis the maximum SNR attained with k∈ {0,1,...,⌊N/2⌋} phase shifts equal to +1, given by Γ∗ k=Pt N0 x x x∗TR R Rx x x∗=Pt N0 N X i=1 |hi||gi|x∗ iej(θi+ϕi) 2 ,(16) with x x x∗being the vector that maximizes the channel gain with PN i=1 xi= 2k−N,θiand ϕiare the phases of hiand gi, respectively. In what follows, we assume hi, gi∼ CN(0,1) and denote by Hk=E(x x x∗TR R Rx x x∗)the average channel gain. Before proceeding with the analytical evaluation of Hk, we first look at the conventional beamforming case with binary phase shifts. We assume that the phase shift design assigns the discrete phase shift that is nearest to the optimal continuous value, i.e., −(θi+ϕi)[13]. Therefore, based on this approach, it is known that the average channel gain for the conventional beamforming is [13] Hc=N+1 4N(N−1).(17) In contrast, the proposed IM-based beamforming technique does not allow for all elements to set their phases as close to the optimal continuous value, which instills a loss in performance. The following proposition provides the average channel gain for this case. Proposition 1. The average channel gain achieved by the IMbased beamforming technique with Nelements and kphase shifts equal to +1 is Hk=N+1 4N(N−1) −Sk,(18) where, for odd N, we have Sk=1 2N−1 ⌊N/2⌋ X n=0 N n|k−n|(N−|k−n|),(19) whereas, for even N, we have Sk=1 2N−1 N/2−1 X n=0 N n|k−n|(N−|k−n|) +1 2NN N/2 k−N 2N− k−N 2.(20) 6 Proof. The proof is given in Appendix E. Comparing (17) with (18), we can observe that Skcharacterizes the loss in channel gain due to the constraints imposed to the RIS vector by the IM-based beamforming technique. This loss in channel gain is inversely proportional to k. Indeed, for k= 0 the loss is maximized with S0=1 4N(N−1), resulting in H0=N, which corresponds to a random phase shift configuration [41]; this is expected, since only one vector is available for this case. On the other hand, values of kclose to ⌊N/2⌋provide smaller values for Sk. It is important to note that although the channel gain is reduced, the IM-based technique compensates by enhancing the capacity (see (15)). To gain further insights, we look at the ratio between Hkand Hcin the asymptotic regime N→ ∞. Corollary 1. As N→ ∞, we have ϵk=Hk Hc→1−4 N2Sk,(21) where Skis given by (19) or (20). From the above, we can conclude that ϵ0→0, as expected. However, we have ϵ⌊N/2⌋→1, which shows that, asymptotically, the IM-based scheme can match the performance of the conventional scheme. We can now provide a bound on the average Shannon capacity. Using (15), we have C ≤ 1 ⌊N/2⌋+ 1 ⌊N/2⌋ X k=0 log2(1+E(Γ∗ k)) + log2(⌊N/2⌋+ 1) =1 ⌊N/2⌋+ 1 ⌊N/2⌋ X k=0 log21 + Pt N0 Hk+ log2(⌊N/2⌋+ 1), (22) which follows with the use of Jensen’s inequality [42, Ch. 2.6] and Hkis given in Proposition 1. D. A toy example We present a simple/toy numerical example to demonstrate the basic characteristics of the proposed scheme. We consider an RIS with N= 5 elements, Pt= 1,N0= 1 and constant wireless channels. Table I presents the RIS vectors for each index (k∈ {0,1,2}} since ⌊5/2⌋= 2) and the associated SNRs. The conventional beamforming scheme selects the RIS vector that achieves the maximum SNR. Specifically, among the 2N/2 = 2N−1= 24= 16 distinct vectors (due to the symmetry in the SNR expression) that are placed in the three columns of Table I, the conventional design will select the entry {+1,−1,−1,+1,−1}with SNR equal to 1.584; in this case the achieved Shannon capacity becomes C= log2(1+SNR) = log2(1+1.584) = 1.37 bits per channel use (bpcu). On the other hand, the proposed IM scheme (at each transmission time), selects the RIS vector with the maximum SNR among the vectors of a specific column e.g., for k= 1, it selects the vector {−1,−1,−1,+1,−1}with SNR 1.57. If the IM data are equiprobable, the achieved average Shannon capacity can be written as C=E(log2(1+SNR))+log2(3) = TABLE I IM-BASED RIS VECTORS AND ASSOCIATED SNR VALUES;SETUP WITH N= 5,Pt= 1,N0= 1,WIRELESS CHANNELS WITH h h h= [−0.048 + 0.0364j, −0.138 + 0.584j, −0.153 + 1.079j, −0.2143 + 0.3302j, 0.0163 −0.1483j],AND g g g= [0.4421 + 0.0956j, 0.1296 + 0.3643j, −0.7282 + 0.1848j, 0.6712 −0.6657j, 0.2171 −0.1148j]. IM k= 0 k= 1 k= 2 RIS vector & SNR {−1,−1,−1,−1,−1} 0.279 {−1,−1,−1,−1,+1},0.208 {+1,+1,−1,−1,−1},0.324 {−1,−1,−1,+1,−1},1.57 {+1,−1,+1,−1,−1},1.346 {−1,−1,+1,−1,−1},1.407 {+1,−1,−1,+1,−1},1.584 {−1,+1,−1,−1,−1},0.281 {+1,−1,−1,−1,+1},0.203 {+1,−1,−1,−1,−1},0.274 {−1,+1,+1,−1,−1},1.405 {−1,+1,−1,+1,−1},1.506 {−1,+1,−1,−1,+1},0.228 {−1,−1,+1,+1,−1},0.271 {−1,−1,+1,−1,+1},1.568 {−1,−1,−1,+1,+1},1.392 1 3log2(1 + 0.279) + 1 3log2(1 + 1.57) + 1 3log2(1 + 1.584) + log2(3) = 2.6138 bpcu. This toy example demonstrates the performance benefits of the proposed technique. We note that while the current framework assumes ideal SNR estimation at the receiver, in practical settings small differences in SNR values across candidate RIS configurations (as observed in Table I) may lead to index detection errors. Investigating the robustness of the IM scheme under SNR fluctuations and developing resilient detection strategies is an important direction for future work. IV. OPTIMAL RIS DESIGN AND D-WAVE HEURISTIC In this section, we deal with the solution of the optimization problems (P1)/(P4), and (P2). We note that (P1)/(P4) correspond to conventional QUBO problems, while (P2) is a constrained binary optimization problem where both the objective and the equality constraint are quadratic binary functions. A. QUBO/Ising problem and D-WAVE heuristic The problems (P1)/(P4) are conventional QUBO problems while the optimization problem in (P2) can be converted to appropriate QUBO form, as it will be presented in the following discussion. Therefore, the solution of a QUBO problem is vital for the proposed RIS-aided design schemes. In this work, we adopt QA to solve the QUBO problems considered and specifically the D-WAVE QA device that offers remote-based access (leap platform) to real-world D-WAVE quantum computers and appropriate source development tools (Python SKD Ocean) [22]. QA is a specialized method of quantum computing aimed at solving QUBO/Ising problems by leveraging quantum mechanical principles (adiabatic theorem). Specifically, at the heart of QA process is the concept of adiabatic evolution, a process where a quantum system remains in its ground state (the lowest quantum energy state) as it gradually evolves from an initial Hamiltonian Hinitial (representing an easy-tosolve problem) to a final Hamiltonian Hfinal that represents the problem to be solved [20], [21]. If we consider the Ising problem in (2), the QA process can be described as H(t)=−A(t) 2Hinitial +B(t) 2Hfinal,(23) where t∈[0,1] denotes the anneal fraction, A(t)(monotonic decreasing function) and B(t)(monotonic increasing function) 7 Algorithm 1 Iterative penalty method to solve the problem in (24). Input: Initial µand the increasing factor ∆µ, maximum number of iteration imax; let g(b b b) = b b bTQ Q Qb b b. Output: Binary vector b b b∗that solves the problem in (24). 1: for i←1to imax do 2: Solve (24) using D-WAVE with b b b←argb b bmin f(b b b) and f(b b b) = b b bT(Q Q Q+ (µ/2)T T T)b b b. 3: if vector b b bis feasible and g(b b b)< g(b b b∗)then 4: b b b∗←b b b 5: end if 6: Update µ←µ(∆µ) 7: end for represent the anneal schedules (adiabatic path) which relay on the quantum processor [43], Hinitial =Piσ(i) x, and Hfinal = Piuiσ(i) z+Pi<j Ji,jσ(i) zσ(j) z;σ(i) xand σ(i) zare xand zPauli matrices acting on qubit i, respectively. D-WAVE (based in British Columbia, Canada) has developed a series of quantum processors designed to implement QA for real-world problems [22]; these processors are noisy versions of the ideal adiabatic evolution. The Advantage System6.4 [44] is the latest D-WAVE quantum processor that features over 5,500 flux qubits, an increase from earlier quantum devices, making it one of the largest commercial QA available. These qubits are arranged in a Pegasus hardware topology (each qubit is connected to 15 other qubits), a high-connectivity hardware graph structure designed to allow for more flexible and efficient embedding of optimization problems. The device has limited arithmetic resolution i.e., the linear terms (ui) and quadratic terms (Ji,j) are quantized in the interval [−4,4] and [−2,1], respectively. The mapping of a physical QUBO problem (which represents the quadratic interconnection of binary variables) into the limited D-WAVE QA hardware topology/graph, is called minor embedding; it is an NP-hard problem and is mainly solved by using various heuristics. Since the hardware graph is not fully connected, minor embedding enables logical channeling between physical qubits to represent logical variables/qubits. The logical channeling is characterized by the strength of the logical links (called channel strength or ferromagnetic coupling) and it is a critical parameter for QA performance. In case a logical chain is broken at the end of QA process (i.e., physical qubits that form a logical qubit have different final values), appropriate consensus algorithm is applied. Due to practical non-idealities (e.g., hardware limitations, Hamiltonian noise, temperature fluctuations, etc.), the output of a single D-WAVE run (referred to as an anneal) is probabilistic and may be different than the ground state of Hfinal. To ensure an efficient solution for the considered QUBO problem, it is a common practice to solve the same QUBO instance multiple times; the best solution among all the anneals is the final D-WAVE QA output. The anneal time and the number of anneals are critical design parameters which are tuned empirically. Algorithm 2 Iterative AL method to solve the problem in (24). Input: Initial λ, µ and the increasing factor ρ. Output: Binary vector b b b∗that solves the problem in (24). 1: repeat 2: Construct AL function f(b b b, λ, µ) = b b bT(Q Q Q+ λdiag(1 1 1) + (µ/2)T T T)b b b. 3: Solve b b b←arg minb b bf(b b b, λ, µ)using D-WAVE. 4: if (b b bT1 1 1 + C′>0)then update λ←λ+µ(b b bT1 1 1 + C′) 5: end if 6: Update µ=ρµ. 7: if vector b b bis feasible and g(b b b)< g(b b b∗)then 8: b b b∗←b b b. 9: end if 10: until stopping criteria are satisfied. B. Constrained optimization: Penalty method The D-WAVE solver as well as all the existing commercial QUBO heuristics are not able to handle equality/inequality constraints directly. The most classical method to handle binary quadratic constraint is the penalty method, where the constraints are embedded in the objective function through penalty parameters [21], [34]. Specifically, the constrained binary optimization problem in (P2), can be converted to the following QUBO form min b b b∈{0,1}b b bTQ Q Qb b b+µ 2b b bTT T Tb b b, = min b b b∈{0,1}b b bTQ Q Q+µ 2T T Tb b b, (24) where µ > 0is the penalty parameter and the constant C can be removed since it does not affect the solution. The above optimization problem is QUBO and can be solved using the D-WAVE QA device, as described in Section IV-A. The parameter µis critical for the performance of the penalty method; as µincreases, we enforce feasibility, but the quality of the solution becomes worse (and vice versa). It is also worth noting that large values µare more sensitive to hardware limitations in coefficient resolution, which could result in further performance degradation. The optimal parameter µcan be tuned empirically through exhaustive numerical studies. To make this process more rigorous, we introduce Algorithm 1, where the parameter µgradually increases while a QUBO problem is solved at each iteration. The best feasible solution over all iterations is the final solution of the penalty method. C. Constrained optimization: Augmented Lagrangian method The key weakness of the penalty method is that the optimal penalty parameter µcannot be tuned automatically and requires exhaustive numerical studies. In addition, its value (if it is large) is very sensitive to the hardware arithmetic resolution/precision of the D-WAVE solver. On the other hand, the AL method combines Lagrangian optimization with the above penalty method in order to converge faster to the optimal solution while it avoids large values of the penalty parameter [25]. In addition, it is associated with an iterative algorithm that allows to tune the auxiliary variables (Lagrangian multipliers and penalty parameters) automatically, through a rigorous 8 iterative process. Based on the AL method, the optimization problem in (P2) can be written as min b b b∈{0,1}b b bTQ Q Qb b b+λ(b b bT1 1 1+C′) + µ 2(b b bTT T Tb b b+C)(25) = min b b b∈{0,1}b b bTQ Q Qb b b+λb b bT1 1 1 + µ 2b b bTT T Tb b b, = min b b b∈{0,1}b b bTQ Q Q+λdiag(1 1 1) + µ 2T T Tb b b, (26) where the second (linear) term in (25) refers to the Lagrangian multipliers method, the third (quadratic) term refers to the penalty method, and λis the Lagrangian multiplier; the constant terms can be ignored when solving the optimization problem. The above optimization problem can be solved iteratively, where a QUBO problem (given in (26)) is solved at each iteration. The parameters λand µare updated at each iteration with λ←λ+µ(b b bT1 1 1 + C′)and µ←ρµ where ρ>1is the increase factor (typically ρ= 1.1[27]). Due to hardware limitations, the D-WAVE solver may occasionally return infeasible solutions. At each iteration, we consider the best feasible solution returned by the QUBO solver; if no feasible solution is found, we proceed with the best available (infeasible) one. The returned solution is used without postprocessing, allowing us to directly assess the annealer’s performance within the AL framework. Thanks to the iterative nature of the algorithm, occasional infeasibility does not significantly affect convergence. Exploring feasibility-enforcing variants or lightweight correction mechanisms is left for future work. The iterative AL algorithm is presented in Algorithm 2; the algorithm repeats until some formal termination criteria are met e.g., based on the number of iterations, time, convergence etc. Note that the local convergence of the AL method has been established when the objective and constraint functions are twice continuously differentiable, which is the case for the problem (P2), in [45]. D. Performance benchmarks 1) Exhaustive search: The exhaustive search (ES) can solve the optimization problems considered by computing the SNR objective function over all the possible RIS vectors; the vector that maximizes SNR (and/or satisfies the equality constraint in the case of (P2) is the solution of the optimization problem. Due to the symmetry of the SNR, the ES algorithm requires 2N/2=2N−1computations, and therefore its complexity is exponential with the number of RIS reflected elements. The ES can be applied for small number of RIS elements, while it becomes impractical for large configurations; it is used as a benchmark for the scenarios where it can be applied. 2) Simulated annealing: Simulated annealing (SA) is an alternative classical method to solve QUBO problems. For our results, we use the the SA scheme of D-WAVE which is embedded in the Ocean SKD tool; SA operates locally on personal computers without necessitating data transmission to the D-WAVE hardware. For comparison, we employ SA in Step 2of Algorithm 2 to implement the iterative AL algorithm and solve the problem in (24). We set the parameters as λ= 2.1, µ = 2, ρ = 1.1, and the maximum number of iterations is 50. This algorithm can be used as an approximate optimal solution when the above ES can not be applied (RIS configurations with a large number of elements). 3) Random selection: A trivial scheme that does not require any complicated computation is random selection. In this scheme, we generate Mrandom RIS vectors and select the best feasible vector (if it exists), that is, the vector that satisfies the IM parameter kand returns the maximum SNR value. To have a fair comparison with the D-WAVE solver, Mis taken equal to the number of D-WAVE anneals. E. Complexity Both the penalty (Algorithm 1) and the AL (Algorithm 2) algorithms are iterative and therefore their complexity is equal to the number of iterations multiplied with the complexity of D-WAVE/SA for a single iteration. Theoretically, within each iteration, the complexity of QA is O(e√N), while the complexity of SA is O(eN)[46], where Nis the size of the QUBO problem. However, in practice, unlike the D-WAVE QA solver, SA is not affected by the quantum hardware topology and numerical resolution. It is also worth noting that in QA, instead of analyzing the computation time/complexity of a given algorithm, we mainly study the trade-off between the time and the probability that the QA output is correct. Therefore, in our D-WAVE QA experimental studies, the number of anneals as well as the duration of each anneal do not scale with the size of the problem and remain constant. Energy consumption is not explicitly analyzed in this work, as it depends on hardware-specific factors such as qubit count, annealing schedule, and embedding strategies, which are not accessible through the current D-WAVE interface. However, future D-WAVE systems are projected to offer notable power efficiency improvements over classical hardware in various wireless communication scenarios [33]. V. NUMERICAL RESULTS Simulation and experimental results are carried-out to evaluate the performance of the proposed RIS-aided IM scheme. For the experimental results, we focus on four case studies that correspond to specific system parameters. Specifically, we consider four indicative RIS scenarios with N= {10,25,50,100}. Note that the elements of the channel vectors h h h,g g gare samples from a complex Gaussian distribution with zero mean and variance one. Fig. 2 visualizes the (complex) matrices R R Rfor the four scenarios considered. As for the IM parameter k, we consider k={3,10,20,20}for N={10,25,50,100}, respectively, without loss of generality. The selected case studies are sufficient to demonstrate the effectiveness of the D-Wave quantum annealer in addressing the RIS design problem under consideration. Specifically, our experimental setup includes four representative, fully dense QUBO instances comprising 10,25,50, and 100 binary variables. These instances allow us to systematically assess the performance and scalability of the D-Wave system as the problem size increases. We note that our approach is general and can, in principle, be extended to larger RIS configurations. However, due to current quantum hardware limitations (including restricted access to the D-WAVE solver), we limit our experiments to RIS sizes up to 100 elements. 9 Channel 1N=10 2 4 6 8 10 Real 2 4 6 8 10 2 4 6 8 10 Imaginary 2 4 6 8 10 Channel 2N=25 5 10 15 20 25 Real 5 10 15 20 25 5 10 15 20 25 Imaginary 5 10 15 20 25 Channel 3N=50 10 20 30 40 50 Real 10 20 30 40 50 10 20 30 40 50 Imaginary 10 20 30 40 50 Channel 4N=100 20 40 60 80 100 Real 20 40 60 80 100 20 40 60 80 100 Imaginary 20 40 60 80 100 -10 -8 -6 -4 -2 0 2 4 6 8 10 Fig. 2. Matrix R R Rfor the four considered cases studies with N= {10,25,50,100}. TABLE II AVERAGE CAPACITY PERFORMANCE (IN BPCU) FOR IM-BASED AND CONVENTIONAL RIS SCHEMES; RIS SETUP WITH N={4,6,10,14},Pt= 1,N0= 1 AND ES. RIS scheme N= 4 N= 6 N= 10 N= 14 IM-based 7.034 8.558 10.507 11.821 Conventional 5.988 7.086 8.482 9.408 A. Proposed IM-based RIS design vs conventional RIS scheme In our first numerical results, we focus on the comparison between the proposed IM-based scheme and the conventional RIS design. Table II shows the average capacity performance (over 10,000 channel realizations) for small RIS configurations where ES can be applied to solve (P1) and (P2). The key observation is that the proposed IM-based scheme significantly outperforms the conventional RIS design and the performance gain increases as the number of elements increases. For larger RIS configurations, we apply the SA algorithm with AL (Algorithm 2) for RIS vector optimization for both schemes; we consider the channel coefficients given in Fig. 2. Specifically, Fig. 3(left) shows the normalized SNR (≜x x xTR R Rx x x) performance for all values of the IM parameter (k= 0,...,⌊N/2⌋) as well as the SNR associated with the conventional RIS design (dashed line). An interesting remark is that the SNR performance of the IM-based scheme is mainly improved as kincreases. The justification is that the function N kincreases monotonically (more combinations for larger k) and therefore the optimal RIS vector that maximizes the SNR is more probable to correspond to higher k. The results (on the right of Fig. 3) show the capacity performance for a normalized set-up (with Pt= 1 and N0= 1) for the four RIS configurations considered. The results are inline with our previous observations in Table II. The proposed IMbased scheme outperforms the conventional design and the performance gain increases as Nincreases; the capacity gain increases from 2to 5bits per channel use for an RIS with 25 and 100 elements, respectively. 012345 0 50 100 SNR Channel 1N=10 IM-based scheme Conventional RIS scheme 0 2 4 6 8 10 12 0 200 400 SNR Channel 2N=25 0 5 10 15 20 25 0 500 1000 SNR Channel 3N=50 0 10 20 30 40 50 IM parameter (k) 0 2000 4000 SNR Channel 4N=100 0 20 40 60 80 100 RIS size (N) 8 10 12 14 16 18 20 Capacity (bits per channel use) IM-based scheme Conventional RIS scheme Fig. 3. (left) Normalized SNR performance of the proposed IM-based RIS schreme versus the IM parameter kfor the four indicative RIS scenarios; the “dashed line” represents the conventional RIS scheme. (right) Capacity performance for both the IM-based and conventional RIS schemes for the four indicative RIS scenarios; Pt= 1 and N0= 1. TABLE III MAIN PARAMETERS FOR THE D-WAVE EXPERIMENTS Number of anneals 1,000 Anneal time 1µsec Channel strength (ferromagnetic coupling parameter) 3[34] Penalty method ∆µ1.5 Maximum number of iterations 20 AL method µ2 λ2.1 ρ1.1 Maximum number of iterations 20 B. D-WAVE experimental results For our D-WAVE QA experiments, we use the D-WAVE Leap interface with the Advantage System 6.4 quantum processing unit [22]. For each QUBO instance, we use the parameters listed in Table III. For minor embedding, we adopt the heuristic algorithm minorminer which is included in the Ocean SDK by default; in this case, a majority vote is applied to broken chains. Due to the probabilistic nature of the QA process, the D-WAVE solver may return several distinct solutions; the returned solutions are ordered in descending order of their objective function. In addition, we consider the probability of occurrence of each distinct solution (over the total number of anneals) and the probability of feasibility, which is the probability to obtain a feasible solution over all the anneals. All experimental results assume Ptand N0= 1. 1) Conventional RIS design: Fig. 4 shows the performance of the D-WAVE solver for the four channels considered, when a conventional RIS optimization is applied. The first key observation is that the D-WAVE solver returns a close-tooptimal solution for all cases, which makes D-WAVE heuristic highly efficient for the combinatorial problem considered. A comparison between the four channels shows that the quality of the solutions reduces with the number of RIS elements. Specifically, we observe that the number of distinct solutions