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:1611.07332 · Quantum Information and Computation

Robustness of QMA against witness noise

Friederike Anna Dziemba

Published Nov 1, 2017• 0 citations
arXivHTMLPDF

Abstract

Using the tool of concatenated stabilizer coding, we prove that the complexity class QMA remains unchanged even if every witness qubit is disturbed by constant noise. This result may not only be relevant for physical implementations of verifying protocols but also attacking the relationship between the complexity classes QMA, QCMA and BQP, which can be reformulated in this unified framework of a verifying protocol receiving a disturbed witness. While QCMA and BQP are described by fully dephasing and depolarizing channels on the witness qubits, respectively, our result proves QMA to be robust against 27% dephasing and 18% depolarizing noise.

DOI
10.26421/qic17.13-14-6

Related papers

Disturbed witnesses in quantum complexity theory

Friederike Anna Dziemba

QMA is the complexity class of computational problems that are efficiently verifiable by a quantum algorithm with the help of a witness in contrast to the smaller class BQP of problems efficiently solvable by a quantum algorithm without a witness. Like their classical counterparts NP and P, the class QMA is believed to be strictly larger than BQP, but the definitive answer remains one of the most fundamental open problems of complexity theory. An equality of QMA and BQP would imply that quantum computers can solve many physically and logically relevant problems efficiently, including the Local Hamiltonian problem and the Satisfiability problem for Boolean formulas. New approaches to gain more insight into the structure of BQP and QMA as well as which witness forms are sufficient for QMA are hence worth pursuing. This thesis comprises three research focuses: Firstly, we extend the uniform diagonalization theorem to complexity classes of promise problems in order to construct strictly intermediate problems between QMA and BQP under the assumption that these classes are unequal. The existence of strictly intermediate problems motivates our definition of noisy QMA classes, which form hierarchies of intermediate classes between QMA and BQP by restricting the witnesses to outputs of certain quantum channels. In our second research focus we apply the tool of concatenated coding to prove a bound on the witness noise up to which QMA stays robust. Besides a bound for general i.i.d. channels, we can prove that QMA stays robust if each witness qubit is disturbed by 18 % depolarizing or 27 % dephasing noise, while for complete depolarization or dephasing the noisy class obviously collapses to BQP and QCMA, respectively. In the third research focus we interpret the famous QPCP conjecture as robustness of the class QMA against high witness disturbance. Moreover, we consider a multiprover protocol by Fitzsimons and Vidick that constitutes a first step towards an important alternative formulation of the QPCP conjecture and achieve a reduction of the number of provers and an improvement of the acceptance probability for this protocol.

•Jan 1, 2019•0 citations

How to Classically Verify a Quantum Cat without Killing It

Yael Tauman Kalai, Dakshita Khurana, Justin Raizes

A quantum verifier decides membership in QMA using a (single) quantum witness state. This witness may be arbitrary, and no requirement is placed on it beyond its acceptance probability. A protocol claiming to classically verify QMA should offer the same guarantee: any witness that would convince a quantum verifier should also suffice to convince a classical verifier. Unfortunately, existing classical verification of quantum computation (CVQC) protocols behave quite differently from the original QMA verifier: they require many copies of the witness and destroy every one, effectively demanding that the prover solve the hard problem of witness duplication before verification can begin. We build a protocol to classically verify QMA languages that uses a single copy of the prover's QMA witness. Whenever the original QMA verifier accepts that witness with overwhelming probability, our protocol has negligible completeness and soundness errors and returns the witness negligibly disturbed after interaction with an honest verifier. The soundness of our CVQC is based on the post-quantum Learning With Errors (LWE) assumption. As an intermediate step of independent interest, we introduce witness-preserving classical arguments for NP which enable provers that start out with a superposition over NP witnesses to convince a verifier without disturbing their superposition.

quant-pharXiv:2602.09282•Feb 11, 2026•0 citations

QMA with subset state witnesses

Alex B. Grilo, Iordanis Kerenidis, Jamie Sikora

The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems. In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones. We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the "simpler" subset states, i.e. a uniform superposition over the elements of a subset of n-bit strings. Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA. We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class QMA$_1$.

arXiv:1410.2882•Oct 10, 2014•2 citations

QMA with Subset State Witnesses

Alex B. Grilo, Iordanis Kerenidis, Jamie Sikora

The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems.In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones.We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the "simpler" subset states, i.e. a uniform superposition over the elements of a subset of n-bit strings.Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA.We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class QMA 1 .

Chicago Journal of Theoretical Computer Science•Jan 1, 2016•3 citations

Susceptibility of qudit-qudit entanglement to quantum noise: insights from the negativity rank

Matthew Chen, Natalie Klco

One aspect of complexity for quantum many-body systems resides in their ability to exhibit entanglement, uniquely quantum correlations central to quantum computation. To quantitatively explore the diminishing effect that quantum noise has on entanglement resources, we focus on the negativity witness, an entanglement measure based on local time reversal transformations that provides a perfect witness in simple physical contexts. Beyond calculation of the negativity, we analyze the associated eigenvalue spectra of partially transposed density matrices for qudit-qudit bipartitions, finding that higher negativity rank provides greater(reduced) robustness to targeted(depolarizing) noise. In particular, we extend the maximum number of separable states that can be arbitrarily mixed into an entangled pure ensemble while retaining negativity to be exactly equal to the original negativity rank. Furthermore, we report how understanding the role of the negativity rank with respect to the completely depolarizing channel allows direct calculation of (1) certain noise boundaries for the Absolutely Positive Partial Transpose (APPT) subspace beyond which no unitary operator is capable of generating negativity and (2) the maximum qutrit-qutrit APPT purity. Beyond proving tight bounds and contributing to the ongoing search for APPT entanglement, these results expand our understanding of the nuanced relationship between computation with entanglement and practical environments for operating quantum devices.

quant-pharXiv:2610.10820•Oct 9, 2026•0 citations

Zero-Knowledge Proof Systems for QMA

Anne Broadbent, Zhengfeng Ji, Fang Song +1 more

Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration.

arXiv:1604.02804•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•44 citations
Using the tool of concatenated stabilizer coding, we prove that the complexity class QMA remains unchanged even if every witness qubit is disturbed by constant noise. This result may not only be relevant for physical implementations of verifying protocols but also attacking the relationship between the complexity classes QMA, QCMA and BQP, which can be reformulated in this unified framework of a verifying protocol receiving a disturbed witness. While QCMA and BQP are described by fully dephasing and depolarizing channels on the witness qubits, respectively, our result proves QMA to be robust against 27% dephasing and 18% depolarizing noise.
QMA is the complexity class of computational problems that are efficiently verifiable by a quantum algorithm with the help of a witness in contrast to the smaller class BQP of problems efficiently solvable by a quantum algorithm without a witness. Like their classical counterparts NP and P, the class QMA is believed to be strictly larger than BQP, but the definitive answer remains one of the most fundamental open problems of complexity theory. An equality of QMA and BQP would imply that quantum computers can solve many physically and logically relevant problems efficiently, including the Local Hamiltonian problem and the Satisfiability problem for Boolean formulas. New approaches to gain more insight into the structure of BQP and QMA as well as which witness forms are sufficient for QMA are hence worth pursuing. This thesis comprises three research focuses: Firstly, we extend the uniform diagonalization theorem to complexity classes of promise problems in order to construct strictly intermediate problems between QMA and BQP under the assumption that these classes are unequal. The existence of strictly intermediate problems motivates our definition of noisy QMA classes, which form hierarchies of intermediate classes between QMA and BQP by restricting the witnesses to outputs of certain quantum channels. In our second research focus we apply the tool of concatenated coding to prove a bound on the witness noise up to which QMA stays robust. Besides a bound for general i.i.d. channels, we can prove that QMA stays robust if each witness qubit is disturbed by 18 % depolarizing or 27 % dephasing noise, while for complete depolarization or dephasing the noisy class obviously collapses to BQP and QCMA, respectively. In the third research focus we interpret the famous QPCP conjecture as robustness of the class QMA against high witness disturbance. Moreover, we consider a multiprover protocol by Fitzsimons and Vidick that constitutes a first step towards an important alternative formulation of the QPCP conjecture and achieve a reduction of the number of provers and an improvement of the acceptance probability for this protocol.
A quantum verifier decides membership in QMA using a (single) quantum witness state. This witness may be arbitrary, and no requirement is placed on it beyond its acceptance probability. A protocol claiming to classically verify QMA should offer the same guarantee: any witness that would convince a quantum verifier should also suffice to convince a classical verifier. Unfortunately, existing classical verification of quantum computation (CVQC) protocols behave quite differently from the original QMA verifier: they require many copies of the witness and destroy every one, effectively demanding that the prover solve the hard problem of witness duplication before verification can begin. We build a protocol to classically verify QMA languages that uses a single copy of the prover's QMA witness. Whenever the original QMA verifier accepts that witness with overwhelming probability, our protocol has negligible completeness and soundness errors and returns the witness negligibly disturbed after interaction with an honest verifier. The soundness of our CVQC is based on the post-quantum Learning With Errors (LWE) assumption. As an intermediate step of independent interest, we introduce witness-preserving classical arguments for NP which enable provers that start out with a superposition over NP witnesses to convince a verifier without disturbing their superposition.
The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems. In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones. We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the "simpler" subset states, i.e. a uniform superposition over the elements of a subset of n-bit strings. Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA. We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class QMA1_11​.
The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems.In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones.We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the "simpler" subset states, i.e. a uniform superposition over the elements of a subset of n-bit strings.Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA.We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class QMA 1 .
One aspect of complexity for quantum many-body systems resides in their ability to exhibit entanglement, uniquely quantum correlations central to quantum computation. To quantitatively explore the diminishing effect that quantum noise has on entanglement resources, we focus on the negativity witness, an entanglement measure based on local time reversal transformations that provides a perfect witness in simple physical contexts. Beyond calculation of the negativity, we analyze the associated eigenvalue spectra of partially transposed density matrices for qudit-qudit bipartitions, finding that higher negativity rank provides greater(reduced) robustness to targeted(depolarizing) noise. In particular, we extend the maximum number of separable states that can be arbitrarily mixed into an entangled pure ensemble while retaining negativity to be exactly equal to the original negativity rank. Furthermore, we report how understanding the role of the negativity rank with respect to the completely depolarizing channel allows direct calculation of (1) certain noise boundaries for the Absolutely Positive Partial Transpose (APPT) subspace beyond which no unitary operator is capable of generating negativity and (2) the maximum qutrit-qutrit APPT purity. Beyond proving tight bounds and contributing to the ongoing search for APPT entanglement, these results expand our understanding of the nuanced relationship between computation with entanglement and practical environments for operating quantum devices.
Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration.