Quantum Dimensionality Reduction by Linear Discriminant Analysis

• URL: http://arxiv.org/abs/2103.03131v1
• Date: Thu, 4 Mar 2021 16:06:30 GMT
• Title: Quantum Dimensionality Reduction by Linear Discriminant Analysis
• Authors: Kai Yu, Gong-De Guo, and Song Lin
• Abstract summary: Dimensionality reduction (DR) of data is a crucial issue for many machine learning tasks, such as pattern recognition and data classification. We present a quantum algorithm and a quantum circuit to efficiently perform linear discriminant analysis (LDA) for dimensionality reduction.
• Score: 14.671957651032638
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dimensionality reduction (DR) of data is a crucial issue for many machine learning tasks, such as pattern recognition and data classification. In this paper, we present a quantum algorithm and a quantum circuit to efficiently perform linear discriminant analysis (LDA) for dimensionality reduction. Firstly, the presented algorithm improves the existing quantum LDA algorithm to avoid the error caused by the irreversibility of the between-class scatter matrix $S_B$ in the original algorithm. Secondly, a quantum algorithm and quantum circuits are proposed to obtain the target state corresponding to the low-dimensional data. Compared with the best-known classical algorithm, the quantum linear discriminant analysis dimensionality reduction (QLDADR) algorithm has exponential acceleration on the number $M$ of vectors and a quadratic speedup on the dimensionality $D$ of the original data space, when the original dataset is projected onto a polylogarithmic low-dimensional space. Moreover, the target state obtained by our algorithm can be used as a submodule of other quantum machine learning tasks. It has practical application value of make that free from the disaster of dimensionality.

Related papers

• A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
  We propose a new quantum algorithm for the quantum linear system problem (QLSP) inspired by the classical proximal point algorithm (PPA) Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing texttimattQLSP_solver. By carefully choosing the step size $eta$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches.
  arXiv  Detail & Related papers  (2024-06-19T23:15:35Z)
• Preconditioning for a Variational Quantum Linear Solver [0.0]
  We numerically demonstrate a notable reduction in the required ansatz depth, demonstrating that preconditioning is useful for quantum algorithms. Our findings suggest that combining classical computing techniques, such as preconditioning, with quantum algorithms can significantly enhance the performance of NISQ algorithms.
  arXiv  Detail & Related papers  (2023-12-25T08:50:22Z)
• Solving Systems of Linear Equations: HHL from a Tensor Networks Perspective [39.58317527488534]
  We present an algorithm for solving systems of linear equations based on the HHL algorithm with a novel qudits methodology. We perform a quantum-inspired version on tensor networks, taking advantage of their ability to perform non-unitary operations such as projection.
  arXiv  Detail & Related papers  (2023-09-11T08:18:41Z)
• A general quantum matrix exponential dimensionality reduction framework based on block-encoding [4.501305807267216]
  Matrix Exponential Dimensionality Reduction (MEDR) deals with the small-sample-size problem that appears in linear Dimensionality Reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential eigenproblem. We design a general quantum algorithm framework for MEDR based on the block-encoding technique.
  arXiv  Detail & Related papers  (2023-06-16T03:36:03Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters. The proposed algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
  arXiv  Detail & Related papers  (2021-04-27T11:03:52Z)
• Quantum Algorithms for Data Representation and Analysis [68.754953879193]
  We provide quantum procedures that speed-up the solution of eigenproblems for data representation in machine learning. The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis. Results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.
  arXiv  Detail & Related papers  (2021-04-19T00:41:43Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Quantum inspired K-means algorithm using matrix product states [4.846953392700506]
  Matrix product state has become the algorithm of choice when studying one-dimensional interacting quantum many-body systems. We propose a quantum inspired K-means clustering algorithm which first maps the classical data into quantum states represented as matrix product states. We show that this algorithm could reach higher prediction accuracies and that it is less likely to be trapped in local minima compared to the classical K-means algorithm.
  arXiv  Detail & Related papers  (2020-06-11T03:00:48Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)

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.