|
Two-message quantum interactive proofs and the quantum separability
problem
(pp0384-0416)
Patrick Hayden, Kevin
Milner, and Mark M. Wilde
doi:
https://doi.org/10.26421/QIC14.5-6-2
Abstracts:
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.
Key words:
quantum separability problem, two-message quantum
interactive proofs, quantum statistical zero knowledge, separable,
entangled |
