Source-linked AI summary
Quantum Recommendation Systems
Iordanis Kerenidis, Anupam Prakash
TL;DR
Recommendation systems must identify valuable products from incomplete user-preference data without incurring the cost of reconstructing a large matrix. The paper develops a quantum sampling-based algorithm that operates in O(poly(k)polylog(mn)) time. It provides good recommendations under the same good low-rank-approximation condition used by classical approaches, while avoiding explicit reconstruction.
Problem
Recommendation requires finding high-value preference-matrix elements, but classical reconstruction-based systems use resources polynomial in the matrix dimensions.
Method
The quantum algorithm samples efficiently from a low-rank projected approximation of a user’s preference row instead of reconstructing the entire matrix.
Results
O(poly(k)polylog(mn)) expected running time is achieved for at least (1−ξ)(1−δ−ζ)m users, with good recommendations produced with high probability.
Takeaways & Limitations
The algorithm provides a recommendation-system application with polylogarithmic dependence on matrix dimensions and no preprocessing or extra memory.
Takeaways & Limitations
Good recommendations are guaranteed only when the preference matrix has a good low-rank approximation, and low rank alone may not ensure quality for most users.
Abstract
from arXiv · showhide
A recommendation system uses the past purchases or ratings of $n$ products by a group of $m$ users, in order to provide personalized recommendations to individual users. The information is modeled as an $m \times n$ preference matrix which is assumed to have a good rank-$k$ approximation, for a small constant $k$. In this work, we present a quantum algorithm for recommendation systems that has running time $O(\text{poly}(k)\text{polylog}(mn))$. All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application.
1 Introduction
Recommendation systems use a user–product preference matrix to identify high-utility products without necessarily reconstructing the entire matrix. The paper presents a quantum approach that samples an approximation efficiently, achieving polylogarithmic dimension dependence under a low-rank assumption.
- Recommendation systems use observed purchases or ratings to suggest high-utility products to individual users.
- The low-rank assumption models users as belonging to a small number of preference types whose information can be aggregated.
- A good recommendation system needs a high-value matrix element, whereas matrix reconstruction produces an approximation of the entire matrix.
- Classical methods typically preprocess a low-rank approximation in poly(mn) time and use O(nk) memory and online time.
- Its recommendations have performance similar to classical matrix-reconstruction systems when the preference matrix has a good low-rank approximation.
- The algorithm requires polylogarithmic time in matrix dimensions and polynomial time in rank, with running time O(poly(k)polylog(mn)).
- The quantum algorithm samples from a projected approximation of each user’s preference row instead of explicitly computing the entire approximation matrix.
2 Preliminaries
The preliminaries define matrix and vector representations, singular-value-based projections, quantum state encoding, measurement, and phase estimation. These tools support sampling and spectral procedures used by the quantum recommendation algorithm.
- An m × n matrix can be sampled by selecting entries with probability proportional to their squared magnitudes.
- The singular value decomposition represents A as UΣV^t, with columns of U and V giving column and row singular vectors.
- The product A+A projects onto the row space of A, while truncation to the k largest singular values defines A_k.
- A vector x is encoded as a normalized quantum state whose standard-basis measurement probabilities are proportional to x_i^2.
- Phase estimation estimates eigenphases of a unitary operator with additive precision ǫ in time O(T(U) log n/ǫ).
3 A model for recommendation systems
The recommendation model represents binary good/bad product choices in a user–product matrix and samples from an approximation to generate recommendations. Frobenius-norm closeness supports good recommendations on average, but guarantees for most users require typical-user assumptions.
- Model: The preference matrix T has one row per user, one column per product, and binary entries indicating whether each product is a good recommendation.A pair (i, j) is good exactly when T_ij = 1; otherwise it is bad.
- Model: Binary recommendation matrices can represent thumbs-up/thumbs-down data or thresholded and top-ranked products from general ratings.Good recommendations may be defined by exceeding a preference threshold or belonging to a user’s top 100 products.
- Sampling: Sampling directly from T always gives a good recommendation because bad products have probability 0.The algorithm instead seeks to sample from an approximation that remains close enough to T.
- Sampling: Frobenius-norm closeness of an approximation to T bounds the bad-recommendation probability for an average user, weighted by the number of products they like.This weighting favors users with many good products over users who like almost nothing.
- User guarantees: Guaranteeing good recommendations for most equally weighted users requires assumptions that most users are typical and have near-average numbers of good products.Without such assumptions, a close approximation may serve heavy users well while performing poorly for most users.
- User guarantees: If 90% of users’ preferences lie between 1/1.1 and 1.1 times the average, the error for typical users increases by at most a factor of 1.5.Recommending several products can further improve the chance that at least one recommendation is good.
4 Matrix Sampling
Matrix sampling replaces full reconstruction with a sampled, rescaled matrix whose dominant singular structure approximates the original. The resulting thresholded projection can be sampled quantumly in time polylogarithmic in matrix dimensions and polynomial in k.
- Sampling construction: Each entry of A is sampled independently with probability p and rescaled to A_ij/p, producing a random matrix bA with expectation A.Unsampled entries are set to zero, and the approach assumes k and the Frobenius norm of A are known.
- Matrix reconstruction: Projecting bA onto its top k singular vectors yields an approximation whose error is not much larger than the best rank-k approximation error of A.This extends matrix reconstruction guarantees from sampled data without reconstructing every entry of A.
- Scope: The guarantees extend to other matrix reconstruction algorithms whenever they provide a comparable Frobenius-norm approximation guarantee.The analysis does not depend on how bA was generated beyond that guarantee.
- Threshold projection: If A has relative rank-k Frobenius error at most ǫ and sufficient norm, suitable parameters give ||A − bA_≥σ||_F ≤ 3ǫ||A||_F.The guarantee relies on the stated low-rank approximation and norm conditions.
- Threshold projection: A thresholded projection retains singular-vector components above σ and may include components in [(1−κ)σ, σ), with κ controlling the precision boundary.This family matches the projection produced by the quantum procedure.
- Threshold projection: Under the same low-rank condition, the extended thresholded projection satisfies ||A − bA_≥σ,κ||_F ≤ 9ǫ||A||_F with suitable parameters.The result accounts for the additional singular vectors near the threshold.
- Quantum recommendation procedure: Sampling recommendations reduces to sampling the relevant row of bT_≥σ,κ, the projection onto singular directions above σ and possibly near-threshold directions.The row corresponds to the target user’s recommendation distribution.
- Quantum recommendation procedure: The quantum procedure outputs a state representing that projected row, which can be sampled by computational-basis measurement in time polylogarithmic in matrix dimensions and polynomial in k.Its dimension dependence is polylogarithmic because σ is inverse-polynomial in k in this setting.
5 Quantum projections in polylogarithmic time
The quantum projection framework combines efficient row-state access with singular value estimation to project vectors onto thresholded singular-vector spaces in polylogarithmic matrix-dimension time. Its runtime depends on the threshold and rank-related parameters rather than the matrix condition number.
- Data access: A row-access data structure supports preparing |Ai⟩ and the row-norm state needed by the quantum procedure in polylog(mn) time.The structure stores row entries and supports the mappings eU and eV for rows and row norms.
- Singular value estimation: The matrices P and Q factor A through A/∥A∥F = P^tQ, with orthonormal columns and polylogarithmic-time multiplication mappings.The associated unitary W is implemented as a product of reflections in the column spaces of P and Q.
- Singular value estimation: Each row singular vector vi maps to an eigenvector Qvi of W, where cos(θi/2) = σi/∥A∥F.Phase estimation on W therefore provides singular-value estimates from the encoded eigenphases.
- Performance: The singular-value estimate has additive error ǫ∥A∥F and running time O(polylog(mn)/ǫ), with success probability at least 1 −1/poly(n).The projection runtime depends on the threshold σ rather than the condition number of A.
- Quantum projection with threshold: The projection algorithm uses quantum singular value estimation to project an input vector onto singular vectors whose values exceed a threshold.It outputs the corresponding projected quantum state, with an optional subset of singular vectors near the threshold.
- Performance: For recommendation-system parameters, the resulting quantum algorithm runs in polynomial time in k and polylogarithmic time in the matrix dimensions.The analysis also assumes the relevant input norm ratio is constant for most users.
6 Quantum recommendation systems
The recommendation algorithm applies quantum projection to a sampled preference matrix and a user row, then samples a product from the projected row. Under the low-rank and sampling conditions, it gives good recommendations for most users with poly(k)polylog(mn) expected time.
- Assumptions: The algorithm assumes ∥T −Tk∥F ≤ǫ∥T∥F for a small approximation parameter ǫ and small rank k.As in the classical approach, recommendation quality depends on the sampled matrix having a suitable low-rank approximation.
- Quantum recommendation algorithm: Algorithm 6.1 projects the sampled matrix row for user i onto singular vectors above a threshold, then measures the resulting state to select a product.The procedure uses the sampled matrix bT stored in the quantum-access data structure.
- Correctness: With probability at least 1 −1/poly(n), the projection procedure returns the state corresponding to the thresholded row bT≥σ,κ.Sampling this state produces a product from that row with high probability.
- Analysis: A subset S′ contains at least (1 −δ −ζ)m users for which the analysis bounds the recommendation error and runtime.The guarantee is then applied to at least (1−ξ)|S′| users.
- Performance: For at least (1−ξ)(1−δ −ζ)m users, expected runtime is O(polylog(mn)poly(k)) and recommendations are good with high probability.A worst-case bound can be obtained by stopping after log(n) times the expected runtime, reducing correctness by only 1 −1/poly(n).
- Sampling requirement: Achieving the desired runtime requires sampling a constant fraction of matrix elements, as in classical recommendation systems.The theorem can tolerate sub-constant sampling probability, but the runtime target requires constant p.
A The data structure
The data structure stores matrix entries in row-wise binary trees and supports quantum preparation of row states and row-norm states. It uses near-linear memory in the number of stored entries and polylogarithmic update time.
- Space: The structure requires O(w log^2(mn)) memory for w entries currently stored.This follows because each inserted entry adds at most ⌈log n⌉ nodes, with O(log mn) bits per node.
- Quantum access: Quantum access supports eU: |i⟩|0⟩→|i⟩|Ai⟩ and eV: |0⟩|j⟩→|eA⟩|j⟩ in polylog(mn) time.Here eAi = ∥Ai∥, so eV prepares access to row norms.
- Tree representation: The data structure stores each matrix row in a binary tree whose leaves contain squared entry amplitudes and signs, while internal nodes store subtree square sums.The root of each row tree stores the squared row norm.
- Updates: Storing a new entry takes O(log^2(mn)) time because at most ⌈log n⌉ tree nodes are updated, each requiring O(log mn) address retrieval.The trees have depth at most ⌈log n⌉.
- State preparation: Conditional rotations driven by internal-node amplitudes prepare each row state using ⌈log n⌉ rotations and two data-structure queries per rotation.A second binary tree over row roots supports efficient preparation of the row-norm state.