Exponential quantum speed-ups are generic (pp0901-0924)
          Fernando G.S.L. Brandao and Michal Horodecki
A central problem in quantum computation is to understand which quantum circuits are useful for exponential speed-ups over classical computation. We address this question in the setting of query complexity and show that for almost any sufficiently long quantum circuit one can construct a black-box problem which is solved by the circuit with a constant number of quantum queries, but which requires exponentially many classical queries, even if the classical machine has the ability to postselect. We prove the result in two steps. In the first, we show that almost any element of an approximate unitary 3-design is useful to solve a certain black-box problem efficiently. The problem is based on a recent oracle construction of Aaronson and gives an exponential separation between quantum and classical post-selected bounded-error query complexities. In the second step, which may be of independent interest, we prove that linear-sized random quantum circuits give an approximate unitary 3-design. The key ingredient in the proof is a technique from quantum many-body theory to lower bound the spectral gap of local quantum Hamiltonians.

Entanglement capabilities of the spin representation of (3+1)D-conformal transformations (pp0925-0936)
          Klaus Scharnhorst
Relying on a mathematical analogy of the pure states of the two-qubit system of quantum information theory with four-component spinors we introduce the concept of the intrinsic entanglement of spinors. To explore its physical sense we study the entanglement capabilities of the spin representation of (pseudo-) conformal transformations in (3+1)-dimensional Minkowski space-time. We find that only those tensor product structures can sensibly be introduced in spinor space for which a given spinor is not entangled.

A 2D nearest-neighbor quantum architecture for factoring in polylogarithmic depth (pp0937-0962)
          Paul Pham and Krysta M. Svore
We present a 2D nearest-neighbor quantum architecture for Shor's algorithm to factor an $n$-bit number in $O(\log^3n)$ depth. Our implementation uses parallel phase estimation, constant-depth fanout and teleportation, and constant-depth carry-save modular addition. We derive upper bounds on the circuit resources of our architecture under a new 2D model which allows a classical controller and parallel, communicating modules. We provide a comparison to all previous nearest-neighbor factoring implementations. Our circuit results in an exponential improvement in nearest-neighbor circuit depth at the cost of a polynomial increase in circuit size and width.

Subsystem surface codes with three-qubit check operators (pp0963-0985)
          Sergey Bravyi, Guillaume Duclos-Cianci, David Poulin, and Martin Suchara
We propose a simplified version of the Kitaev's surface code in which error correction requires only three-qubit parity measurements for Pauli operators XXX and ZZZ. The new code belongs to the class of subsystem stabilizer codes. It inherits many favorable properties of the standard surface code such as encoding of multiple logical qubits on a planar lattice with punctured holes, efficient decoding by either minimum-weight matching or renormalization group methods, and high error threshold. The new subsystem surface code (SSC) gives rise to an exactly solvable Hamiltonian with 3-qubit interactions, topologically ordered ground state, and a constant energy gap. We construct a local unitary transformation mapping the SSC Hamiltonian to the one of the ordinary surface code thus showing that the two Hamiltonians belong to the same topological class. We describe error correction protocols for the SSC and determine its error thresholds under several natural error models. In particular, we show that the SSC has error threshold approximately $0.6\%$ for the standard circuit-based error model studied in the literature. We also consider a model in which three-qubit parity operators can be measured directly. We show that the SSC has error threshold approximately 0.97% in this setting.

Upper bounds on mixing rates (pp0986-0994)
          Elliott H.Lieb and AnnaVershynina
We prove upper bounds on the rate, called "mixing rate", at which the von Neumann entropy of the expected density operator of a given ensemble of states changes under non-local unitary evolution.
For an ensemble consisting of two states, with probabilities of p and 1-p, we prove that the mixing rate is bounded above by 4\sqrt{p(1-p)} for any Hamiltonian of norm 1. For a general ensemble of states with probabilities distributed according to a random variable X and individually evolving according to any set of bounded Hamiltonians, we conjecture that the mixing rate is bounded above by a Shannon entropy of a random variable $X$. For this general case we prove an upper bound that is independent of the dimension of the Hilbert space on which states in the ensemble act.

Loss tolerance with a concatenated graph state (pp0995-1006)
          David A. Herrera-Marti and Terry Rudolph
A new way of addressing loss errors is introduced which combines ideas from measurement-based quantum computation and concatenated quantum codes, allowing for universal quantum computation. It is shown that for the case where qubit loss is detected upon measurement, the scheme performs well under $23\%$ loss rate. For loss rates below $10\%$ this approach performs better than the best scheme known up to date \cite{varnava2006loss}. If lost qubits are tagged prior to measurement, it can tolerate up to $50\%$ loss. The overhead per logical qubit is shown to be significantly lower than other schemes. The obtention of the threshold is entirely analytic.

Efficient classical simulations of quantum Fourier transforms and Normalizer circuits over Abelian groups (pp1007-1037)
          Maarten Van den Nest
The quantum Fourier transform (QFT) is an important ingredient in various quantum algorithms which achieve superpolynomial speed-ups over classical computers. In this paper we study under which conditions the QFT can be simulated efficiently classically. We introduce a class of quantum circuits, called \emph{normalizer circuits}: a normalizer circuit over a finite Abelian group is any quantum circuit comprising the QFT over the group, gates which compute automorphisms and gates which realize quadratic functions on the group. In our main result we prove that all normalizer circuits have polynomial-time classical simulations. The proof uses algorithms for linear diophantine equation solving and the monomial matrix formalism introduced in our earlier work. Our result generalizes the Gottesman-Knill theorem: in particular, Clifford circuits for $d$-level qudits arise as normalizer circuits over the group ${\mathbf Z}_d^m$. We also highlight connections between normalizer circuits and Shor's factoring algorithm, and the Abelian hidden subgroup problem in general. Finally we prove that quantum factoring cannot be realized as a normalizer circuit owing to its modular exponentiation subroutine.

Obstructions to classically simulating the quantum adiabatic algorithm (pp1038-1076)
          Matthew B. Hastings
We consider the adiabatic quantum algorithm for systems with ``no sign problem", such as the transverse field Ising model, and analyze the equilibration time for quantum Monte Carlo (QMC) on these systems. We ask: if the spectral gap is only inverse polynomially small, will equilibration methods based on slowly changing the Hamiltonian parameters in the QMC simulation succeed in a polynomial time? We show that this is {\it not} true, by constructing counter-examples. In some examples, the space of configurations where the wavefunction has non-negligible amplitude has a nontrivial fundamental group, causing the space of trajectories in imaginary time to break into disconnected components with only negligible probability outside these components. For the simplest example we give with an abelian fundamental group, QMC does not equilibrate but still solves the optimization problem. More severe effects leading to failure to solve the optimization can occur when the fundamental group is a free group on two generators. Other examples where QMC fails have a {\it trivial} fundamental group, but still use ideas from topology relating group presentations to simplicial complexes. We define gadgets to realize these Hamiltonians as the effective low-energy dynamics of a transverse field Ising model. We present some analytic results on equilibration times which may be of some independent interest in the theory of equilibration of Markov chains. Conversely, we show that a small spectral gap implies slow equilibration at low temperature for some initial conditions and for a natural choice of local QMC updates.

A note on locally unextendible non-maximally entangled basis (pp1077-1080)
          Bin Chen, Halqum Nizamidin, and Shao-Ming Fei
We study the locally unextendible non-maximally entangled basis (LUNMEB) in $H^{d}\bigotimes H^{d}$. We point out that there exists an error in the proof of the main result of LUNMEB [Quant. Inf. Comput. 12, 0271(2012)], which claims that there are at most d orthogonal vectors in a LUNMEB, constructed from a given non-maximally entangled state. We show that both the proof and the main result are not correct in general. We present a counter example for d=4, in which five orthogonal vectors from a specific non-maximally entangled state are constructed. Besides, we completely solve the problem of LUNMEB for the case of d=2.