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.
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.
Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory. The quantum setting is even more challenging since it is highly desirable that the quantum code be an LDPC code.
Local coordinate-wise linear (LCL) [Levi, Mosheiff, and Shagrithaya, FOCS 2025] witnesses provide a unifying language for many coding-theoretic properties, from distance to list decoding and list recovery. In particular, it provides a framework to study properties of random linear codes, which achieve optimal parameters for many properties of linear codes.
For CSS quantum codes, however, a local witness has two distinct ranks: its physical rank before quotienting by stabilizers and its logical rank after quotienting. We develop a quantum version of the LCL framework for nested spaces S⊆C, in which local constraints are imposed on physical representatives while independence is measured in the logical quotient C/S. The resulting theory gives a threshold theorem for random CSS codes, and as a consequence shows that the per-sector rate threshold is equal to the classical rate threshold. We also define a quantum analogue of subspace design [Guruswami and Xing, STOC 2013] and show that they can be described in a natural manner within the quantum-LCL framework.
Finally, we give explicit constructions for arbitrary folded quantum-LCL properties, in a manner similar to the LCL derandomization of [Jeronimo and Shagrithaya, STOC 2026]. As a consequence, we obtain the first explicit constructions of quantum list-decodable codes and list-recoverable codes that have optimal list sizes, in addition to explicit quantum subspace design codes. We note that all our explicit constructions are qLDPC codes, an important property for quantum error-correcting codes.
In a celebrated paper, Valiant and Vazirani raised the question of whether the difficulty of NP-complete problems was due to the wide variation of the number of witnesses of their instances. They gave a strong negative answer by showing that distinguishing between instances having zero or one witnesses is as hard as recognizing NP, under randomized reductions. We consider the same question in the quantum setting and investigate the possibility of reducing quantum witnesses in the context of the complexity class QMA, the quantum analogue of NP. The natural way to quantify the number of quantum witnesses is the dimension of the witness subspace W in some appropriate Hilbert space H. We present an efficient deterministic procedure that reduces any problem where the dimension d of W is bounded by a polynomial to a problem with a unique quantum witness. The main idea of our reduction is to consider the Alternating subspace of the d-th tensor power of H. Indeed, the intersection of this subspace with the d-th tensor power of W is one-dimensional, and therefore can play the role of the unique quantum witness.
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.
It has been known for almost three decades that many NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit C with n uninitialized inputs, poly(n) gates, and treewidth t, one can compute in time (δn)exp(O(t)) a classical assignment y∈{0,1}n that maximizes the acceptance probability of C up to a δ additive factor. In particular, our algorithm runs in polynomial time if t is constant and 1/poly(n)<δ<1. For unrestricted values of t, this problem is known to be complete for the complexity class QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t=O(logn) even when δ is constant.
On the other hand, we show that given a n-input quantum circuit C of treewidth t=O(logn), and a constant δ<1/2, it is QMA-complete to determine whether there exists a quantum state ∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣φ⟩ is greater than 1−δ, or whether for every such state ∣φ⟩, the acceptance probability of C∣φ⟩ is less than δ. As a consequence, under the widely believed assumption that QMA=NP, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
It has been known for almost three decades that many NP-hard optimization problems can be solved in polynomial time when restricted to structures of constant treewidth. In this work we provide the first extension of such results to the quantum setting. We show that given a quantum circuit C with n uninitialized inputs, poly(n) gates, and treewidth t, one can compute in time (δn)exp(O(t)) a classical assignment y∈{0,1}n that maximizes the acceptance probability of C up to a δ additive factor. In particular, our algorithm runs in polynomial time if t is constant and 1/poly(n)<δ<1. For unrestricted values of t, this problem is known to be complete for the complexity class QCMA, a quantum generalization of MA. In contrast, we show that the same problem is NP-complete if t=O(logn) even when δ is constant. On the other hand, we show that given a n-input quantum circuit C of treewidth t=O(logn), and a constant δ<1/2, it is QMA-complete to determine whether there exists a quantum state ∣φ⟩∈(Cd)⊗n such that the acceptance probability of C∣φ⟩ is greater than 1−δ, or whether for every such state ∣φ⟩, the acceptance probability of C∣φ⟩ is less than δ. As a consequence, under the widely believed assumption that QMA=NP, we have that quantum witnesses are strictly more powerful than classical witnesses with respect to Merlin-Arthur protocols in which the verifier is a quantum circuit of logarithmic treewidth.
Interference and entanglement are among the most fundamental properties of quantum mechanics. In this work, we investigate the power of interference in the role of detecting entanglement in the context of quantum Merlin-Arthur verification. In particular, we show that unentanglement gives no additional power to stoquastic Merlin-Arthur proof systems, whose restriction to a classical gate set results in entrywise non-negative acceptance operators and non-negative optimal witnesses, therein removing destructive interference from the verification process. Our results show that for any polynomial number of unentangled witnesses k=k(n), StoqMA(k)=StoqMA. The analytic core of this result is a new non-negative de Finetti theorem for separately bosonic states. If a mixed state ρ is supported on the tensor product of symmetric subspaces of H1⊗R⊗H2⊗R⊗⋯⊗Hk⊗R then there exists a separable state τ on H1⊗⋯⊗Hk such that Tr(M(ρH1⊗⋯⊗Hk−τ))≤2R−1klog2dim(H1⊗⋯⊗Hk), simultaneously for all non-negative effects M. For any such operator M, one can define the separately symmetric lift SSR(M) whose largest eigenvalue approximates the maximum acceptance probability of M over product states within the same error bound. Such a lift can be approximated by a stoquastic verifier, giving that product-state constraint of StoqMA(k) verifiers can be absorbed into a polynomially larger one-witness StoqMA verification, while preserving an inverse polynomial completeness-soundness gap.