Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.06302

Robust subspace designs and the power of a unique small quantum witness

Simon Apers, Roman Edenhofer, Benjamin Mathieu-Bloise, Partha Mukhopadhyay

quant-phcs.CCcs.DSSubmitted Oct 5, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textAI use disclosedStrong assumptions
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.

Related papers

On the power of a unique quantum witness

Rahul Jain, Iordanis Kerenidis, Greg Kuperberg +3 more

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.

arXiv:0906.4425•International Conference on Supercomputing•Jun 24, 2009•5 citations

From Random Quantum Codes to Explicit qLDPC Codes via Local Properties

Fernando Granha Jeronimo, Xiaojuan Ma, Nikhil Shagrithaya

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 \subseteq 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.

cs.ITCross-listedarXiv:2609.40252•Oct 1, 2026•1 citation

The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings

Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandão +1 more

Valiant-Vazirani showed in 1985 \cite{VV85} that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions).We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA \cite{AN02}. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard, under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP \cite{Has07}. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values.Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.

arXiv:0810.4840•Quantum•Mar 17, 2022•32 citations

Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems

Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj +1 more

This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, ${\QCMA = \QCMA_1}$. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, \emph{e.g.}, ${\{\textrm{Hadamard, Toffoli, NOT}\}}$. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that \emph{additively} adjusts the success probability, which may be of independent interest.

arXiv:1111.5306•Quantum Information and Computation•May 1, 2012•47 citations

Quantum Worst-Case to Average-Case Reductions for All Linear Problems

Vahid R. Asadi, Alexander Golovnev, Tom Gur +2 more

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 $Ω(n^2)$ 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.

arXiv:2212.03348•Dec 6, 2022•1 citation

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems

William Gay, Fernando Granha Jeronimo

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)$, \[ \mathsf{StoqMA}(k) = \mathsf{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 $\mathcal{H}_1^{\otimes R} \otimes \mathcal{H}_2^{\otimes R} \otimes \cdots \otimes \mathcal{H}_k^{\otimes R}$ then there exists a separable state $τ$ on $\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k$ such that \[ \mathrm{Tr}\big(M(ρ_{\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k} - τ)\big) \le 2 \sqrt{\frac{k\, \log_2\dim(\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k)}{R-1}}, \] simultaneously for all non-negative effects $M$. For any such operator $M$, one can define the separately symmetric lift $\mathrm{SS}_R(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 $\mathsf{StoqMA}(k)$ verifiers can be absorbed into a polynomially larger one-witness $\mathsf{StoqMA}$ verification, while preserving an inverse polynomial completeness-soundness gap.

quant-pharXiv:2605.16249•May 18, 2026•2 citations
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\mathsf{NP}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\mathsf{C_= L}C=​L containment of Allender, Beals, and Ogihara (STOC'96) for general nullity testing through a simpler proof.
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 Qi:Cn→CkQ_i:\mathbb C^n\to\mathbb C^kQi​:Cn→Ck for which every kkk-dimensional subspace has few restrictions with small singular values. A Gaussian construction gives m=O(k(n−k)log⁡(nk))m=O(k(n-k)\log(nk))m=O(k(n−k)log(nk)) maps with robustness η=Θ(1/nk)\eta=\Theta(1/\sqrt{nk})η=Θ(1/nk​), with at most m/4m/4m/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(n4kO(k))O(n^4k^{O(k)})O(n4kO(k)) and robustness Ω(1/(k3/2n))\Omega(1/(k^{3/2}\sqrt n))Ω(1/(k3/2n​)).
A kernel-peeling lemma supplies rank-k′k'k′ perturbations that reduce nullity by exactly k′k'k′ while retaining a nonzero singular-value gap of at least η2γ/3\eta^2\gamma/3η2γ/3. Combined with circuit-to-Hamiltonian and kernel verification, this proves FewQUMAL1⊆RLUQUMAL1\mathsf{FewQ_U MAL}_1\subseteq\mathsf{RL}^{\mathsf{UQ_U MAL}_1}FewQU​MAL1​⊆RLUQU​MAL1​. Applications include randomized oracle upper bounds for conditioned nullity testing and linear-system feasibility, and an alternative proof of classical nullity testing in C=L\mathsf{C_=L}C=​L.
Polynomial-size explicit robust designs for arbitrary kkk 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.
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.
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⊆CS \subseteq CS⊆C, in which local constraints are imposed on physical representatives while independence is measured in the logical quotient C/SC/SC/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.
Valiant-Vazirani showed in 1985 \cite{VV85} that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions).We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA \cite{AN02}. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard, under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP \cite{Has07}. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values.Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.
This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, ${\QCMA = \QCMA_1}$. This holds under any gate set with which the Hadamard and arbitrary classical reversible transformations can be exactly implemented, \emph{e.g.}, {Hadamard, Toffoli, NOT}{\{\textrm{Hadamard, Toffoli, NOT}\}}{Hadamard, Toffoli, NOT}. The proof is quantumly nonrelativizing, and uses a simple but novel quantum technique that \emph{additively} adjusts the success probability, which may be of independent interest.
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)Ω(n^2)Ω(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.
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)k = k(n)k=k(n), StoqMA(k)=StoqMA. \mathsf{StoqMA}(k) = \mathsf{StoqMA}. 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\mathcal{H}_1^{\otimes R} \otimes \mathcal{H}_2^{\otimes R} \otimes \cdots \otimes \mathcal{H}_k^{\otimes R}H1⊗R​⊗H2⊗R​⊗⋯⊗Hk⊗R​ then there exists a separable state τττ on H1⊗⋯⊗Hk\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_kH1​⊗⋯⊗Hk​ such that Tr(M(ρH1⊗⋯⊗Hk−τ))≤2k log⁡2dim⁡(H1⊗⋯⊗Hk)R−1, \mathrm{Tr}\big(M(ρ_{\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k} - τ)\big) \le 2 \sqrt{\frac{k\, \log_2\dim(\mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_k)}{R-1}}, Tr(M(ρH1​⊗⋯⊗Hk​​−τ))≤2R−1klog2​dim(H1​⊗⋯⊗Hk​)​​, simultaneously for all non-negative effects MMM. For any such operator MMM, one can define the separately symmetric lift SSR(M)\mathrm{SS}_R(M)SSR​(M) whose largest eigenvalue approximates the maximum acceptance probability of MMM 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)\mathsf{StoqMA}(k)StoqMA(k) verifiers can be absorbed into a polynomially larger one-witness StoqMA\mathsf{StoqMA}StoqMA verification, while preserving an inverse polynomial completeness-soundness gap.