We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands in contrast to the classical setting, where such results are only known for a small number of specific problems or restricted computational models. En route, we obtain a tight $Ω(n^2)$ lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem. Our techniques strengthen and generalise the recently introduced additive combinatorics framework for classical worst-case to average-case reductions (STOC 2022) to the quantum setting. We rely on quantum singular value transformations to construct quantum algorithms for linear verification in superposition and learning Bogolyubov subspaces from noisy quantum oracles. We use these tools to prove a quantum local correction lemma, which lies at the heart of our reductions, based on a noise-robust probabilistic generalisation of Bogolyubov's lemma from additive combinatorics.
We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands in contrast to the classical setting, where such results are only known for a small number of specific problems or restricted computational models. En route, we obtain a tight Ω(n2) lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem. Our techniques strengthen and generalise the recently introduced additive combinatorics framework for classical worst-case to average-case reductions (STOC 2022) to the quantum setting. We rely on quantum singular value transformations to construct quantum algorithms for linear verification in superposition and learning Bogolyubov subspaces from noisy quantum oracles. We use these tools to prove a quantum local correction lemma, which lies at the heart of our reductions, based on a noise-robust probabilistic generalisation of Bogolyubov's lemma from additive combinatorics.
We study the problem of constructing worst-case algorithms from average-case algorithms. Prior to this work, such reductions were only known for a small number of specific problems or restricted computational models. In contrast, we show that for quantum computation, all linear problems admit worst-case to average-case reductions. Specifically, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. En route, we obtain a tight Ω(n2) lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem.
We study quantum random self-reductions for linear problems over finite fields. Let M∈Fn×n be an arbitrary matrix, and let O be an oracle that agrees with the linear map x↦Mx on an ε-fraction of inputs x∼Fn. Given coherent access to O and coherent entry access to M, we give a uniform quantum reduction that computes Mx on any prescribed input x with probability at least 2/3 in time O(nT1/3), for n≤T≤n3/2 and constant field size and ε, where T is the cost of one coherent query to O. In particular, when T=O(n), the reduction runs in time O(n4/3), improving the O(n3/2+T) reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024).
Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.
Worst-case to average-case reductions are a cornerstone of complexity theory, providing a bridge between worst-case hardness and average-case computational difficulty. While recent works have demonstrated such reductions for fundamental problems using deep tools from ad- ditive combinatorics, these approaches often suffer from substantial complexity and suboptimal overheads. In this work, we focus on the quantum setting, and provide a new reduction for the Matrix-Vector Multiplication problem that is more efficient, and conceptually simpler than previous constructions. By adapting hardness self-amplification techniques to the quantum do- main, we obtain a quantum worst-case to average-case reduction with improved dependence on the success probability, laying the groundwork for broader applications in quantum fine-grained complexity.
The linear problem specified by an n × n matrix M over a finite field is the problem of computing the product of M and a given vector x. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit that computes M x on an ε-fraction of inputs x for a positive constant ε, we construct a randomized linear-size circuit that computes M x for all inputs x with high probability. This resolves the open problem posed by Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA’24), who presented quantum n1.5-time random self-reductions for all linear problems. Somewhat surprisingly, we also demonstrate the quantum advantage of their quantum reduction over classical uniform algorithms, by proving that any classical subquadratic-time random self-reduction requires the advice complexity of Ω(log(1/ε) · logn), as long as the field size is at most 1/ε. We complement this advice complexity lower bound by presenting (1) a random self-reduction with the optimal advice complexity of O(log(1/ε) · logn) and (2) a uniform random self-reduction over a large finite field.
The security of efficient post-quantum cryptographic primitives, particularly those based on the Ring Learning With Errors (Ring-LWE) problem, relies fundamentally on the presumed intractability of the Shortest Vector Problem (SVP) over ideal lattices. This monograph investigates the hardness of Ideal-SVP in the presence of quantum adversaries. We rigorously analyze the worst-case to average-case reductions that underpin the security of ideal lattice-based schemes, extending classical Gaussian smoothing arguments to the quantum setting. Specifically, we examine the impact of quantum sieving algorithms and the Quantum Fourier Transform (QFT) on the algebraic structure of number fields. While quantum algorithms provide a quadratic speedup for general lattice sieving, we argue that the additional algebraic structure of ideal lattices does not yield a catastrophic collapse in hardness under current quantum reduction models. We present a synthesis of recent results concerning the lower bounds of quantum query complexity for Ideal-SVP, establishing that for cyclotomic fields of degree n, the problem remains hard up to sub-exponential factors, thereby validating the asymptotic security of structured lattice cryptography.
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∈Cn , we can sample from the distribution pu:{1,…,n}→[0,1] defined as pu(i)=∣u(i)∣2 for each i∈{1,…,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.