
$\textit{Normalizer circuits}$ [1,2] are generalized Clifford circuits that
act on arbitrary finitedimensional systems $\mathcal{H}_{d_1}\otimes ...
\otimes \mathcal{H}_{d_n}$ with a standard basis labeled by the elements of a
finite Abelian group $G=\mathbb{Z}_{d_1}\times... \times \mathbb{Z}_{d_n}$.
Normalizer gates implement operations associated with the group $G$ and can be
of three types: quantum Fourier transforms, group automorphism gates and
quadratic phase gates. In this work, we extend the normalizer formalism [1,2]
to infinite dimensions, by allowing normalizer gates to act on systems of the
form $\mathcal{H}_\mathbb{Z}^{\otimes a}$: each factor $\mathcal{H}_\mathbb{Z}$
has a standard basis labeled by $\textit{integers}$ $\mathbb{Z}$, and a Fourier
basis labeled by $\textit{angles}$, elements of the circle group $\mathbb{T}$.
Normalizer circuits become hybrid quantum circuits acting both on continuous
and discretevariable systems. We show that infinitedimensional normalizer
circuits can be efficiently simulated classically with a generalized
$\textit{stabilizer formalism}$ for Hilbert spaces associated with groups of
the form $\mathbb{Z}^a\times \mathbb{T}^b \times
\mathbb{Z}_{d_1}\times...\times \mathbb{Z}_{d_n}$. We develop new techniques to
track stabilizergroups based on normal forms for group automorphisms and
quadratic functions. We use our normal forms to reduce the problem of
simulating normalizer circuits to that of finding general solutions of systems
of mixed realinteger linear equations [3] and exploit this fact to devise a
robust simulation algorithm: the latter remains efficient even in pathological
cases where stabilizer groups become infinite, uncountable and noncompact. The
techniques developed in this paper might find applications in the study of
faulttolerant quantum computation with superconducting qubits [4,5].

This work presents a precise connection between Clifford circuits, Shor's
factoring algorithm and several other famous quantum algorithms with
exponential quantum speedups for solving Abelian hidden subgroup problems. We
show that all these different forms of quantum computation belong to a common
new restricted model of quantum operations that we call \emph{blackbox
normalizer circuits}. To define these, we extend the previous model of
normalizer circuits [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], which
are built of quantum Fourier transforms, group automorphism and quadratic phase
gates associated to an Abelian group $G$. In previous works, the group $G$ is
always given in an explicitly decomposed form. In our model, we remove this
assumption and allow $G$ to be a blackbox group. While standard normalizer
circuits were shown to be efficiently classically simulable
[arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], we find that normalizer
circuits are powerful enough to factorize and solve classicallyhard problems
in the blackbox setting. We further set upper limits to their computational
power by showing that decomposing finite Abelian groups is complete for the
associated complexity class. In particular, solving this problem renders
blackbox normalizer circuits efficiently classically simulable by exploiting
the generalized stabilizer formalism in
[arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208]. Lastly, we employ our
connection to draw a few practical implications for quantum algorithm design:
namely, we give a nogo theorem for finding new quantum algorithms with
blackbox normalizer circuits, a universality result for lowdepth normalizer
circuits, and identify two other complete problems.

We propose a noncommutative extension of the Pauli stabilizer formalism. The
aim is to describe a class of manybody quantum states which is richer than the
standard Pauli stabilizer states. In our framework, stabilizer operators are
tensor products of singlequbit operators drawn from the group $\langle \alpha
I, X,S\rangle$, where $\alpha=e^{i\pi/4}$ and $S=\operatorname{diag}(1,i)$. We
provide techniques to efficiently compute various properties related to
bipartite entanglement, expectation values of local observables, preparation by
means of quantum circuits, parent Hamiltonians etc. We also highlight
significant differences compared to the Pauli stabilizer formalism. In
particular, we give examples of states in our formalism which cannot arise in
the Pauli stabilizer formalism, such as topological models that support
nonAbelian anyons.

Here we investigate the connection between topological order and the
geometric entanglement, as measured by the logarithm of the overlap between a
given state and its closest product state of blocks. We do this for a variety
of topologicallyordered systems such as the toric code, double semion, color
code, and quantum double models. As happens for the entanglement entropy, we
find that for sufficiently large block sizes the geometric entanglement is, up
to possible subleading corrections, the sum of two contributions: a bulk
contribution obeying a boundary law times the number of blocks, and a
contribution quantifying the underlying pattern of longrange entanglement of
the topologicallyordered state. This topological contribution is also present
in the case of singlespin blocks in most cases, and constitutes an alternative
characterisation of topological order for these quantum states based on a
multipartite entanglement measure. In particular, we see that the topological
term for the 2D color code is twice as much as the one for the toric code, in
accordance with recent renormalization group arguments. Motivated by this, we
also derive a general formalism to obtain upper and lowerbounds to the
geometric entanglement of states with a nonAbelian symmetry, and which we use
to analyse quantum double models. Furthermore, we also analyse the robustness
of the topological contribution using renormalization and perturbation theory
arguments, as well as a numerical estimation for small systems. Some of our
results rely on the ability to disentangle single sites from the system, which
is always possible in our framework. Aditionally, we relate our results to the
relative entropy of entanglement in topological systems, and discuss some
tensor network numerical approaches that could be used to extract the
topological contribution for large systems beyond exactlysolvable models.

Can one certify the preparation of a coherent, manybody quantum state by
measurements with bounded accuracy in the presence of noise and decoherence?
Here, we introduce a criterion to assess the fragility of largescale quantum
states which is based on the distinguishability of orthogonal states after the
action of very small amounts of noise. States which do not pass this criterion
are called asymptotically incertifiable. We show that, if a coherent quantum
state is asymptotically incertifiable, there exists an incoherent mixture (with
entropy at least log 2) which is experimentally indistinguishable from the
initial state. The GreenbergerHorneZeilinger states are examples of such
asymptotically incertifiable states. More generally, we prove that any
socalled macroscopic superposition state is asymptotically incertifiable. We
also provide examples of quantum states that are experimentally
indistinguishable from highly incoherent mixtures, i.e., with an almostlinear
entropy in the number of qubits. Finally we show that all unique ground states
of local gapped Hamiltonians (in any dimension) are certifiable.

We show that several quantum circuit families can be simulated efficiently
classically if it is promised that their output distribution is approximately
sparse i.e. the distribution is close to one where only a polynomially small, a
priori unknown subset of the measurement probabilities are nonzero. Classical
simulations are thereby obtained for quantum circuits whichwithout the
additional sparsity promiseare considered hard to simulate. Our results
apply in particular to a family of Fourier sampling circuits (which have
structural similarities to Shor's factoring algorithm) but also to several
other circuit families, such as IQP circuits. Our results provide examples of
quantum circuits that cannot achieve exponential speedups due to the presence
of too much destructive interference i.e. too many cancelations of amplitudes.
The crux of our classical simulation is an efficient algorithm for
approximating the significant Fourier coefficients of a class of states called
computationally tractable states. The latter result may have applications
beyond the scope of this work. In the proof we employ and extend sparse
approximation techniques, in particular the KushilevitzMansour algorithm, in
combination with probabilistic simulation methods for quantum circuits.

Quantum normalizer circuits were recently introduced as generalizations of
Clifford circuits [arXiv:1201.4867]: a normalizer circuit over a finite Abelian
group $G$ is composed of the quantum Fourier transform (QFT) over G, together
with gates which compute quadratic functions and automorphisms. In
[arXiv:1201.4867] it was shown that every normalizer circuit can be simulated
efficiently classically. This result provides a nontrivial example of a family
of quantum circuits that cannot yield exponential speedups in spite of usage
of the QFT, the latter being a central quantum algorithmic primitive. Here we
extend the aforementioned result in several ways. Most importantly, we show
that normalizer circuits supplemented with intermediate measurements can also
be simulated efficiently classically, even when the computation proceeds
adaptively. This yields a generalization of the GottesmanKnill theorem (valid
for nqubit Clifford operations [quantph/9705052, quantph/9807006] to quantum
circuits described by arbitrary finite Abelian groups. Moreover, our
simulations are twofold: we present efficient classical algorithms to sample
the measurement probability distribution of any adaptivenormalizer
computation, as well as to compute the amplitudes of the state vector in every
step of it. Finally we develop a generalization of the stabilizer formalism
[quantph/9705052, quantph/9807006] relative to arbitrary finite Abelian
groups: for example we characterize how to update stabilizers under generalized
Pauli measurements and provide a normal form of the amplitudes of generalized
stabilizer states using quadratic functions and subgroup cosets.

Clifford gates are a winsome class of quantum operations combining
mathematical elegance with physical significance. The GottesmanKnill theorem
asserts that Clifford computations can be classically efficiently simulated but
this is true only in a suitably restricted setting. Here we consider Clifford
computations with a variety of additional ingredients: (a) strong vs. weak
simulation, (b) inputs being computational basis states vs. general product
states, (c) adaptive vs. nonadaptive choices of gates for circuits involving
intermediate measurements, (d) single line outputs vs. multiline outputs. We
consider the classical simulation complexity of all combinations of these
ingredients and show that many are not classically efficiently simulatable
(subject to common complexity assumptions such as P not equal to NP). Our
results reveal a surprising proximity of classical to quantum computing power
viz. a class of classically simulatable quantum circuits which yields universal
quantum computation if extended by a purely classical additional ingredient
that does not extend the class of quantum processes occurring.

The study of quantum circuits composed of commuting gates is particularly
useful to understand the delicate boundary between quantum and classical
computation. Indeed, while being a restricted class, commuting circuits exhibit
genuine quantum effects such as entanglement. In this paper we show that the
computational power of commuting circuits exhibits a surprisingly rich
structure. First we show that every 2local commuting circuit acting on dlevel
systems and followed by singlequdit measurements can be efficiently simulated
classically with high accuracy. In contrast, we prove that such strong
simulations are hard for 3local circuits. Using sampling methods we further
show that all commuting circuits composed of exponentiated Pauli operators
e^{i\theta P} can be simulated efficiently classically when followed by
singlequbit measurements. Finally, we show that commuting circuits can
efficiently simulate certain noncommutative processes, related in particular
to constantdepth quantum circuits. This gives evidence that the power of
commuting circuits goes beyond classical computation.

We show that universal quantum computation can be achieved in the standard
purestate circuit model while, at any time, the entanglement entropy of all
bipartitions is smalleven tending to zero with growing system size. The
result is obtained by showing that a quantum computer operating within a small
region around the set of unentangled states still has universal computational
power, and by using continuity of entanglement entropy. In fact an analogous
conclusion applies to every entanglement measure which is continuous in a
certain natural sense, which amounts to a large class. Other examples include
the geometric measure, localizable entanglement, smooth epsilonmeasures,
multipartite concurrence, squashed entanglement, and several others. We discuss
implications of these results for the believed role of entanglement as a key
necessary resource for quantum speedups.

We propose a framework to describe and simulate a class of manybody quantum
states. We do so by considering joint eigenspaces of sets of monomial unitary
matrices, called here "Mspaces"; a unitary matrix is monomial if precisely one
entry per row and column is nonzero. We show that Mspaces encompass various
important state families, such as all Pauli stabilizer states and codes, the
AKLT model, Kitaev's (abelian and nonabelian) anyon models, group coset
states, W states and the locally maximally entanglable states. We furthermore
show how basic properties of Mspaces can transparently be understood by
manipulating their monomial stabilizer groups. In particular we derive a
unified procedure to construct an eigenbasis of any Mspace, yielding an
explicit formula for each of the eigenstates. We also discuss the computational
complexity of Mspaces and show that basic problems, such as estimating local
expectation values, are NPhard. Finally we prove that a large subclass of
Mspacescontaining in particular most of the aforementioned examplescan
be simulated efficiently classically with a unified method.

We study mappings between distinct classical spin systems that leave the
partition function invariant. As recently shown in [Phys. Rev. Lett. 100,
110501 (2008)], the partition function of the 2D square lattice Ising model in
the presence of an inhomogeneous magnetic field, can specialize to the
partition function of any Ising system on an arbitrary graph. In this sense the
2D Ising model is said to be "complete". However, in order to obtain the above
result, the coupling strengths on the 2D lattice must assume complex values,
and thus do not allow for a physical interpretation. Here we show how a
complete model with real and, hence, "physical" couplings can be obtained if
the 3D Ising model is considered. We furthermore show how to map general
qstate systems with possibly manybody interactions to the 2D Ising model with
complex parameters, and give completeness results for these models with real
parameters. We also demonstrate that the computational overhead in these
constructions is in all relevant cases polynomial. These results are proved by
invoking a recently found crossconnection between statistical mechanics and
quantum information theory, where partition functions are expressed as quantum
mechanical amplitudes. Within this framework, there exists a natural
correspondence between manybody quantum states that allow universal quantum
computation via local measurements only, and complete classical spin systems.

We investigate which entanglement resources allow universal measurementbased
quantum computation via singlequbit operations. We find that any entanglement
feature exhibited by the 2D cluster state must also be present in any other
universal resource. We obtain a powerful criterion to assess universality of
graph states, by introducing an entanglement measure which necessarily grows
unboundedly with the system size for all universal resource states.
Furthermore, we prove that graph states associated with 2D lattices such as the
hexagonal and triangular lattice are universal, and obtain the first example of
a universal nongraph state.

The local complement G*i of a simple graph G at one of its vertices i is
obtained by complementing the subgraph induced by the neighborhood of i and
leaving the rest of the graph unchanged. If e={i,j} is an edge of G then
G*e=((G*i)*j)*i is called the edgelocal complement of G along the edge e. We
call two graphs edgelocally equivalent if they are related by a sequence of
edgelocal complementations. The main result of this paper is an algebraic
description of edgelocal equivalence of graphs in terms of linear fractional
transformations of adjacency matrices. Applications of this result include (i)
a polynomial algorithm to recognize whether two graphs are edgelocally
equivalent, (ii) a formula to count the number of graphs in a class of
edgelocal equivalence, and (iii) a result concerning the coefficients of the
interlace polynomial, where we show that these coefficients are all even for a
class of graphs; this class contains, as a subset, all strongly regular graphs
with parameters (n, k, a, c), where k is odd and a and c are even.

We study the algebra of complex polynomials which remain invariant under the
action of the local Clifford group under conjugation. Within this algebra, we
consider the linear spaces of homogeneous polynomials degree by degree and
construct bases for these vector spaces for each degree, thereby obtaining a
generating set of polynomial invariants. Our approach is based on the
description of Clifford operators in terms of linear operations over GF(2).
Such a study of polynomial invariants of the local Clifford group is mainly of
importance in quantum coding theory, in particular in the classification of
binary quantum codes. Some applications in entanglement theory and quantum
computing are briefly discussed as well.

In [Phys. Rev. A 69, 022316 (2004)] we presented a description of the action
of local Clifford operations on graph states in terms of a graph transformation
rule, known in graph theory as \emph{local complementation}. It was shown that
two graph states are equivalent under the local Clifford group if and only if
there exists a sequence of local complementations which relates their
associated graphs. In this short note we report the existence of a polynomial
time algorithm, published in [Combinatorica 11 (4), 315 (1991)], which decides
whether two given graphs are related by a sequence of local complementations.
Hence an efficient algorithm to detect local Clifford equivalence of graph
states is obtained.

In [Phys. Rev. A 58, 1833 (1998)] a family of polynomial invariants which
separate the orbits of multiqubit density operators $\rho$ under the action of
the local unitary group was presented. We consider this family of invariants
for the class of those $\rho$ which are the projection operators describing
stabilizer codes and give a complete translation of these invariants into the
binary framework in which stabilizer codes are usually described. Such an
investigation of local invariants of quantum codes is of natural importance in
quantum coding theory, since locally equivalent codes have the same
errorcorrecting capabilities and local invariants are powerful tools to
explore their structure. Moreover, the present result is relevant in the
context of multipartite entanglement and the development of the
measurementbased model of quantum computation known as the oneway quantum
computer.

We translate the action of local Clifford operations on graph states into
transformations on their associated graphs  i.e. we provide transformation
rules, stated in purely graph theoretical terms, which completely characterize
the evolution of graph states under local Clifford operations. As we will show,
there is essentially one basic rule, successive application of which generates
the orbit of any graph state under local unitary operations within the Clifford
group.

We present new algorithms for mixedstate multicopy entanglement
distillation for pairs of qubits. Our algorithms perform significantly better
than the best known algorithms. Better algorithms can be derived that are tuned
for specific initial states. The new algorithms are based on a characterization
of the group of all locally realizable permutations of the 4^n possible tensor
products of n Bell states.