KP 量子推荐系统

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.

参数:

• 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.

返回:

Singular value estimate σ̂.

返回类型:

float

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

基类：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)

基类：object

KP recommendation sampling circuit and its readout contract.

变量:

• 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.

返回:

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.

返回类型:

dict

readout(state)

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

参数:

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

返回:

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

返回类型:

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.

参数:

• 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.

返回:

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

返回类型:

RecommendationResult