KP quantum recommendation system

oracq.algorithms.qml.recommendation

Kerenidis-Prakash quantum recommendation system (arXiv:1603.08675): QSVE plus threshold projection plus sampling.

The data plane is QMatrix’s sample-and-query structure (algorithms/qdata.py). Following Lemma 5.3 of the paper, build W = U·V with U = Ũ R₁ Ũ⁻¹ and V = Ṽ R₀ Ṽ⁻¹: Ũ maps (i, 0) to (i, the normalized vector of row i) via the row tree, Ṽ maps (0, j) to (the user distribution Ã, j) via the row-norm root tree, and R₀/R₁ are reflections about the zero basis states of the row/item registers. Phase estimation on W yields θ satisfying cos(θ_i/2) = σ_i/‖A‖_F; σ̂ is estimated per phase word and the flag is flipped by threshold (the deterministic projection version of §5.3 Alg 2), and after inverse phase estimation (flag, item) is measured: the item register distribution on the flag=1 branch is exactly the recommendation sampling distribution (§6).

oracq.algorithms.qml.recommendation.sigma_from_phase(value, precision, frobenius)

Phase readout t → singular value estimate σ̂ = ‖A‖_F times the absolute value of cos(π t/2^precision).

The eigenvalues of W come in pairs e^{±iθ} (the two rotation directions of the same σ), and the mirror phase 2^precision−t must map to the same singular value, hence the absolute value.

Parameters:

• value – Phase register readout, an integer in 0..2^precision−1.

• precision – Number of phase register bits.

• frobenius – Frobenius norm ‖A‖_F of the matrix.

Returns:

Singular value estimate σ̂.

Return type:

float

class oracq.algorithms.qml.recommendation.KPRecommendationConfig(precision=4, sigma=None)

Bases: object

precision is the number of phase register bits; sigma is the singular value threshold, defaulting to 0.5·‖A‖_F.

precision = 4

sigma = None

class oracq.algorithms.qml.recommendation.RecommendationResult(operation, matrix, user, precision, sigma, frobenius)

Bases: object

KP recommendation sampling circuit and its readout contract.

Variables:

• operation (oracq.infrastructure.builder.Operation) – Recommendation sampling circuit; registers row, item, phase, and flag, with QRAM resources row_angles and root_angles.

• matrix (oracq.algorithms.input_model.qdata.QMatrix) – The QMatrix input used to build the circuit.

• user (int) – Target user index.

• precision (int) – Number of phase register bits.

• sigma (float) – Singular value threshold actually applied; 0.5·frobenius when config leaves it unspecified.

• frobenius (float) – Frobenius norm of the matrix, used when decoding with sigma_from_phase.

operation

matrix

user

precision

sigma

frobenius

memories()

Extract the initial values of the two QRAM angle banks required by the circuit.

Returns:

Keys row_angles (the row tree) and root_angles (the row-norm root tree); values map addresses to angle words, for the execution entry point to bind the QRAM resources declared by the circuit.

Return type:

dict

readout(state)

Reduce a simulation or execution result to (success probability, conditional recommendation distribution).

Parameters:

state – Amplitude state obtained from register-level simulation or execution.

Returns:

The total probability of the flag=1 branch and the conditional recommendation distribution over items on that branch.

Return type:

tuple[float, dict[int, float]]

oracq.algorithms.qml.recommendation.kp_recommendation(matrix, user, config=None)

Generate the recommendation sampling circuit for user user; returns a RecommendationResult carrying the readout contract.

Parameters:

• matrix – Recommendation matrix input model with the sample-and-query structure.

• user – Target user index, in 0..number of rows − 1.

• config – Phase bit count and singular value threshold configuration; defaults to 4 phase bits and threshold 0.5·‖A‖_F.

Returns:

Result containing the recommendation sampling circuit, the initial QRAM angle bank values, and the readout contract.

Return type:

RecommendationResult