Penalty-Free Ising Encodings for Low-Resolution Reflecting Surfaces

A reconfigurable intelligent surface is a flat panel of hundreds of cheap antenna elements, each of which reflects an incoming radio wave with an adjustable phase delay. To keep the hardware cheap, each element usually offers only two phase settings (1-bit: $0$ or $\pi$) or four (2-bit: quarter turns). Choosing the settings is therefore a combinatorial problem with $B^N$ configurations for $N$ elements and $B$ states. Most current algorithms avoid the combinatorics. They optimize continuous phases and then either round them or push them toward the allowed states with a penalty. Both routes are local and depend on initialization. A separate community solves quadratic binary problems (QUBO, the minimization of a quadratic function of 0/1 variables, equivalently an Ising energy over $\pm 1$ "spins") with annealing-style solvers that are built to escape local minima.

The observation behind this proposal is that for 1-bit and 2-bit surfaces, no penalty is needed to join the two. A 1-bit phase is already a spin. A 2-bit phase is an exact linear function of two spins. Inside a standard alternating design loop, the surface subproblem is a quadratic form in the phases, so it becomes an exact Ising problem with no penalty weight to tune. The more important claim is about when this helps. When the quadratic form has rank one, as in single-user power maximization, the discrete problem is easy and an Ising solver is overkill. Global solvers should begin to matter only as the coupling matrix gains rank and becomes indefinite, which happens with more users, interference constraints, and eavesdroppers. We propose to build the encoding and to measure that transition directly.

Core Claim

Let $\phi \in \mathbb{C}^N$ collect the surface reflection coefficients. In alternating schemes that majorize or reweight the rate objective, the surface step minimizes a surrogate of the form

$$f(\phi) = \phi^H A \phi - 2\,\mathrm{Re}(b^H \phi),$$

where $A$ is a Hermitian $N\times N$ matrix and $b\in\mathbb{C}^N$ is a vector, both built from the current channels and base-station precoder. Majorization of this kind is used for passive mirrors in Achievable Rate maximization by Passive Intelligent Mirrors.

For a 1-bit surface, $\phi_n = s_n \in \{\pm 1\}$. For a 2-bit surface, the allowed set $\{1, j, -1, -j\}$ is written exactly as

$$\phi_n = e^{-j\pi/4}\,\frac{s_{n,1} + j\,s_{n,2}}{\sqrt{2}}, \qquad s_{n,1}, s_{n,2} \in \{\pm 1\}.$$

This gives $\phi = D s$ for a fixed complex $N \times 2N$ matrix $D$. Then $f$ becomes the real Ising energy $s^T \mathrm{Re}(D^H A D)\, s - 2\,\mathrm{Re}(b^H D)\, s$. The linear term is absorbed by one extra spin fixed by symmetry. Every spin assignment is a valid hardware configuration. There is no constraint penalty, and so none of the penalty-weight sensitivity that Evaluating dynamic spectrum allocation using quantum annealing reports, where a narrow sweet spot sat at $\lambda = 0.7$. For 3 bits and above, no exact linear spin map of this kind exists in general. That case is a controlled contrast: we compare a one-hot encoding with penalties against an approximate three-spin linear encoding whose modulus error we quantify.

The claim we will test is conditional. The gain of a global Ising solver over simple local search on this surrogate should grow with the effective rank and indefiniteness of $A$. Effective rank rises roughly with the number of served users. Indefiniteness appears when eavesdropper or interference terms enter with a negative sign.

The rank-one limit is a classical observation. Maximizing $|h^T s|^2$ over $s \in \{\pm1\}^N$ is solved exactly by testing $O(N)$ half-plane splits of the angles of $h$. More generally, rank-$r$ binary quadratics admit enumeration that is polynomial in $N$ for fixed $r$. A proposal that ignored this would be selling an annealer for an easy problem.

Research Program

The first component is the encoding and the loop. We embed the exact 1-bit and 2-bit maps in an alternating optimization. In that loop, the continuous base-station precoder is updated in closed form or by gradient steps, following the decoupling used by A Low-Complexity Algorithmic Framework for Large-Scale IRS-Assisted Wireless Systems and Alternating Minimization Algorithms for Hybrid Precoding in Millimeter Wave MIMO Systems. Both of those papers assume continuous phases and leave the discrete case open. Our loop changes only one thing: the surface step is solved as an Ising problem.

We target three objectives:

The second component is the solvers. We use classical Ising heuristics: simulated annealing and a GPU momentum-annealing style solver of the kind used for spectrum allocation in Evaluating dynamic spectrum allocation using quantum annealing. We also use the vectorized positive semidefinite penalty method with its projection-alternating Barzilai-Borwein variant from A Vectorized Positive Semidefinite Penalty Method for Unconstrained Binary Quadratic Programming. That method removes the full-matrix cost of semidefinite relaxation. It has been evaluated only on abstract benchmark matrices, never on matrices coming from array channels. Physical quantum annealers are a secondary target. The coupling matrices here are dense, so minor embedding would chain each logical spin across many qubits, a cost flagged by Quantum Computing for Large-scale Network Optimization: Opportunities and Challenges. We will therefore report embedding overhead, not headline hardware results.

The third component is a regime map. For each channel draw we record the effective rank of $A$ (the number of eigenvalues needed for 95% of its spectral mass) and the fraction of negative spectral mass. We then plot how solver advantage varies along these two coordinates. This map is the main scientific output: it tells a system designer when a combinatorial solver is worth its cost.

Baselines

The naive reference is continuous optimization followed by rounding to the nearest allowed state. We implement it as AO-GD from A Low-Complexity Algorithmic Framework for Large-Scale IRS-Assisted Wireless Systems followed by per-element quantization. Robust and Secure Wireless Communications via Intelligent Reflecting Surfaces argues this destroys the precise phase alignment that interference cancellation and nulling depend on. Beating it is necessary but not impressive.

The strongest existing method is the continuous penalty scheme of Active RIS-Assisted Multi-User Multi-Stream Transmit Precoding Relying on Scalable-Complexity Iterations. It drives relaxed phases toward discrete states and reports convergence in 30–45 iterations, running over 20 times faster than cubic-complexity solvers. The closely related hybrid-beamforming version is Max-min Rate Optimization of Low-Complexity Hybrid Multi-User Beamforming Maintaining Rate-Fairness. That paper reports a 3–5% drop from infinite resolution to 3-bit shifters, and a sum-rate of about 40 bps/Hz with minimum user rates of 1.0–2.5 bps/Hz at 25 dBm, for 72 antennas and 8 users. We found no reported result on Lacuna for either penalty method at 1-bit or 2-bit resolution. That coarse regime is where we expect differences, so we will reimplement both. Our method beats them only if it achieves a higher minimum rate or secrecy rate at equal wall-clock time, on the same channel realizations, with each method given the same number of random restarts and hyperparameter trials.

Two further baselines matter because they are cheap. The first is greedy single-element flipping with random restarts on the identical surrogate. The second is exact low-rank enumeration when the rank of $A$ is at most two or three. Semidefinite relaxation with Gaussian randomization serves as the classical quality reference.

Two ablations isolate the key ingredients. The first swaps the exact 2-bit spin map for a one-hot penalty encoding while keeping the same solver, which isolates the value of removing penalties. The second swaps the global Ising solver for greedy flips while keeping the same encoding, which isolates the value of global search.

Solution gaps are measured against exact optima. We obtain these by exhaustive enumeration up to about 30 spins, and on 16–64 element instances by the branch-and-bound approach of Joint Antenna Selection and Phase-Only Beamforming Using Mixed-Integer Nonlinear Programming. That paper reports a 26% speedup from custom modulus cuts and a 39% time reduction from warm starts, but does not scale further.

Why not just…?

Why not just optimize continuous phases and round? Rounding is fine when the objective rewards coherent addition, which is why single-user gains survive quantization. It fails when the design relies on cancellation, as Robust and Secure Wireless Communications via Intelligent Reflecting Surfaces argues for multi-user nulling and secrecy. Our regime map makes this concrete: rounding's gap to optimum should grow with the negative spectral mass of $A$. If it does not, rounding wins and we will say so.

Why not just use the continuous penalty methods that already scale linearly? This is the real competitor. At 3 bits the reported loss is only 3–5%, which leaves little headroom. We therefore expect no advantage at 3 bits and concentrate on 1-bit and 2-bit surfaces, where the file notes that penalty methods are most initialization-sensitive. The head-to-head uses equal wall-clock time and equal restarts. The outcome could be that penalty methods with a few restarts match Ising solvers everywhere. That result is still useful: it would show that the discrete RIS landscape is benign.

Why not just run greedy element flips, or solve the low-rank problem exactly? This is the objection most likely to succeed, and the proposal is built around it rather than against it. For single-user and few-user cases, the surrogate matrix is low rank, exact enumeration is polynomial, and greedy search is probably near-optimal. We commit to reporting the rank threshold below which these cheap methods match annealing. The claim for Ising solvers survives only above that threshold, for example in the 8-user and secrecy settings.

Why not just use semidefinite relaxation? Its runtime is prohibitive at hundreds of elements, as A Low-Complexity Algorithmic Framework for Large-Scale IRS-Assisted Wireless Systems shows. The vectorized penalty method keeps its bound-driven character at vector cost, reaching a 0.02% gap at $n=80$ on random QUBO instances according to A Vectorized Positive Semidefinite Penalty Method for Unconstrained Binary Quadratic Programming. Whether that transfers to array-channel matrices is one of our tests.

Proposed Experiments

We use three benchmark setups, each with 1-bit and 2-bit surfaces:

We also scale surfaces to 1,000 elements, where brute force and branch-and-bound are impossible and only relative comparisons are available. As a sanity check, the Ising solvers are first validated on G-set instances, to confirm they perform sensibly before any claim about channel matrices.

Metrics are:

  • Minimum user rate, sum-rate, and secrecy rate.
  • Gap to exact optimum on small instances.
  • Per-subproblem wall-clock time, compared against channel coherence time.
  • Number of outer alternating iterations.
  • For the penalty-encoded 3-bit ablation, the fraction of runs that return infeasible or near-infeasible configurations across a sweep of penalty weights.

Two outcomes decide the proposal. First, on the exhaustively solvable instances, the gap of greedy flips and of the continuous penalty method must plotted against effective rank and negative spectral mass of $A$. The claim holds only if these gaps rise with those quantities while the Ising solvers stay near optimal. Second, at 1-bit and 2-bit resolution with 8 users or with an eavesdropper present, the Ising-based loop must beat the strongest penalty baseline in minimum or secrecy rate at matched wall-clock time. If both hold, designers get a rule for when combinatorial solvers are worth using on reflecting surfaces. If only the low-rank methods and greedy search hold up, the proposal still delivers a precise account of why discrete surface design is easier than its $B^N$ search space suggests.