Refined Quantum Algorithms for Principal Component Analysis and Solving Linear System

• URL: http://arxiv.org/abs/2504.00833v1
• Date: Tue, 01 Apr 2025 14:23:54 GMT
• Title: Refined Quantum Algorithms for Principal Component Analysis and Solving Linear System
• Authors: Nhat A. Nghiem,
• Abstract summary: We outline refined versions of two major quantum algorithms for performing principal component analysis and solving linear equations.<n>Our methods are exponentially faster than their classical counterparts and even previous quantum algorithms/dequantization algorithms.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We outline refined versions of two major quantum algorithms for performing principal component analysis and solving linear equations. Our methods are exponentially faster than their classical counterparts and even previous quantum algorithms/dequantization algorithms. Oracle/black-box access to classical data is not required, thus implying great capacity for near-term realization. Several applications and implications of these results are discussed. First, we show that a Hamiltonian $H$ with classically known rows/columns can be efficiently simulated, adding another model in addition to the well-known sparse access and linear combination of unitaries models. Second, we provide a simpler proof of the known result that quantum matrix inversion cannot achieve sublinear complexity $\kappa^{1-\gamma}$ where $\kappa$ is the conditional number of the inverted matrix.

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)
• 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)
• Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD. Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers. Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
  arXiv  Detail & Related papers  (2024-04-30T23:55:03Z)
• 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)
• Hybrid quantum-classical and quantum-inspired classical algorithms for solving banded circulant linear systems [0.8192907805418583]
  We present an efficient algorithm based on convex optimization of combinations of quantum states to solve for banded circulant linear systems. By decomposing banded circulant matrices into cyclic permutations, our approach produces approximate solutions to such systems with a combination of quantum states linear to $K$. We validate our methods with classical simulations and actual IBM quantum computer implementation, showcasing their applicability for solving physical problems such as heat transfer.
  arXiv  Detail & Related papers  (2023-09-20T16:27:16Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
  We study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure. We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation. This unitary has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware.
  arXiv  Detail & Related papers  (2021-12-05T15:42:32Z)
• 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)
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions [4.327821619134312]
  We introduce a quantum primitive called fast inversion, which can be used as a preconditioner for solving quantum linear systems. We demonstrate the application of preconditioned linear system solvers for computing single-particle Green's functions of quantum many-body systems.
  arXiv  Detail & Related papers  (2020-08-30T23:24:58Z)

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.