Algorithms

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), and 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.

Abstract: We introduce the graph composition framework, a generalization of the st-connectivity framework for constructing quantum algorithms. Our framework constructs algorithms that solve a connectivity problem on an undirected graph, where the availability of each edge is computed by a span program. The key novelty of our framework is that the construction allows for amortization of the span programs’ costs, while at the same time avoiding build-up of errors due to composition. We give generic time-efficient implementations of algorithms generated through the graph composition framework in the quantum read-only memory model, which is a weaker assumption than the more common quantum random-access model. Along the way, we also simplify the span program algorithm by converting it to a transducer, and remove the dependence of its analysis on the effective spectral gap lemma. We use graph composition to unify existing quantum algorithmic frameworks. Surprisingly, we show that any randomized algorithm can be converted into an instance of the st-connectivity framework. Furthermore, we show that the st-connectivity framework subsumes the learning graph framework, and the weighted-decision-tree framework. We show that the graph composition framework subsumes part of the quantum divide-and-conquer framework, and that it is itself subsumed by the multidimensional quantum walk framework. Moreover, we show polynomial relations and separations between the optimal query complexities that can be achieved with several of these frameworks. Finally, we apply our techniques to give improved algorithms for various string-search problems, namely the Dyck-language recognition problem of depth 3, the 3-increasing subsequence problem, and the OR ◦ pSEARCH-problem. We also simplify existing quantum algorithms for the space-efficient directed st-connectivity problem, the pattern matching problem and the Σ∗ 20∗ 2Σ∗ -problem.