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.