Quantum-assited anomaly detection with multivariate Gaussian distribution

• URL: http://arxiv.org/abs/2505.02316v1
• Date: Mon, 05 May 2025 02:21:11 GMT
• Title: Quantum-assited 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 is a prominent problem in data mining and machine learning.<n>We propose a new quantum algorithm for GAD without phase estimation.<n>Our quantum algorithm is highly efficient when handling low-dimensional datasets.
• Score: 0.8444410725308873
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Anomaly detection with multivariate Gaussian distribution, termed Gassian anomaly detection (GAD), is a prominent problem in data mining and machine learning, in which all training data points of a given dataset are assumed to be drawn from an unknown multivariate Gassian distribution and those points with low probability density function values are deemed anomalies. Hence, the central task of GAD is to calculate the probability density function of a new data point by retrieving its mean values and covariance matrix, which could be time-consuming when addressing a large dataset. Recently, several quantum algorithms have been proposed to for GAD, which have been shown significantly faster than the classical counterparts under certain conditions. However, they all require quantum phase estimation as a key subroutine that may have exponentially high quantum circuit depth and is not desirable in the noisy intermediate-scale quantum (NISQ) era. In this paper, we propose a new quantum algorithm for GAD without phase estimation, whose quantum circuit has depth only linear in the number of qubits, which is relatively more friendly on NISQ devices. Specifically, building on arithmetic-free black-box quantum state preparation (AFBBQSP), our quantum algorithm outputs the estimates of the mean values and the covariance matrix both in the classical form, 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 is highly efficient when handling low-dimensional datasets with well-conditioned data matrices. Moreover, unlike prior quantum algorithms for GAD which require the input data to be quantum, mean centered, or feature correlated, our quantum algorithm release these constraints and thus is more data practical. Our work highlights the role of AFBBQSP in bringing quantum machine learning closer to reality.

Related papers

• 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)
• 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)
• 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)
• 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.