Optional exact Boolean checker

The following program expands the literal gate specification and checks its Boolean action on every four-bit basis input. It also checks the gate ledger and padded output decoding. It uses no random sampling, floating-point arithmetic, order-finding oracle, or supplied factorization routine.

Its execution is not asserted. The mathematical proof is Lemma lem:row and Theorem thm:finite.

# Optional exact checker for Oai279-A. # This program is supplied, not reported as executed.

ell = 4 n = 128 q = ell + n*n + 3 u, v, f = q-3, q-2, q-1

# Rows: (input integer, zero-control positions, output targets). rows = [ (2, (0,2,3), (5,)), (3, (2,3), (4,5)), (4, (0,1,3), (5,133)), (5, (1,3), (4,6)), (6, (0,3), (5,132,133)), (7, (3,), (4,5,6)), (8, (0,1,2), (5,133,261)), (9, (1,2), (4,5,132,133)), (10, (0,2), (5,132,134)), (11, (2,), (4,5,7)), (12, (0,1), (5,133,260,261)), (13, (1,), (4,6,7)), (14, (0,), (5,132,133,134)), (15, (), (4,5,132,134)), ]

gates = [] compute = [ ("CCX", 0, 1, u), ("CCX", u, 2, v), ("CCX", v, 3, f), ]

for m, zeros, targets in rows: assert zeros == tuple( j for j in range(ell) if ((m >> j) & 1) == 0 ) gates.extend(("X", j) for j in zeros) gates.extend(compute) gates.extend(("CX", f, t) for t in targets) gates.extend(reversed(compute)) gates.extend(("X", j) for j in reversed(zeros))

assert len(gates) == 175 assert sum(g[0] == "X" for g in gates) == 50 assert sum(g[0] == "CX" for g in gates) == 41 assert sum(g[0] == "CCX" for g in gates) == 84

for gate in gates: wires = gate[1:] assert len(wires) == len(set(wires)) assert all(0 <= j < q for j in wires)

def apply_gate(state, gate): kind = gate[0] if kind == "X": return state ^ (1 << gate[1]) if kind == "CX": _, a, t = gate return state ^ ((((state >> a) & 1)) << t) if kind == "CCX": _, a, b, t = gate control = ((state >> a) & 1) & ((state >> b) & 1) return state ^ (control << t) raise ValueError("Unauthorized gate")

def run(value): state = value for gate in gates: state = apply_gate(state, gate) return state

def decode_output(state): mask = (1 << n)-1 return tuple( (state >> (ell + a*n)) & mask for a in range(n) )

def elementary_factor_list(value): assert value >= 2 result = [] divisor = 2 while value > 1: while value result.append(divisor) value //= divisor divisor += 1 return result

for value in range(16): final = run(value) assert (final & 15) == value assert ((final >> u) & 7) == 0

factors = elementary_factor_list(value) if value >= 2 else [] expected = tuple(factors + [0]*(n-len(factors))) assert decode_output(final) == expected

assert q == 16391 assert run(12) == sum(1 << j for j in (2,3,5,133,260,261))

def P(t): return (t+128)**2 + 512

assert P(4) == 17936 assert len(gates) <= P(4) assert q <= P(4)

The loop in elementary_factor_list is used only to independently check sixteen finite inputs. It is not claimed to be polynomial-time factoring in the bit length of arbitrary integers.