Dequantizing algorithms to understand quantum advantage in machine learning

Mehrad Sahebi, Alice Barthe, Yudai Suzuki +2 more

In the quest for quantum advantage, a central question is under what conditions can classical algorithms achieve a performance comparable to quantum algorithms--a concept known as dequantization. Random Fourier features (RFFs) have demonstrated potential for dequantizing certain quantum neural networks (QNNs) applied to regression tasks, but their applicability to other learning problems and architectures remained unexplored. In this work, we derive bounds on the true risk gap between classical RFF models and quantum models for regression and classification tasks with both QNN and quantum kernel architectures. Furthermore, we provide sufficient conditions under which this gap is small and thus the quantum system can be dequantized via the RFF method. We support our findings with numerical experiments that illustrate the practical dequantization of existing quantum kernel-based methods. Our findings not only broaden the applicability of RFF-dequantization but also enhance the understanding of potential quantum advantages in practical machine-learning tasks.

Natsuto Isogai, Mio Murao, Hayata Yamasaki

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.

Andrew Stewart Caldin

CLAIM: It has never been necessary to build quantum computers. A classical machine running E8 geometry could always have performed the same simultaneous information processing — without cryogenic cooling, without specialist hardware, and without the fundamental fragility that makes quantum computers impractical at scale. EVIDENCE STRAND 1 — THE DEQUANTIZATION WAVE: In 2018, Ewin Tang (University of Washington) published a proof that the Kerenidis-Prakash quantum recommendation algorithm — previously held as definitive evidence of quantum advantage — could be replicated on a classical computer using probabilistic sampling. This was the first crack in the quantum advantage claim for AI. It was not the last. Tang subsequently dequantized quantum principal component analysis (2019). Gilyen, Song, and Tang (2022) dequantized a further class of quantum sampling-based machine learning algorithms. The common thread in every dequantized quantum algorithm: the underlying problem had low-rank mat Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

Y.V.R. Naga Pawan, Bhanu Prakash Kolla

Hiep L. Thi