Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces robust subspace designs, a quantitative extension of subspace designs that ensures a family of subspaces has limited proximity to any given subspace of a fixed dimension. The authors provide both probabilistic and explicit constructions for these robust designs. Their primary application is a quantum space-bounded variant of the Valiant-Vazirani theorem, enabling the isolation of a unique witness for quantum Merlin-Arthur protocols with perfect completeness and a non-trivial acceptance gap.
A unique small quantum witness can certify Merlin's claims in space-bounded quantum computation, preserving hardness for $\mathsf{NP}$-like problems.
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.