Robustness of QMA against witness noise
arXiv:1611.07332 · doi:10.26421/QIC17.13-14
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.
arXiv comment24 pages, 3 figures
References in corpus (20)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Improved Simulation of Stabilizer Circuits
- A Theory of Quantum Error-Correcting Codes
- Quantum Networks for Elementary Arithmetic Operations
- Stabilizer Codes and Quantum Error Correction
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Improved classical simulation of quantum circuits dominated by Clifford gates
- Efficient Networks for Quantum Factoring
- Fast Quantum Modular Exponentiation
- The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
- Quantum NP - A Survey
- Fast versions of Shor's quantum factoring algorithm
- Semidefinite programs for completely bounded norms
- The Quantum PCP Conjecture
- Further extensions of Clifford circuits and their classical simulation complexities
- 3-Local Hamiltonian is QMA-complete
- Quantum Probabilistic Subroutines and Problems in Number Theory
- Quantum Merlin-Arthur with noisy channel
- An Algorithm for Constructing Polynomial Systems Whose Solution Space Characterizes Quantum Circuits
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 , controlled-, 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