Longest common substring (), longest palindrome substring (), and Ulam distance () are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for and are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact $${{\tilde{O}}}(\sqrt{n})$$O~(n) time algorithm for , we prove that needs at least time $$\tilde{\Omega }(n^{2/3})$$Ω~(n2/3) even for 0/1 strings.

We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: We give a new distributed algorithm that finds a c-coloring in χ-chromatic graphs in Õ(n^1/α) rounds, with α = ⌊c−1/χ − 1⌋. We prove that any distributed algorithm for this problem requires Ω(n^1/α) rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or c-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.

Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been “dequantized” in the past few years. These dequantization results typically hold when classical algorithms can access the data via length-squared sampling. This assumption, which is standard in the field of randomized linear algebra, means that for a unit-norm vector \(u\in\mathbb{C}^{n}\), we can sample from the distribution \(p_u\colon\{1,\ldots,n\}\to [0,1]\) defined as \(p_u(i)=|u(i)|^2\) for each \(i\in\{1,\ldots,n\}\). Since this distribution corresponds to the distribution obtained by measuring the quantum state |\(u\)> in the computational basis, length-squared sampling access gives a reasonable classical analogue to the kind of quantum access considered in many quantum algorithms for linear algebra problems. In this work we investigate how robust these dequantization results are. We introduce the notion of approximate length-squared sampling, where classical algorithms are only able to sample from a distribution close to the ideal distribution in total variation distance. While quantum algorithms are natively robust against small perturbations, current techniques in dequantization are not. Our main technical contribution is showing how many techniques from randomized linear algebra can be adapted to work under this weaker assumption as well. We then use these techniques to show that the recent low-rank dequantization framework by Chia, Gilyén, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based on the Quantum Singular Value Transformation, can be generalized to the case of approximate length-squared sampling access to the input. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms, including quantum algorithms for recommendation systems, supervised clustering and low-rank matrix inversion.

Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this Letter, we give quantum algorithms which, given any k -body Hamiltonian H , compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any ϵ > 0 , our algorithms return, with high probability, an estimate of the ground state energy of H within additive error ϵ M , or a quantum state with the corresponding energy. Here, M is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the run-time of our algorithms scales as 2 c n / 2 for c < 1 , yielding the first quantum algorithms for low-energy estimation breaking a standard square root Grover speedup for unstructured search. The core of our approach is remarkably simple, and relies on showing that an extensive fraction of the interactions can be neglected with a controlled error. What this ultimately implies is that even arbitrary k -local Hamiltonians have structure in their low energy space, in the form of an exponential-dimensional low energy subspace. Published by the American Physical Society 2025