arXiv:2610.06302
Robust subspace designs and the power of a unique small quantum witness
Simon Apers, Roman Edenhofer, Benjamin Mathieu-Bloise, Partha Mukhopadhyay
Abstract
The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of subspaces that have small intersection with any given subspace of a fixed dimension. We introduce \emph{robust subspace designs}. Informally, these are a quantitative extension in which we demand that not too many subspaces of the family contain directions that lie close to any given subspace of a fixed dimension. We give a probabilistic construction of such a robust subspace design of polynomial size, as well as a non-trivial explicit construction of superpolynomial size. Our main application of this new concept is a quantum space-bounded variant of the Valiant-Vazirani theorem (Theor.Comput.Sci.'86), which shows that restricting $\mathsf{NP}$-complete problems to instances with at most one accepting witness preserves hardness under randomized reductions. For quantum witnesses, the analogous quantity is the dimension of an accepting witness subspace. We use our probabilistic construction of robust subspace designs to isolate a unique witness for space-bounded quantum Merlin-Arthur protocols with perfect completeness and an acceptance gap outside their perfectly accepting subspace. As further applications, we give a randomized reduction of well-conditioned nullity testing to space-bounded quantum Merlin-Arthur protocols with perfect completeness. Using a similar idea, we find that ordinary subspace designs allow us to recover the classical $\mathsf{C_= L}$ containment of Allender, Beals, and Ogihara (STOC'96) for general nullity testing through a simpler proof.
AI Summary
The paper asks whether a quantum accepting subspace can be reduced to a unique witness without asymptotically enlarging the witness register. It addresses logarithmic-space unitary verifiers with perfect completeness and an acceptance gap on the orthogonal complement of the perfectly accepting subspace—not general quantum witness isolation. Its main tool is a robust subspace design: a family of norm-bounded maps $Q_i:\mathbb C^n\to\mathbb C^k$ for which every $k$-dimensional subspace has few restrictions with small singular values. A Gaussian construction gives $m=O(k(n-k)\log(nk))$ maps with robustness $\eta=\Theta(1/\sqrt{nk})$, with at most $m/4$ small singular values in total across the family. The proof combines Gaussian singular-value counting bounds with a Grassmannian net; finite-precision sampling makes the construction randomized-logspace computable. A deterministic construction combining four-wise-independent sketching and coordinate projections has size $O(n^4k^{O(k)})$ and robustness $\Omega(1/(k^{3/2}\sqrt n))$. A kernel-peeling lemma supplies rank-$k'$ perturbations that reduce nullity by exactly $k'$ while retaining a nonzero singular-value gap of at least $\eta^2\gamma/3$. Combined with circuit-to-Hamiltonian and kernel verification, this proves $\mathsf{FewQ_U MAL}_1\subseteq\mathsf{RL}^{\mathsf{UQ_U MAL}_1}$. Applications include randomized oracle upper bounds for conditioned nullity testing and linear-system feasibility, and an alternative proof of classical nullity testing in $\mathsf{C_=L}$. Polynomial-size explicit robust designs for arbitrary $k$ remain open. Extension to polynomial-time quantum witness isolation would require handling exponentially large witness spaces without losing efficiency or the verification gap; known quantum-oracle barriers also constrain black-box approaches.
GPT 5.6 Sol, 6.0 Astra and 6.1 Sol were also used to improve the presentation of parts of the manuscript and to help identify errors.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.