Research Articles:

**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.

*
***Correspondence:**

**
****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.