DQI decoding quantum interference optimization

oracq.algorithms.optimization.dqi

GF(2) max-XORSAT generator for DQI (Decoded Quantum Interferometry).

Implements the circuit skeleton of Jordan et al. 2024 (arXiv:2408.08292, figure 4): prepare a Dicke state of weight l on the m-bit error register, apply the right-hand-side phase (-1)**(v.y), reversibly compute B^T y into the n-bit syndrome register, then unload the error register back to |0> with a reversible classical decoder, and finally apply the Hadamard transform to the syndrome register and measure. The decoder is part of the input model and plugs in through the three-layer paradigm of open declaration (abstract) plus batched binding (bind).

Only GF(2) is supported for now: the GF(q) case needs a q-ary discrete Fourier transform and generalized Dicke states, and the register would additionally have to be organized into subregisters of log2(q) bits, left as future work. Keeping the branches where the error register is zero after measurement (postselection) is up to the caller.

class oracq.algorithms.optimization.dqi.XorSatInstance(rows, rhs, num_variables)

Bases: object

GF(2) max-XORSAT instance: a sparse row representation of the constraint system Bx = v.

rows holds one constraint per row, listing the variable indices that take part in that constraint, with no repetition inside a row; rhs is the right-hand side v, of the same length as the number of rows and valued 0 or 1; num_variables is the number of variables n, also the bit width of the syndrome register.

rows

rhs

num_variables

property num_constraints

Number of constraints m, i.e. the bit width of the error register.

satisfied_count(assignment)

Count the constraints satisfied by a given integer assignment.

Parameters:

assignment – Integer encoding of the assignment, in 0..2^number of variables−1, with bit j holding the value of variable j.

Returns:

Number of constraints satisfied by that assignment.

Return type:

int

class oracq.algorithms.optimization.dqi.DecoderOracle(operation)

Bases: OracleView

Reversible form of a syndrome decoder, the key open input of DQI.

The semantics are |syndrome, error> -> |syndrome, error XOR D(syndrome)>, where D is the classical decoding function (for example a reversible implementation of belief propagation). Undecodable syndromes may map to arbitrary error patterns; the corresponding branches are eliminated by postselection.

oracle_kind = 'reversible_function'

operation

decoder()

Decoder role accessor, returns itself; consistent with the role methods of other OracleView classes.

Returns:

A reference to itself, keeping the role accessor interface uniform.

Return type:

DecoderOracle

property syndrome_width

Bit width of the syndrome register, read directly from the RIR register signature.

property error_width

Bit width of the error register, read directly from the RIR register signature.

oracq.algorithms.optimization.dqi.abstract_decoder(name, syndrome_width, error_width)

Declare a decoder slot; efficient classical decoding algorithms are bound in batches via bind.

Parameters:

• name – Declared module name of the decoder slot.

• syndrome_width – Bit width of the syndrome register, in 1..64.

• error_width – Bit width of the error register, in 1..64.

Returns:

Handle of the decoder slot with an empty body, whose implementation is bound later by bind.

Return type:

DecoderOracle

oracq.algorithms.optimization.dqi.table_decoder(syndrome_width, error_width, table, *, name=None)

A gate witness implementing the decoder with an explicit lookup table; only the syndromes listed in the table are decoded.

Parameters:

• syndrome_width – Bit width of the syndrome register, i.e. the instance’s variable count n.

• error_width – Bit width of the error register, i.e. the instance’s constraint count m.

• table – Map from syndrome integer values to error pattern integer values.

• name – Optional module name.

Returns:

Syndromes not listed map to the zero error pattern.

Return type:

DecoderOracle

oracq.algorithms.optimization.dqi.bruteforce_decoder(instance, *, max_weight=None, name=None)

Bruteforce minimum-weight decoder: gives each syndrome the lightest error of weight at most max_weight.

Enumerates all 2**m error patterns and only accepts small instances with m <= 16; larger instances should bind a reversible implementation of an efficient decoder. On equal-weight ties the error pattern that comes first in enumeration order is kept.

Parameters:

• instance – The XOR instance being decoded, with at most 16 constraints.

• max_weight – Weight cap for error patterns, in 0..constraint count; defaults to the constraint count.

• name – Optional name of the generated module.

Returns:

An explicit lookup-table decoder mapping each syndrome to the lightest error pattern.

Return type:

DecoderOracle

oracq.algorithms.optimization.dqi.dicke_state(m, weight)

Prepare the m-bit Dicke state |D_l^m> of weight weight.

Built by multi-way rotations from explicit amplitudes and only accepts small sizes with m <= 16; large-scale preparation needs dedicated Dicke state circuits (such as the O(l*m) construction of Bartschi-Eidenbenz), which can be attached separately as a state_prep_isometry open declaration.

Parameters:

• m – Number of target bits, in 1..16.

• weight – Hamming weight, in 0..m.

Returns:

A zero-input preparation whose target width is m.

Return type:

StatePreparation

oracq.algorithms.optimization.dqi.dqi(instance, decoder, *, weight)

Assemble the main DQI circuit (GF(2), the single-weight version of figure 4 in the paper).

Parameters:

• instance – XorSatInstance; the constraint count m and variable count n determine the register widths.

• decoder – DecoderOracle whose interface widths must match the instance’s n and m; it may be an abstract declaration.

• weight – Dicke state weight l, in 0..m; meaningful only when the decoding radius covers this weight.

Returns:

Registers error(m) and syndrome(n). Starting from the all-zero state, error returns to |0> on the branches where decoding succeeds, and after the Hadamard transform syndrome measures assignment x with probability proportional to K_l(u(x))**2, where u(x) is the number of unsatisfied constraints and K_l is the Krawtchouk polynomial. Postselecting on zero error is up to the caller.

Return type:

Operation