1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
//! How a discrete variable is spelled in spins.
//!
//! The fabric has one variable: the spin, ±1. A problem may have a variable that takes one of `k`
//! values, and someone has to choose how to write it down. That choice is a compiler decision with
//! measurable consequences — spin count, how many penalty couplings it drags in, and whether the
//! penalty strength then needs tuning — which is exactly why it is a pass here rather than a type
//! in the IR.
//!
//! Three encodings, and the trade is real:
//!
//! | Encoding | Spins | Penalty couplings | Note |
//! |---|---|---|---|
//! | [`Encoding::OneHot`] | k | k(k−1)/2, **quadratic** | the obvious one, and the expensive one |
//! | [`Encoding::Binary`] | ⌈log₂k⌉ | none *if k is a power of two* | fewest spins, densest factors |
//! | [`Encoding::DomainWall`] | k−1 | k−2, **linear**, a chain | Chancellor 2019 |
//!
//! The domain-wall advantage is usually stated as "no penalty", which is not quite right and worth
//! being precise about: it still needs terms to suppress states with more than one wall. What it
//! does is replace one-hot's all-to-all penalty with a *chain*, so the penalty cost falls from
//! quadratic to linear in k, and it saves a spin. That is the honest claim.
//!
//! Binary is the trap. It uses the fewest spins, but only excludes surplus codes for free when `k`
//! is a power of two; otherwise the leftover codes are invalid states that cannot in general be
//! excluded by pairwise couplings at all. [`Slot::decode`] returns `None` for them and
//! [`Slot::add_penalty`] says so rather than pretending.
use crate::graph::GraphBuilder;
/// How to spell a `k`-valued variable in spins.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Encoding {
/// One spin per value; exactly one is +1. Penalty is all-to-all.
OneHot,
/// Binary expansion. Fewest spins, but surplus codes when `k` is not a power of two.
Binary,
/// A chain of `k-1` spins holding a single domain wall (Chancellor 2019).
DomainWall,
}
impl Encoding {
/// Spins needed for a `k`-valued variable.
pub fn spins(&self, k: usize) -> usize {
assert!(k >= 2, "a variable with fewer than 2 values is a constant");
match self {
Encoding::OneHot => k,
Encoding::Binary => (usize::BITS - (k - 1).leading_zeros()) as usize,
Encoding::DomainWall => k - 1,
}
}
/// Penalty couplings this encoding drags in for a `k`-valued variable.
pub fn penalty_couplings(&self, k: usize) -> usize {
match self {
Encoding::OneHot => k * (k - 1) / 2,
Encoding::Binary => 0,
Encoding::DomainWall => k.saturating_sub(2),
}
}
/// Whether this encoding can exclude every invalid state with pairwise terms.
///
/// Binary cannot when `k` is not a power of two: the surplus codes are an arbitrary subset of
/// the hypercube, and no pairwise penalty carves that out in general.
#[must_use = "false means invalid codewords remain reachable and `decode` is the only thing between them and a wrong answer"]
pub fn is_exact(&self, k: usize) -> bool {
match self {
Encoding::Binary => k.is_power_of_two(),
_ => true,
}
}
}
/// Where one categorical variable's spins live in a graph.
#[derive(Clone, Copy, Debug)]
pub struct Slot {
pub base: usize,
pub k: usize,
pub encoding: Encoding,
}
impl Slot {
pub fn new(base: usize, k: usize, encoding: Encoding) -> Self {
assert!(k >= 2, "a variable with fewer than 2 values is a constant");
Slot { base, k, encoding }
}
/// Spins this slot occupies.
pub fn width(&self) -> usize {
self.encoding.spins(self.k)
}
/// Range of spin indices this slot occupies.
pub fn range(&self) -> std::ops::Range<usize> {
self.base..self.base + self.width()
}
/// Write `value` into `s` in this encoding.
pub fn encode(&self, value: usize, s: &mut [i8]) {
assert!(value < self.k, "value {value} out of range for a {}-valued variable", self.k);
let w = self.width();
match self.encoding {
Encoding::OneHot => {
for i in 0..w {
s[self.base + i] = if i == value { 1 } else { -1 };
}
}
Encoding::Binary => {
for i in 0..w {
s[self.base + i] = if (value >> i) & 1 == 1 { 1 } else { -1 };
}
}
Encoding::DomainWall => {
// value v: the first v spins are +1, the rest -1. v = 0 is all -1, v = k-1 all +1.
for i in 0..w {
s[self.base + i] = if i < value { 1 } else { -1 };
}
}
}
}
/// Read this slot's value, or `None` if the spins do not form a valid codeword.
///
/// Returning `None` rather than a nearest-valid guess is deliberate: a sampler that has landed
/// on an invalid state is telling you the penalty was too weak, and silently rounding that away
/// is how a constraint violation becomes a wrong answer nobody notices.
pub fn decode(&self, s: &[i8]) -> Option<usize> {
let w = self.width();
let bits = &s[self.base..self.base + w];
match self.encoding {
Encoding::OneHot => {
let mut found = None;
for (i, &b) in bits.iter().enumerate() {
if b > 0 {
if found.is_some() {
return None; // more than one hot
}
found = Some(i);
}
}
found
}
Encoding::Binary => {
let mut v = 0usize;
for (i, &b) in bits.iter().enumerate() {
if b > 0 {
v |= 1 << i;
}
}
if v < self.k {
Some(v)
} else {
None // a surplus code
}
}
Encoding::DomainWall => {
// valid iff non-increasing: a block of +1 then a block of -1, one wall
let v = bits.iter().take_while(|&&b| b > 0).count();
if bits[v..].iter().all(|&b| b < 0) {
Some(v)
} else {
None // more than one wall
}
}
}
}
/// Add this encoding's penalty terms at strength `p`.
///
/// Returns whether the penalty is exact. A `false` means invalid states remain reachable and
/// [`Slot::decode`] is the only thing standing between them and a wrong answer.
#[must_use = "this says whether the encoding can be made EXACT. Discarding it is how a k=6 binary variable shipped with invalid codewords costing exactly what valid ones cost, for three releases"]
pub fn add_penalty(&self, b: &mut GraphBuilder, p: f64) -> bool {
let w = self.width();
match self.encoding {
Encoding::OneHot => {
// P * (sum_i x_i - 1)^2 with x_i = (1 + s_i)/2, dropped to pairwise:
// J_ij = -P/2 for every pair, h_i = -P(k-2)/2
for i in 0..w {
for j in (i + 1)..w {
b.couple(self.base + i, self.base + j, -p / 2.0);
}
b.bias(self.base + i, -p * (self.k as f64 - 2.0) / 2.0);
}
true
}
Encoding::Binary => self.k.is_power_of_two(),
Encoding::DomainWall => {
// A ferromagnetic chain: every wall costs 2p, and the fixed boundaries force
// exactly one, so the k valid codewords are the degenerate ground states.
for i in 0..w.saturating_sub(1) {
b.couple(self.base + i, self.base + i + 1, p);
}
// boundaries s_0 = +1 and s_k = -1, folded into biases on the end spins
b.bias(self.base, p);
b.bias(self.base + w - 1, -p);
true
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::graph::GraphBuilder;
const ALL: [Encoding; 3] = [Encoding::OneHot, Encoding::Binary, Encoding::DomainWall];
#[test]
fn encode_decode_round_trips() {
for enc in ALL {
for k in 2..=9 {
let slot = Slot::new(0, k, enc);
let mut s = vec![0i8; slot.width()];
for v in 0..k {
slot.encode(v, &mut s);
assert_eq!(slot.decode(&s), Some(v), "{enc:?} k={k} v={v}");
}
}
}
}
#[test]
fn domain_wall_uses_fewer_spins_than_one_hot() {
// The acceptance criterion for this pass.
for k in 2..=32 {
assert!(
Encoding::DomainWall.spins(k) < Encoding::OneHot.spins(k),
"k={k}"
);
}
}
#[test]
fn domain_wall_penalty_is_linear_where_one_hot_is_quadratic() {
// The claim that actually matters, and the one usually mis-stated as "no penalty".
for k in [4, 8, 16, 64] {
let dw = Encoding::DomainWall.penalty_couplings(k);
let oh = Encoding::OneHot.penalty_couplings(k);
assert_eq!(dw, k - 2);
assert_eq!(oh, k * (k - 1) / 2);
assert!(dw < oh, "k={k}: dw {dw} vs oh {oh}");
}
// and it really is a chain, not merely smaller
assert_eq!(Encoding::DomainWall.penalty_couplings(1000), 998);
}
/// Enumerate every spin configuration and check the penalty's ground states are exactly the
/// valid codewords. This is the test that proves the construction rather than the algebra.
fn ground_states(enc: Encoding, k: usize, p: f64) -> Vec<usize> {
let slot = Slot::new(0, k, enc);
let w = slot.width();
let mut b = GraphBuilder::new(w);
// Asserted, not discarded. Both callers pass one-hot or domain-wall, which are exact for
// every k, so a `false` here means the construction regressed -- and the whole point of the
// `#[must_use]` is that discarding this once already shipped a k=6 binary variable whose
// invalid codewords cost exactly what valid ones cost, for three releases.
assert!(slot.add_penalty(&mut b, p), "{enc:?} k={k} must be exactly encodable");
let g = b.build();
let mut best = f64::INFINITY;
let mut at_best = Vec::new();
for mask in 0..(1usize << w) {
let s: Vec<i8> = (0..w).map(|i| if mask >> i & 1 == 1 { 1 } else { -1 }).collect();
let e = g.energy(&s);
if e < best - 1e-9 {
best = e;
at_best.clear();
}
if e < best + 1e-9 {
at_best.push(mask);
}
}
at_best
}
#[test]
fn domain_wall_ground_states_are_exactly_the_codewords() {
for k in 2..=8 {
let slot = Slot::new(0, k, Encoding::DomainWall);
let g = ground_states(Encoding::DomainWall, k, 2.0);
assert_eq!(g.len(), k, "k={k}: expected {k} degenerate ground states, got {}", g.len());
// and each one decodes to a distinct value
let w = slot.width();
let mut seen: Vec<usize> = g
.iter()
.map(|&mask| {
let s: Vec<i8> =
(0..w).map(|i| if mask >> i & 1 == 1 { 1 } else { -1 }).collect();
slot.decode(&s).expect("a ground state must be a valid codeword")
})
.collect();
seen.sort_unstable();
assert_eq!(seen, (0..k).collect::<Vec<_>>(), "k={k}");
}
}
#[test]
fn one_hot_ground_states_are_exactly_the_codewords() {
for k in 2..=7 {
let g = ground_states(Encoding::OneHot, k, 2.0);
assert_eq!(g.len(), k, "k={k}");
}
}
#[test]
fn binary_is_honest_about_surplus_codes() {
// k = 6 needs 3 spins, so codes 6 and 7 are invalid and no pairwise penalty removes them.
let slot = Slot::new(0, 6, Encoding::Binary);
assert_eq!(slot.width(), 3);
assert!(!Encoding::Binary.is_exact(6));
let mut b = GraphBuilder::new(3);
assert!(!slot.add_penalty(&mut b, 1.0), "must report that it cannot be exact");
let mut s = vec![-1i8; 3];
s[1] = 1;
s[2] = 1; // code 6
assert_eq!(slot.decode(&s), None, "a surplus code must decode to None, not a guess");
// powers of two have no surplus and are exact
assert!(Encoding::Binary.is_exact(8));
let mut b = GraphBuilder::new(3);
assert!(Slot::new(0, 8, Encoding::Binary).add_penalty(&mut b, 1.0));
}
#[test]
fn invalid_states_decode_to_none_rather_than_a_guess() {
// two hot
let oh = Slot::new(0, 4, Encoding::OneHot);
assert_eq!(oh.decode(&[1, 1, -1, -1]), None);
assert_eq!(oh.decode(&[-1, -1, -1, -1]), None, "none hot is also invalid");
// two walls
let dw = Slot::new(0, 5, Encoding::DomainWall);
assert_eq!(dw.decode(&[1, -1, 1, -1]), None);
assert_eq!(dw.decode(&[1, 1, -1, -1]), Some(2), "one wall is fine");
}
#[test]
fn slots_can_be_packed_side_by_side() {
// A model has many variables; their spins must not collide.
let a = Slot::new(0, 4, Encoding::DomainWall); // 3 spins: 0..3
let b = Slot::new(a.range().end, 5, Encoding::OneHot); // 5 spins: 3..8
assert_eq!(a.range(), 0..3);
assert_eq!(b.range(), 3..8);
let mut s = vec![0i8; 8];
a.encode(2, &mut s);
b.encode(3, &mut s);
assert_eq!(a.decode(&s), Some(2));
assert_eq!(b.decode(&s), Some(3));
}
}