Source-linked AI summary
A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features
Natsuto Isogai, Mio Murao, Hayata Yamasaki
TL;DR
The paper addresses a dequantization gap for QSVT-based sampling when the matrix to be inverted lacks sampling-and-query access. It truncates the diagonal factor to heavy coordinates, computes the matrix function on a small principal block, and obtains a sparse classical representation; this yields a classical sampler for optimized random features with prescribed accuracy and polynomially related runtime.
Problem
QSVT-based learning with optimized random features requires inverting a matrix that is not itself available through sampling-and-query access, so existing dequantization techniques do not apply.
Method
The method samples heavy diagonal coordinates, replaces the diagonal factor with a low-support approximation, and computes the matrix function on the resulting principal block.
Results
The algorithm outputs sparse query access to an operator-norm approximation of f(γI + DAD) and dequantizes the optimized-random-feature sampler with polynomially related runtime except in δ.
Takeaways & Limitations
The diagonal factorization can provide sufficient classical structure even when sampling access to the composite matrix DAD cannot be efficiently constructed.
Abstract
from arXiv · showhide
Quantum-inspired classical algorithms have dequantized several quantum machine learning routines by replacing quantum linear-algebra subroutines with classical counterparts. However, the sampler based on quantum singular value transformation (QSVT) for learning with optimized random features is not covered by existing dequantization frameworks, because the matrix to be inverted is not itself available through sampling access. In this work, we develop a classical algorithm to address this type of quantum-advantage candidate. Our method samples heavy indices, reduces the transformation to a small principal block, and outputs a sparse classical representation with operator-norm guarantees. Applying this method dequantizes the sampler for optimized random features, giving a classical sampler with prescribed accuracy and polynomially related runtime. These results show that the factorization underlying a quantum block encoding can itself provide sufficient classical structure even when sampling-and-query access to the composite matrix is unavailable.
1. Notations and general definitions
The paper fixes notation for vectors, matrices, eigenvalues, spectra, principal submatrices, randomized algorithms, and total variation distance, and recalls Hoeffding’s inequality for concentration.
- Notation: Vectors and matrices use standard norms, entries, adjoints, eigenvalues, spectra, and principal-submatrix notation.For a square matrix, A_S restricts A to rows and columns indexed by S.
- Probability and concentration: The paper defines total variation distance as its metric for comparing probability distributions.It notes that total variation distance satisfies the triangle inequality and lies between 0 and 1.
- Probability and concentration: Hoeffding’s inequality is introduced to bound estimation errors and failure probabilities for independent bounded random variables.
2. Matrix functions
The paper defines singular-value and eigenvalue transformations through matrix decompositions, then uses f(A) as shorthand when the transformation type is clear.
- Matrix transformations: Singular-value transformation applies f to the nonzero singular values in an SVD and reconstructs the transformed matrix.The diagonal transformation f^SV(D) contains the values f(d_i).
- Matrix transformations: Eigenvalue transformation applies f to the eigenvalues in a Hermitian matrix’s eigenvalue decomposition.For positive semidefinite matrices, eigenvalue and singular-value transformations coincide because eigenvalues equal singular values.
- Matrix transformations: The notation f(A) denotes either transformation when the intended meaning is unambiguous.
3. Lipschitz constant
The paper defines Lipschitz continuity on a real interval and records that translation preserves the same Lipschitz constant, alongside an operator-norm perturbation bound.
- Lipschitz constant: A function is L-Lipschitz on F when its output difference is at most L times the input difference for all points in F.
- Lipschitz constant: Translating the input by γ preserves L-Lipschitz continuity on the correspondingly shifted interval.For g(x)=f(γ+x), the shifted domain is F_γ={x | x+γ∈F}.
- Lipschitz constant: For Hermitian matrices, the operator-norm perturbation bound includes a logarithmic factor in the number of distinct eigenvalues.The paper applies this bound when the spectra lie in the interval where f is Lipschitz.
4. Access models
The paper distinguishes query, noisy-query, sampling-and-query, and sparse-access oracles, which provide different combinations of entry access, sampling, norm computation, and sparsity information.
- Access models: Query access returns individual vector or matrix entries, while noisy query access returns additive approximations with specified success probability.The noisy oracle guarantees an error at most ϵ with probability at least 1−δ for each query.
- Access models: Sampling-and-query access combines entry queries with index sampling and norm computation for vectors and matrices.Its matrix form is built from sampling-and-query access to rows or associated vectors, with costs q, s, n, and sq.
- Access models: Sparse query access exposes nonzero locations in each row and column together with entry values for a sparse matrix.The oracle uses row and column sparsity bounds and a sentinel value when a requested nonzero position does not exist.
Appendix B: Heavy-coordinate truncation of diagonal data
The method samples diagonal coordinates according to their squared entries, retains sufficiently heavy coordinates, and constructs a sparse approximation with controlled operator-norm error.
- Heavy-coordinate detection: Repeated SQ(D) sampling identifies every coordinate with d_i ≥ ϵ with high probability, producing the retained support S.The sampling distribution is proportional to squared diagonal entries, so sufficiently large entries are detected through repeated trials.
- Approximation guarantee: The truncation algorithm outputs a nonnegative diagonal matrix e D with ∥D − e D∥op ≤ ϵ when all heavy coordinates are sampled.For diagonal matrices, the operator norm equals the largest coordinatewise approximation error.
- Output representation: From the retained entries, a standard ℓ2-sampling data structure implements SQ(e D) using O(s log s) construction time and O(s) space.The resulting structure supports entry queries, ℓ2-sampling, and norm queries.
- Runtime: The total runtime is O(R × (sq(D) + log(R))), combining repeated sampling and checking with construction of the sparse diagonal structure.The sampling count R depends on the truncation threshold and failure probability.
Appendix C: Diagonal truncation method
The diagonal-truncation method replaces D by a low-support approximation, computes the matrix function on the resulting principal block, and represents the result with support-sparse access.
- Construction: The algorithm uses SQ(D) to form e D, queries A only on the retained support S, computes the function on an s × s block, and fills the complement with f(γ).After permuting S first, the truncated matrix is block diagonal with a principal block and γI on the remaining coordinates.
- Guarantee: Theorem 16 provides operator-norm approximation for f(γI + DAD) using SQ(D), noisy entry queries to A, norm bounds, and an evaluation oracle for f.The theorem assumes f is L-Lipschitz on an interval covering the relevant spectra and γ.
- Sparse representation: The retained block has size s ≤ (∥D∥F/ϵD)^2, while the output stores the block result B and f(γ) outside the support.The representation provides support, index lists, a bijection, and the s × s matrix B.
- Success probability: The method combines truncation and noisy-query success probabilities, with accuracy of all s(s+1)/2 queried upper-triangular entries handled by a union bound.The overall success probability is obtained by combining the truncation event with the query-accuracy event.
- Scope of the bound: For arbitrary Lipschitz f, the perturbation bound includes C(1 + log(1 + s))L, although special functions may admit sharper bounds.The logarithmic factor comes from a general operator-norm Lipschitz estimate.
- Access-model scope: The construction does not provide sampling access to true DAD, but it can construct sampling-and-query access to the approximated e D A e D after support reduction.This avoids requiring efficient sampling access to the composite matrix while retaining operator-norm approximation of its function.
Appendix D: Application to learning with optimized random features
The paper applies diagonal truncation to the optimized-random-feature sampler, whose QSVT inversion targets a diagonally weighted kernel matrix unavailable through standard sampling-and-query access.
- Application setting: The optimized-random-feature quantum subroutine inverts a diagonally weighted kernel matrix that existing dequantization techniques do not cover.Its diagonal factor comes from an empirical distribution, while the kernel is specified through a separate kernel-dependent access model.
- Dequantization: The application supplies the diagonal distribution structure and kernel information separately, enabling the diagonal-truncation framework to dequantize the sampler.The method addresses the mismatch between the composite matrix used by QSVT and the available classical access assumptions.
- Optimized features: Optimized random features use a data-dependent importance-weighted distribution intended to reduce the number of features needed for kernel methods while preserving approximation quality.The distribution is used instead of the kernel’s original spectral measure.
2. The subroutine of learning with optimized random features
The optimized-random-feature subroutine samples from an importance-weighted distribution defined over a discretized domain, using an empirical distribution and kernel-related inputs.
- Discretized setting: The input domain is discretized as X = {0, 1, …, G − 1}^D with n = G^D points, and F_D denotes the corresponding discrete Fourier transform.The Fourier representation is part of the notation used to formulate the subroutine.
- Inputs: The setup provides a nonnegative function Q(τ) and an empirical probability distribution q̂(ρ), represented as diagonal matrices over X.The empirical distribution is normalized over the discretized domain.
- Access assumptions: The quantum input model includes an oracle for preparing the empirical-distribution state, equivalent to query access to SQ(q̂(ρ)).The kernel matrix is also part of the associated construction and is positive semidefinite under the stated setting.
- Sampling objective: The core task is to approximately sample from the optimized distribution Dϵ over the discretized domain X.The target total-variation error is dTV(Dϵ, ˜D) ≤ δ for δ ∈ (0, 1].
3. Dequantization of sampling from the optimized probability distribution
The paper dequantizes sampling from the optimized probability distribution by applying its matrix-function approximation theorem and implementing the missing kernel-entry queries approximately. The resulting classical sampler has polynomially related runtime, with a polynomial rather than polylogarithmic dependence on the accuracy parameter δ.
- Theorem 19 gives a randomized classical sampler whose runtime is polynomially related to the quantum sampler except in δ.The stated exception is that the classical runtime depends polynomially on δ-related accuracy, whereas the quantum runtime is polylogarithmic in 1/δ.
- The sampler outputs a distribution D′ whose total variation distance from the optimized distribution Dϵ is at most δ.
- The method uses Theorem 16 to approximate the inverse of the inner matrix required for optimized sampling.
- Because direct kernel queries are unavailable, the algorithm estimates kernel entries through Q(Q(τ)) and constructs an approximate query oracle.
- Rejection sampling converts the approximate matrix computation into samples from an approximation of the optimized probability distribution.
Appendix E: Proof of Theorem 19
The appendix proves the kernel-query component by estimating each kernel entry from uniform samples and the oracle Q(Q(τ)). Hoeffding’s inequality supplies the corresponding accuracy and success-probability guarantees.
- The kernel matrix is symmetric, so the construction can estimate one orientation and set e k(α,β)=e k(β,α).
- The implementation accounts for cosine-evaluation overhead using polylogarithmic factors absorbed into the stated runtime notation.
- Hoeffding’s inequality bounds the estimation error and failure probability for the resulting approximate kernel query.
- Lemma 20 constructs a randomized approximate query oracle Q(e k) for each kernel entry using Q(Q(τ)).
- Uniformly sampled points y1,…,yI from X provide the empirical averages used to estimate each kernel entry.
3. Compute
The computation applies the matrix-function approximation with an estimated kernel oracle, then uses rejection sampling to produce the target distribution. The proof establishes bounded kernel-entry error, controlled failure probability, and the algorithm’s runtime.
- Kernel-entry estimates have absolute error at most ϵ with probability at least 1−δ.
- The algorithm samples from D′ with total variation distance at most δ from Dϵ.
- Theorem 16 is instantiated with A=k, γ=ϵ, and f(x)=x^-1 to construct sparse-query and sampling access for the approximating matrix N.
- Rejection sampling uses the approximate weight function and accepts uniformly sampled proposals with probability proportional to the estimated weight.
- The runtime is dominated by Algorithm 1 and repeated weight evaluations, with s≤1/ϵ^2 controlling the retained-block contribution.
- The block structure of N eliminates cross terms outside the retained principal indices, making each approximate weight computable through the small block.