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

WORLD SCIENTIFIC eBooks

Two-State Problems

Published Apr 1, 2002• 0 citations
Publisher
DOI
10.1142/9789812778406_0007

Related papers

Two State Systems

WORLD SCIENTIFIC eBooks•Apr 29, 2014•0 citations

Method of areas for manipulating the entanglement properties of one copy of a two-particle pure entangled state

Lucién Hardy

We consider the problem of how to manipulate the entanglement properties of a general two-particle pure state, shared between Alice and Bob, by using only local operations at each end and classical communication between Alice and Bob. A method is developed in which this type of problem is found to be equivalent to a problem involving the cutting and pasting of certain shapes along with certain coloring problems. We consider two problems. First, we find the most general way of manipulating the state to obtain maximally entangled states. After such a manipulation, the entangled states $|11〉+|22〉+\ensuremath{\cdot}\ensuremath{\cdot}\ensuremath{\cdot}+|\mathrm{mm}〉$ are obtained with probability ${p}_{m}.$ We obtain an expression for the optimal average entanglement obtainable. Also, some results of Lo and Popescu (e-print quant-ph/9707038) pertaining to this problem are given simple geometric proofs. Second, we consider how to manipulate one two-particle entangled state $|\ensuremath{\psi}〉$ to another $|{\ensuremath{\psi}}^{\ensuremath{'}}〉$ with certainty. We derive Nielsen's theorem (which states a necessary and sufficient condition for this to be possible) using the method of areas.

arXiv:quant-ph/9903001•Physical Review A•Sep 1, 1999•69 citations

Two-message quantum interactive proofs and the quantum separability problem

Patrick M. Hayden, Kevin Milner, Mark M. Wilde

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.

Quantum Information and Computation•May 1, 2014•13 citations

More two-state systems

Richard P. Feynman

Basic Books•Jan 1, 2010•0 citations

Two-Message Quantum Interactive Proofs and the Quantum Separability Problem

Patrick M. Hayden, Kevin Milner, Mark M. Wilde

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 distinguish ability" 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.

arXiv:1211.6120•IEEE Conference on Computational Complexity (CCC)•Jun 1, 2013•26 citations

Two State Systems

WORLD SCIENTIFIC eBooks•Jan 1, 2013•0 citations
We consider the problem of how to manipulate the entanglement properties of a general two-particle pure state, shared between Alice and Bob, by using only local operations at each end and classical communication between Alice and Bob. A method is developed in which this type of problem is found to be equivalent to a problem involving the cutting and pasting of certain shapes along with certain coloring problems. We consider two problems. First, we find the most general way of manipulating the state to obtain maximally entangled states. After such a manipulation, the entangled states $|11〉+|22〉+\ensuremath{\cdot}\ensuremath{\cdot}\ensuremath{\cdot}+|\mathrm{mm}〉$ are obtained with probability pm.{p}_{m}.pm​. We obtain an expression for the optimal average entanglement obtainable. Also, some results of Lo and Popescu (e-print quant-ph/9707038) pertaining to this problem are given simple geometric proofs. Second, we consider how to manipulate one two-particle entangled state $|\ensuremath{\psi}〉$ to another $|{\ensuremath{\psi}}^{\ensuremath{'}}〉$ with certainty. We derive Nielsen's theorem (which states a necessary and sufficient condition for this to be possible) using the method of areas.
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.
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 distinguish ability" 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.