Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.07273

End-to-end quantum algorithms for tensor problems

Fontana, Enrico, Sivaprasad Omanakuttan, Junhyung Lyle Kim, Joseph Sullivan, Michael A. Perlin, Ruslan Shaydulin, Shouvanik Chakrabarti

Published Oct 8, 2025• 0 citations
arXivHTMLPDF

Abstract

We present a comprehensive end-to-end quantum algorithm for tensor problems, including tensor PCA and planted kXOR, that achieves potential superquadratic quantum speedups over classical methods. We build upon prior works by Hastings~(\textit{Quantum}, 2020) and Schmidhuber~\textit{et al.}~(\textit{Phys.~Rev.~X.}, 2025), we address key limitations by introducing a native qubit-based encoding for the Kikuchi method, enabling explicit quantum circuit constructions and non-asymptotic resource estimation. Our approach substantially reduces constant overheads through a novel guiding state preparation technique as well as circuit optimizations, reducing the threshold for a quantum advantage. We further extend the algorithmic framework to support recovery in sparse tensor PCA and tensor completion, and generalize detection to asymmetric tensors, demonstrating that the quantum advantage persists in these broader settings. Detailed resource estimates show that 900 logical qubits, $\sim 10^{15}$ gates and $\sim 10^{12}$ gate depth suffice for a problem that classically requires $\sim 10^{23}$ FLOPs. The gate count and depth for the same problem without the improvements presented in this paper would be at least $10^{19}$ and $10^{18}$ respectively. These advances position tensor problems as a candidate for quantum advantage whose resource requirements benefit significantly from algorithmic and compilation improvements; the magnitude of the improvements suggest that further enhancements are possible, which would make the algorithm viable for upcoming fault-tolerant quantum hardware.

DOI
10.48550/arxiv.2510.07273

Related papers

Quartic quantum speedups for planted inference

Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari +1 more

We describe a quantum algorithm for the Planted Noisy kXOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (4th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings [Has20], by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy kXOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•1 citation

Accelerating Classical and Quantum Tensor PCA

Matthew B. Hastings

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.

quant-pharXiv:2602.10366•Feb 12, 2026•0 citations

Quartic Quantum Speedups for Planted Inference

Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari +1 more

We describe a quantum algorithm for the Planted Noisy k XOR Problem (also known as Sparse Learning Parity with Noise) that achieves a nearly (fourth-power) speedup over the best known classical algorithm while using exponentially less space. Our work generalizes and simplifies prior work of Hastings [], by building on his quantum algorithm for the tensor principal component analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the guided sparse Hamiltonian problem. Since the Planted Noisy k XOR Problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to superquadratic quantum attacks.

arXiv:2406.19378•Physical Review X•Jun 2, 2025•4 citations

Harnessing problem structure for end-to-end quantum speed-ups

Qifan Jiang, Xiao-Ming Zhang, Debin Xiang +3 more

Quantum algorithms can offer substantial computational speed-ups, yet these advantages may disappear once the cost of structure-agnostic classical data encoding is taken into account. Real-world problem instances, however, often possess rich internal structure. This raises a fundamental question: can such structure be harnessed to make quantum speed-ups survive end-to-end cost accounting? Here we show that it can. We introduce a general framework for structure-aware quantum data encoding that compiles compact recursive descriptions of problem structure into efficient state-preparation circuits, translating structural information directly into reduced encoding complexity. For the uncapacitated facility-location problem, structure-agnostic encoding admits a classical dequantization that eliminates the quadratic quantum speed-up, whereas exploiting the underlying problem structure restores this advantage even when state-preparation costs are included. More broadly, the same framework prepares structured quantum states for combinatorial optimization that capture non-trivial relations among constraints, including group balance, conflicts and synergistic rewards, extending previously reported super-polynomial quantum advantages to broader classes of objectives. These results establish exploitable problem structure as a computational resource for quantum algorithms and provide a systematic route towards realizing quantum advantage in data-intensive problems.

quant-pharXiv:2609.40105•Oct 1, 2026•0 citations

Quartic quantum speedups for community detection

Alexander Schmidhuber, Alexander Zlokapa

Community detection is a foundational problem in data science. Its natural extension to hypergraphs captures higher-order correlations beyond pairwise interactions. In this work, we develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup over the best known classical algorithm, along with superpolynomial savings in space. Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as Tensor PCA and $p$XORSAT to a broad family of generalized stochastic block models. To demonstrate (near) optimality of this method, we prove matching lower bounds (up to logarithmic factors) in the low-degree framework, showing that the algorithm saturates a smooth statistical-computational tradeoff. The quantum speedup arises from a quantized version of the Kikuchi method and is based on the efficient preparation of a guiding state correlated with the underlying community structure. Our work suggests that prior quantum speedups using the Kikuchi method are sufficiently robust to encompass a broader set of problems than previously believed; we conjecture that a quantity known as marginal order characterizes the existence of these quantum speedups.

arXiv:2510.08494•Oct 9, 2025•0 citations

Scalable Tensor Ring Methods for Variational Quantum Algorithms

Dheeraj Peddireddy

Variational quantum algorithms (VQAs) have emerged as a promising candidate for realizing quantum advantage in machine learning and optimization tasks on noisy intermediate-scale quantum (NISQ) devices. Despite significant theoretical promise, the practical impact of VQAs is constrained by the exponential growth in computational resources required for classical simulation, the onset of barren plateaus in parameterized landscapes, and the inherent difficulties of scaling classical optimization routines to circuits with many qubits and layers. Addressing these intertwined challenges is essential for both advancing quantum algorithm development and extracting actionable physical insights from modern quantum hardware.This dissertation develops, analyzes, and validates an efficient framework based on approximate tensor ring decompositions for the classical simulation, training, and benchmarking of variational quantum circuits and eigensolvers. The first component of this work formalizes the representation of quantum states and gates within a cyclic tensor ring structure, enabling the compression of parameterized quantum circuits to linear scaling in both qubit number and circuit depth, while preserving essential quantum correlations and entanglement structure. Gate operations are efficiently approximated via truncated singular value decomposition, and novel algorithms for forward propagation and gradient-based training in the tensor ring domain are developed. These methodological advances are systematically benchmarked on standard supervised learning tasks, including Iris and MNIST datasets, and compared to conventional statevector and matrix product state baselines, resulting in competitive accuracy and orders-of-magnitude reductions in simulation cost. Extending this framework, the dissertation also introduces a scalable method for gradient evaluation in variational quantum eigensolvers (VQE) using the approximate tensor ring representation. This approach enables the simulation and training of large circuits for combinatorial optimization problems, supporting practical qubit counts and circuit depths inaccessible to traditional simulation methods. Detailed experiments on the Maximum-Cut optimization problem demonstrate both the computational efficiency and robustness of the tensor ring framework in nontrivial optimization landscapes.Collectively, the results establish approximate tensor ring decomposition as a versatile and powerful framework for advancing quantum machine learning and discrete optimization, supporting both pre-deployment benchmarking on classical hardware and algorithm design for next-generation quantum devices. This work provides a foundation for the further exploration of scalable quantum-classical hybrid algorithms, with implications for quantum simulation, optimization, and beyond.

•Jan 20, 2026•0 citations
We present a comprehensive end-to-end quantum algorithm for tensor problems, including tensor PCA and planted kXOR, that achieves potential superquadratic quantum speedups over classical methods. We build upon prior works by Hastings~(\textit{Quantum}, 2020) and Schmidhuber~\textit{et al.}~(\textit{Phys.~Rev.~X.}, 2025), we address key limitations by introducing a native qubit-based encoding for the Kikuchi method, enabling explicit quantum circuit constructions and non-asymptotic resource estimation. Our approach substantially reduces constant overheads through a novel guiding state preparation technique as well as circuit optimizations, reducing the threshold for a quantum advantage. We further extend the algorithmic framework to support recovery in sparse tensor PCA and tensor completion, and generalize detection to asymmetric tensors, demonstrating that the quantum advantage persists in these broader settings. Detailed resource estimates show that 900 logical qubits, ∼1015\sim 10^{15}∼1015 gates and ∼1012\sim 10^{12}∼1012 gate depth suffice for a problem that classically requires ∼1023\sim 10^{23}∼1023 FLOPs. The gate count and depth for the same problem without the improvements presented in this paper would be at least 101910^{19}1019 and 101810^{18}1018 respectively. These advances position tensor problems as a candidate for quantum advantage whose resource requirements benefit significantly from algorithmic and compilation improvements; the magnitude of the improvements suggest that further enhancements are possible, which would make the algorithm viable for upcoming fault-tolerant quantum hardware.
We describe a quantum algorithm for the Planted Noisy kXOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (4th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings [Has20], by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy kXOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks.
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.
We describe a quantum algorithm for the Planted Noisy k XOR Problem (also known as Sparse Learning Parity with Noise) that achieves a nearly (fourth-power) speedup over the best known classical algorithm while using exponentially less space. Our work generalizes and simplifies prior work of Hastings [], by building on his quantum algorithm for the tensor principal component analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the guided sparse Hamiltonian problem. Since the Planted Noisy k XOR Problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to superquadratic quantum attacks.
Quantum algorithms can offer substantial computational speed-ups, yet these advantages may disappear once the cost of structure-agnostic classical data encoding is taken into account. Real-world problem instances, however, often possess rich internal structure. This raises a fundamental question: can such structure be harnessed to make quantum speed-ups survive end-to-end cost accounting? Here we show that it can. We introduce a general framework for structure-aware quantum data encoding that compiles compact recursive descriptions of problem structure into efficient state-preparation circuits, translating structural information directly into reduced encoding complexity. For the uncapacitated facility-location problem, structure-agnostic encoding admits a classical dequantization that eliminates the quadratic quantum speed-up, whereas exploiting the underlying problem structure restores this advantage even when state-preparation costs are included. More broadly, the same framework prepares structured quantum states for combinatorial optimization that capture non-trivial relations among constraints, including group balance, conflicts and synergistic rewards, extending previously reported super-polynomial quantum advantages to broader classes of objectives. These results establish exploitable problem structure as a computational resource for quantum algorithms and provide a systematic route towards realizing quantum advantage in data-intensive problems.
Community detection is a foundational problem in data science. Its natural extension to hypergraphs captures higher-order correlations beyond pairwise interactions. In this work, we develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup over the best known classical algorithm, along with superpolynomial savings in space. Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as Tensor PCA and pppXORSAT to a broad family of generalized stochastic block models. To demonstrate (near) optimality of this method, we prove matching lower bounds (up to logarithmic factors) in the low-degree framework, showing that the algorithm saturates a smooth statistical-computational tradeoff. The quantum speedup arises from a quantized version of the Kikuchi method and is based on the efficient preparation of a guiding state correlated with the underlying community structure. Our work suggests that prior quantum speedups using the Kikuchi method are sufficiently robust to encompass a broader set of problems than previously believed; we conjecture that a quantity known as marginal order characterizes the existence of these quantum speedups.
Variational quantum algorithms (VQAs) have emerged as a promising candidate for realizing quantum advantage in machine learning and optimization tasks on noisy intermediate-scale quantum (NISQ) devices. Despite significant theoretical promise, the practical impact of VQAs is constrained by the exponential growth in computational resources required for classical simulation, the onset of barren plateaus in parameterized landscapes, and the inherent difficulties of scaling classical optimization routines to circuits with many qubits and layers. Addressing these intertwined challenges is essential for both advancing quantum algorithm development and extracting actionable physical insights from modern quantum hardware.This dissertation develops, analyzes, and validates an efficient framework based on approximate tensor ring decompositions for the classical simulation, training, and benchmarking of variational quantum circuits and eigensolvers. The first component of this work formalizes the representation of quantum states and gates within a cyclic tensor ring structure, enabling the compression of parameterized quantum circuits to linear scaling in both qubit number and circuit depth, while preserving essential quantum correlations and entanglement structure. Gate operations are efficiently approximated via truncated singular value decomposition, and novel algorithms for forward propagation and gradient-based training in the tensor ring domain are developed. These methodological advances are systematically benchmarked on standard supervised learning tasks, including Iris and MNIST datasets, and compared to conventional statevector and matrix product state baselines, resulting in competitive accuracy and orders-of-magnitude reductions in simulation cost. Extending this framework, the dissertation also introduces a scalable method for gradient evaluation in variational quantum eigensolvers (VQE) using the approximate tensor ring representation. This approach enables the simulation and training of large circuits for combinatorial optimization problems, supporting practical qubit counts and circuit depths inaccessible to traditional simulation methods. Detailed experiments on the Maximum-Cut optimization problem demonstrate both the computational efficiency and robustness of the tensor ring framework in nontrivial optimization landscapes.Collectively, the results establish approximate tensor ring decomposition as a versatile and powerful framework for advancing quantum machine learning and discrete optimization, supporting both pre-deployment benchmarking on classical hardware and algorithm design for next-generation quantum devices. This work provides a foundation for the further exploration of scalable quantum-classical hybrid algorithms, with implications for quantum simulation, optimization, and beyond.