CS Paper Radar

Quantum-Stable Robust Principal Component Analysis: Theory and Evidence from NISQ Regimes

Angshul Majumdar

eess.SP cs.ET ·submitted 2026-08-29 07:00 UTC · v1
published

Abstract

Robust Principal Component Analysis (RPCA) is a fundamental technique for extracting low-rank structures from data corrupted by sparse anomalies and noise. While classical RPCA and its stable variants have been widely studied, their computational cost grows prohibitively with data dimensionality. Motivated by emerging trends in quantum machine learning, this paper introduces Quantum-Stable RPCA, the first quantum algorithm for robust low-rank and sparse decomposition under noisy intermediate-scale quantum (NISQ) constraints. Our approach integrates Quantum Singular Value Thresholding (QSVT) for low-rank recovery with Quantum Sparse Approximation (QSA) for anomaly detection, while explicitly modeling gate, decoherence, and measurement errors inherent in quantum hardware. We establish six theoretical results covering recovery guarantees, identifiability, robustness to approximate structure, quantum noise resilience, convergence of alternating minimization, and generalization bounds, thereby extending classical RPCA theory to the quantum regime. Extensive Qiskit-based simulations confirm that Quantum-Stable RPCA delivers significant runtime improvements over classical solvers while maintaining competitive reconstruction accuracy, even under realistic NISQ noise levels. This work provides a blueprint for quantum-enhanced robust learning, bridging machine learning and signal processing paradigms.

Journal ref
Majumdar, A. Quantum-stable robust principal component analysis: theory and evidence from NISQ regimes. Quantum Mach. Intell. 8, 6 (2026)
DOI
10.1007/s42484-026-00348-x

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG quant-phstat.ML ·2026-09-09 ·Natsuto Isogai, Mio Murao, Hayata Yamasaki
similarity 0.72
Abstract · 18 pages, 1 figure

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.

0.39

Adaptive Low-Rank Quantum Kernel Acquisition under Finite-Shot Measurements: Perturbation Guarantees for QSVMs

eess.SY ·2026-11-02 ·Duong The Do, Duong Tung Nguyen
benchmark similarity 0.66
Abstract

Quantum kernel methods require estimating entries of a dense Gram matrix through repeated circuit measurements, making kernel construction expensive and statistically noisy. For a dataset of size $n$, dense construction requires $O(n^2)$ kernel queries, while existing approximation methods typically assume inexpensive access to kernel entries or use non-adaptive sampling. We study adaptive low-rank quantum kernel acquisition when the kernel is accessible only through a finite-shot quantum overlap oracle. Our framework, ICAQKL, uses residual-driven incomplete Cholesky construction to acquire informative kernel columns sequentially and form a positive-semidefinite rank-$r$ surrogate, reducing the training-kernel acquisition cost to $O(nrN_s)$ circuit executions for $r\ll n$, where $N_s$ is the number of shots per queried entry. The central difficulty is that finite-shot errors perturb both the queried kernel values and the adaptive pivot sequence that determines the low-rank factor. We develop a non-asymptotic perturbation framework for this stochastic adaptive process, establishing concentration over the realized queries, stability of noisy pivot selection and factor construction, and propagation of the coupled sampling and approximation errors to the QSVM objective, optimizer, prediction function, and classification margin. The resulting rank--shot conditions characterize when ICAQKL approaches the full QSVM induced by the same quantum feature map. Experiments on benchmark and biomedical datasets show favorable accuracy--query-cost tradeoffs, competitive performance with the full QSVM, and competitive or improved performance relative to the evaluated Nyström baselines under comparable settings. ICAQKL is intended to enable measurement-efficient and theoretically controlled use of a selected quantum kernel, rather than to establish quantum advantage over classical kernels.

0.13

Quantized Low-Rank Quantum State Tomography: Hyperbolic Quantization and Riemannian Least-Squares Recovery

cs.IT quant-ph ·2026-08-27 ·HanQin Cai, Longxiu Huang, Juntao You
similarity 0.65
Abstract

We study low-rank quantum state tomography from finite-bit Pauli batch responses. To avoid bias introduced by generic quantization, we propose HyperQuant, a mean-preserving hyperbolic quantizer adapted to the second-moment scale of Pauli responses. We establish minimax distortion guarantees and show that exact mean preservation enables direct rank-constrained least-squares recovery without altering the population target. We derive nonasymptotic recovery guarantees and an explicit bit--shot tradeoff under which finite-bit responses retain the error order of unquantized batch averages using fewer response bits. For efficient computation, we develop QuantRGD, a Riemannian gradient method with provable linear convergence to the corresponding statistical neighborhood under explicit resource conditions. Numerical experiments validate the predicted quantization, recovery, and convergence behavior.

0.29

Learning sparse quantum states from single-qubit measurements

cs.DS quant-phcs.IT ·2026-09-28 ·Su-un Lee, Liang Jiang, Kunal Sharma
similarity 0.63
Abstract

We study the problem of learning a sparse quantum state, an $n$-qubit quantum state whose density matrix has at most $s$ nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity $s$ is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When $s$ grows polynomially with $n$, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.

0.19

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

cs.DS quant-ph ·2026-09-30 ·Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén, Francisca Vasconcelos
similarity 0.63
Abstract

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

0.28

Quantum Sparse Autoencoders for Q-Matrix Estimation in Cognitive Diagnosis

cs.LG ·2026-09-01 ·Arif Hassan Zidan, Yi Pan, Bowen Guo, Xiang Li, Yu Bao +3 more
benchmark similarity 0.63
Abstract

Q-matrices play a central role in cognitive diagnosis within educational data mining (EDM), specifying which latent skills each assessment item requires. Data-driven Q-matrix estimation remains challenging when assessments involve many correlated skills and when real response patterns depart from idealized generative assumptions. We introduce a novel quantum sparse autoencoder (QSAE) for Q-matrix estimation, which, to the best of our knowledge, is the first application of quantum machine learning (QML) to cognitive diagnosis. Overall, the QSAE embeds each student's binary response vector into a quantum circuit using an encoder, compresses it into a sparse latent representation, and maps that representation to the Q-matrix. We benchmark the QSAE against a classical autoencoder (CAE) across 60 simulated datasets and 9 real-world assessment datasets. The results reveal complementary strengths. Although the CAE partially achieves higher average accuracy under several simulation conditions, the QSAE is substantially more stable across replications, exhibiting lower variance in 49 of the 60 conditions. Moreover, on real assessment data, the QSAE outperforms the CAE on 6 of the 9 datasets. These findings suggest that the principal advancement of QML in this setting is not universal accuracy improvement, but enhanced robustness and capability to explore latent-structure complexity in real datasets.

0.14

Margin-Based Generalization for Quantum Machine Learning with Classical Data Encoding

cs.LG quant-ph ·2026-10-17 ·Ju-Young Ryu, Tak Hur, Daniel K. Park
similarity 0.62
Abstract · 22 pages, 6 figures, 7 tables

Understanding generalization is essential for assessing the practical viability of quantum machine learning. In many applications, quantum models operate on classical data that must first be encoded into quantum states, making the encoding part of the effective hypothesis class. We develop a margin-based generalization framework for this setting, covering both fixed and trainable quantum data encodings. For fixed encodings, the existing margin bound transfers unchanged. For trainable encodings, we derive a bound using a two-scale covering argument that combines the original margin-dependent term with an additive encoding-capacity term of order $\tilde O(\sqrt{L/m})$, where $L$ is the number of trainable encoding parameters and $m$ is the training-sample size. Across 19,440 simulated training runs spanning various image datasets, circuit architectures, and optimization settings, the inverse margin performs best among five baseline and two bound-derived complexity measures under conditional-independence and 90th-percentile sign-error criteria, within bootstrap uncertainty. These results provide a unified margin-based view of generalization in quantum machine learning with classical data.

0.14

Quantum anomaly detection in real scarce data

cs.LG quant-ph ·2026-10-07 ·Emanuele Casciaro, Fabio Mascherpa, Alfonso Amendola, Filippo Caruso
similarity 0.62
Abstract

Anomaly detection on small and unbalanced datasets remains very challenging in machine learning, although this scenario is common in several domains, including healthcare, cybersecurity, finance, and energy. Data augmentation and generative AI may mitigate training-data scarcity, but they often fall short because anomalies are, by definition, unpredictable, rare, and highly diverse events compared to high-probability normal data. Overfitting to pseudo-anomalies, model collapse, high-dimensional data, uninterpretable black-box models, and validation challenges are typical issues limiting their practical applicability. In this context, quantum machine learning may provide a promising and more sustainable avenue because it can enable more interpretable models with far fewer trainable parameters and smaller datasets, implementable on energy-efficient quantum hardware. Here, we propose a novel two-step hybrid classical--quantum architecture for sequential data and test it on a realistic scenario in the global energy-transition domain, i.e., automated anomaly detection in large-scale photovoltaic plants. The achieved generalization capability and competitive prediction accuracy may pave the way for new hybrid learning models able to exploit the continuously increasing power of cloud-available and more sustainable quantum accelerators integrated with more traditional energy-hungry High Performance Computing resources.

0.18