Quantum Speedup for Spectral Approximation of Kronecker Products

• URL: http://arxiv.org/abs/2402.07027v1
• Date: Sat, 10 Feb 2024 19:21:29 GMT
• Title: Quantum Speedup for Spectral Approximation of Kronecker Products
• Abstract summary: We introduce an innovative approach to efficiently address the spectral approximation of the Kronecker product $A_otimes A$ using quantum methods. By treating matrices as quantum states, our proposed method significantly reduces the time complexity of spectral approximation to $O_d,epsilon(sqrtn)$.
• Score: 10.602399256297032
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Given its widespread application in machine learning and optimization, the Kronecker product emerges as a pivotal linear algebra operator. However, its computational demands render it an expensive operation, leading to heightened costs in spectral approximation of it through traditional computation algorithms. Existing classical methods for spectral approximation exhibit a linear dependency on the matrix dimension denoted by $n$, considering matrices of size $A_1 \in \mathbb{R}^{n \times d}$ and $A_2 \in \mathbb{R}^{n \times d}$. Our work introduces an innovative approach to efficiently address the spectral approximation of the Kronecker product $A_1 \otimes A_2$ using quantum methods. By treating matrices as quantum states, our proposed method significantly reduces the time complexity of spectral approximation to $O_{d,\epsilon}(\sqrt{n})$.

Related papers

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Quantum Eigenvalue Transformation via Linear Combination of Hamiltonian Simulation: A Weyl Calculus Approach [13.252368760346265]
  Linear combination of Hamiltonian simulation (LCHS) provides efficient method for implementing matrix exponentials $e-tA$ on quantum computers.<n>We develop LCHS formulas for computing general matrix functions $f(A)$ when $f$ is analytic on the numerical range of $A$, with $A$ possibly non-normal.<n>Our construction yields a quantum eigenvalue transformation algorithm with optimal $mathcalO(logfrac1)$ query complexity scaling.
  arXiv  Detail & Related papers  (2026-06-29T06:37:46Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Two Quantum Algorithms for Nonlinear Reaction-Diffusion Equation using Chebyshev Approximation Method [1.775629639045375]
  We present two new quantum algorithms for reaction-diffusion equations that employ the truncated Chebyshevpoly approximation.<n>We derive the sufficient conditions for the diagonalization of the Carleman embedding matrix.<n>The success of the diagonalization is based on a conjecture that a specific trigonometric equation has no integral solution.
  arXiv  Detail & Related papers  (2025-10-21T19:14:23Z)
• $O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation [0.0]
  We obtain an improved gradient bound of $O (1/k)$ for nonlinear two-time-scale approximations. Our result applies to algorithms such as descent-ascent and two-time-scale Lagrangian optimization.
  arXiv  Detail & Related papers  (2025-04-27T22:45:00Z)
• An improved quantum algorithm for linear autonomous differential equations via Padé approximation [0.0]
  The discretized solution can be represented by a product of matrix exponentials. The proposed algorithm approximates the matrix exponential by the diagonal Pad'e approximation. The complexity of the proposed algorithm is analyzed.
  arXiv  Detail & Related papers  (2025-04-09T14:54:27Z)
• Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices [14.25435308779899]
  Hilbert-space Gaussian Process (HGP) approach offers hyper-independent basis function approximation for speeding up GP inference. In this paper, we lower this dominating computational complexity to $mathcalO(NM)$ with no additional approximations. Our contribution provides a pure speed-up of several existing, widely used, GP approximations, without further approximations.
  arXiv  Detail & Related papers  (2024-08-05T09:45:31Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  We consider the spectral tail condition number, $kappa_ell$, defined as the ratio between the $ell$th largest and the smallest singular value of the matrix representing the system. Some of the implications of our result, and of the use of $kappa_ell$, include direct improvement over a fine-grained analysis of the Conjugate method.
  arXiv  Detail & Related papers  (2024-05-09T14:56:49Z)
• Tensor networks based quantum optimization algorithm [0.0]
  In optimization, one of the well-known classical algorithms is power iterations. We propose a quantum realiziation to circumvent this pitfall. Our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.
  arXiv  Detail & Related papers  (2024-04-23T13:49:11Z)
• An efficient quantum algorithm for generation of ab initio n-th order susceptibilities for non-linear spectroscpies [0.13980986259786224]
  We develop and analyze a fault-tolerant quantum algorithm for computing $n$-th order response properties. We use a semi-classical description in which the electronic degrees of freedom are treated quantum mechanically and the light is treated as a classical field.
  arXiv  Detail & Related papers  (2024-04-01T20:04:49Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  We give an input sparsity time sampling algorithm for approximating the Gram matrix corresponding to the $q$-fold column-wise tensor product of $q$ matrices. Our sampling technique relies on a collection of $q$ partially correlated random projections which can be simultaneously applied to a dataset $X$ in total time.
  arXiv  Detail & Related papers  (2022-02-09T15:26:03Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  Preconditioning is a highly effective step for any iterative method involving matrix-vector multiplication. We prove that preconditioning has an additional benefit that has been previously unexplored. It simultaneously can reduce variance at essentially negligible cost.
  arXiv  Detail & Related papers  (2021-07-01T06:43:11Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10: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.