Quantum-assisted anomaly detection with multivariate Gaussian distribution

• URL: http://arxiv.org/abs/2505.02316v2
• Date: Tue, 23 Sep 2025 16:01:19 GMT
• Title: Quantum-assisted anomaly detection with multivariate Gaussian distribution
• Authors: Chao-Hua Yu, Hong-Miao Rao, Ying-Pei Wu, De-Xi Liu, Xi-Ping Liu, Lin-Chun Wan,
• Abstract summary: Gassian anomaly detection (GAD) is a prominent task in data mining and machine learning.<n>We propose a quantum algorithm for GAD biult on arithmetic-free black-box quantum state preparation (AFQSP)<n>Our algorithm achieves exponential speedup over the classical GAD when handling low-dimensional datasets.
• Score: 1.752215225501591
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Anomaly detection with multivariate Gaussian distribution, which we refer to as Gassian anomaly detection (GAD), is a prominent task in data mining and machine learning. The core task of GAD is to obtain the mean value vector and the covariance matrix that characterize the probability density function of an unknown multivariate Gaussian distribution used to detect anomalies, which could be time-consuming when addressing a large dataset. Recently, several quantum algorithms have been proposed for GAD with substantial speedup over the classical GAD. However, they all require quantum phase estimation as key subroutines so that their quantum ciruits have long depth and are unfavorable in the noisy intermediate-scale and early fault-tolerant quantum eras. In this paper, we propose a quantum algorithm for GAD biult on arithmetic-free black-box quantum state preparation (AFQSP), which significantly shortens the quantum circuit depth and reduces the burden of quantum hardware. Specifically, we take advantage of AFQSP to estimate the magnitude of every mean value and that of every covariance matrix element in the classical form, and develop a technique referred to as Hadamard sign test to further reveal their signs, so that anomaly detection of any data point can be done immediately on a classical computer at little cost. It is shown that our quantum algorithm for GAD achieves exponential speedup over the classical GAD when handling low-dimensional datasets with well-conditioned data matrices, and is also time competitive compared to the prior quantum algorithms for GAD. Moreover, our algorithm releases the requirements of input data being quantum, mean centered, or feature correlated in the prior quantum algorithms for GAD, meaning that our algorithm is more practical on input data. Our work highlights the role of AFQSP in bringing quantum machine learning closer to reality.

Related papers

• Toward speedup without quantum coherent access [0.0]
  We propose a variant of quantum algorithms, leveraging both classical and quantum resources.<n>We show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, and data fitting.
  arXiv  Detail & Related papers  (2026-02-24T11:21:44Z)
• Quantum Gated Recurrent GAN with Gaussian Uncertainty for Network Anomaly Detection [10.435718832887988]
  Anomaly detection in time-series data is a critical challenge with significant implications for network security.<n>Recent quantum machine learning approaches have shown promise in capturing complex data distributions for anomaly detection but remain constrained by limited qubit counts.<n>We introduce in this work a novel Quantum Gated Recurrent Unit (QGRU)-based Generative Adversarial Network (GAN) for robust network anomaly detection.
  arXiv  Detail & Related papers  (2025-10-30T13:39:44Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• The curse of random quantum data [62.24825255497622]
  We quantify the performances of quantum machine learning in the landscape of quantum data. We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits. Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
  arXiv  Detail & Related papers  (2024-08-19T12:18:07Z)
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation [39.20075231137991]
  We investigate the feasibility of early fault-tolerant quantum algorithms focusing on ground-state energy estimation problems.<n> scaling these methods to larger system sizes reveals three key challenges: the smoothness of the CDF for large supports, the lack of tight lower bounds on the overlap with the true ground state, and the difficulty of preparing high-quality initial states.
  arXiv  Detail & Related papers  (2024-05-06T18:00:03Z)
• Quadratic speed-ups in quantum kernelized binary classification [1.3812010983144802]
  Several quantum machine learning algorithms that use quantum kernels as a measure of similarities between data have emerged to perform binary classification on datasets encoded as quantum states. We propose new quantum circuits for the QKCs in which the number of qubits is reduced by one, and the circuit depth is reduced linearly with respect to the number of sample data. We verify the quadratic speed-up over previous methods through numerical simulations on the Iris dataset.
  arXiv  Detail & Related papers  (2024-03-26T07:39:48Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• 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)
• Quantum Conformal Prediction for Reliable Uncertainty Quantification in Quantum Machine Learning [47.991114317813555]
  Quantum models implement implicit probabilistic predictors that produce multiple random decisions for each input through measurement shots. This paper proposes to leverage such randomness to define prediction sets for both classification and regression that provably capture the uncertainty of the model.
  arXiv  Detail & Related papers  (2023-04-06T22:05:21Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Quantum density estimation with density matrices: Application to quantum anomaly detection [8.893420660481734]
  Density estimation is a central task in statistics and machine learning. We present a novel quantum-classical density matrix density estimation model, called Q-DEMDE. We also present an application of the method for quantum-classical anomaly detection.
  arXiv  Detail & Related papers  (2022-01-24T23:40:00Z)
• Kernel Matrix Completion for Offline Quantum-Enhanced Machine Learning [0.09786690381850353]
  We show quantum kernel matrices can be extended to incorporate new data using a classical (chordal-graph-based) matrix completion algorithm. The minimal sample complexity needed for perfect completion is dependent on matrix rank. On a real-world, industrially-relevant data set, the completion error behaves gracefully even when the minimal sample complexity is not reached.
  arXiv  Detail & Related papers  (2021-12-15T19:44:39Z)
• Efficient criteria of quantumness for a large system of qubits [58.720142291102135]
  We discuss the dimensionless combinations of basic parameters of large, partially quantum coherent systems. Based on analytical and numerical calculations, we suggest one such number for a system of qubits undergoing adiabatic evolution.
  arXiv  Detail & Related papers  (2021-08-30T23:50:05Z)
• Robust quantum classifier with minimal overhead [0.8057006406834467]
  Several quantum algorithms for binary classification based on the kernel method have been proposed. These algorithms rely on estimating an expectation value, which in turn requires an expensive quantum data encoding procedure to be repeated many times. We show that the kernel-based binary classification can be performed with a single-qubit measurement regardless of the number and the dimension of the data.
  arXiv  Detail & Related papers  (2021-04-16T14:51:00Z)
• Statistical Limits of Supervised Quantum Learning [90.0289160657379]
  We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning cannot achieve polylogarithmic runtimes in the input dimension. We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most speedups over efficient classical algorithms.
  arXiv  Detail & Related papers  (2020-01-28T17:35:32Z)

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.