Testing non-isometry is QMA-complete

DOI10.1007/978-3-642-18073-6_6MaRDI QIDQ3070977zbMATH OpenOpenAlexFDO

Authors Bill Rosgen

Publication date 28 January 2011

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

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

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)

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.

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

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)