Accelerating Classical and Quantum Tensor PCA

• URL: http://arxiv.org/abs/2602.10366v1
• Date: Tue, 10 Feb 2026 23:35:30 GMT
• Title: Accelerating Classical and Quantum Tensor PCA
• Authors: Matthew B. Hastings,
• Abstract summary: We show how to accelerate both classical and quantum algorithmsally, while maintaining the same quartic separation between them.<n>We only prove these speedups for detection, rather than recovery, but we give a strong plausibility argument that our algorithm achieves recovery also.
• Score: 0.40611352512781873
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Spectral methods are a leading approach for tensor PCA with a ``spiked" Gaussian tensor. The methods use the spectrum of a linear operator in a vector space with exponentially high dimension and in Ref. 1 it was shown that quantum algorithms could then lead to an exponential space saving as well as a quartic speedup over classical. Here we show how to accelerate both classical and quantum algorithms quadratically, while maintaining the same quartic separation between them. That is, our classical algorithm here is quadratically faster than the original classical algorithm, while the quantum algorithm is eigth-power faster than the original classical algorithm. We then give a further modification of the quantum algorithm, increasing its speedup over the modified classical algorithm to the sixth power. We only prove these speedups for detection, rather than recovery, but we give a strong plausibility argument that our algorithm achieves recovery also. Note added: After this paper was prepared, A. Schmidhuber pointed out to me Ref. 3. This improves the best existing bounds on the spectral norm of a certain random operator. Because the norm of this operator enters into the runtime, with this improvement on the norm, we no longer have a provable polynomial speedup. Our results are phrased in terms of certain properties of the spectrum of this operator (not merely the largest eigenvalue but also the density of states). So, if these properties still hold, the speedup still holds. Rather than modify the paper, I have left it unchanged but added a section at the end discussing the needed property of density of states and considering for which problems (there are several problems for which this kind of quartic quantum speedup has been used and the techniques here will likely be applicable to several of them) the property is likely to hold.

Related papers

• 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)
• Quantum Dissipative Search via Lindbladians [0.0]
  We analyze a purely dissipative quantum random walk on an unstructured classical search space.<n>We show that certain jump operators make the quantum process replicate a classical one, while others yield differences between open quantum (OQRW) and classical random walks.<n>We also clarify a previously observed quadratic speedup, demonstrating that OQRWs are no more efficient than classical search.
  arXiv  Detail & Related papers  (2024-07-16T14:39:18Z)
• 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)
• Quantum Bayesian Optimization [64.58749619145908]
  We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
  arXiv  Detail & Related papers  (2023-10-09T03:10:42Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs. Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
  arXiv  Detail & Related papers  (2023-04-17T16:42:05Z)
• Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer [0.157286095422595]
  We show that some quantum SDO solvers provide speedups in the low-precision regime.<n>We exploit this fact to exponentially improve the dependence of their algorithm on precision.<n>A quantum implementation of our algorithm exhibits a worst case running time of $mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$.
  arXiv  Detail & Related papers  (2023-01-10T23:12:05Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions [4.2698418800007865]
  We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. We modify the classical algorithm of vStefankovivc, Vempala and Vigoda to improve its sample complexity. We quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei.
  arXiv  Detail & Related papers  (2020-09-23T17:27:28Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.