File size: 4,477 Bytes
83f5598 79eda78 83f5598 79eda78 83f5598 79eda78 83f5598 | 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 | """Compile a reversible circuit to a ternary matrix stack and show the composed
transition is a permutation, realized on a crossbar with a measured noise
margin. This substantiates neural_reversible's no-erasure claim concretely with
the same matrix/crossbar machinery neural_matrix8 uses: a reversible circuit is
one product of ternary matrices with a Heaviside step, and because the circuit
is a bijection the composed map is a permutation of the state space, so every
matrix in the stack is applied without erasing information."""
from __future__ import annotations
import os
import sys
import torch
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
sys.path.insert(0, os.path.join(ROOT, "src"))
import reversible as rv
from matrix8 import Net, compile_net, MatrixMachine
def adder_net(width: int):
"""The in-place Cuccaro adder (b <- a+b) as a feedforward ternary netlist:
each reversible gate writes a fresh wire, so the input->output map is the
permutation the circuit computes."""
a_bits = list(range(width))
b_bits = list(range(width, 2 * width))
carry = 2 * width
n = 2 * width + 1
ops = rv._adder_ops(a_bits, b_bits, carry)
net = Net()
inputs = [f"in{i}" for i in range(n)]
cur = list(inputs)
for k, (gate, *args) in enumerate(ops):
if gate is rv.CNOT:
c, t = args
cur[t] = net.XOR(f"c{k}", cur[t], cur[c]) # t ^= c
else: # Toffoli: t ^= a&b
a, b, t = args
tmp = net.AND(f"t{k}a", [cur[a], cur[b]])
cur[t] = net.XOR(f"t{k}x", cur[t], tmp)
return net, inputs, list(cur), n, a_bits, b_bits, carry
def _refs(n, a_bits, b_bits, carry):
out = []
for x in range(1 << n):
reg = [(x >> i) & 1 for i in range(n)]
rv._apply(reg, rv._adder_ops(a_bits, b_bits, carry))
out.append(sum(reg[i] << i for i in range(n)))
return torch.tensor(out)
def _outputs(mm, states, n, **step_kw):
v = mm.step(states.clone(), **step_kw)
bits = (v >= 0.5).to(torch.int64)
weights = torch.tensor([1 << i for i in range(n)])
return (bits * weights).sum(dim=1)
def analog_sweep(mm, states, refs, n):
"""The permutation must survive analog imperfection. Read noise is injected
per matrix-vector product; conductance mismatch is a fixed per-device
perturbation of the ternary weights."""
print(" read-noise sweep (bit-exact = all 512 outputs still match, 4 trials):")
for sigma in (0.05, 0.10, 0.15, 0.20):
ok = all((_outputs(mm, states, n, analog=True, noise_sigma=sigma,
gen=torch.Generator().manual_seed(s)) == refs).all()
for s in range(4))
print(f" sigma={sigma:.2f}: {'bit-exact' if ok else 'errors appear'}")
print(" conductance-mismatch sweep (fixed per-device weight perturbation):")
for sg in (0.05, 0.10, 0.15):
ok = (_outputs(mm.perturbed(sg, seed=0), states, n, analog=True) == refs).all()
print(f" sigma_G={sg:.2f}: {'bit-exact' if ok else 'errors appear'}")
def main() -> int:
width = 4
net, inputs, outputs, n, a_bits, b_bits, carry = adder_net(width)
layers, info = compile_net(net, inputs, outputs)
mm = MatrixMachine(layers)
states = torch.stack([torch.tensor([float((x >> i) & 1) for i in range(n)])
for x in range(1 << n)])
refs = _refs(n, a_bits, b_bits, carry)
got = _outputs(mm, states, n)
bad = int((got != refs).sum())
perm = len(set(got.tolist())) == (1 << n)
margin = mm.min_margin(states[:256])
print(f"reversible {width}-bit adder as a ternary matrix stack")
print(f" layers={info['layers']} gates={info['gates']} "
f"max_width={info['max_width']} total_weights={info['total_weights']}")
print(f" every weight ternary: {'OK' if all(((W == -1) | (W == 0) | (W == 1)).all() for W, _ in layers) else 'FAIL'}")
print(f" matches the gate circuit over all {1 << n} inputs: {'OK' if bad == 0 else f'FAIL({bad})'}")
print(f" composed transition is a permutation of the state space: {'OK' if perm else 'FAIL'}")
print(f" analog noise margin, all layers: {margin:.3f} (guarantee 0.5)")
analog_sweep(mm, states, refs, n)
ok = bad == 0 and perm and abs(margin - 0.5) < 1e-6
print("PASS" if ok else "FAIL")
return 0 if ok else 1
if __name__ == "__main__":
sys.exit(main())
|