Testing quantum circuits and detecting insecure encryption
arXiv:1108.1052
Abstract
We show that computational problem of testing the behaviour of quantum circuits is hard for the class of problems known as QMA that can be verified efficiently with a quantum computer. This result is a generalization of the techniques previously used to prove the hardness of other problem on quantum circuits. We use this result to show the QMA-hardness of a weak version of the problem of detecting the insecurity of a symmetric-key quantum encryption system, or alternately the problem of determining when a quantum channel is not private. We also give a QMA protocol for the problem of detecting insecure encryption to show that it is QMA-complete.
15 pages
References in corpus (12)
- Universal Quantum Estimator
- Direct estimations of linear and non-linear functionals of a quantum state
- Randomizing quantum states: Constructions and applications
- Optimal Encryption of Quantum Bits
- Authentication of Quantum Messages
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- The computational difficulty of finding MPS ground states
- Identity check is QMA-complete
- Private Quantum Channels and the Cost of Randomizing Quantum Information
- Consistency of Local Density Matrices is QMA-complete
- Quantum Arthur-Merlin Games
- Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption