• ### Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems(1409.3208)

Jan. 20, 2015 quant-ph, math-ph, math.MP, cs.CC
$\textit{Normalizer circuits}$ [1,2] are generalized Clifford circuits that act on arbitrary finite-dimensional 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 discrete-variable systems. We show that infinite-dimensional 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 stabilizer-groups 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 real-integer 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 non-compact. The techniques developed in this paper might find applications in the study of fault-tolerant quantum computation with superconducting qubits [4,5].
• ### The computational power of normalizer circuits over black-box groups(1409.4800)

Sept. 16, 2014 quant-ph, cs.CC
This work presents a precise connection between Clifford circuits, Shor's factoring algorithm and several other famous quantum algorithms with exponential quantum speed-ups 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{black-box 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 black-box 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 classically-hard problems in the black-box 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 black-box 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 no-go theorem for finding new quantum algorithms with black-box normalizer circuits, a universality result for low-depth normalizer circuits, and identify two other complete problems.
• ### A Non-Commuting Stabilizer Formalism(1404.5327)

April 21, 2014 quant-ph, cond-mat.str-el
We propose a non-commutative extension of the Pauli stabilizer formalism. The aim is to describe a class of many-body quantum states which is richer than the standard Pauli stabilizer states. In our framework, stabilizer operators are tensor products of single-qubit 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 non-Abelian anyons.
• ### Geometric Entanglement in Topologically Ordered States(1304.1339)

Dec. 11, 2013 quant-ph, hep-th, cond-mat.str-el
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 topologically-ordered 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 sub-leading 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 long-range entanglement of the topologically-ordered state. This topological contribution is also present in the case of single-spin 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 lower-bounds to the geometric entanglement of states with a non-Abelian 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 exactly-solvable models.
• ### Certifiability criterion for large-scale quantum systems(1306.0370)

Nov. 14, 2013 quant-ph
Can one certify the preparation of a coherent, many-body quantum state by measurements with bounded accuracy in the presence of noise and decoherence? Here, we introduce a criterion to assess the fragility of large-scale 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 Greenberger-Horne-Zeilinger states are examples of such asymptotically incertifiable states. More generally, we prove that any so-called 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 almost-linear entropy in the number of qubits. Finally we show that all unique ground states of local gapped Hamiltonians (in any dimension) are certifiable.
• ### Simulating Quantum Circuits with Sparse Output Distributions(1310.6749)

Oct. 24, 2013 quant-ph, cs.CC
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 which---without the additional sparsity promise---are 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 speed-ups 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 Kushilevitz-Mansour algorithm, in combination with probabilistic simulation methods for quantum circuits.
• ### Classical simulations of Abelian-group normalizer circuits with intermediate measurements(1210.3637)

Oct. 22, 2013 quant-ph, cs.CC
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 speed-ups 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 Gottesman-Knill theorem (valid for n-qubit Clifford operations [quant-ph/9705052, quant-ph/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 adaptive-normalizer 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 [quant-ph/9705052, quant-ph/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.
• ### Classical simulation complexity of extended Clifford circuits(1305.6190)

May 27, 2013 quant-ph, cs.CC
Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill 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. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line 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.
• ### Commuting quantum circuits: efficient classical simulations versus hardness results(1204.4570)

April 20, 2012 quant-ph
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 2-local commuting circuit acting on d-level systems and followed by single-qudit measurements can be efficiently simulated classically with high accuracy. In contrast, we prove that such strong simulations are hard for 3-local 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 single-qubit measurements. Finally, we show that commuting circuits can efficiently simulate certain non-commutative processes, related in particular to constant-depth quantum circuits. This gives evidence that the power of commuting circuits goes beyond classical computation.
• ### Universal quantum computation with little entanglement(1204.3107)

April 13, 2012 quant-ph
We show that universal quantum computation can be achieved in the standard pure-state circuit model while, at any time, the entanglement entropy of all bipartitions is small---even 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 epsilon-measures, 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 speed-ups.
• ### A monomial matrix formalism to describe quantum many-body states(1108.0531)

Aug. 2, 2011 quant-ph
We propose a framework to describe and simulate a class of many-body quantum states. We do so by considering joint eigenspaces of sets of monomial unitary matrices, called here "M-spaces"; a unitary matrix is monomial if precisely one entry per row and column is nonzero. We show that M-spaces encompass various important state families, such as all Pauli stabilizer states and codes, the AKLT model, Kitaev's (abelian and non-abelian) anyon models, group coset states, W states and the locally maximally entanglable states. We furthermore show how basic properties of M-spaces can transparently be understood by manipulating their monomial stabilizer groups. In particular we derive a unified procedure to construct an eigenbasis of any M-space, yielding an explicit formula for each of the eigenstates. We also discuss the computational complexity of M-spaces and show that basic problems, such as estimating local expectation values, are NP-hard. Finally we prove that a large subclass of M-spaces---containing in particular most of the aforementioned examples---can be simulated efficiently classically with a unified method.
• ### Completeness of classical spin models and universal quantum computation(0812.2368)

Dec. 12, 2008 quant-ph, cond-mat.stat-mech
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 q-state systems with possibly many-body 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 cross-connection 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 many-body quantum states that allow universal quantum computation via local measurements only, and complete classical spin systems.
• ### Universal resources for measurement-based quantum computation(quant-ph/0604010)

Oct. 16, 2006 quant-ph
We investigate which entanglement resources allow universal measurement-based quantum computation via single-qubit 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 non-graph state.
• ### Edge-local equivalence of graphs(math/0510246)

Oct. 12, 2005 quant-ph, math.CO
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 edge-local complement of G along the edge e. We call two graphs edge-locally equivalent if they are related by a sequence of edge-local complementations. The main result of this paper is an algebraic description of edge-local 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 edge-locally equivalent, (ii) a formula to count the number of graphs in a class of edge-local 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.
• ### The invariants of the local Clifford group(quant-ph/0410035)

Oct. 5, 2004 quant-ph
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.
• ### An efficient algorithm to recognize local Clifford equivalence of graph states(quant-ph/0405023)

Sept. 15, 2004 quant-ph
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.
• ### Local invariants of stabilizer codes(quant-ph/0404106)

Sept. 15, 2004 quant-ph
In [Phys. Rev. A 58, 1833 (1998)] a family of polynomial invariants which separate the orbits of multi-qubit 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 error-correcting 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 measurement-based model of quantum computation known as the one-way quantum computer.
• ### Graphical description of the action of local Clifford transformations on graph states(quant-ph/0308151)

Feb. 17, 2004 quant-ph
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.
• ### Local permutations of products of Bell states and entanglement distillation(quant-ph/0207154)

July 26, 2002 quant-ph
We present new algorithms for mixed-state multi-copy 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.