Boolean Networks

English · 简体中文

Category C1 · Module oracq.algorithms.common.arithmetic · Stage V1

Overview

Boolean networks are the intermediate representation of reversible arithmetic: a sequential, acyclic SSA graph whose nodes are constants (numbered 0/1), input bits, and immutable Boolean values (not / xor / and); algorithms are described on the graph as classical combinational logic (bitwise addition, shift-and-accumulate multiplication, restoring division, bitwise square root, etc.), then compiled uniformly into reversible circuits in compute/XOR/uncompute form, or the same graph generates a native C++ operator. Fixed-point arithmetic, the mathfunc fixed-point lowering, and applications such as Roe / QFVM / QHAM all use it as their arithmetic foundation.

Interface and input model

BooleanNetwork()
net.operation(name=None, *, attributes=None)
BooleanNetwork.from_payload(value)
arithmetic_native_registry(program, *, cache_dir="out/native-cache")

API entry points: BooleanNetwork, arithmetic_native_registry

The graph-construction API of BooleanNetwork (excerpt; all return node numbers or bit lists):

Method

Meaning

input(name, width) / const(value, width) / resize(bits, width)

declare input bits, constants, and bit-width adjustment

inv / xor / and_ / or_ / any

basic Boolean algebra (including simplifications such as \(a \oplus a = 0\) and canonicalized deduplication)

mux(select, yes, no)

bitwise selection

add / neg / sub / lt / abs / mul / div / sqrt

bitwise combinational arithmetic

evaluate(**inputs)

classical evaluation of the graph (integer inputs; integer values of each output port)

payload() / from_payload(value)

JSON serialization and strictly validated deserialization

net.operation() returns an Operation whose registers are all input and output ports (the bit widths are the port widths), and writes the attributes arithmetic_network (payload JSON), correctness = "pending", and workspace_contract = "zero_in_zero_out"; the module name defaults to a payload-hash prefix. arithmetic_native_registry scans the program for modules carrying the arithmetic_network attribute and raises ValidationError when the ports disagree with the payload.

Implementation notes

The compilation strategy is “compute–copy–uncompute”: every non-constant, non-input node is allocated a private bank of width 64 (ssa_0, ssa_1, …); not/xor are realized with X gates and XOR copies, and with a controlled X, written into the banks node by node; then the output bits are XOR-copied into the public output registers; finally the previously emitted frames are uncomputed as a whole by taking an Adjoint over all banks, satisfying the zero-in-zero-out contract so that callers need not manage dirty workspaces. On the graph-construction side, node implementations are hash-consed with tuple keys: xor/and_ canonically sort their operands, and together with algebraic simplification (constant absorption, not(not a) = a) identical subexpressions share a single node.

from_payload validates the network as untrusted input: constant prefixes, port naming, bit widths 1..64, bit-reference ranges, the sequential DAG property, and input-port mapping consistency; any violation raises ValidationError. On the native route, BooleanCppFactory generates a real PySparQ C++ operator for the same graph: compilation artifacts are cached per the actual layout at the call site (start/width of cross-register views), and the code evaluates node values into a v[] array and XOR-writes back to the output registers, consistent with gate-level circuit semantics.

Validation approach

Category C1 (exact discrete semantics; acceptance criteria in ../development/validation-plan.md §2): the compiled circuit must equal classical evaluation of the graph pointwise. Three layers of evidence:

  • Structure: tests/core/test_stage2.py:Stage2StructureTests — test_arithmetic_construction_and_basis checks, for the network modules generated by all 14 arithmetic kind values, that a private workspace exists, the program JSON round-trips equal, and the Toffoli/U3/CZ basis export contains only the three basis gates and no controlled_by.

  • Numerical: Stage2StructureTests.test_gate_network_is_executable_small_example — the arithmetic_network payload of the add module is restored via from_payload and evaluates evaluate(a=1, b=2) == {"out": 3, "status": 0}, and on the simulator the amplitudes of the same program are exactly concentrated on the corresponding basis state (the circuit cross-checked against classical evaluation).

  • Binding: this mechanism has no separate binding witness (matrix criterion is —). The native execution path is covered by tests/integration/test_stage2_native.py:Stage2NativeTests.test_compiled_arithmetic_views_controls_and_adjoint (native operator amplitudes equal to the reference simulator on real PySparQ, cross-register views + controlled + adjoint scenarios, native_calls = 2) and test_native_module_private_workspace (private workspace uncomputed through an adjoint call), as L4 smoke.

Known gaps and planned stages

No known gaps (the gap column of the validation matrix is —); stage V1.

Numerical validation

Paper-grade numerical validation scripts: tests/verification/verify_oracles.py (dj-boolean-network-* cases), output out/verification/oracles.json.

Experimental design: the compiled products of a BooleanNetwork are used as the oracle of a query algorithm, checking end to end that “compiled circuit ≡ classical evaluation of the graph”. Two 3-bit networks — parity3 (a balanced function built from xor nodes) and const3 (the constant 1) — are compiled via operation() and wrapped as an XOR database interface (address/data, output with XOR-copy semantics, private banks uncomputed by the adjoint frame): first, with address/data in full superposition, one run each on rir-pysparq and originir-ext, cross-checked amplitude by amplitude on all 16 branches against the truth table generated pointwise by net.evaluate; then the circuit is plugged into Deutsch–Jozsa for the constant/balanced decision.

Case

Scale

Path

Metric value

dj-boolean-network-parity3

3 bit balanced, 16 branches

rir-pysparq, originir-ext

max_error = 8.3e-17, p_zero_error = 0.0

dj-boolean-network-const3

3 bit constant, 16 branches

rir-pysparq, originir-ext

max_error = 8.3e-17, p_zero_error = 1.1e-15

Reproduction command:

PYTHONPATH=src /path/to/backend/python tests/verification/verify_oracles.py

Output path: out/verification/oracles.json.