A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features
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.
Related
- Optimized bounds for the product and the ratios of modified Bessel functions
- Landscape Limits of Quantum-Inspired Evolutionary Optimization across 256 continuous functions
- Efficient Solution of Third-Order ODEs with Diagonally Implicit RK Method Using Tri-Colored Tree and B-series Analysis
- Asymptotic expansion of smooth functions in deterministic and iid Haar unitary matrices, and application to tensor products of matrices
- Adaptive Diagonally Implicit Runge-Kutta Methods Devoid of Order Reduction for Semilinear ODEs
BibTeX
@misc{isogai2026quantuminspired,
title = {{A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features}},
author = {Natsuto Isogai and Mio Murao and Hayata Yamasaki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10729},
eprint = {2609.10729},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10729},
}
RIS
TY - UNPB
TI - A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features
AU - Natsuto Isogai
AU - Mio Murao
AU - Hayata Yamasaki
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10729
UR - https://arxiv.org/abs/2609.10729
AB - 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.
ER -