Testing non-isometry is QMA-complete

DOI10.1007/978-3-642-18073-6_6zbMATH Open1309.68077arXiv0910.3740OpenAlexW1631902221MaRDI QIDQ3070977FDOQ3070977

Authors: Bill Rosgen 

Publication date: 28 January 2011

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

Abstract: Determining the worst-case uncertainty added by a quantum circuit is shown to be computationally intractable. This is the problem of detecting when a quantum channel implemented as a circuit is close to a linear isometry, and it is shown to be complete for the complexity class QMA of verifiable quantum computation. This is done by relating the problem of detecting when a channel is close to an isometry to the problem of determining how mixed the output of the channel can be when the input is a pure state. How mixed the output of the channel is can be detected by a protocol making use of the swap test: this follows from the fact that an isometry applied twice in parallel does not affect the symmetry of the input state under the swap operation.

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

Recommendations

• "NON-IDENTITY-CHECK" IS QMA-COMPLETE
• Testing quantum circuits and detecting insecure encryption
• Quantum interactive proofs and the complexity of separability testing
• Distinguishing short quantum computations
• Two QCMA-complete problems

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Cited In (3)

• "NON-IDENTITY-CHECK" IS QMA-COMPLETE
• Exact non-identity check is NQP-complete
• Testing quantum circuits and detecting insecure encryption

This page was built for publication: Testing non-isometry is QMA-complete

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