Robust subspace designs and the power of a unique small quantum witness
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 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 C= L containment of Allender, Beals, and Ogihara (STOC'96) for general nullity testing through a simpler proof.
Related
- Hamiltonian-Guided Leverage Embedding: Robust Subspace Compression for Efficient QAOA Parameter Estimation
- Quantum thermodynamics of ergotopy for a relativistic battery as a witness to Unruh–Hawking thermality in curved (A)dS spacetimes
- Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness & An Algorithm for Torsion Witness
- White paper: 1-10 Hz matter-wave interferometer to test the spin entanglement witness for quantum gravity
- Mirror subspace diagonalization: a real-time quantum Krylov algorithm with near-optimal sampling cost
BibTeX
@misc{apers2026robust,
title = {{Robust subspace designs and the power of a unique small quantum witness}},
author = {Simon Apers and Roman Edenhofer and Benjamin Mathieu-Bloise and Partha Mukhopadhyay},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06302},
eprint = {2610.06302},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06302},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Robust subspace designs and the power of a unique small quantum witness
AU - Simon Apers
AU - Roman Edenhofer
AU - Benjamin Mathieu-Bloise
AU - Partha Mukhopadhyay
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06302
UR - https://arxiv.org/abs/2610.06302
AB - 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 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 C_= L containment of Allender, Beals, and Ogihara (STOC'96) for general nullity testing through a simpler proof.
ER -