arXiv:2611.14411 · v1

Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized $k$-Orthogonal Vectors

算术化 k-正交向量问题的均匀量子平均情形细粒度困难性

首次提交 2026-11-11 01:52

版本更新 2026-11-11 01:52

雷达观测 2026-11-11 13:07

摘要

We study exact evaluation of the arithmetized $k$-Orthogonal Vectors polynomial $FOV^k$ of Ball et al. (2017, 2018). For every fixed integer $k \geq 3$, set $d(n) = \left \lceil \log^2 n \right \rceil$. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant $\varepsilon > 0$, no uniform quantum algorithm runs in $O(n^{k/2 - \varepsilon})$ time on every input and evaluates this polynomial correctly with probability at least $3 / 4$ over a uniformly random input in $\mathbb F_{p(n)}^{knd(n)}$ and the algorithm's internal randomness, for all sufficiently large $n$. This holds when $p(n)$ is the smallest prime greater than $n^{k - 1}$ and when it is the smallest prime greater than $n^k$. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo $p(n)$; otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.

作者备注：21 pages