Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0910.3740

Testing non-isometry is QMA-complete

Bill Rosgen

Published Oct 20, 2009• 0 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.0910.3740

Related papers

Testing quantum circuits and detecting insecure encryption

Bill Rosgen

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.

arXiv:1108.1052•Aug 4, 2011•2 citations

Quantum interactive proofs and the complexity of separability testing

Gus Gutoski, Patrick M. Hayden, Kevin Milner +1 more

We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), and QSZK), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either QMA-complete or QMA(2)-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by employing prior work on entanglement purification protocols to prove that for each n-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in n.

Civil War Book Review•Jan 1, 2015•20 citations

"NON-IDENTITY-CHECK" IS QMA-COMPLETE

Dominik Janzing, Paweł Wocjan, Thomas Beth

We describe a computational problem that is complete for the complexity class QMA, a quantum generalization of NP. It arises as a natural question in quantum computing and quantum physics. "Non-identity-check" is the following decision problem: Given a classical description of a quantum circuit (a sequence of elementary gates), determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is "non-equivalence check": given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that non-equivalence check is also in QMA and hence QMA-complete.

International Journal of Quantum Information•Sep 1, 2005•74 citations

On the Hardness of Distinguishing Mixed-State Quantum Computations

Bill Rosgen, John Watrous

This paper considers the following problem. Two mixed-state quantum circuits Q/sub 0/ and Q/sub 1/ are given, and the goal is to determine which of two possibilities holds: (i) Q/sub 0/ and Q/sub 1/ act nearly identically on all possible quantum state inputs, or (ii) there exists some input state /spl rho/ that Q/sub 0/ and Q/sub 1/ transform into almost perfectly distinguishable outputs. This may be viewed as an abstraction of the problem that asks, given two discrete quantum mechanical processes described by sequences of local interactions, are the processes effectively the same or are they different? We prove that this promise problem is complete for the class QIP of problems having quantum interactive proof systems, and is therefore PSPACE-hard. This is in contrast to the fact that the analogous problem for classical (probabilistic) circuits is in AM, and for unitary quantum circuits is in QMA.

arXiv:cs/0407056•IEEE Conference on Computational Complexity (CCC)•Jun 28, 2005•66 citations

Quantum interactive proofs and the complexity of separability testing

Gus Gutoski, Patrick M. Hayden, Kevin Milner +1 more

We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including $\mathsf{BQP}$, $\mathsf{QMA}$, $\mathsf{QMA}(2)$, and $\mathsf{QSZK}$), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either $\mathsf{QMA}$-complete or $\mathsf{QMA}(2)$-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by employing prior work on entanglement purification protocols to prove that for each $n$-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in $n$.

arXiv:1308.5788•Theory of Computing•Jan 1, 2015•17 citations

Efficient Quantum State Identity Testing

Shih-Han Hung, Ming-Hsien Tsai

We study the following quantum state identity problem: given access to copies of $n$ unknown pure quantum states, the goal is to determine whether every pair has fidelity at least $1-\varepsilon$ or some pair has fidelity at most $\varepsilon$. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter $\varepsilon\in(0,1/4)$, we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes $O(\log(n/δ)\log(2/δ))$ copies of each input state to succeed with probability at least $1-δ$. The second uses the Schur transform to reduce the sample complexity to $O(\log(n/δ))$, through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of $Ω(\log(n/δ))$ for any quantum algorithm with failure probability at most $δ\le 1/2-c$, for any constant $c>0$, establishing that the second algorithm achieves the optimal dependence on both $n$ and $δ$ for fixed $\varepsilon$.

quant-pharXiv:2610.04597•Oct 6, 2026•0 citations
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.
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.
We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), and QSZK), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either QMA-complete or QMA(2)-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by employing prior work on entanglement purification protocols to prove that for each n-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in n.
We describe a computational problem that is complete for the complexity class QMA, a quantum generalization of NP. It arises as a natural question in quantum computing and quantum physics. "Non-identity-check" is the following decision problem: Given a classical description of a quantum circuit (a sequence of elementary gates), determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is "non-equivalence check": given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that non-equivalence check is also in QMA and hence QMA-complete.
This paper considers the following problem. Two mixed-state quantum circuits Q/sub 0/ and Q/sub 1/ are given, and the goal is to determine which of two possibilities holds: (i) Q/sub 0/ and Q/sub 1/ act nearly identically on all possible quantum state inputs, or (ii) there exists some input state /spl rho/ that Q/sub 0/ and Q/sub 1/ transform into almost perfectly distinguishable outputs. This may be viewed as an abstraction of the problem that asks, given two discrete quantum mechanical processes described by sequences of local interactions, are the processes effectively the same or are they different? We prove that this promise problem is complete for the class QIP of problems having quantum interactive proof systems, and is therefore PSPACE-hard. This is in contrast to the fact that the analogous problem for classical (probabilistic) circuits is in AM, and for unitary quantum circuits is in QMA.
We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP\mathsf{BQP}BQP, QMA\mathsf{QMA}QMA, QMA(2)\mathsf{QMA}(2)QMA(2), and QSZK\mathsf{QSZK}QSZK), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either QMA\mathsf{QMA}QMA-complete or QMA(2)\mathsf{QMA}(2)QMA(2)-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by employing prior work on entanglement purification protocols to prove that for each nnn-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in nnn.
We study the following quantum state identity problem: given access to copies of nnn unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε1-\varepsilon1−ε or some pair has fidelity at most ε\varepsilonε. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter ε∈(0,1/4)\varepsilon\in(0,1/4)ε∈(0,1/4), we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes O(log⁡(n/δ)log⁡(2/δ))O(\log(n/δ)\log(2/δ))O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ1-δ1−δ. The second uses the Schur transform to reduce the sample complexity to O(log⁡(n/δ))O(\log(n/δ))O(log(n/δ)), through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of Ω(log⁡(n/δ))Ω(\log(n/δ))Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤1/2−cδ\le 1/2-cδ≤1/2−c, for any constant c>0c>0c>0, establishing that the second algorithm achieves the optimal dependence on both nnn and δδδ for fixed ε\varepsilonε.