# Boolean Networks

**English** · <a href="../../zh/manual/algorithms/boolean-networks.html">简体中文</a>

> Category C1 · Module [`oracq.algorithms.common.arithmetic`](../../api/algorithms/common/arithmetic.rst) · 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](fixed-point-arithmetic.md), the mathfunc fixed-point lowering, and applications such as Roe / QFVM / QHAM all use it as their arithmetic foundation.

## Interface and input model

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

API entry points: {obj}`BooleanNetwork <oracq.algorithms.common.arithmetic.BooleanNetwork>`, {obj}`arithmetic_native_registry <oracq.algorithms.common.arithmetic.arithmetic_native_registry>`

The graph-construction API of {obj}`BooleanNetwork <oracq.algorithms.common.arithmetic.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 {obj}`Operation <oracq.infrastructure.builder.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. {obj}`arithmetic_native_registry <oracq.algorithms.common.arithmetic.arithmetic_native_registry>` scans the program for modules carrying the `arithmetic_network` attribute and raises {obj}`ValidationError <oracq.infrastructure.ir.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 {obj}`Adjoint <oracq.infrastructure.ir.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, {obj}`BooleanCppFactory <oracq.algorithms.common.arithmetic.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.

## Related links

- Same module: [Fixed-point arithmetic](fixed-point-arithmetic.md)
- Source: `src/oracq/algorithms/common/arithmetic.py`
- API reference: [Reversible arithmetic](../../api/algorithms/common/arithmetic.rst)
- Validation matrix: [Validation coverage matrix](../../development/validation-coverage.md)

## 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](deutsch-jozsa.md) 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:

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

Output path: `out/verification/oracles.json`.