Reversible arithmetic

oracq.algorithms.common.arithmetic

Reversible fixed-point arithmetic: Boolean SSA to compute/XOR/uncompute, plus native implementations of the same graph.

class oracq.algorithms.common.arithmetic.FixedFormat(width=8, fraction=3, signed=True)

Bases: object

Describes the fixed-point number format used by reversible arithmetic.

The low fraction bits of the width-bit word hold the fraction; when signed is True the most significant bit is the two’s-complement sign bit. Values and bit patterns are converted through encode and decode.

Variables:

• width (int) – Total bit width, including the sign bit if present; the valid range is 2..64.

• fraction (int) – Number of fraction bits, which must not occupy the sign bit.

• signed (bool) – Whether the most significant bit is a two’s-complement sign bit.

Raises:

ValidationError – width falls outside 2..64, or fraction occupies the sign bit.

width = 8

fraction = 3

signed = True

encode(value)

Encode a fixed-point value as a width-bit integer.

The value is first multiplied by 2**fraction and truncated toward zero, then masked to width bits.

Parameters:

value – The fixed-point value to encode.

Returns:

The integer bit pattern after wrapping modulo 2**width.

Return type:

int

decode(value)

Decode a width-bit integer bit pattern back to a fixed-point value.

Parameters:

value – The integer bit pattern; higher bits beyond the word width are masked off first.

Returns:

The value after interpreting the sign bit as two’s complement in the signed format, then dividing by 2**fraction.

Return type:

float

class oracq.algorithms.common.arithmetic.BooleanNetwork

Bases: object

0/1 are constants; every other index is an input or an immutable Boolean value.

nodes

cache

inputs

outputs

node(key)

Return the node index for a key, creating a new node when absent.

Hash-consing on tuple keys: identical keys always return the same index.

Parameters:

key – Iterable key describing a constant, input, or operation.

Returns:

The node index of the key.

Return type:

int

input(name, width)

Declare an input port and register its per-bit nodes.

Parameters:

• name – Port name.

• width – Port bit width.

Returns:

List of node indices, indexed by bit position, least significant bit first.

Return type:

list

inv(a)

Invert a node, with constant folding and double-negation simplification.

Parameters:

a – Node index.

Returns:

Node index of the inverted result.

Return type:

int

xor(a, b)

XOR two nodes, with the constant identity and a xor a = 0 simplifications.

Parameters:

• a – Node index.

• b – Node index.

Returns:

Node index of the XOR result.

Return type:

int

and_(a, b)

Bitwise AND of two nodes, with constant absorption and idempotence simplifications.

Parameters:

• a – Node index.

• b – Node index.

Returns:

Node index of the AND result.

Return type:

int

or_(a, b)

Bitwise OR of two nodes, composed through xor and and_.

Parameters:

• a – Node index.

• b – Node index.

Returns:

Node index of the OR result.

Return type:

int

any(bits)

Reduce a group of nodes to their bitwise OR.

Parameters:

bits – Iterable of node indices.

Returns:

Node index of the reduced result; an empty input yields constant 0.

Return type:

int

mux(select, yes, no)

Select bit by bit between two equal-width signals according to a select bit.

Parameters:

• select – Node index of the select bit.

• yes – Bit list to output when the select bit is 1.

• no – Bit list to output when the select bit is 0; must match the width of yes.

Returns:

Node indices of the bit-by-bit selection result.

Return type:

list

static const(value, width)

Expand a nonnegative integer into a width-bit constant bit list.

Parameters:

• value – The nonnegative integer constant.

• width – Bit width.

Returns:

Each bit is 0 or 1, least significant bit first.

Return type:

list

static resize(bits, width)

Truncate a bit list or zero-pad its high end to the given width.

Parameters:

• bits – The original bit list.

• width – The target bit width.

Returns:

A new list whose length is exactly width.

Return type:

list

add(a, b, carry=0)

Ripple-carry addition.

Parameters:

• a – Bit list of one addend.

• b – Bit list of the other addend, the same width as a.

• carry – Node index of the initial carry entering the least significant bit.

Returns:

(result, carry), the bit-by-bit sum and the carry out of the most significant bit.

Return type:

tuple

neg(a)

Two’s-complement negation: invert every bit, then add one at the least significant bit.

Parameters:

a – Bit list of the operand.

Returns:

Bit list of -a.

Return type:

list

sub(a, b)

Subtraction, implemented as a + ~b + 1.

Parameters:

• a – Bit list of the minuend.

• b – Bit list of the subtrahend, the same width as a.

Returns:

Bit list of a - b.

Return type:

list

lt(a, b)

Unsigned comparison a < b.

Parameters:

• a – Bit list of the left operand.

• b – Bit list of the right operand, the same width as a.

Returns:

Node index of the comparison result, truth value 1.

Return type:

int

abs(a, signed)

Return the absolute value of the operand.

Parameters:

• a – Bit list of the operand.

• signed – When True, select between a and -a by the sign bit; when False, return a unchanged.

Returns:

Bit list of the absolute value.

Return type:

list

mul(a, b, width)

Shift-and-accumulate multiplication, with the product truncated to width bits.

Parameters:

• a – Bit list of the multiplicand.

• b – Bit list of the multiplier.

• width – Result bit width.

Returns:

Bit list of the low width bits of the product.

Return type:

list

div(a, b)

Restoring division, returning only the quotient.

The dividend bits are shifted into the partial remainder from the most significant end; whenever the remainder is at least the divisor, the divisor is subtracted and the quotient bit is set.

Parameters:

• a – Bit list of the dividend.

• b – Bit list of the divisor.

Returns:

Bit list of the quotient, with the same width as a; the remainder is discarded.

Return type:

list

sqrt(a)

Digit-by-digit restoring square root.

When the input has an odd number of bits, it is first zero-padded at the high end to an even count; the radicand bits then enter in two-bit groups from the high end.

Parameters:

a – Bit list of the radicand.

Returns:

Bit list of the square root, with half the padded input bit count.

Return type:

list

evaluate(**inputs)

Evaluate the whole network on the classical side.

Parameters:

**inputs – Mapping from port names to nonnegative integers, read bit by bit into the input ports.

Returns:

Each output port name mapped to its integer evaluation result.

Return type:

dict

payload()

Serialize the network into a compact JSON string.

Returns:

The payload containing nodes, inputs and output ports, usable as a cache key or module attribute.

Return type:

str

classmethod from_payload(value)

Rebuild a network from a JSON payload, validating the payload fully as untrusted input.

The validation covers the constant prefix, port naming and mutual exclusion, bit widths in 1..64, bit reference ranges, the sequential directed-acyclic property, and the consistency of the input port mapping.

Parameters:

value – The JSON string produced by payload.

Returns:

The network rebuilt after the validation passes.

Return type:

BooleanNetwork

Raises:

ValidationError – Any structural or consistency check of the payload fails.

operation(name=None, *, attributes=None)

Compile the network into a reversible quantum operation in compute/copy/uncompute form.

Every operation node is first computed forward into a private ssa_-prefixed bank grouped in 64-bit words (not and xor via X/XOR copies, and via a controlled X); after the output bits are XOR-copied into the public registers, the adjoint of the forward compute frame is emitted to clean all banks, satisfying the zero_in_zero_out workspace contract.

Parameters:

• name – Module name; when omitted, an arith_-prefixed name is generated from the hash of the network payload.

• attributes – Additional module attributes, which may override the built-in keys.

Returns:

The public registers are all input and output ports of the network.

Return type:

Operation

oracq.algorithms.common.arithmetic.DEFAULT_FIXED_FORMAT = FixedFormat(width=8, fraction=3, signed=True)

width=8, fraction=3, signed.

Type:

Default fixed-point format

oracq.algorithms.common.arithmetic.fixed_arithmetic(kind, fmt=FixedFormat(width=8, fraction=3, signed=True))

Outputs XOR; status[0] marks a domain failure and status[1] marks exceeding the word width, not a precision bound.

Parameters:

• kind – Arithmetic kind, one of add, sub, neg, abs, mul, div, reciprocal, sqrt, lt, eq, select, and, or or xor.

• fmt – Fixed-point format of the operands, bit width, fraction bits and signedness; defaults to the signed 8-bit format with 3 fraction bits.

Returns:

The reversible fixed-point arithmetic operation synthesized from the Boolean network, with output registers out and status(2).

Return type:

Operation

class oracq.algorithms.common.arithmetic.BooleanCppFactory(network, cache_dir)

Bases: object

Generates a real PySparQ C++ operator for the same Boolean graph; supports cross-register views.

network

cache_dir

classes

oracq.algorithms.common.arithmetic.arithmetic_native_registry(program, *, cache_dir='out/native-cache')

Build a native operator registry for the arithmetic modules in a program.

It scans modules carrying the arithmetic_network attribute, rebuilds the Boolean network from the attribute payload and registers a BooleanCppFactory. C++ compilation does not happen here: the PySparQ operator is compiled on demand, and cached, only when the factory is invoked with a concrete call layout.

Parameters:

• program – The program to scan.

• cache_dir – Cache directory for the C++ compilation artifacts.

Returns:

Registry mapping arithmetic modules to native implementations; the label is taken from the arithmetic_kind attribute, defaulting to the module name.

Return type:

NativeRegistry

Raises:

ValidationError – The module registers and the network ports mismatch in name or bit width.