**
***
*Research Articles:

**The computational power of matchgates and the XY
interaction on arbitrary graphs**
(pp0901-0916)

Daniel J. Brod and
Andrew M. Childs

Matchgates are a restricted set of two-qubit gates known to be
classically simulable when acting on nearest-neighbor qubits on a path,
but universal for quantum computation when the qubits are arranged on
certain other graphs. Here we characterize the power of matchgates
acting on arbitrary graphs. Specifically, we show that they are
universal on any connected graph other than a path or a cycle, and that
they are classically simulable on a cycle. We also prove the same
dichotomy for the XY interaction, a proper subset of matchgates related
to some implementations of quantum computing.

**Channel covariance, twirling, contraction and some
upper bounds on the quantum capacity**
(pp0917-0936)

Yingkai
Ouyang

Evaluating the quantum capacity of quantum channels is an important but
difficult problem, even for channels of low input and output dimension.
Smith and Smolin showed that the quantum capacity of the Clifford-twirl
of a qubit amplitude damping channel (a qubit depolarizing channel) has
a quantum capacity that is at most the coherent information of the qubit
amplitude damping channel evaluated on the maximally mixed input state.
We restrict our attention to obtaining upper bounds on the quantum
capacity using a generalization of Smith and Smolin's degradable
extension technique. Given a degradable channel $\cN$ and a finite
projective group of unitaries $\cV$, we show that the $\cV$-twirl of $\cN$
has a quantum capacity at most the coherent information of $\cN$
maximized over a $\cV$-contracted space of input states. As a
consequence, degradable channels that are covariant with respect to
diagonal Pauli matrices have quantum capacities that are their coherent
information maximized over just the diagonal input states. As an
application of our main result, we supply new upper bounds on the
quantum capacity of some unital and non-unital channels --
$d$-dimensional depolarizing channels, two-qubit locally symmetric Pauli
channels, and shifted qubit depolarizing channels.

**Entanglement classification of relaxed
Greenberger-Horne-Zeilinger-symmetric states**
(pp0937-0948)

Eylee Jung and
DaeKil Park

In this paper we analyze entanglement classification of relaxed
Greenberger-Horne-Zeilinger-symmetric states $\rho^{ES}$, which is
parametrized by four real parameters $x$, $y_1$, $y_2$ and $y_3$. The
condition for separable states of $\rho^{ES}$ is analytically derived.
The higher classes such as bi-separable, W, and Greenberger-Horne-Zeilinger
classes are roughly classified by making use of the class-specific
optimal witnesses or map from the relaxed Greenberger-Horne-Zeilinger
symmetry to the Greenberger-Horne-Zeilinger symmetry. From this analysis
we guess that the entanglement classes of $\rho^{ES}$ are not dependent
on $y_j \hspace{.2cm} (j=1,2,3)$ individually, but dependent on $y_1 +
y_2 + y_3$ collectively. The difficulty arising in extension of analysis
with Greenberger-Horne-Zeilinger symmetry to the higher-qubit system is
discussed.

**Decomposition and gluing for adiabatic quantum
optimization**
(pp0949-0965)

Micah Blake
McCurdy, Jeffrey Egger, and Jordan Kyriakidis

Farhi and others~\cite{Farhi} have introduced the notion of solving NP
problems using adiabatic quantum computers. We discuss an application of
this idea to the problem of integer factorization, together with a
technique we call \emph{gluing} which can be used to build adiabatic
models of interesting problems. Although adiabatic quantum computers
already exist, they are likely to be too small to directly tackle
problems of interesting practical sizes for the foreseeable future.
Therefore, we discuss techniques for decomposition of large problems,
which permits us to fully exploit such hardware as may be available.
Numerical results suggest that even simple decomposition techniques may
yield acceptable results with subexponential overhead, independent of
the performance of the underlying device.

**Global convergence of diluted iterations in
maximum-likelihood quantum tomography**
(pp0966-0980)

Doglas S.
Goncalves, Marcia A. Gomes-Ruggiero, and Carlile Lavor

In this paper we address convergence issues of the Diluted $R \rho R$
algorithm \cite{rehacek2007}, used to obtain the maximum likelihood
estimate for the density matrix in quantum state tomography. We give a
new interpretation to the diluted $R \rho R$ iterations that allows us
to prove the global convergence under weaker assumptions. Thus, we
propose a new algorithm which is globally convergent and suitable for
practical implementation.

**Majorana fermions and non-locality**
(pp0981-0995)

Earl T.
Campbell, Matty J. Hoban, and Jens Eisert

Localized Majorana fermions emerge in many topologically ordered systems
and exhibit exchange statistics of Ising anyons. This enables
noise-resistant implementation of a limited set of operations by
braiding and fusing Majorana fermions. Unfortunately, these operations
are incapable of implementing universal quantum computation. We show
that, regardless of these limitations, Majorana fermions could be used
to demonstrate non-locality (correlations incompatible with a local
hidden variable theory) in experiments using only topologically
protected operations. We also demonstrate that our proposal is optimal
in terms of resources, with 10 Majorana fermions shown to be both
necessary and sufficient for demonstrating bipartite non-locality.
Furthermore, we identify severe restrictions on the possibility of
tripartite non-locality. We comment on the potential of such entangled
systems to be used in quantum information protocols.

**Tests for quantum contextuality in terms of
Q-entropies**
(pp0996-1013)

Alexey E.
Rastegin

The information-theoretic approach to Bell's theorem is developed with
use of the conditional $q$-entropies. The $q$-entropic measures fulfill
many similar properties to the standard Shannon entropy. In general,
both the locality and noncontextuality notions are usually treated with
use of the so-called marginal scenarios. These hypotheses lead to the
existence of a joint probability distribution, which marginalizes to all
particular ones. Assuming the existence of such a joint probability
distribution, we derive the family of inequalities of Bell's type in
terms of conditional $q$-entropies for all $q\geq1$. Quantum violations
of the new inequalities are exemplified within the Clauser--Horne--Shimony--Holt
(CHSH) and Klyachko--Can--Binicio\v{g}lu--Shumovsky (KCBS) scenarios. An
extension to the case of $n$-cycle scenario is briefly mentioned. The
new inequalities with conditional $q$-entropies allow to expand a class
of probability distributions, for which the nonlocality or contextuality
can be detected within entropic formulation. The $q$-entropic
inequalities can also be useful in analyzing cases with detection
inefficiencies. Using two models of such a kind, we consider some
potential advantages of the

$q$-entropic formulation.

**Quantum computation of scattering in scalar
quantum field theories**
(pp1014-1080)

Stephen P.
Jordan, Keith S. M. Lee, and John Preskill

Quantum field theory provides the framework for the most fundamental
physical theories to be confirmed experimentally and has enabled
predictions of unprecedented precision. However, calculations of
physical observables often require great computational complexity and
can generally be performed only when the interaction strength is weak. A
full understanding of the foundations and rich consequences of quantum
field theory remains an outstanding challenge. We develop a quantum
algorithm to compute relativistic scattering amplitudes in massive
$\phi^4$ theory in spacetime of four and fewer dimensions. The algorithm
runs in a time that is polynomial in the number of particles, their
energy, and the desired precision, and applies at both weak and strong
coupling. Thus, it offers exponential speedup over existing classical
methods at high precision or strong coupling.