Testing quantum circuits and detecting insecure encryption

DOI10.1007/978-3-642-35656-8_6MaRDI QIDQ3455199zbMATH OpenOpenAlexFDO

Authors Bill Rosgen

Publication date 3 December 2015

Published in Theory of Quantum Computation, Communication, and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.1052

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94) Quantum gates (81P65)

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.

Recommendations

• Testing non-isometry is QMA-complete
• "NON-IDENTITY-CHECK" IS QMA-COMPLETE
• Self-testing of Quantum Circuits
• Model checking quantum Markov chains
• How to Verify a Quantum Computation

Cites work

• "NON-IDENTITY-CHECK" IS QMA-COMPLETE
• Coding theorem and strong converse for quantum channels
• Consistency of Local Density Matrices Is QMA-Complete
• Quantum Arthur-Merlin games
• Randomizing quantum states: constructions and applications
• Testing non-isometry is QMA-complete
• The Complexity of the Local Hamiltonian Problem

Cited in

(3)

• Generalized quantum Arthur-Merlin games
• scientific article; zbMATH DE number 5320168 (Why is no real title available?)
• Testing non-isometry is QMA-complete

This page was built for publication: Testing quantum circuits and detecting insecure encryption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3455199)