A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features

• URL: http://arxiv.org/abs/2609.10729v1
• Date: Wed, 09 Sep 2026 18:23:55 GMT
• Title: A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features
• Abstract summary: We develop a classical algorithm to address this type of quantum-advantage candidate.<n>Applying this method dequantizes the sampler for optimized random features, giving a classical sampler with prescribed accuracy and runtime.
• Score: 0.9558392439655014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 papers

• Towards Surrogate Based Dequantization of Quantum Reinforcement Learning [0.1749935196721634]
  We build on recent kernel-based dequantization results for supervised learning to extend this surrogate-based dequantization program to reinforcement learning.<n>We provide finite sample guarantees for classical kernelized Fitted Q-Iteration, with classical kernels designed to match the inductive bias of particular parameterized quantum circuits.
  arXiv  Detail & Related papers  (2026-09-14T19:26:35Z)
• Benchmarking Quantum Extreme Learning based on Gaussian Boson Sampling [0.5161531917413708]
  Reservoir models offer a hardware-efficient learning paradigm for noisy intermediate-scale quantum devices.<n>We propose a quantum extreme learning machine that achieves high classification accuracy while reducing optical resource requirements.
  arXiv  Detail & Related papers  (2026-06-13T10:00:10Z)
• A Quantum Search Approach to Magic Square Constraint Problems with Classical Benchmarking [0.0]
  We reformulate magic square construction as a quantum search problem in which a reversible, constraint-sensitive marks valid for amplitude amplification.<n>This work uses the classical component for structured initialisation and the quantum component for search, and benchmarks the quantum approach against classical brute-force enumeration and backtracking.
  arXiv  Detail & Related papers  (2026-04-06T15:55:52Z)
• Probabilistic modeling over permutations using quantum computers [0.0]
  We develop a quantum algorithm that encodes the exact probabilistic model into the amplitudes of a quantum state.<n>We envision the scaling, limitations, and practical use of such an approach, which we envision to be a first step towards useful applications of non-Abelian QFTs.
  arXiv  Detail & Related papers  (2026-03-23T18:00:12Z)
• Classically Prepared, Quantumly Evolved: Hybrid Algorithm for Molecular Spectra [41.99844472131922]
  We introduce a hybrid classical-quantum algorithm to compute dynamical correlation functions and excitation spectra in many-body quantum systems.<n>The method combines classical preparation of a perturbed ground state with short-time quantum evolution of product states sampled from it.
  arXiv  Detail & Related papers  (2025-10-28T19:27:12Z)
• Quantum Random Feature Method for Solving Partial Differential Equations [36.58357595906332]
  Quantum computing holds promise for scientific computing due to its potential for exponential speedups over classical methods.<n>In this work, we introduce a quantum random method (QRFM) that leverages advantages from both numerical analysis and neural analysis.
  arXiv  Detail & Related papers  (2025-10-09T08:42:09Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classicalNPG estimators with a deterministic gradient estimation approach.<n>The proposed QNPG algorithm achieves a sample complexity of $tildemathcalO(epsilon-1.5)$ for queries to the quantum oracle, significantly improving the classical lower bound of $tildemathcalO(epsilon-2)$ for queries to the Markov Decision Process (MDP)
  arXiv  Detail & Related papers  (2025-01-27T17:38:30Z)
• Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms [0.39886149789339326]
  We show how many techniques from randomized linear algebra can be adapted to work under this weaker assumption.<n>We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms.
  arXiv  Detail & Related papers  (2023-04-11T02:09:13Z)
• Generalization Metrics for Practical Quantum Advantage in Generative Models [68.8204255655161]
  Generative modeling is a widely accepted natural use case for quantum computers. We construct a simple and unambiguous approach to probe practical quantum advantage for generative modeling by measuring the algorithm's generalization performance. Our simulation results show that our quantum-inspired models have up to a $68 times$ enhancement in generating unseen unique and valid samples.
  arXiv  Detail & Related papers  (2022-01-21T16:35:35Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Quantum Machine Learning with SQUID [64.53556573827525]
  We present the Scaled QUantum IDentifier (SQUID), an open-source framework for exploring hybrid Quantum-Classical algorithms for classification problems. We provide examples of using SQUID in a standard binary classification problem from the popular MNIST dataset.
  arXiv  Detail & Related papers  (2021-04-30T21:34:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.