Classical method recreates quantum sampling for optimized matrix functions
A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features
Machine Learning
Summary
Quantum computers can speed up some machine learning tasks by using advanced math operations on matrices, but they often require special kinds of access to data. The authors developed a classical (non-quantum) algorithm that mimics one such quantum method for selecting important parts of data. Their method focuses on picking out key elements and working with smaller parts of matrices, making it possible to achieve similar results without needing quantum resources. This shows that certain quantum-inspired approaches can be done efficiently on regular computers under specific conditions.
What this means in practice
- •For machine learning engineers: Use classical algorithms to sample optimized random features efficiently without quantum hardware, enabling improved model training on large datasets.
- •For data scientists: Apply the classical sampling method to analyze diagonally weighted matrices in data processing tasks requiring accurate operator norm guarantees.
Authors
Natsuto Isogai, Mio Murao, Hayata Yamasaki
Abstract
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.