(pp0361-0383)
Adam D.
Bookatz
In this paper we give an overview of the quantum computational
complexity class QMA and a description of known QMA-complete problems to
date (The reader is invited to share more proven QMA-complete problems
with the author). Such problems are believed to be difficult to solve,
even with a quantum computer, but have the property that if a purported
solution to the problem is given, a quantum computer would easily be
able to verify whether it is correct. An attempt has been made to make
this paper as self-contained as possible so that it can be accessible to
computer scientists, physicists, mathematicians, and quantum chemists.
Problems of interest to all of these professions can be found here.
Research Articles:
Two-message quantum interactive proofs and the quantum separability
problem
(pp0384-0416)
Patrick Hayden, Kevin
Milner, and 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.
Periodicity and perfect state transfer in quantum walks on variants of
cycles (pp0417-0438)
Katharine E. Barr, Tim
J. Proctor, Daniel Allen, and Viv M. Kendon
We systematically investigated perfect state transfer between
antipodal nodes of discrete time quantum walks on variants of the cycles
$C_4$, $C_6$ and $C_8$ for three choices of coin operator. Perfect state
transfer was found, in general, to be very rare, only being preserved
for a very small number of ways of modifying the cycles. We observed
that some of our useful modifications of $C_4$ could be generalised to
an arbitrary number of nodes, and present three families of graphs which
admit quantum walks with interesting dynamics either in the continuous
time walk, or in the discrete time walk for appropriate selections of
coin and initial conditions. These dynamics are either periodicity,
perfect state transfer, or very high fidelity state transfer. These
families are modifications of families known not to exhibit periodicity
or perfect state transfer in general. The robustness of the dynamics is
tested by varying the initial state, interpolating between structures
and by adding decoherence.
Quantum algorithms for search with wildcards and combinatorial group
testing (pp0439-0453)
Andris
Ambainis and Ashley Montanaro
We consider two combinatorial problems. The first we call ``search
with wildcards'': given an unknown $n$-bit string $x$, and the ability
to check whether any subset of the bits of $x$ is equal to a provided
query string, the goal is to output $x$. We give a nearly optimal $O(\sqrt{n}
\log n)$ quantum query algorithm for search with wildcards, beating the
classical lower bound of $\Omega(n)$ queries. Rather than using
amplitude amplification or a quantum walk, our algorithm is ultimately
based on the solution to a state discrimination problem. The second
problem we consider is combinatorial group testing, which is the task of
identifying a subset of at most $k$ special items out of a set of $n$
items, given the ability to make queries of the form ``does the set $S$
contain any special items?''\ for any subset $S$ of the $n$ items. We
give a simple quantum algorithm which uses $O(k)$ queries to solve this
problem, as compared with the classical lower bound of $\Omega(k \log(n/k))$
queries.
The witness of sudden change of geometric quantum correlation
(pp0454-0466)
Chang-shui Yu, Bo Li,
and Heng Fan
In this paper, we give a sufficient and necessary condition
(witness) for the sudden change of geometric quantum discord by
considering mathematical definition of the discontinuity of a function.
Based on the witness, we can find out various sudden changes of quantum
correlation by considering both the Markovian and the non-Markovian
cases. In particular, we can accurately find out critical points of the
sudden changes even though they are not quite obvious in the graphical
representation. In addition, one can also find that sudden change of
quantum correlation, like the frozen quantum correlation, strongly
depends on the choice of the quantum correlation measure.
An improved query for the hidden subbroup problem
(pp0467-0492)
Asif Shakeel
The Hidden Subgroup Problem (HSP) is at the forefront of problems in
quantum algorithms. In this paper, we introduce a new query, the \textit{character}
query, generalizing the well-known phase kickback trick that was first
used successfully to efficiently solve Deutsch's problem. An equal
superposition query with $\vert 0 \rangle$ in the response register is
typically used in the ``standard method" of single-query algorithms for
the HSP. The proposed character query improves over this query by
maximizing the success probability of subgroup identification under a
uniform prior, for the HSP in which the oracle functions take values in
a finite abelian group. We apply our results to the case when the
subgroups are drawn from a set of conjugate subgroups and obtain a
success probability greater than that found by Moore and Russell.
Can quantum entanglement implement classical correlated equilibria?
(pp0493-0516)
Alan Deckelbaum
We ask whether players of a classical game can partition a pure
quantum state to implement classical correlated equilibrium
distributions. The main contribution of this work is an impossibility
result: we provide an example of a classical correlated equilibrium that
cannot be securely implemented without useful information leaking
outside the system. We study the model where players of a classical
complete information game initially share an entangled pure quantum
state. Players may perform arbitrary local operations on their
subsystems, but no direct communication (either quantum or classical) is
allowed. We explain why, for the purpose of implementing classical
correlated equilibria, it is desirable to restrict the initial state to
be pure and to restrict communication. In this framework, we define the
concept of pure quantum correlated equilibrium (PQCE) and show that in a
normal form game, any outcome distribution implementable by a PQCE can
also be implemented by a classical correlated equilibrium (CE), but that
the converse is false. We extend our analysis to extensive form games,
and compare the power of PQCE to extensive form classical correlated
equilibria (EFCE) and immediate-revelation extensive form correlated
equilibria (IR-EFCE).
Hardness of approximation for quantum problems
(pp0517-0540)
Sevag Gharibian and
Julia Kempe
The polynomial hierarchy plays a central role in classical
complexity theory. Here, we define a quantum generalization of the
polynomial hierarchy, and initiate its study. We show that not only are
there natural complete problems for the second level of this quantum
hierarchy, but that these problems are in fact hard to approximate.
Using the same techniques, we also obtain hardness of approximation for
the class QCMA. Our approach is based on the use of dispersers, and is
inspired by the classical results of Umans regarding hardness of
approximation for the second level of the classical polynomial hierarchy
[Umans, FOCS 1999]. The problems for which we prove hardness of
approximation for include, among others, a quantum version of the
Succinct Set Cover problem, and a variant of the local Hamiltonian
problem with hybrid classical-quantum ground states.