RECORD
Two-message quantum interactive proofs and the quantum separability problem
Quantum Physics · Submitted 26 Nov 2012
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. One might then wonder, does this quantum circuit produce a state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. We then prove that the promise problem is hard for the class of promise problems with "quantum statistical zero knowledge" (QSZK) proof systems by demonstrating a polynomial-time Karp reduction from the QSZK-complete promise problem "quantum state distinguishability" to our quantum separability problem. By exploiting Knill's efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard with respect to Cook reductions. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. We also consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. | background 1.00 | 0.08 | 0.02 | asserted 0.63 |
| s1 | One might then wonder, does this quantum circuit produce a state that is separable or entangled? | background 0.72 | 0.04 | 0.02 | speculative 0.53 |
| s2 | Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. | result 0.80 | 0.72 | 0.68 | hedged possibility 0.72 |
| s3 | We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. | contribution 0.72 | 0.95 | 0.08 | asserted 1.00 |
| s4 | We then prove that the promise problem is hard for the class of promise problems with "quantum statistical zero knowledge" (QSZK) proof systems by demonstrating a polynomial-time Karp reduction from the QSZK-complete promise problem "quantum state distinguishability" to our quantum separability problem. | method 0.51 | 0.93 | 0.14 | asserted 1.00 |
| s5 | By exploiting Knill's efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard with respect to Cook reductions. | result 0.56 | 0.90 | 0.07 | asserted 0.98 |
| s6 | Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. | interpretation 0.61 | 0.92 | 0.76 | asserted 1.00 |
| s7 | We also consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. | contribution 0.96 | 0.75 | 0.03 | asserted 0.67 |
| s8 | We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. | result 0.94 | 0.94 | 0.13 | asserted 1.00 |
| s9 | Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem. | result 0.74 | 0.94 | 0.06 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v5
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. One might then wonder, does this quantum circuit produce a state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. We then prove that the promise problem is hard for the class of promise problems with "quantum statistical zero knowledge" (QSZK) proof systems by demonstrating a polynomial-time Karp reduction from the QSZK-complete promise problem "quantum state distinguishability" to our quantum separability problem. By exploiting Knill's efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard with respect to Cook reductions. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. We also consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem.
Human review
References
How the literature uses it
13 arXiv papers cite this in 44 sentences
Papers citing it · 28 sentences without a confident label
Builds on it 3 papers
-
These completeness results build upon the work of [ref] , which exhibits a separability testing problem in $QIP(2)$ and another problem complete for $QIP$.
Quantum interactive proofs and the complexity of separability testing · Conclusion · 0.99
-
Our results thus generalize previous results in the context of unextendibility and entanglement of bipartite quantum states [ref] ; additionally, we go on to clarify the relation between our results and previous ones (Section [ref]).
Testing symmetry on quantum computers · Introduction · 0.85
-
For the last question above, note that one might be able to show a similar collapse theorem even with $(2)$ when the verifier cannot use quantum operations at all during the first $(m-2)$ turns (by extending the argument due to Goldwasser and Sipser [ref] to replace the classical interaction of the first $(m-2)$ turns by an $m$-turn classical public-coin interaction, and then applying arguments similar to those in this paper, using some appropriate $(2)$-complete problem like the Close Image problem [ref] ).
Generalized Quantum Arthur-Merlin Games · Conclusion · 0.89
Uses its method or tool 1 paper
-
We now justify the claim in [ref] using a method similar to that in [ref] .
Quantum interactive proofs and the complexity of separability testing · Containment in $QMA$ · 0.80
Compares with it 4 papers
-
By contrast, the two-message single-prover quantum interactive proof of [ref] depends critically upon the ability of the verifier to exchange two messages with the prover.
Quantum interactive proofs and the complexity of separability testing · Overview of results · 1.00
-
It was argued in [ref] that the acceptance probability of the test there is bounded from above by the maximum $k$-extendible fidelity, which is consistent with the fact that the set of $k$-Bose extendible states is contained in the set of $k$-extendible states and our observation here that the acceptance probability of the test in [ref] is equal to the maximum $k$-Bose extendible fidelity.
A Menagerie of Symmetry Testing Quantum Algorithms · $k$-Extendibility Test for Bipartite States · 0.93
-
It was argued in [ref] that the acceptance probability of the test there is bounded from above by the maximum $k$-extendible fidelity, which is consistent with the fact that the set of $k$-Bose extendible states is contained in the set of $k$-extendible states and our observation here that the acceptance probability of the test in [ref] is equal to the maximum $k$-Bose extendible fidelity.
Testing symmetry on quantum computers · $k$-Extendibility test for bipartite states · 0.92
Cites it as background 7 papers
-
To recall the prior developments, the authors of [ref] showed that, for most quantum complexity classes that involve interaction with a computationally-unbounded prover, including BQP, QMA, QSZK, QMA(2), and QIP, there exists a corresponding natural separability testing problem that is complete for the class.
Quantum Computational Complexity and Symmetry · Introduction · 0.92
-
Recall the definition of the one-way LOCC version of the Separable State problem [ref] :
Quantum interactive proofs and the complexity of separability testing · A short quantum game for the one-way LOCC version of Separable State · 0.87
-
Both detection [ref] and decision [ref] problems of entanglement have been considered, and the computational complexity of the latter problems have been analyzed.
Entanglement of $\pi$-LME states and the SAT problem · Introduction · 0.98
What it cites · 21 sentences without a confident label
Builds on 1 paper
-
This lemma follows from Theorem 2 of Brandão and Harrow [ref] , and we provide a proof for it in the appendix.
Quantum de Finetti Theorems under Local Measurements with Applications · Introduction · 0.90
Uses the method or tool of 3 papers
-
The verifier then performs phase estimation over the symmetric group [ref] (also known as the “permutation test” [ref] ) on the registers $C$, $C_2$, …, $C_k$, using the qubits in system $D$ as the control.
The Efficiency of Quantum Identity Testing of Multiple States · Introduction · 1.00
-
The verifier then performs phase estimation over the symmetric group [ref] (also known as the “permutation test” [ref] ) on the registers $C$, $C_2$, …, $C_k$, using the qubits in system $D$ as the control.
Quantum measurements and the Abelian Stabilizer Problem · Introduction · 1.00
-
The verifier then performs phase estimation over the symmetric group [ref] (also known as the “permutation test” [ref] ) on the registers $C$, $C_2$, …, $C_k$, using the qubits in system $D$ as the control.
Stabilisation of Quantum Computations by Symmetrisation · Introduction · 1.00
Cites as background 15 papers
-
When the state is specified as the rational entries of a density matrix acting on a finite-dimensional Hilbert space $ℋ=ℋ_A⊗ℋ_B$, one can formulate several variations of the problem, all of them being known collectively as the quantum separability problem, and characterize their computational complexity [ref] .
Strong NP-Hardness of the Quantum Separability Problem · Introduction · 0.89
-
When the state is specified as the rational entries of a density matrix acting on a finite-dimensional Hilbert space $ℋ=ℋ_A⊗ℋ_B$, one can formulate several variations of the problem, all of them being known collectively as the quantum separability problem, and characterize their computational complexity [ref] .
A quasipolynomial-time algorithm for the quantum separability problem · Introduction · 0.89
-
When the state is specified as the rational entries of a density matrix acting on a finite-dimensional Hilbert space $ℋ=ℋ_A⊗ℋ_B$, one can formulate several variations of the problem, all of them being known collectively as the quantum separability problem, and characterize their computational complexity [ref] .
Classical deterministic complexity of Edmonds' problem and Quantum Entanglement · Introduction · 0.89
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.