*
Research Articles:*

**The complexity of stoquastic
local Hamiltonian problems**
(pp0361-0385)

S.
Bravyi, D.P. DiVincenzo, R. Oliveira, and B.M. Terhal

We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN)
in the special case when a Hamiltonian obeys the condition that all
off-diagonal matrix elements in the standard basis are real and
non-positive. We will call such Hamiltonians, which are common in the
natural world, *stoquastic*. An equivalent characterization of
stoquastic Hamiltonians is that they have an entry-wise non-negative
Gibbs density matrix for any temperature. We prove that LH-MIN for
stoquastic Hamiltonians belongs to the complexity class \AM{}--- a
probabilistic version of \NP{} with two rounds of communication between
the prover and the verifier. We also show that $2$-local stoquastic LH-MIN
is hard for the class \MA. With the additional promise of having a
polynomial spectral gap, we show that stoquastic LH-MIN belongs to the
class \POSTBPP=\BPPpath --- a generalization of \BPP{} in which a
post-selective readout is allowed. This last result also shows that any
problem solved by adiabatic quantum computation using stoquastic
Hamiltonians is in PostBPP.

**Generation and detection of photonic
qutrit states by linear optics**
(pp0386-0398)

Y.-T.
Chen and G. Bjork

We address the problem of generation and detection of the four mutually
unbiased biphoton polarization-qutrit bases by linear optics. First, the
generation of the bases is studied. Our numeric results show that the
linear optics method can be used to generate the 4 mutually unbiased
basis qutrit states probabilistically with high fidelity. Second, we
investigate whether or not linear polarization-optics components are
sufficient to realize the simultaneous detection of the qutrit states
forming a complete basis. Analytical results show that every state in
two of the bases, namely only half of the 4 mutually unbiased bases
qutrit states can be identified.

**Trade-off between the tolerance of
located and unlocated errors in nondegenrate quantum**
(pp0399-0410)

H.L.
Haselgrove and P.P. Rohde

In a recent study [Rohde et al., quant-ph/0603130 (2006)] of several
quantum error correcting protocols designed for tolerance against qubit
loss, it was shown that these protocols have the undesirable effect of
magnifying the effects of depolarization noise. This raises the question
of which general properties of quantum error-correcting codes might
explain such an apparent trade-off between tolerance to located and
unlocated error types. We extend the counting argument behind the
well-known quantum Hamming bound to derive a bound on the weights of
combinations of located and unlocated errors which are correctable by
nondegenerate quantum codes. Numerical results show that the bound gives
an excellent prediction to which combinations of unlocated and located
errors can be corrected {\em with high probability} by certain large
degenerate codes. The numerical results are explained partly by showing
that the generalized bound, like the original, is closely connected to
the information-theoretic quantity the {\em quantum coherent
information}. However, we also show that as a measure of the exact
performance of quantum codes, our generalized Hamming bound is provably
far from tight.

**Constructions for quantum computing
with symmetrized gates**
(pp0411-0429)

G.
Ivanyos, A.B. Nagy, and L. Ronyai

We investigate constructions for simulating quantum computers with a
polynomial slowdown on ensembles composed of qubits on which symmetrized
versions of one- and two-qubit gates can be performed. The simulation is
based on taking Lie commutators of symmetrized Hamiltonians to extract
Hamiltonians at desired local positions. During the simulation, only a
part of the qubits can be used for storing information, the others are
left unchanged by the commutators. We propose constructions for various
symmetry groups where a pretty large fraction of the qubits can be used.
As a few of the other qubits need to be set to one, our construction
requires individual initialization of some of the qubits.

**An extremal result for geometries in
the one-way measurement model**
(pp0430-0437)

N.
de Beaudrap and M. Pei

We present an extremal result for the class of graphs $G$ which
(together with some specified sets of input and output vertices, $I$ and
$O$) have a certain ``flow'' property introduced by Danos and Kashefi
for the one-way measurement model of quantum computation. The existence
of a flow for a triple $(G,I,O)$ allows a unitary embedding to be
derived from any choice of measurement bases allowed in the one-way
measurement model. We prove an upper bound on the number of edges that a
graph $G$ may have, in order for a triple $(G,I,O)$ to have a flow for
some $I, O \subseteq V(G)$, in terms of the number of vertices in $G$
and $O$. This implies that finding a flow for a triple $(G,I,O)$ when $\lvert
I \rvert = \lvert O \rvert = k$ (corresponding to unitary
transformations in the measurement model) and $\lvert V(G) \rvert = n$
can be performed in time $O(k^2 n)$, improving the earlier known bound
of $O(km)$ given in \cite{B06a}, where $m = \lvert E(G) \rvert$.

**How a Clebsch-Gordan transform helps
to solve the Heisenberg hidden subgroup problem**
(pp0438-0467)

D.
Bacon

It has recently been shown that quantum computers can efficiently solve
the Heisenberg hidden subgroup problem, a problem whose classical query
complexity is exponential. This quantum algorithm was discovered within
the framework of using pretty good measurements for obtaining optimal
measurements in the hidden subgroup problem. Here we show how to solve
the Heisenberg hidden subgroup problem using arguments based instead on
the symmetry of certain hidden subgroup states. The symmetry we consider
leads naturally to a unitary transform known as the Clebsch-Gordan
transform over the Heisenberg group. This gives a new representation
theoretic explanation for the pretty good measurement derived algorithm
for efficiently solving the Heisenberg hidden subgroup problem and
provides evidence that Clebsch-Gordan transforms over finite groups are
a new primitive in quantum algorithm design.

**A quantum repeater based on
decoherence free subspaces**
(pp0468-0488)

U.
Dorner, A. Klein, and D. Jaksch

We study a quantum repeater which is based on decoherence free quantum
gates recently proposed by Klein {\it et al.} [Phys. Rev. A, {\bf 73},
012332 (2006)]. A number of operations on the decoherence free subspace
in this scheme makes use of an ancilla qubit, which undergoes dephasing
and thus introduces decoherence to the system. We examine how this
decoherence affects entanglement swapping and purification as well as
the performance of a quantum repeater. We compare the decoherence free
quantum repeater with a quantum repeater based on qubits that are
subject to decoherence and show that it outperforms the latter when
decoherence due to long waiting times of conventional qubits becomes
significant. Thus, a quantum repeater based on decoherence free
subspaces is a possibility to greatly improve quantum communication over
long or even intercontinental distances.

**Efficient quantum circuits for
approximating the Jones polynomial**
(pp0489-0500)

Y.
Nakajima, Y. Kawano, and H. Sekigawa

Freedman, Kitaev, and Wang proved the equivalence between quantum field
theory and quantum computation, and consequently showed that the problem
of approximating the Jones polynomial (a knot invariant) at the fifth
root of unity is BQP-complete. Recently, Aharonov, Jones, and Landau
proposed a concrete quantum algorithm, called the AJL algorithm, that
approximates the Jones polynomial at the $k$th root of unity in
polynomial time. In this paper, we propose a new method for implementing
the AJL algorithm, which improves the performance from $O(mn\log^2k)$ to
$O(mn)$. Here, $n$ is the number of strands, $m$ is the number of the
crossings in a braid. Since, in the AJL algorithm, $m$ and $k$ are
assumed to be given as polynomials in $n$, the difference in the
performance between the original implementation and our design is
significant if $k$ is a large-degree polynomial.

*
Book Review:*

**On “xxxxx (authored by )” **
(pp0359-0360)

G.J.
Milburn

**back to QIC online Front page**