Research Articles:

**An algorithm for the T-countAn algorithm for the
T-count**
(pp1261-1276)

David Gosset,
Vadym Kliuchnikov, Michele Mosca, and Vincent Russo

We consider quantum circuits composed of Clifford and $T$ gates. In
this context the $T$ gate has a special status since it confers
universal computation when added to the (classically simulable) Clifford
gates. However it can be very expensive to implement fault-tolerantly.
We therefore view this gate as a resource which should be used only when
necessary. Given an $n$-qubit unitary $U$ we are interested in computing
a circuit that implements it using the minimum possible number of $T$
gates (called the $T$-count of $U$). A related task is to decide if the
$T$-count of $U$ is less than or equal to $m$; we consider this problem
as a function of $N=2^n$ and $m$. We provide a classical algorithm which
solves it using time and space both upper bounded as $\mathcal{O}(N^m \text{poly}(m,N))$.
We implemented our algorithm and used it to show that any Clifford+T
circuit for the Toffoli or the Fredkin gate requires at least 7 $T$
gates. This implies that the known 7 $T$ gate circuits for these gates
are $T$-optimal. We also provide a simple expression for the $T$-count
of single-qubit unitaries.

**Repeat-Until-Success: Non-deterministic
decomposition of single-qubit unitaries**
(pp1277-1301)

Adam
Paetznick and Krysta M. Svore

We present a decomposition technique that uses non-deterministic
circuits to approximate an arbitrary single-qubit unitary to within
distance $\epsilon$ and requires significantly fewer non-Clifford gates
than existing techniques. We develop ``Repeat-Until-Success" (RUS)
circuits and characterize unitaries that can be exactly represented as
an RUS circuit. Our RUS circuits operate by conditioning on a given
measurement outcome and using only a small number of non-Clifford gates
and ancilla qubits. We construct an algorithm based on RUS circuits that
approximates an arbitrary single-qubit $Z$-axis rotation to within
distance $\epsilon$, where the number of $T$ gates scales as
$1.26\log_2(1/\epsilon) - 3.53$, an improvement of roughly three-fold
over state-of-the-art techniques. We then extend our algorithm and show
that a scaling of $2.4\log_2(1/\epsilon) - 3.28$ can be achieved for
arbitrary unitaries and a small range of $\epsilon$, which is roughly
twice as good as optimal deterministic decomposition methods.

**Strong equivalence of reversible circuits is coNP-complete**
(pp1302-1307)

Stephen P. Jordan

It is well-known that deciding equivalence of logic circuits is a
coNP-complete problem. As a corollary, the problem of deciding weak
equivalence of reversible circuits, \emph{i.e.} allowing initialized
ancilla bits in the input and ignoring ``garbage'' ancilla bits in the
output, is also coNP-complete. The complexity of deciding strong
equivalence, including the ancilla bits, is less obvious and may depend
on gate set. Here we use Barrington's theorem to show that deciding
strong equivalence of reversible circuits built from the Fredkin gate is
coNP-complete. This implies coNP-completeness of deciding strong
equivalence for other commonly used universal reversible gate sets,
including any gate set that includes the Toffoli or Fredkin gate.

**Separability for weakly irreducible matrices**
(pp1308-1337)

Daniel
Cariello

This paper is devoted to the study of the separability problem in
the field of Quantum information theory. We focus on the bipartite
finite dimensional case and on two types of matrices: SPC and PPT
matrices (see definitions 32 and 33). We prove that many results hold
for both types. If these matrices have specific Hermitian Schmidt
decompositions then they are separable in a very strong sense (see
theorem 38 and corollary 39). We prove that both types have what we call
\textbf{split decompositions} (see theorems 41 and 42). We also define
the notion of weakly irreducible matrix (see definition 43), based on
the concept of irreducible state defined recently in \cite{chen1}, \cite{chen}
and \cite{chen2}.}{These split decomposition theorems imply that every
SPC $($PPT$)$ matrix can be decomposed into a sum of $s+1$ SPC $($PPT$)$
matrices of which the first $s$ are weakly irreducible, by theorem 48,
and the last one has a further split decomposition of lower tensor rank,
by corollary 49. Thus the SPC $($PPT$)$ matrix is decomposed in a finite
number of steps into a sum of weakly irreducible matrices. Different
components of this sum have support on orthogonal local Hilbert spaces,
therefore the matrix is separable if and only if each component is
separable. This reduces the separability problem for SPC $($PPT$)$
matrices to the case of weakly irreducible SPC $($PPT$)$ matrices. We
also provide a complete description of weakly irreducible matrices of
both types (see theorem 46).}{Using the fact that every positive
semidefinite Hermitian matrix with tensor rank 2 is separable (see
theorem 58), we found sharp inequalites providing separability for both
types (see theorems 61 and 62).

**Fault-Tolerant quantum computation with constant
overhead**
(pp1338-1371)

Daniel
Gottesman

What is the minimum number of extra qubits needed to perform a large
fault-tolerant quantum circuit? Working in a common model of
fault-tolerance, I show that in the asymptotic limit of large circuits,
the ratio of physical qubits to logical qubits can be a constant. The
construction makes use of quantum low-density parity check codes, and
the asymptotic overhead of the protocol is equal to that of the family
of quantum error-correcting codes underlying the fault-tolerant
protocol.

**Generation of quantum correlation in quantum dots
by Lyapunov control methods**
(pp1372-1382)

Da-Wei Luo
and Jing-Bo Xu

We present a scheme to generate steady-state quantum correlations in
quantum dots. The shape of the control field is obtained by using the
Lyapunov control method, and the controlled state is found to approach
the target state monotonically. We also explore the possibility of
replacing the continuous control field with a train of discreet
rectangular pulses, which is much easier to implement experimentally.
The discretized control field is found to be still able to drive the
initial state to the target state with very small errors, which suggests
that the Lyapunov based control is still effective under practical
limitations.

**BosonSampling is far from uniform**
(pp1383-1423)

Scott
Aaronson and Alex Arkhipov

BosonSampling, which we proposed three years ago, is a scheme for
using linear-optical networks to solve sampling problems that appear to
be intractable for a classical computer. \ In a recent manuscript,
Gogolin et al.\ claimed that even an ideal BosonSampling device's output
would be *operationally indistinguishable\textquotedblright\ from a
uniform random outcome, at least \textquotedblleft without detailed a
priori knowledge*; or at any rate, that telling the two apart might
itself be a hard problem. We first answer these claims---explaining why
the first is based on a definition of *a priori knowledge* such
that, were it adopted, almost no quantum algorithm could be
distinguished from a pure random-number source; while the second is
neither new nor a practical obstacle to interesting BosonSampling
experiments.However, we then go further, and address some interesting
research questions inspired by Gogolin et al.'s arguments. We prove
that, with high probability over a Haar-random matrix $A$, the
BosonSampling distribution induced by $A$ is far from the uniform
distribution in total variation distance. More surprisingly, and counter
to Gogolin et al., we give an efficient algorithm that distinguishes
these two distributions with constant bias. Finally, we offer three *
bonus* results about BosonSampling. First, we report an observation
of Fernando Brandao: that one can efficiently sample a distribution that
has large entropy and that's indistinguishable from a BosonSampling
distribution by any circuit of fixed polynomial size. Second,

we show that BosonSampling distributions can be efficiently
distinguished from uniform even with photon losses and for general
initial states. Third, we offer the simplest known proof that *Fermion*
Sampling is solvable in classical polynomial time, and we reuse
techniques from our *Boson *Sampling analysis to characterize
random FermionSampling distributions.

**Families of codes of topological quantum codes
from tessellations tessellations {4i+2,2i+1}, {4i,4i}, {8i-4,4} and
${12i-6,3}**
(pp1424-1440)

Clarice
Dias de Albuquerque, Reginaldo Palazzo Jr., and Eduardo Brandani da
Silva

In this paper we present some classes of topological quantum codes
on surfaces with genus $g \geq 2$ derived from hyperbolic tessellations
with a specific property. We find classes of codes with distance $d = 3$
and encoding rates asymptotically going to 1, $\frac{1}{2}$ and
$\frac{1}{3}$, depending on the considered tessellation. Furthermore,
these codes are associated with embedding of complete bipartite graphs.
We also analyze the parameters of these codes, mainly its distance, in
addition to show a class of codes with distance 4. We also present a
class of codes achieving the quantum Singleton bound, possibly the only
one existing under this construction.