Ferkans — Interactive Telecom Tutor

Every Real RIS Is Discrete

Chapter 2 covered the hardware story: a PIN-diode unit cell gives $2^B$ phase states for $B$ diodes, while a varactor with a 3-bit DAC gives 8 phase states. Continuous phases are a mathematical convenience, not a deployable reality. Section 8.1 formalizes the discrete-phase optimization problem, highlights its combinatorial structure, and contrasts it with the continuous case.

The golden thread: the RIS programs the channel. Discretizing the phase-shift alphabet constrains how finely the channel can be programmed, but does not fundamentally change what the RIS can do. Section 2.2 showed the loss is $\text{sinc}^2(\pi/2^B)$ under coherent alignment — modest at $B = 3$ , severe at $B = 1$ . Here we translate the optimization framework from continuous $\mathcal{M} = (S^1)^N$ to discrete $\mathcal{M}_B$ .

Discrete Torus

The finite feasible set $\mathcal{M}_B = \{e^{j\theta} : \theta \in \Theta_B\}^N$ of the $B$ -bit RIS, consisting of $L^N = 2^{BN}$ distinct configurations. A finite subset of the continuous unit-modulus torus $\mathcal{M} = (S^1)^N$ .

Nearest-Level Projection

The operator $\mathcal{P}_{\Theta_B}(\theta)$ that maps a continuous phase $\theta \in [0, 2\pi)$ to its closest point on the discrete grid $\Theta_B$ . Implements the "project-from-continuous" discrete optimization approach.

Definition:
Discrete-Phase Unit-Modulus QCQP

Let $\Theta_B = \{0, \Delta\theta, 2\Delta\theta, \ldots, (L-1)\Delta\theta\}$ with $L = 2^B, \Delta\theta = 2\pi/L$ be the $B$ -bit phase alphabet. The discrete feasible set is

$\mathcal{M}_B = \{(e^{j\theta_1}, \ldots, e^{j\theta_N}) : \theta_n \in \Theta_B\} \subset \mathcal{M}.$

The discrete-phase passive subproblem is

$\boxed{\;\max_{\boldsymbol{\phi} \in \mathcal{M}_B}\; \boldsymbol{\phi}^H \mathbf{A} \boldsymbol{\phi}\;}$

with PSD $\mathbf{A}$ . The continuous-phase QCQP relaxes $\mathcal{M}_B$ to $\mathcal{M}$ ; the continuous problem is NP-hard, and the discrete version is strictly harder (at best the same, but typically combinatorially harder).

Theorem: Discrete-Phase QCQP Is NP-Hard

The discrete-phase unit-modulus QCQP with $L \geq 2$ phase levels is NP-hard. Specifically:

At $L = 2$ (1-bit), the problem reduces to MAX-CUT, which is NP-hard (Karp 1972).
For general $L$ , the problem can be reduced to 1-bit by discretization arguments.

The brute-force search space has $L^N$ configurations: at $N = 256, B = 2$ , that is $4^{256} \approx 10^{154}$ . Exhaustive search is hopeless for any practical $N$ .

The continuous case is NP-hard (Ch. 6, Theorem 6.2); restricting to a discrete subset can only make the problem harder or equal — in this case, equal: both are NP-hard. The brute-force search space is $L^N$ , which is astronomically large even for modest $N$ .

,

Key Takeaway

Discrete-phase RIS is combinatorially hopeless — and pedagogically informative. No polynomial-time algorithm exists for the exact global optimum. Two practical routes: (1) continuous-then-project (Section 8.2), giving near-optimal solutions in polynomial time; (2) direct discrete optimization (Section 8.3), matching the continuous-project quality in most cases with similar cost. Both are approximate.

Two Routes to the Discrete Solution

Two algorithmic philosophies for the discrete-phase problem:

Continuous-then-project: Solve the continuous-phase problem (Chapters 5–7), then project each $\phi_n^\star$ onto the nearest discrete level. Simple, uses existing machinery, discretization loss of $\text{sinc}^2(\pi/2^B)$ for coherent problems (Chapter 2, Theorem 2.4).
Direct discrete optimization: Work natively in $\mathcal{M}_B$ . Methods: discrete BCD (closed-form at each coordinate), branch-and-bound for small $N$ , tabu/simulated annealing heuristics, SDR + discrete randomization.

Section 8.2 develops the projection approach (simpler, usually sufficient), Section 8.3 the direct approach (slightly better for multi-user scenarios).

Example: Projection for a 2-bit RIS, $N = 3$

A continuous-phase solution is $\theta_n^\star = [0.3, 2.5, 4.8]$ (radians). Project onto the 2-bit phase grid $\Theta_2 = \{0, \pi/2, \pi, 3\pi/2\}$ .

Solution

Grid boundaries

$\Delta\theta = 2\pi/4 = \pi/2 \approx 1.571$ . Grid points at $\{0, 1.571, 3.142, 4.712\}$ . Boundaries between grid cells: midpoints at $\{0.785, 2.356, 3.927, 5.498\}$ .

Project each

$0.3$ : nearest grid point is $0$ (distance $0.3$ ). Projected: $0$ .
$2.5$ : between $1.571$ (dist $0.929$ ) and $3.142$ (dist $0.642$ ). Projected: $3.142 = \pi$ .
$4.8$ : between $4.712$ (dist $0.088$ ) and $6.283$ (dist $1.483$ ). Projected: $4.712 = 3\pi/2$ .

Discretized $\boldsymbol{\theta}$

$\theta^{\text{disc}} = [0, \pi, 3\pi/2]$ — a valid 2-bit configuration. The quantization error is $[0.3, -0.642, 0.088]$ , with max magnitude $0.642 \leq \Delta\theta/2 = 0.785$ ✓. $\blacksquare$

Discrete Phase Grid on the Complex Unit Circle — Left: 1-bit (2 phases). Center: 2-bit (4 phases). Right: 3-bit (8 phases). The discrete torus $\mathcal{M}_B$ is the Cartesian product of $N$ copies of the grid. Projection rounds any continuous $\theta$ to its nearest grid point (dashed lines: Voronoi cell boundaries).

Multi-User: Discretization Couples the Users

For single-user scenarios, the continuous-phase optimum projects cleanly: each element's optimal phase is independent of the others ( $\phi_n^\star = e^{-j\arg(a_n)}$ ), so rounding each is independently near-optimal.

For multi-user scenarios, the continuous-phase optimum has coupled coordinates — each $\phi_n$ depends on all others through the inter-user interference terms. Independent per-coordinate rounding can disrupt the coupling, giving a worse discrete solution than a more careful joint projection. Section 8.3's direct-discrete BCD is designed to handle this coupling.

⚠️Engineering Note

Bit Budget vs. Element Count

A fixed hardware complexity budget (number of control pins) can be spent as either more elements at lower resolution, or fewer elements at higher resolution. The tradeoff:

$N = 1024$ elements at $B = 1$ -bit: $N \log_2 L = 1024 \cdot 1 = 1024$ control bits. Loss: $3.92\text{ dB}$ per Theorem 2.4. Effective size: $N_{\text{eff}} \approx N/\eta_B^{-1} \approx 416$ .
$N = 256$ at $B = 3$ -bit: $256 \cdot 3 = 768$ control bits. Loss: $0.22\text{ dB}$ . Effective size: $\sim N$ .
$N = 128$ at $B = 4$ -bit: $128 \cdot 4 = 512$ control bits. Loss: $0.06\text{ dB}$ . Effective size: $\sim N$ .

A fixed budget of $\sim 1024$ control bits favors the higher-resolution option because coherent SNR is quadratic in $N$ : doubling $N$ at the cost of 1 fewer bit gives $2^2 / 1/\eta_1 \approx 4 \cdot 0.4 = 1.6 \times$ SNR, a favorable trade. So at hardware cost parity, more elements at lower resolution generally wins — but only if $B \geq 2$ (below which the quantization loss erodes the scaling benefit).

Practical Constraints

•
Control-bit budgets scale roughly with panel cost: $\sim \$0.05$ - $0.30$ per bit/pin in volume.
•
Phase resolution $B \geq 3$ is standard for production RIS panels (losses $\leq 0.3$ dB).
•
1-bit RIS is rare except in research prototypes (Arun and Balakrishnan 2020 RFocus).

Bit Budget: More Elements or More Bits?

For a fixed total control-bit budget $B \cdot N = C$ , plot the effective coherent SNR as $B$ varies (with $N = C/B$ ). The curve shows the optimal tradeoff — typically $B = 2$ - $3$ bits with the maximum $N$ allowed by the budget.

Parameters

Total control-bit budget1024

Single-element SNR reference (dB)-20

Common Mistake: Don't Chase 1-Bit Because It's Simple

Mistake:

"1-bit RIS is cheapest; I'll build a huge $N = 4096$ panel and exploit the $N^2$ gain to beat all comers."

Correction:

1-bit costs $\text{sinc}^2(\pi/2) = 0.405$ — a $3.92\text{ dB}$ coherent SNR penalty. To match 3-bit's performance, need $N_{\text{1-bit}} = N_{\text{3-bit}} / \sqrt{0.405/0.949} \approx 1.53 N_{\text{3-bit}}$ . If control-bit budget is the constraint, $B = 2$ - $3$ with moderate $N$ is typically the sweet spot. Go to 1-bit only if the pin/cost budget is very tight and you are happy with a $\sim 4\text{ dB}$ penalty.

The Discrete-Phase RIS Problem