Oracle declarations and implementations¶

oracq.algorithms.input_model.oracles

Catalog of oracle paradigms and plain gate/QRAM implementations. Mathematical correctness certification is out of scope for this module.

oracq.algorithms.input_model.oracles.PARADIGMS = {'algorithm_stage': 'an unfinished algorithm stage with an explicit register interface', 'block_encoding': 'combined convention of the zero-signal projected-angle block and be_alpha', 'database_xor': '|address,data> -> |address,data XOR memory[address]>', 'phase_oracle': 'applies a phase to target basis states per a defined predicate', 'reversible_function': 'domain computation interface with inputs preserved and outputs reversibly updated', 'sparse_entry_xor': 'CKS P_A(2): |row,column,data> -> |row,column,data XOR A[row,column]>', 'sparse_location_inplace': 'CKS P_A(1): |column,index> -> |column,nu(column,index)>', 'state_prep_isometry': 'prepares the target state from the zero-state subspace; adjoint and controlled use requires a reversible extension', 'unitary': 'quantum operation interface over the full register space'}¶: Built-in oracle role conventions; applications may use custom identifiers without modifying this catalog.

oracq.algorithms.input_model.oracles.declare(name, registers, *, paradigm='unitary', resources=None, attributes=None, supports_adjoint=True, supports_controlled=True)[source]¶

Declare an open oracle operation.

Generates an Operation with an empty body and implementation_status set to unresolved; the structure is validated at generation time, and the implementation can be closed via annotate or binding.

Parameters:

name – Module name.
registers – Ordered mapping from register names to types such as Bits.
paradigm – Built-in or application-defined role identifier; the role name itself proves no mathematical property.
resources – Mapping from resource names to resource types such as QRAM.
attributes – Extra attributes merged into the module.
supports_adjoint – Whether to declare support for the adjoint operation.
supports_controlled – Whether to declare support for the controlled operation.

Returns:

The unresolved open declaration.

Return type:

Operation

Raises:

ValidationError – The paradigm name is invalid, or the generated module fails structural validation.

oracq.algorithms.input_model.oracles.annotate(operation, paradigm, **attributes)[source]¶

Sets implementation_status to constructed and writes oracle_paradigm; adjoint/controlled capabilities explicitly restricted to False cannot be re-granted through annotation. When the paradigm is state_prep_isometry, the zero_input and clean_work promises are added by default.

Parameters:

operation – The generated Operation.
paradigm – Built-in or application-defined role identifier.
**attributes – Additional key-value pairs merged into the module attributes.

Returns:

A new Operation with the attributes replaced.

Return type:

Operation

Raises:

ValidationError – The input type or paradigm name is invalid, or a restricted capability is being restored.

oracq.algorithms.input_model.oracles.resources_for(*items)[source]¶

Aggregate the resources of several operations and rename them as prefix__resource_name.

Parameters:: *items – Pairs of the form (prefix, operation), where operation is an Operation carrying resource declarations.
Returns:: Mapping from prefix__resource_name keys to resource types, for the nested Builder to declare resources.
Return type:: dict

oracq.algorithms.input_model.oracles.invoke(builder, operation, prefix='', **arguments)[source]¶

Invoke an operation in a builder with a prefixed resource mapping.

Parameters:

builder – The current Builder, whose resources must already be declared under the same prefix.
operation – The Operation to invoke.
prefix – Resource name prefix; an empty string passes resource names through unchanged.
**arguments – Bindings from the invoked module’s register names to argument views.

Raises:

ValidationError – A register or resource argument name does not match the invoked module, or a dependency definition conflicts.

class oracq.algorithms.input_model.oracles.XorDatabase(operation)[source]¶

Bases: OracleView

XOR database view: |address,data> -> |address,data XOR memory[address]>.

Reversible quantum access interface for a classical lookup table; the wrapped Operation contains exactly the two bits registers address and data, and the XOR semantics is self-inverse under any initial value.

Variables:: operation (oracq.infrastructure.builder.Operation) – The wrapped Operation.

oracle_kind = 'database_xor'¶

operation¶

xor_database()[source]¶

Return self; the view adapter method implementing XorDatabaseProtocol.

Returns:: This view itself.
Return type:: XorDatabase

property address_width¶: Bit width of the address register.

property data_width¶: Bit width of the data register.

class oracq.algorithms.input_model.oracles.StatePreparation(operation)[source]¶

Bases: OracleView

Zero-input state preparation view: an isometry acting from the zero-state subspace.

The convention is V|0,0> = |psi,0>, i.e. the work register is restored to zero; the adjoint and controlled operations require a reversible extension to exist. The wrapped Operation contains exactly the two bits registers target and work.

Variables:: operation (oracq.infrastructure.builder.Operation) – The wrapped Operation.

oracle_kind = 'state_prep_isometry'¶

operation¶

state_preparation()[source]¶

Return self; the view adapter method implementing StatePreparationProtocol.

Returns:: This view itself.
Return type:: StatePreparation

classmethod from_unitary(operation, *, target=None, work=None, clean_work=False)[source]¶

Explicitly assign the U|0> zero-input role; with a work register, the caller promises it is restored to zero.

Parameters:

operation – The full-unitary Operation.
target – Name of the register carrying the state preparation; by default all registers are concatenated into target.
work – Work register name; may only be given when target is given explicitly.
clean_work – Must be True when work has nonzero width, promising that work is restored to zero after preparation.

Returns:

The preparation view wrapping the operation in the zero-input role.

Return type:

StatePreparation

property width¶: Bit width of the target register.

property work_width¶: Bit width of the work register.

class oracq.algorithms.input_model.oracles.StateOracle(operation)[source]¶

Bases: OracleView

State output view: the success subspace is defined by signal being all zeros.

The output carrier for algorithm stages such as solver kernels; the wrapped Operation contains exactly the two bits registers target and signal, and reading the signal == 0 branch yields the target state.

Variables:: operation (oracq.infrastructure.builder.Operation) – The wrapped Operation.

oracle_kind = 'state_oracle'¶

operation¶

state_oracle()[source]¶

Return self; the view adapter method implementing StateOracleProtocol.

Returns:: This view itself.
Return type:: StateOracle

property width¶: Bit width of the target register.

property signal_qubits¶: Bit width of the signal register.

class oracq.algorithms.input_model.oracles.SparseAccess(location, entry, width, value_width, sparsity)[source]¶

Bases: OracleView

Bundle view of CKS sparse access: a composition of the position and entry query operations, not disguised as a total unitary.

Variables:

location (oracq.infrastructure.builder.Operation) – Position operation P_A(1), permuting index in place, with signature column, index, work.
entry (oracq.infrastructure.builder.Operation) – Entry operation P_A(2), queryable at any row and column, with signature row, column, data.
width (int) – Number of bits of the matrix dimension, range 1..64.
value_width (int) – Word width of an entry value, range 1..64.
sparsity (int) – Upper bound on nonzeros per column, range 1..2**width.

location¶

entry¶

width¶

value_width¶

sparsity¶

sparse_access()[source]¶

Return self; the view adapter method implementing CKSSparseProtocol.

Returns:: This view itself.
Return type:: SparseAccess

describe()[source]¶

Aggregate the two components into a read-only description of the whole bundle.

The type is cks_sparse and anc_qubit is always None; the adjoint and controlled capabilities are the conjunction of the two components, the bundle is marked closed only when every component is closed, and the sparsity and value_width parameters are attached.

Returns:: Description of the whole bundle, with components named position and entry.
Return type:: OracleSpec

oracq.algorithms.input_model.oracles.abstract_database(name, address_width, data_width)[source]¶

Return an open XOR database declaration with no bound implementation.

Parameters:

name – Declaration name.
address_width – Bit width of the address register.
data_width – Bit width of the data register.

Returns:

An open declaration with an empty body, closed by binding an implementation.

Return type:

XorDatabase

oracq.algorithms.input_model.oracles.abstract_state_prep(name, width, work_width=0, *, reversible=True)[source]¶

Return an open state preparation declaration with no bound implementation.

Parameters:

name – Declaration name.
width – Bit width of the target register.
work_width – Bit width of the work register, zero by default.
reversible – When False, declare no support for adjoint or controlled.

Returns:

An open declaration carrying the zero_input and clean_work promises.

Return type:

StatePreparation

oracq.algorithms.input_model.oracles.abstract_block_encoding(name, width, signal_width, alpha)[source]¶

Return an open block encoding declaration with no bound implementation.

Parameters:

name – Declaration name.
width – Bit width of the target register.
signal_width – Bit width of the signal register.
alpha – Normalization constant, written into the be_alpha attribute.

Returns:

An open declaration with an empty body.

Return type:

BlockEncoding

oracq.algorithms.input_model.oracles.abstract_sparse_access(name, width, value_width, sparsity, work_width=None)[source]¶

Return an open sparse-access bundle with no bound implementation.

Generates the two open operations name_position and name_entry; the position operation carries the sparsity and full permutation extension attributes.

Parameters:

name – Declaration name prefix.
width – Number of bits of the matrix dimension.
value_width – Word width of an entry value.
sparsity – Upper bound on nonzeros per column, at most 2**width.
work_width – work bit width of the position operation, defaults to width.

Returns:

A bundle of the two open declarations for position and entry.

Return type:

SparseAccess

Raises:

ValidationError – sparsity exceeds the dimension.

oracq.algorithms.input_model.oracles.gate_database(address_width, data_width, table, *, name=None)[source]¶

Implement an XOR database with a gate-level truth table.

Nonzero table words apply X gates bit by bit under address control; the gate count grows with the table size, suitable as a small-instance witness.

Parameters:

address_width – Bit width of the address register.
data_width – Bit width of the data register.
table – Mapping from addresses to words, or a word sequence enumerated by address.
name – Module name; generated deterministically from the content by default.

Returns:

Gate-level implementation annotated implementation="gate_truth_table".

Return type:

XorDatabase

Raises:

ValidationError – A table entry is not an integer, or an address or word exceeds its bit-width range.

oracq.algorithms.input_model.oracles.qram_database(address_width, data_width, *, name=None)[source]¶

Implement an XOR database with a QRAM resource.

Declares a QRAM(address_width, data_width) resource named table and emits one query primitive; the data table is supplied at execution time as a memory and never enters the IR.

Parameters:

address_width – Bit width of the address register.
data_width – Bit width of the data register.
name – Module name; generated from the bit widths by default.

Returns:

Resource-based implementation annotated implementation="qram".

Return type:

XorDatabase

oracq.algorithms.input_model.oracles.basis_state(width, value=0, *, work_width=0)[source]¶

Prepare the computational basis state |value> with bit-by-bit X gates.

Parameters:

width – Bit width of the target register.
value – Integer index of the target basis state, range 0 .. 2**width - 1.
work_width – Bit width of the work register, zero by default.

Returns:

Gate-level preparation carrying the zero_input promise.

Return type:

StatePreparation

Raises:

ValidationError – value is not an integer or is out of range.

oracq.algorithms.input_model.oracles.uniform_state(width, *, work_width=0)[source]¶

Apply Hadamard to the whole target to prepare the uniform superposition state.

Parameters:

width – Bit width of the target register.
work_width – Bit width of the work register, zero by default.

Returns:

Gate-level preparation carrying the zero_input promise.

Return type:

StatePreparation

oracq.algorithms.input_model.oracles.gate_state_prep(amplitudes, *, work_width=0, name=None)[source]¶

Prepare an arbitrary complex-amplitude state with a multiplexed Ry rotation tree.

The amplitudes decompose over a binary tree into controlled Ry angles, and nonzero phase components are compensated pointwise by a controlled global_phase, so amplitudes may be complex.

Parameters:

amplitudes – Finite complex amplitude sequence of power-of-two length with nonzero norm.
work_width – Bit width of the work register, zero by default.
name – Module name; generated deterministically from the amplitude content by default.

Returns:

Gate-level preparation annotated implementation="multiplexed_rotations".

Return type:

StatePreparation

Raises:

ValidationError – The amplitude vector is invalid, or there is a single amplitude and no target bit.

oracq.algorithms.input_model.oracles.qram_state_prep(width, angle_width=8)[source]¶

Implement rotation-tree state preparation with a QRAM angle table.

Layer by layer, the high-bit prefix of target is swapped into the address and the angle table is queried; controlled Ry rotations are applied according to the bits of the angle word and the address is then restored to zero, with two queries per layer; the angle resolution 2*pi/2**angle_width is the source of the quantization error.

Parameters:

width – Bit width of the target register.
angle_width – Bit width of the angle word.

Returns:

Resource-based preparation annotated implementation="qram_rotation_tree"; work is max(1, width) + angle_width bits, with qram_queries attached as an attribute.

Return type:

StatePreparation

oracq.algorithms.input_model.oracles.qram_state_angles(amplitudes, angle_width=8)[source]¶

Generate the QRAM rotation-tree angle table from an amplitude vector.

Keys are tree node indices of the form (1 << depth) - 1 + prefix and values are Ry angle words quantized to the 2*pi/2**angle_width grid, supplied at execution time as the angle-table memory.

Parameters:

amplitudes – Nonnegative real amplitude sequence of power-of-two length with nonzero norm.
angle_width – Bit width of the angle word.

Returns:

Mapping from tree node indices to angle words.

Return type:

dict

Raises:

ValidationError – The amplitude vector is invalid, or contains amplitudes with negative real part or nonzero imaginary part.

oracq.algorithms.input_model.oracles.phase_marks(width, marked)[source]¶

Generate a phase oracle applying phase pi to the given computational basis states.

Parameters:

width – Bit width of the target register.
marked – Iterable of integer indices of basis states to mark; duplicates are removed automatically.

Returns:

Operation annotated with the phase_oracle paradigm.

Return type:

Operation

oracq.algorithms.input_model.oracles.sparse_location_gate(width, permutations, *, work_width=None, name=None)[source]¶

Implement the CKS in-place position query with a gate-level permutation network.

Each column decomposes its permutation into transpositions by cycle under column control, and each transposition becomes a round-trip path of controlled X; the gate count grows with 2**width, suitable only as a small-instance witness.

Parameters:

width – Bit width of the column and index registers.
permutations – 2**width permutations given per column, each a complete arrangement of 0 .. 2**width - 1.
work_width – Bit width of the work register, defaults to width.
name – Module name; generated deterministically from the content by default.

Returns:

Operation annotated with the sparse_location_inplace paradigm and the full permutation extension attribute.

Return type:

Operation

Raises:

ValidationError – The number of columns is not 2**width, or some column is not a complete permutation.

oracq.algorithms.input_model.oracles.sparse_location_qram(width)[source]¶

Implement the CKS in-place position query with a forward and an inverse QRAM table.

Done in three steps: work ^= forward[column, index], swap(index, work), work ^= inverse[column, index]; the last step restores work to zero while index holds the new value.

Parameters:: width – Bit width of the column, index, and work registers.
Returns:: Operation annotated with the sparse_location_inplace
Return type:: Operation

paradigm, declaring the two QRAM(2*width, width) resources forward and inverse.

oracq.algorithms.input_model.oracles.sparse_entry(database, width)[source]¶

Adapt an XOR database into a matrix entry query at any row and column.

row and column concatenate into a 2*width-bit address driving the database, and data holds the XOR result.

Parameters:

database – An XOR database whose address_width is exactly 2*width.
width – Bit width of rows and columns respectively.

Returns:

Entry query operation annotated with the sparse_entry_xor paradigm.

Return type:

Operation

Raises:

ValidationError – The database address width is not 2*width.

oracq.algorithms.input_model.oracles.diagonal_block_encoding(database, *, alpha=1.0, angle_scale=None)[source]¶

Control a signal Ry by the queried word, encoding the diagonal matrix determined by that angle table.

Parameters:

database – XOR database storing rotation angle words, with address driving target.
alpha – Block encoding normalization constant.
angle_scale – Angle step of bit k of the data word; defaults to 2π/2**data_width.

Returns:

Block encoding whose diagonal entries are alpha*cos(encoded_angle/2).

Return type:

BlockEncoding

oracq.algorithms.input_model.oracles.banked_database(address_width, data_width, *, name='BankedData', abstract=False)[source]¶

Split a wide data word into registers and QRAM banks of at most 64 bits each.

Parameters:

address_width – Bit width of the address word.
data_width – Total bit width of the logical data word, which must be a positive integer.
name – Name of the generated operation, BankedData by default.
abstract – When True, generate an open declaration with an empty body instead of a QRAM implementation.

Returns:

Database operation split little-endian into banks of at most 64 bits each.

Return type:

Operation