Quantum data structures (qsample and sample-and-query)

oracq.algorithms.input_model.qdata

KP/QFVM style quantum data structures: QVector (qsample) with a squared-norm tree, and the sample-and-query QMatrix.

QVector implements the data structure shared by Kerenidis-Prakash (arXiv:1603.08675 Thm 5.1 + Appendix A.1) and QFVM (arXiv:2102.03557 Eqs. 15–22): a binary tree whose leaves store squared components rolled up layer by layer, with internal nodes caching RY rotation angle words; the quantum side prepares the normalized state layer by layer, with two QRAM queries per layer. Signs are written through an independent 1-bit bank by phase kickback. On top of this, QMatrix implements sample-and-query access (arXiv:1704.04992 §I.1): the entries bank supports queries in arbitrary superposition, the row trees give Ũ|i⟩|0⟩→|i⟩|Ā_i⟩, and the row-norm root tree gives Ṽ|0⟩|j⟩→|Ã⟩|j⟩.

class oracq.algorithms.input_model.qdata.QVector(values, *, fmt=None, angle_width=8, name='qvec')

Bases: object

qsample vector: squared-norm binary tree + angle-word/sign banks, supporting O(log) classical local updates.

signs()

Sign bank content; when all signs are zero the signed preparation can be omitted.

Returns:

Mapping from indices to sign bits, containing only negative-component entries.

Return type:

dict[int, int]

update(index, value)

Single-point update: only the sums and angle words along the leaf-to-root path are recomputed; returns the changes to the angle word bank.

Parameters:

• index – Index of the component to update, range 0..2^width-1.

• value – New component value, which must be encodable by the fixed-point format.

Returns:

Changes to the angle word bank, keyed by the address, i.e. the tree node number minus one.

Return type:

dict[int, int]

property norm

the square root of the squared-norm tree root (computed from the fixed-point decoded values).

Type:

Euclidean norm of the vector

amplitudes()

Normalized expected amplitudes (including quantization and signs), as the classical reference.

Returns:

Amplitude table of length 2^width after division by the Euclidean norm.

Return type:

list[float]

snapshot(*, signed=False)

Export a snapshot of the QRAM bank contents, for simulate and the like to bind data by name.

Parameters:

signed – When True, attach the sign bank, containing only negative-component entries.

Returns:

Keys are {name}_angles (address is the tree node number minus one), plus the optional {name}_sign.

Return type:

dict

preparation(*, signed=False, name=None)

Layer-by-layer tree preparation addressed via QMem; when signed, the phase is written via Load→Z→inverse Load.

Parameters:

• signed – When True, attach the phase writing from the sign bank.

• name – Name of the generated operation; derived from the vector name and bit widths by default.

Returns:

View preparing the normalized state via layer-by-layer QRAM queries.

Return type:

StatePreparation

class oracq.algorithms.input_model.qdata.QMatrix(matrix, *, fmt=None, angle_width=8, name='qmat')

Bases: object

Sample-and-query matrix: entry query + row qsample Ũ + row-norm root tree Ṽ; entries are restricted to nonnegative values.

update(row, column, value)

Single-entry update: recompute the affected row tree and the root tree path; returns the changes to each bank.

Parameters:

• row – Row index of the entry to update, range 0..2^rows-1.

• column – Column index of the entry to update, range 0..2^cols-1.

• value – New entry value, which must lie within the nonnegative range of the fixed-point format.

Returns:

Changes to the three banks entries, row_angles and root_angles.

Return type:

dict[str, dict[int, int]]

property frobenius

the square root of the root tree root, i.e. the square root of the sum of squared entries.

Type:

Frobenius norm of the matrix

row_norm(index)

Return the Euclidean norm of row index (the square root of the row tree root).

Parameters:

index – Row index, range 0..2^rows-1.

Returns:

Square root of the sum of squared entries of that row.

Return type:

float

row_amplitudes(index)

Normalized expected amplitudes of row index (the reference ground truth for the row qsample).

Parameters:

index – Row index, range 0..2^rows-1.

Returns:

Amplitude table of that row after division by the row norm.

Return type:

list[float]

user_amplitudes()

Normalized expected amplitudes of the root tree (the reference ground truth for the user superposition prepared by Ṽ).

Returns:

The i-th entry is the ratio of the i-th row norm to the Frobenius norm.

Return type:

list[float]

snapshot()

Export a snapshot of the entries bank and the row/root angle banks.

Returns:

Keys are entries (row-major flattened addresses to fixed-point words), row_angles and root_angles.

Return type:

dict

query()

Entry XOR query: the word at address (row, column) is XORed into data, addressed by a two-dimensional pointer.

Returns:

Query view backed by the row-major flattened entries bank.

Return type:

XorDatabase

row_preparation()

Ũ: prepare the item register from the zero state into the normalized row vector of row i; the row trees are addressed two-dimensionally by (row, prefix).

Returns:

The unitary operation implementing Ũ.

Return type:

Operation

amplitude_preparation()

Ṽ: prepare the zero-state row register into the user distribution Ã, with the item register passed through.

Returns:

The unitary operation implementing Ṽ.

Return type:

Operation

row_state_prep(user)

One-dimensional tree preparation of the classical row user, with the row number folded into a constant address.

Parameters:

user – Classical row number, range 0..2^rows-1.

Returns:

1D tree preparation view of that row’s normalized row vector.

Return type:

StatePreparation