Oracle query algorithms

oracq.algorithms.basics.oracle_algorithms

Deutsch–Jozsa, Bernstein–Vazirani, and Simon query algorithms.

oracq.algorithms.basics.oracle_algorithms.deutsch_jozsa(function)

Generate the D-J query circuit; the caller asserts the function is constant or balanced.

Parameters:

function – An XOR database with one-bit results, satisfying the constant or balanced promise.

Returns:

Query circuit with registers input and answer; read out input to decide constant versus balanced.

Return type:

Operation

oracq.algorithms.basics.oracle_algorithms.bernstein_vazirani(function)

Generate the Bernstein–Vazirani secret string readout circuit.

Parameters:

function – An XOR database with one-bit results; the caller guarantees f(x)=s·x XOR c.

Returns:

Exposes input and answer. When the input promise holds, reading input yields s.

Return type:

Operation

The oracle may stay as an open declaration, with a gate or QRAM implementation bound later.

oracq.algorithms.basics.oracle_algorithms.affine_boolean_oracle(width, secret, *, bias=0)

Build a plain gate oracle for BV; bit i of secret corresponds to bit i of the address.

Parameters:

• width – Address register bit width, in 1..64.

• secret – Integer encoding of the secret string, in 0..2^width−1.

• bias – Constant bias c, either 0 or 1.

Returns:

Gate-level XOR database handle implementing f(x)=s·x XOR c.

Return type:

XorDatabase

oracq.algorithms.basics.oracle_algorithms.simon_sample(function)

Generate one Simon sampling circuit.

Parameters:

function – An XOR database; the caller guarantees a two-to-one map with a nonzero XOR period.

Returns:

Exposes input and output. Reading input alone yields an orthogonality constraint on the period.

Return type:

Operation

The output register need not be measured inside the circuit; elimination over repeated samples happens on the classical side.

oracq.algorithms.basics.oracle_algorithms.simon_nullspace(samples, width)

Compute the GF(2) null space of the Simon sample constraints.

Parameters:

• samples – Integer samples encoded in little endian.

• width – Bit width of the secret string.

Returns:

Null space basis vectors. Only a one-dimensional null space determines the nonzero period directly; with insufficient samples several basis vectors remain.

Return type:

tuple