Robustness of QMA against witness noise

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.

24 pages, 3 figures

References in corpus (8)

• Instantaneous non-local computation of low T-depth quantum circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Fast Quantum Modular Exponentiation
• Quantum NP - A Survey
• Semidefinite programs for completely bounded norms
• Further extensions of Clifford circuits and their classical simulation complexities
• 3-Local Hamiltonian is QMA-complete
• Quantum Merlin-Arthur with noisy channel

Cited by in corpus (19)

• Advances in Quantum Cryptography
• Long-Distance Continuous-Variable Quantum Key Distribution over 202.81 km of Fiber
• Towards Large-scale Functional Verification of Universal Quantum Circuits
• Continuous-variable measurement-device-independent quantum key distribution: Composable security against coherent attacks
• Using and reusing coherence to realize quantum processes
• Probabilistic distillation of quantum coherence
• Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates
• Quantifying the resource content of quantum channels: An operational approach
• Polarization attack on continuous-variable quantum key distribution
• Composable security analysis of continuous-variable measurement-device-independent quantum key distribution with squeezed states for coherent attacks
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
• Gaussian one-way thermal quantum cryptography with finite-size effects
• Quantifying coherence in terms of the pure-state coherence
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• Advantages and limitations of quantum routing
• Coherence manipulation with dephasing-covariant operations
• Cohering and decohering power of massive scalar fields under instantaneous interactions
• Continuous-variable nonlocality and contextuality
• The Interplay between Quantum Contextuality and Wigner Negativity