Search

In three dimensions, there is a nontrivial quantum cellular automaton (QCA) which disentangles the three-fermion Walker--Wang model, a model whose action depends on Stiefel--Whitney classes of the spacetime manifold. Here we present a conjectured generalization to higher dimensions. For an arbitrary symmetry protected topological phase of time reversal whose action depends on Stiefel--Whitney classes, we construct a corresponding QCA that we conjecture disentangles that phase. Some of our QCA are Clifford, and we relate these to a classification theorem of Clifford QCA. We identify Clifford QCA in $4m+1$ dimensions, for which we find a low-depth circuit description using non-Clifford gates but not with Clifford gates., Comment: v2, corrects and clarifies the Stiefel Whitney - QCA correspondence

Random reversible and quantum circuits form random walks on the alternating group $\mathrm{Alt}(2^n)$ and unitary group $\mathrm{SU}(2^n)$, respectively. Known bounds on the spectral gap for the $t$-th moment of these random walks have inverse-polynomial dependence in both $n$ and $t$. We prove that the gap for random reversible circuits is $\Omega(n^{-3})$ for all $t\geq 1$, and the gap for random quantum circuits is $\Omega(n^{-3})$ for $t \leq \Theta(2^{n/2})$. These gaps are independent of $t$ in the respective regimes. We can further improve both gaps to $n^{-1}/\mathrm{polylog}(n, t)$ for $t\leq 2^{\Theta(n)}$, which is tight up to polylog factors. Our spectral gap results have a number of consequences: 1) Random reversible circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error $t$-wise independent (even) permutations for all $t\geq 1$; for $t \leq \Theta(2^{n/6.1})$, we show that $\tilde{\mathcal{O}}(n^2 t)$ gates suffice. 2) Random quantum circuits with $\mathcal{O}(n^4 t)$ gates form multiplicative-error unitary $t$-designs for $t \leq \Theta(2^{n/2})$; for $t\leq \Theta(2^{2n/5})$, we show that $\tilde{\mathcal{O}}(n^2t)$ gates suffice. 3) The robust quantum circuit complexity of random circuits grows linearly for an exponentially long time, proving the robust Brown--Susskind conjecture [BS18,BCHJ+21]. Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the ``$\mathrm{PFC}$ ensemble'' from [MPSY24] together with an expander on the alternating group due to Kassabov [Kas07a], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians., Comment: 79 pages, 5 figures, v2: added references and minor changes to the presentation, v3: updated acknowledgements and minor changes to the presentation

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order $t$. Specifically, a step of the walk on the unitary or orthognoal group of dimension $2^{\mathsf n}$ is a random Pauli rotation $e^{\mathrm i \theta P /2}$. The spectral gap of this random walk is shown to be $\Omega(1/t)$, which coincides with the best previously known bound for a random walk on the permutation group on $\{0,1\}^{\mathsf n}$. This implies that the walk gives an $\varepsilon$-approximate unitary $t$-design in depth $O(\mathsf n t^2 + t \log 1/\varepsilon)d$ where $d=O(\log \mathsf n)$ is the circuit depth to implement $e^{\mathrm i \theta P /2}$. Our simple proof uses quadratic Casimir operators of Lie algebras., Comment: 21 pages, 1 figure

The surface code is one of the most popular quantum error correction codes. It comes with efficient decoders, such as the Minimum Weight Perfect Matching (MWPM) decoder and the Union-Find (UF) decoder, allowing for fast quantum error correction. For a general linear code or stabilizer code, the decoding problem is NP-hard. What makes it tractable for the surface code is the special structure of faults and checks: Each X and Z fault triggers at most two checks. As a result, faults can be interpreted as edges in a graph whose vertices are the checks, and the decoding problem can be solved using standard graph algorithms such as Edmonds' minimum-weight perfect matching algorithm. For general codes, this decoding graph is replaced by a hypergraph making the decoding problem more challenging. In this work, we propose two heuristic algorithms for splitting the hyperedges of a decoding hypergraph into edges. After splitting, hypergraph faults can be decoded using any surface code decoder. Due to the complexity of the decoding problem, we do not expect this strategy to achieve a good error correction performance for a general code. However, we empirically show that this strategy leads to a good performance for some classes of LDPC codes because they are defined by low weight checks. We apply this splitting decoder to Floquet codes for which some faults trigger up to four checks and verify numerically that this decoder achieves the maximum code distance for two instances of Floquet codes., Comment: 12 pages, 1 figure

We develop protocols for Hastings-Haah Floquet codes in the presence of dead qubits., Comment: 12 pages, 6 figures (correction to Fig. 4 and minor errors)

We investigate the evolution of quantum information under Pauli measurement circuits. We focus on the case of one- and two-dimensional systems, which are relevant to the recently introduced Floquet topological codes. We define local reversibility in context of measurement circuits, which allows us to treat finite depth measurement circuits on a similar footing to finite depth unitary circuits. In contrast to the unitary case, a finite depth locally reversible measurement circuit can implement a translation in one dimension. A locally reversible measurement circuit in two dimensions may also induce a flow of logical information along the boundary. We introduce "measurement quantum cellular automata" which unifies these ideas and define an index in one dimension to characterize the flow of logical operators. We find a $\mathbb{Z}_2$ bulk invariant for two-dimensional Floquet topological codes which indicates an obstruction to having a trivial boundary. We prove that the Hastings-Haah honeycomb code belongs to a class with such obstruction, which means that any boundary must have either nonlocal dynamics, period doubled, or admits anomalous boundary flow of quantum information., Comment: v2 changes: clarified the definition of "locally reversible measurement cycle" (LRMC), and added more examples of boundary circuits for the HH code

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a $\textsf{d}$-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$-close to the unknown unitary in diamond norm. We design an algorithm achieving error $\varepsilon$ using $O(\textsf{d}^2/\varepsilon)$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O(\textsf{d}^3/\varepsilon^2)$ [via standard process tomography] or $O(\textsf{d}^{2.5}/\varepsilon)$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to "bootstrap" an algorithm that can produce constant-error estimates to one that can produce $\varepsilon$-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega(\textsf{d}^2/\varepsilon)$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity., Comment: 43 pages; v2, minor edits for referee comments

We introduce invertible subalgebras of local operator algebras on lattices. An invertible subalgebra is defined to be one such that every local operator can be locally expressed by elements of the inveritible subalgebra and those of the commutant. On a two-dimensional lattice, an invertible subalgebra hosts a chiral anyon theory by a commuting Hamiltonian, which is believed not to be possible on any full local operator algebra. We prove that the stable equivalence classes of $\mathsf d$-dimensional invertible subalgebras form an abelian group under tensor product, isomorphic to the group of all $\mathsf d + 1$ dimensional QCA modulo blending equivalence and shifts. In an appendix, we consider a metric on the group of all QCA on infinite lattices and prove that the metric completion contains the time evolution by local Hamiltonians, which is only approximately locality-preserving. Our metric topology is strictly finer than the strong topology., Comment: 34 pages, 2 figures, (v2) includes a proof that any 1d invertible subalgebra is trivial, (v3) minor changes (v4) expanding the proof of A.5

A quantum cellular automaton (QCA) or a causal unitary is by definition an automorphism of local operator algebra, by which local operators are mapped to local operators. Quantum circuits of small depth, local Hamiltonian evolutions for short time, and translations (shifts) are examples. A Clifford QCA is one that maps any Pauli operator to a finite tensor product of Pauli operators. Here, we obtain a complete table of groups $\mathfrak C(\mathsf d,p)$ of translation invariant Clifford QCA in any spatial dimension $\mathsf d \ge 0$ modulo Clifford quantum circuits and shifts over prime $p$-dimensional qudits, where the circuits and shifts are allowed to obey only coarser translation invariance. The group $\mathfrak C(\mathsf d,p)$ is nonzero only for $\mathsf d = 2k+3$ if $p=2$ and $\mathsf d = 4k+3$ if $p$ is odd where~$k \ge 0$ is any integer, in which case $\mathfrak C(\mathsf d,p) \cong \widetilde{\mathfrak W}(\mathbb F_p)$, the classical Witt group of nonsingular quadratic forms over the finite field $\mathbb F_p$. It is well known that $\widetilde{\mathfrak W}(\mathbb F_2) \cong \mathbb Z/2\mathbb Z$, $\widetilde{\mathfrak W}(\mathbb F_p) \cong \mathbb Z/4\mathbb Z$ if $p = 3 \bmod 4$, and $\widetilde{\mathfrak W}(\mathbb F_p)\cong \mathbb Z/2\mathbb Z \oplus \mathbb Z/2\mathbb Z$ if $p = 1 \bmod 4$. The classification is achieved by a dimensional descent, which is a reduction of Laurent extension theorems for algebraic $L$-groups of surgery theory in topology., Comment: 48 pages (v2) minor revision in Sec.5.7 (v3) typo correction

Quantum error correction is crucial for any quantum computing platform to achieve truly scalable quantum computation. The surface code and its variants have been considered the most promising quantum error correction scheme due to their high threshold, low overhead, and relatively simple structure that can naturally be implemented in many existing qubit architectures, such as superconducting qubits. The recent development of Floquet codes offers another promising approach. By going beyond the usual paradigm of stabilizer codes, Floquet codes achieve similar performance while being constructed entirely from two-qubit measurements. This makes them particularly suitable for platforms where two-qubit measurements can be implemented directly, such as measurement-only topological qubits based on Majorana zero modes (MZMs). Here, we explain how two variants of Floquet codes can be implemented on MZM-based architectures without any auxiliary qubits for syndrome measurement and with shallow syndrome extraction sequences. We then numerically demonstrate their favorable performance. In particular, we show that they improve the threshold for scalable quantum computation in MZM-based systems by an order of magnitude, and significantly reduce space and time overheads below threshold., Comment: 16 pages, 10 figures. (v2): Corrected some inconsistencies, and a fixed bug affecting 4.8.8 simulations. Changed the article format

Quasiparticle excitations in $3+1$ dimensions can be either bosons or fermions. In this work, we introduce the notion of fermionic loop excitations in $3+1$ dimensional topological phases. Specifically, we construct a new many-body lattice invariant of gapped Hamiltonians, the loop self-statistics, that distinguishes two bosonic topological orders that both superficially resemble $3+1$ d ${\mathbb{Z}}_2$ gauge theory coupled to fermionic charged matter. The first has fermionic charges and bosonic ${\mathbb{Z}}_2$ gauge flux loops (FcBl) and is just the ordinary fermionic toric code. The second has fermionic charges and fermionic loops (FcFl), and, as we argue, can only exist at the boundary of a non-trivial 4+1d invertible bosonic phase, stable without any symmetries, i.e. it possesses a gravitational anomaly. We substantiate these claims by constructing an explicit exactly solvable $4+1$ d Walker-Wang model and computing the loop self-statistics in the fermionic ${\mathbb{Z}}_2$ gauge theory hosted at its boundary. We also show that the FcFl phase has the same gravitational anomaly as all-fermion quantum electrodynamics. Our results are in agreement with the recent classification of nondegenerate braided fusion 2-categories by Johnson-Freyd, and with the cobordism prediction of a non-trivial ${\mathbb{Z}}_2$ classified $4+1$ d invertible phase with action $S=\frac{1}{2} \int w_2 w_3$., Comment: V2: 62 pages, included proof of quantization of the gravitational anomaly indicator, expanded discussion, additional references. Close to published version

We introduce a simple construction of boundary conditions for the honeycomb code that uses only pairwise checks and allows parallelogram geometries at the cost of modifying the bulk measurement sequence. We discuss small instances of the code., Comment: 11 pages, 7 figures; v2 final version in Quantum

Triorthogonal codes are a class of quantum error correcting codes used in magic state distillation protocols. We classify all triorthogonal codes with $n+k \le 38$, where $n$ is the number of physical qubits and $k$ is the number of logical qubits of the code. We find $38$ distinguished triorthogonal subspaces and show that every triorthogonal code with $n+k\le 38$ descends from one of these subspaces through elementary operations such as puncturing and deleting qubits. Specifically, we associate each triorthogonal code with a Reed-Muller polynomial of weight $n+k$, and classify the Reed-Muller polynomials of low weight using the results of Kasami, Tokura, and Azumi and an extensive computerized search. In an appendix independent of the main text, we improve a magic state distillation protocol by reducing the time variance due to stochastic Clifford corrections., Comment: 27 pages, 1 figure (v2) minor changes

We present a quantum error correcting code with dynamically generated logical qubits. When viewed as a subsystem code, the code has no logical qubits. Nevertheless, our measurement patterns generate logical qubits, allowing the code to act as a fault-tolerant quantum memory. Our particular code gives a model very similar to the two-dimensional toric code, but each measurement is a two-qubit Pauli measurement., Comment: 18 pages, 7 figures; v2 final version accepted in Quantum

We introduce a notion of homogeneous topological order, which is obeyed by most, if not all, known examples of topological order including fracton phases on quantum spins (qudits). The notion is a condition on the ground state subspace, rather than on the Hamiltonian, and demands that given a collection of ball-like regions, any linear transformation on the ground space be realized by an operator that avoids the ball-like regions. We derive a bound on the ground state degeneracy $\mathcal D$ for systems with homogeneous topological order on an arbitrary closed Riemannian manifold of dimension $d$, which reads \[ \log \mathcal D \le c \mu (L/a)^{d-2}.\] Here, $L$ is the diameter of the system, $a$ is the lattice spacing, and $c$ is a constant that only depends on the isometry class of the manifold, and $\mu$ is a constant that only depends on the density of degrees of freedom. If $d=2$, the constant $c$ is the (demi)genus of the space manifold. This bound is saturated up to constants by known examples., Comment: 12 pages, 2 figures (v2) clarified the main theorem for d=2, added some detail for Pauli stabilizer models, (v3) minor corrections

We present a quantum LDPC code family that has distance $\Omega(N^{3/5}/\operatorname{polylog}(N))$ and $\tilde\Theta(N^{3/5})$ logical qubits. This is the first quantum LDPC code construction which achieves distance greater than $N^{1/2} \operatorname{polylog}(N)$. The construction is based on generalizing the homological product of codes to a fiber bundle., Comment: 39 pages, 2 figures; v2 gives self-contained presentation of weight reduction using weight reduction for classical base code. Also contains explanation of relation between codes in terms of homotopy equivalence of chain complexes

Motivated by recent work showing that a quantum error correcting code can be generated by hybrid dynamics of unitaries and measurements, we study the long time behavior of such systems. We demonstrate that even in the "mixed" phase, a maximally mixed initial density matrix is purified on a time scale equal to the Hilbert space dimension (i.e., exponential in system size), albeit with noisy dynamics at intermediate times which we connect to Dyson Brownian motion. In contrast, we show that free fermion systems -- i.e., ones where the unitaries are generated by quadratic Hamiltonians and the measurements are of fermion bilinears -- purify in a time quadratic in the system size. In particular, a volume law phase for the entanglement entropy cannot be sustained in a free fermion system., Comment: 24 pages, 2 figures (v3) expanding the proof of Lemma 3

Magic state distillation uses special codes to suppress errors in input states, which are often tailored to a Clifford-twirled error model. We present detailed measurement sequences for magic state distillation protocols which can suppress arbitrary errors on any part of a protocol, assuming the independence of errors across qubits. Provided with input magic states, our protocol operates on a two-dimensional square grid by measurements of $ZZ$ on horizontal pairs of qubits, $XX$ on vertical pairs, and $Z,X$ on single qubits., Comment: 8 pages

The surface code is a prominent topological error-correcting code exhibiting high fault-tolerance accuracy thresholds. Conventional schemes for error correction with the surface code place qubits on a planar grid and assume native CNOT gates between the data qubits with nearest-neighbor ancilla qubits. Here, we present surface code error-correction schemes using $\textit{only}$ Pauli measurements on single qubits and on pairs of nearest-neighbor qubits. In particular, we provide several qubit layouts that offer favorable trade-offs between qubit overhead, circuit depth and connectivity degree. We also develop minimized measurement sequences for syndrome extraction, enabling reduced logical error rates and improved fault-tolerance thresholds. Our work applies to topologically protected qubits realized with Majorana zero modes and to similar systems in which multi-qubit Pauli measurements rather than CNOT gates are the native operations., Comment: Added overhead analysis

We construct an exactly solvable commuting projector model for a $4+1$ dimensional ${\mathbb Z}_2$ symmetry-protected topological phase (SPT) which is outside the cohomology classification of SPTs. The model is described by a decorated domain wall construction, with "three-fermion" Walker-Wang phases on the domain walls. We describe the anomalous nature of the phase in several ways. One interesting feature is that, in contrast to in-cohomology phases, the effective ${\mathbb Z}_2$ symmetry on a $3+1$ dimensional boundary cannot be described by a quantum circuit and instead is a nontrivial quantum cellular automaton (QCA). A related property is that a codimension-two defect (for example, the termination of a ${\mathbb Z}_2$ domain wall at a trivial boundary) will carry nontrivial chiral central charge $4$ mod $8$. We also construct a gapped symmetric topologically-ordered boundary state for our model, which constitutes an anomalous symmetry enriched topological phase outside of the classification of arXiv:1602.00187, and define a corresponding anomaly indicator., Comment: 57 pages, 6 figures

We consider the group structure of quantum cellular automata (QCA) modulo circuits and show that it is abelian even without assuming the presence of ancillas, at least for most reasonable choices of control space; this is a corollary of a general method of ancilla removal. Further, we show how to define a group of QCA that is well-defined without needing to use families, by showing how to construct a coherent family containing an arbitrary finite QCA; the coherent family consists of QCA on progressively finer systems of qudits where any two members are related by a shallow quantum circuit. This construction applied to translation invariant QCA shows that all translation invariant QCA in three dimensions and all translation invariant Clifford QCA in any dimension are coherent., Comment: 25 pages, 10 figures

We study locality preserving automorphisms of operator algebras on $D$-dimensional uniform lattices of prime $p$-dimensional qudits (QCA), specializing in those that are translation invariant (TI) and map every prime $p$-dimensional Pauli matrix to a tensor product of Pauli matrices (Clifford). We associate antihermitian forms of unit determinant over Laurent polynomial rings to TI Clifford QCA with lattice boundaries, and prove that the form determines the QCA up to Clifford circuits and shifts (trivial). It follows that every 2D TI Clifford QCA is trivial since the antihermitian form in this case is always trivial. Further, we prove that for any $D$ the fourth power of any TI Clifford QCA is trivial. We present explicit examples of nontrivial TI Clifford QCA for $D=3$ and any odd prime $p$, and show that the Witt group of the finite field $\mathbb F_p$ is a subgroup of the group $\mathfrak C(D = 3, p)$ of all TI Clifford QCA modulo trivial ones. That is, $\mathfrak C(D = 3, p \equiv 1 \mod 4) \supseteq \mathbb Z_2 \times \mathbb Z_2$ and $\mathfrak C(D = 3, p \equiv 3 \mod 4) \supseteq \mathbb Z_4$. The examples are found by disentangling the ground state of a commuting Pauli Hamiltonian which is constructed by coupling layers of prime dimensional toric codes such that an exposed surface has an anomalous topological order that is not realizable by commuting Pauli Hamiltonians strictly in two dimensions. In an appendix independent of the main body of the paper, we revisit a recent theorem of Freedman and Hastings that any two-dimensional QCA, which is not necessarily Clifford or translation invariant, is a constant depth quantum circuit followed by a shift. We give a more direct proof of the theorem without using any ancillas., Comment: 43 pages and a calculation note in Mathematica, (v2, v3) a new section on boundary antihermitian forms (v4) more detail (v5) fixing Lemma III.11

We analyze the class of Generalized Double Semion (GDS) models in arbitrary dimensions from the point of view of lattice Hamiltonians. We show that on a $d$-dimensional spatial manifold $M$ the dual of the GDS is equivalent, up to constant depth local quantum circuits, to a group cohomology theory tensored with lower dimensional cohomology models that depend on the manifold $M$. We comment on the space-time topological quantum field theory (TQFT) interpretation of this result. We also investigate the GDS in the presence of time reversal symmetry, showing that it forms a non-trivial symmetry enriched toric code phase in odd spatial dimensions., Comment: 28 pages (v2) close to final version

We investigate two dimensional compactifications of three dimensional fractonic stabilizer models. We find the two dimensional topological phases produced as a function of compactification radius for the X-cube model and Haah's cubic code. Furthermore, we uncover translation symmetry-enrichment in the compactified cubic code that leads to twisted boundary conditions., Comment: 15 + 2 pages, 4 figures, 1 + 6 tables

We prove that on any two-dimensional lattice of qudits of a prime dimension, every translation invariant Pauli stabilizer group with local generators and with code distance being the linear system size, is decomposed by a local Clifford circuit of constant depth into a finite number of copies of the toric code (abelian discrete gauge theory) stabilizer group. This means that under local Clifford circuits the number of toric code copies is the complete invariant of topological Pauli stabilizer codes. Previously, the same conclusion was obtained under the assumption of nonchirality for qubit codes or the Calderbank-Shor-Steane structure for prime qudit codes; we do not assume any of these., Comment: 19 pages, (v2) removed the need of Clifford QCA of v1 using recent results (v3) some clarification, minor rewording

We consider an algorithm to approximate complex-valued periodic functions $f(e^{i\theta})$ as a matrix element of a product of $SU(2)$-valued functions, which underlies so-called quantum signal processing. We prove that the algorithm runs in time $\mathcal O(N^3 \mathrm{polylog}(N/\epsilon))$ under the random-access memory model of computation where $N$ is the degree of the polynomial that approximates $f$ with accuracy $\epsilon$; previous efficiency claim assumed a strong arithmetic model of computation and lacked numerical stability analysis., Comment: 22 pages, (v2) numerical experiment result, clarifications and minor fixes, (v3) removed the need of distinguishing real roots from nonreal ones, and elaborated the error analysis (v4) footnote added. An implementation available at https://github.com/microsoft/Quantum-NC

We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice and the Hamiltonian only includes geometrically local interactions (i.e., a qubit may only interact with qubits in its vicinity). This class of Hamiltonians is very general and is believed to capture fundamental interactions of physics. Our algorithm simulates the time evolution of such a Hamiltonian on $n$ qubits for time $T$ up to error $\epsilon$ using $\mathcal O( nT \mathrm{polylog} (nT/\epsilon))$ gates with depth $\mathcal O(T \mathrm{polylog} (nT/\epsilon))$. Our algorithm is the first simulation algorithm that achieves gate cost quasilinear in $nT$ and polylogarithmic in $1/\epsilon$. Our algorithm also readily generalizes to time-dependent Hamiltonians and yields an algorithm with similar gate count for any piecewise slowly varying time-dependent bounded local Hamiltonian. We also prove a matching lower bound on the gate count of such a simulation, showing that any quantum algorithm that can simulate a piecewise constant bounded local Hamiltonian in one dimension to constant error requires $\tilde \Omega(nT)$ gates in the worst case. The lower bound holds even if we only require the output state to be correct on local measurements. To our best knowledge, this is the first nontrivial lower bound on the gate complexity of the simulation problem. Our algorithm is based on a decomposition of the time-evolution unitary into a product of small unitaries using Lieb-Robinson bounds. In the appendix, we prove a Lieb-Robinson bound tailored to Hamiltonians with small commutators between local terms, giving zero Lieb-Robinson velocity in the limit of commuting Hamiltonians. This improves the performance of our algorithm when the Hamiltonian is close to commuting., Comment: 37 pages, 4 figures (v2) refs added (v3) FOCS 2018 (v4) minor corrections

A divisible binary classical code is one in which every code word has weight divisible by a fixed integer. If the divisor is $2^\nu$ for a positive integer $\nu$, then one can construct a Calderbank-Shor-Steane (CSS) code, where $X$-stabilizer space is the divisible classical code, that admits a transversal gate in the $\nu$-th level of Clifford hierarchy. We consider a generalization of the divisibility by allowing a coefficient vector of odd integers with which every code word has zero dot product modulo the divisor. In this generalized sense, we construct a CSS code with divisor $2^{\nu+1}$ and code distance $d$ from any CSS code of code distance $d$ and divisor $2^\nu$ where the transversal $X$ is a nontrivial logical operator. The encoding rate of the new code is approximately $d$ times smaller than that of the old code. In particular, for large $d$ and $\nu \ge 2$, our construction yields a CSS code of parameters $[[O(d^{\nu-1}), \Omega(d),d]]$ admitting a transversal gate at the $\nu$-th level of Clifford hierarchy. For our construction we introduce a conversion from magic state distillation protocols based on Clifford measurements to those based on codes with transversal $T$-gates. Our tower contains, as a subclass, generalized triply even CSS codes that have appeared in so-called gauge fixing or code switching methods., Comment: 26 pages, 1 figure, (v2) minor changes

Recently we proposed a family of magic state distillation protocols that obtains asymptotic performance that is conjectured to be optimal. This family depends upon several codes, called "inner codes" and "outer codes." We presented some small examples of these codes as well as an analysis of codes in the asymptotic limit. Here, we analyze such protocols in an intermediate size regime, using hundreds to thousands of qubits. We use BCH inner codes, combined with various outer codes. We extend our protocols by adding error correction in some cases. We present a variety of protocols in various input error regimes; in many cases these protocols require significantly fewer input magic states to obtain a given output error than previous protocols., Comment: 33 pages

We present several different codes and protocols to distill $T$, controlled-$S$, and Toffoli (or $CCZ$) gates. One construction is based on codes that generalize the triorthogonal codes, allowing any of these gates to be induced at the logical level by transversal $T$. We present a randomized construction of generalized triorthogonal codes obtaining an asymptotic distillation efficiency $\gamma\rightarrow 1$. We also present a Reed-Muller based construction of these codes which obtains a worse $\gamma$ but performs well at small sizes. Additionally, we present protocols based on checking the stabilizers of $CCZ$ magic states at the logical level by transversal gates applied to codes; these protocols generalize the protocols of 1703.07847. Several examples, including a Reed-Muller code for $T$-to-Toffoli distillation, punctured Reed-Muller codes for $T$-gate distillation, and some of the check based protocols, require a lower ratio of input gates to output gates than other known protocols at the given order of error correction for the given code size. In particular, we find a $512$ T-gate to $10$ Toffoli gate code with distance $8$ as well as triorthogonal codes with parameters $[[887,137,5]],[[912,112,6]],[[937,87,7]]$ with very low prefactors in front of the leading order error terms in those codes., Comment: 28 pages. (v2) fixed a part of the proof on random triorthogonal codes, added comments on Clifford circuits for Reed-Muller states (v3) minor change

Random quantum circuits yield minimally structured models for chaotic quantum dynamics, able to capture for example universal properties of entanglement growth. We provide exact results and coarse-grained models for the spreading of operators by quantum circuits made of Haar-random unitaries. We study both 1+1D and higher dimensions, and argue that the coarse-grained pictures carry over to operator spreading in generic many-body systems. In 1+1D, we demonstrate that the out-of-time-order correlator (OTOC) satisfies a biased diffusion equation, which gives exact results for the spatial profile of the OTOC, and the butterfly speed $v_{B}$. We find that in 1+1D the `front' of the OTOC broadens diffusively, with a width scaling in time as $t^{1/2}$. We address fluctuations in the OTOC between different realizations of the random circuit, arguing that they are negligible in comparison to the broadening of the front. Turning to higher D, we show that the averaged OTOC can be understood exactly via a remarkable correspondence with a classical droplet growth problem. This implies that the width of the front of the averaged OTOC scales as $t^{1/3}$ in 2+1D and $t^{0.24}$ in 3+1D (KPZ exponents). We support our analytic argument with simulations in 2+1D. We point out that, in a lattice model, the late time shape of the spreading operator is in general not spherical. However when full spatial rotational symmetry is present in 2+1D, our mapping implies an exact asymptotic form for the OTOC in terms of the Tracy-Widom distribution. For an alternative perspective on the OTOC in 1+1D, we map it to the partition function of an Ising-like model. As a result of special structure arising from unitarity, this partition function reduces to a random walk calculation which can be performed exactly. We also use this mapping to give exact results for entanglement growth in 1+1D circuits., Comment: 29 pages, 16 figures. v2: new appendix on 'mean field'

We present an infinite family of protocols to distill magic states for $T$-gates that has a low space overhead and uses an asymptotic number of input magic states to achieve a given target error that is conjectured to be optimal. The space overhead, defined as the ratio between the physical qubits to the number of output magic states, is asymptotically constant, while both the number of input magic states used per output state and the $T$-gate depth of the circuit scale linearly in the logarithm of the target error $\delta$ (up to $\log \log 1/\delta$). Unlike other distillation protocols, this protocol achieves this performance without concatenation and the input magic states are injected at various steps in the circuit rather than all at the start of the circuit. The protocol can be modified to distill magic states for other gates at the third level of the Clifford hierarchy, with the same asymptotic performance. The protocol relies on the construction of weakly self-dual CSS codes with many logical qubits and large distance, allowing us to implement control-SWAPs on multiple qubits. We call this code the "inner code". The control-SWAPs are then used to measure properties of the magic state and detect errors, using another code that we call the "outer code". Alternatively, we use weakly-self dual CSS codes which implement controlled Hadamards for the inner code, reducing circuit depth. We present several specific small examples of this protocol., Comment: 39 pages, (v2) renamed "odd" and "even" weakly self-dual CSS codes of (v1) to "normal" and "hyperbolic" codes, respectively. (v3) published in Quantum

We investigate relaxation in the recently discovered "fracton" models and discover that these models naturally host glassy quantum dynamics in the absence of quenched disorder. We begin with a discussion of "type I" fracton models, in the taxonomy of Vijay, Haah, and Fu. We demonstrate that in these systems, the mobility of charges is suppressed exponentially in the inverse temperature. We further demonstrate that when a zero temperature type I fracton model is placed in contact with a finite temperature heat bath, the approach to equilibrium is a logarithmic function of time over an exponentially wide window of time scales. Generalizing to the more complex "type II" fracton models, we find that the charges exhibit subdiffusion upto a relaxation time that diverges at low temperatures as a super-exponential function of inverse temperature. This behaviour is reminiscent of "nearly localized" disordered systems, but occurs with a translation invariant three-dimensional Hamiltonian. We also conjecture that fracton models with conserved charge may support a phase which is a thermal metal but a charge insulator., Comment: 15 pages, 14 figures

We study the fundamental limits on the reliable storage of quantum information in lattices of qubits by deriving tradeoff bounds for approximate quantum error correcting codes. We introduce a notion of local approximate correctability and code distance, and give a number of equivalent formulations thereof, generalizing various exact error-correction criteria. Our tradeoff bounds relate the number of physical qubits $n$, the number of encoded qubits $k$, the code distance $d$, the accuracy parameter $\delta$ that quantifies how well the erasure channel can be reversed, and the locality parameter $\ell$ that specifies the length scale at which the recovery operation can be done. In a regime where the recovery is successful to accuracy $\epsilon$ that is exponentially small in $\ell$, which is the case for perturbations of local commuting projector codes, our bound reads $kd^{\frac{2}{D-1}} \le O\bigl(n (\log n)^{\frac{2D}{D-1}} \bigr)$ for codes on $D$-dimensional lattices of Euclidean metric. We also find that the code distance of any local approximate code cannot exceed $O\bigl(\ell n^{(D-1)/D}\bigr)$ if $\delta \le O(\ell n^{-1/D})$. As a corollary of our formulation of correctability in terms of logical operator avoidance, we show that the code distance $d$ and the size $\tilde d$ of a minimal region that can support all approximate logical operators satisfies $\tilde d d^{\frac{1}{D-1}}\le O\bigl( n \ell^{\frac{D}{D-1}} \bigr)$, where the logical operators are accurate up to $O\bigl( ( n \delta / d )^{1/2}\bigr)$ in operator norm. Finally, we prove that for two-dimensional systems if logical operators can be approximated by operators supported on constant-width flexible strings, then the dimension of the code space must be bounded. This supports one of the assumptions of algebraic anyon theories, that there exist only finitely many anyon types., Comment: 20+10 pages, 5 figures. v2, Final published version to appear in the journal Quantum. v3, fixing Lemma 15(iv)

Characterizing how entanglement grows with time in a many-body system, for example after a quantum quench, is a key problem in non-equilibrium quantum physics. We study this problem for the case of random unitary dynamics, representing either Hamiltonian evolution with time--dependent noise or evolution by a random quantum circuit. Our results reveal a universal structure behind noisy entanglement growth, and also provide simple new heuristics for the `entanglement tsunami' in Hamiltonian systems without noise. In 1D, we show that noise causes the entanglement entropy across a cut to grow according to the celebrated Kardar--Parisi--Zhang (KPZ) equation. The mean entanglement grows linearly in time, while fluctuations grow like $(\text{time})^{1/3}$ and are spatially correlated over a distance $\propto (\text{time})^{2/3}$. We derive KPZ universal behaviour in three complementary ways, by mapping random entanglement growth to: (i) a stochastic model of a growing surface; (ii) a `minimal cut' picture, reminiscent of the Ryu--Takayanagi formula in holography; and (iii) a hydrodynamic problem involving the dynamical spreading of operators. We demonstrate KPZ universality in 1D numerically using simulations of random unitary circuits. Importantly, the leading order time dependence of the entropy is deterministic even in the presence of noise, allowing us to propose a simple `minimal cut' picture for the entanglement growth of generic Hamiltonians, even without noise, in arbitrary dimensionality. We clarify the meaning of the `velocity' of entanglement growth in the 1D `entanglement tsunami'. We show that in higher dimensions, noisy entanglement evolution maps to the well-studied problem of pinning of a membrane or domain wall by disorder.

We show that Ramsey spectroscopy of fermionic alkaline-earth atoms in a square-well trap provides an efficient and accurate estimate for the eigenspectrum of a density matrix whose $n$ copies are stored in the nuclear spins of $n$ such atoms. This spectrum estimation is enabled by the high symmetry of the interaction Hamiltonian, dictated, in turn, by the decoupling of the nuclear spin from the electrons and by the shape of the square-well trap. Practical performance of this procedure and its potential applications to quantum computing, quantum simulation, and time-keeping with alkaline-earth atoms are discussed., Comment: Journal version. 4 pages (plus 6 pages of supplemental material), 3 figures

This is a note from a series of lectures at Encuentro Colombiano de Computacion Cuantica, Universidad de los Andes, Bogota, Colombia, 2015. The purpose is to introduce additive quantum error correcting codes, with emphasis on the use of binary representation of Pauli matrices and modules over a translation group algebra. The topics include symplectic vector spaces, Clifford group, cleaning lemma, an error correcting criterion, entanglement spectrum, implications of the locality of stabilizer group generators, and the classification of translation-invariant one-dimensional additive codes and two-dimensional CSS codes with large code distances. In particular, we describe an algorithm to find a Clifford quantum circuit (CNOTs) to transform any two-dimensional translation-invariant CSS code on qudits of a prime dimension with code distance being the linear system size, into a tensor product of finitely many copies of the qudit toric code and a product state. Thus, the number of embedded toric codes is the complete invariant of these CSS codes under local Clifford circuits., Comment: 54 pages; (v2) ref. added

Topological entanglement entropy has been regarded as a smoking-gun signature of topological order in two dimensions, capturing the total quantum dimension of the topological particle content. An extrapolation method on cylinders has been used frequently to measure the topological entanglement entropy. Here, we show that a class of short-range entangled 2D states, when put on an infinite cylinder of circumference $L$, exhibits the entanglement R\'enyi entropy of any integer index $\alpha \ge 2$ that obeys $S_\alpha = a L - \gamma$ where $a, \gamma > 0 $. Under the extrapolation method, the subleading term $\gamma$ would be identified as the topological entanglement entropy, which is spurious. A nonzero $\gamma$ is always present if the 2D state reduces to a certain symmetry-protected topological 1D state, upon disentangling spins that are far from the entanglement cut. The internal symmetry that stabilizes $\gamma > 0$ is not necessarily a symmetry of the 2D state, but should be present after the disentangling reduction. If the symmetry is absent, $\gamma$ decays exponentially in $L$ with a characteristic length, termed as a replica correlation length, which can be arbitrarily large compared to the two-point correlation length of the 2D state. We propose a simple numerical procedure to measure the replica correlation length through replica correlation functions. We also calculate the replica correlation functions for representative wave functions of abelian discrete gauge theories and the double semion theory in 2D, to show that they decay abruptly to zero. This supports a conjecture that the replica correlation length being small implies that the subleading term from the extrapolation method determines the total quantum dimension., Comment: 19 pages, 12 figures; (v2) more references, added discussion on Gibbs states and higher dimensions

We introduce a generalization of conventional lattice gauge theory to describe fracton topological phases, which are characterized by immobile, point-like topological excitations, and sub-extensive topological degeneracy. We demonstrate a duality between fracton topological order and interacting spin systems with symmetries along extensive, lower-dimensional subsystems, which may be used to systematically search for and characterize fracton topological phases. Commutative algebra and elementary algebraic geometry provide an effective mathematical toolset for our results. Our work paves the way for identifying possible material realizations of fracton topological phases., Comment: 9 pages, 4 figures; 8 pages of appendices, 3 figures

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error $\epsilon$ in trace distance required $O(dr^2/\epsilon^2)$ copies for a $d$-dimensional density matrix of rank $r$. Here, we give a theoretical measurement scheme (POVM) that requires $O (dr/ \delta ) \ln (d/\delta) $ copies of $\rho$ to error $\delta$ in infidelity, and a matching lower bound up to logarithmic factors. This implies $O( (dr / \epsilon^2) \ln (d/\epsilon) )$ copies suffice to achieve error $\epsilon$ in trace distance. We also prove that for independent (product) measurements, $\Omega(dr^2/\delta^2) / \ln(1/\delta)$ copies are necessary in order to achieve error $\delta$ in infidelity. For fixed $d$, our measurement can be implemented on a quantum computer in time polynomial in $n$., Comment: revtex, 16 pages, 3 figures. (v1) in STOC 2016, 913-925. (v2) improved lower bound for independent measurements

We introduce exactly solvable models of interacting (Majorana) fermions in $d \ge 3$ spatial dimensions that realize a new kind of topological quantum order, building on a model presented in ref. [1]. These models have extensive topological ground-state degeneracy and a hierarchy of point-like, topological excitations that are only free to move within sub-manifolds of the lattice. In particular, one of our models has fundamental excitations that are completely stationary. To demonstrate these results, we introduce a powerful polynomial representation of commuting Majorana Hamiltonians. Remarkably, the physical properties of the topologically-ordered state are encoded in an algebraic variety, defined by the common zeros of a set of polynomials over a finite field. This provides a "geometric" framework for the emergence of topological order., Comment: 13 pages, 5 figures

We study a translation invariant spin model in a three-dimensional regular lattice, called the cubic code model, in the presence of arbitrary extensive perturbations. Below a critical perturbation strength, we show that most states with finite energy are localized; the overwhelming majority of such states have energy concentrated around a finite number of defects, and remain so for a time that is near-exponential in the distance between the defects. This phenomenon is due to an emergent superselection rule and does not require any disorder. An extensive number of local integrals of motion for these finite energy sectors are identified as well. Our analysis extends more generally to systems with immobile topological excitations., Comment: 7.5+1pages, 2 figures

For an anyon model in two spatial dimensions described by a modular tensor category, the topological S-matrix encodes the mutual braiding statistics, the quantum dimensions, and the fusion rules of anyons. It is nontrivial whether one can compute the S-matrix from a single ground state wave function. Here, we define a class of Hamiltonians consisting of local commuting projectors and an associated matrix that is invariant under local unitary transformations. We argue that the invariant is equivalent to the topological S-matrix. The definition does not require degeneracy of the ground state. We prove that the invariant depends on the state only, in the sense that it can be computed by any Hamiltonian in the class of which the state is a ground state. As a corollary, we prove that any local quantum circuit that connects two ground states of quantum double models (discrete gauge theories) with non-isomorphic abelian groups, must have depth that is at least linear in the system's diameter. As a tool for the proof, a manifestly Hamiltonian-independent notion of locally invisible operators is introduced. This gives a sufficient condition for a many-body state not to be generated from a product state by any small depth quantum circuit; this is a many-body entanglement witness., Comment: revtex 11pt, 43 pages, (v2) minor change (v3) ref. added. To appear in Commun. Math. Phys

We study entanglement renormalization group transformations for the ground states of a spin model, called cubic code model $H_A$ in three dimensions, in order to understand long-range entanglement structure. The cubic code model has degenerate and locally indistinguishable ground states under periodic boundary conditions. In the entanglement renormalization, one applies local unitary transformations on a state, called disentangling transformations, after which some of the spins are completely disentangled from the rest and then discarded. We find a disentangling unitary to establish equivalence of the ground state of $H_A$ on a lattice of lattice spacing $a$ to the tensor product of ground spaces of two independent Hamiltonians $H_A$ and $H_B$ on lattices of lattice spacing $2a$. We further find a disentangling unitary for the ground space of $H_B$ with the lattice spacing $a$ to show that it decomposes into two copies of itself on the lattice of the lattice spacing $2a$. The disentangling transformations yield a tensor network description for the ground state of the cubic code model. Using exact formulas for the degeneracy as a function of system size, we show that the two Hamiltonians $H_A$ and $H_B$ represent distinct phases of matter., Comment: 13 pages + supplementary Mathematica file containing calculation. (v2) Added a section on an algebro-geometric criterion for bifurcation

This thesis addresses whether it is possible to build a robust memory device for quantum information. A three-dimensional gapped lattice spin model is found which demonstrates for the first time that a reliable quantum memory at finite temperature is possible, at least to some extent. When quantum information is encoded into a highly entangled ground state of this model and subjected to thermal errors, the errors remain easily correctable for a long time without any active intervention, because a macroscopic energy barrier keeps the errors well localized. As a result, stored quantum information can be retrieved faithfully for a memory time which grows exponentially with the square of the inverse temperature. In contrast, for previously known types of topological quantum storage in three or fewer spatial dimensions the memory time scales exponentially with the inverse temperature, rather than its square. This spin model exhibits a previously unexpected topological quantum order, in which ground states are locally indistinguishable, pointlike excitations are immobile, and the immobility is not affected by small perturbations of the Hamiltonian. The degeneracy of the ground state, though also insensitive to perturbations, is a complicated number-theoretic function of the system size, and the system bifurcates into multiple noninteracting copies of itself under real-space renormalization group transformations. The degeneracy, the excitations, and the renormalization group flow can be analyzed using a framework that exploits the spin model's symmetry and some associated free resolutions of modules over polynomial algebras., Comment: PhD thesis. 200 pages. Based on arXiv:1011.3529, arXiv:1101.1962, arXiv:1105.4159, arXiv:1112.3252, arXiv:1204.1063. Appendix on commutative algebra

We propose a new family of error detecting stabilizer codes with an encoding rate 1/3 that permit a transversal implementation of the pi/8-rotation $T$ on all logical qubits. The new codes are used to construct protocols for distilling high-quality `magic' states $T|+>$ by Clifford group gates and Pauli measurements. The distillation overhead has a poly-logarithmic scaling as a function of the output accuracy, where the degree of the polynomial is $\log_2{3}\approx 1.6$. To construct the desired family of codes, we introduce the notion of a triorthogonal matrix --- a binary matrix in which any pair and any triple of rows have even overlap. Any triorthogonal matrix gives rise to a stabilizer code with a transversal $T$-gate on all logical qubits, possibly augmented by Clifford gates. A powerful numerical method for generating triorthogonal matrices is proposed. Our techniques lead to a two-fold overhead reduction for distilling magic states with output accuracy $10^{-12}$ compared with the best previously known protocol., Comment: 11 pages, 3 figures

We study unfrustrated spin Hamiltonians that consist of commuting tensor products of Pauli matrices. Assuming translation-invariance, a family of Hamiltonians that belong to the same phase of matter is described by a map between modules over the translation-group algebra, so homological methods are applicable. In any dimension every point-like charge appears as a vertex of a fractal operator, and can be isolated with energy barrier at most logarithmic in the separation distance. For a topologically ordered system in three dimensions, there must exist a point-like nontrivial charge. If the ground-state degeneracy is upper bounded by a constant independent of the system size, then the topological charges in three dimensions always appear at the end points of string operators. A connection between the ground state degeneracy and the number of points on an algebraic set is discussed. Tools to handle local Clifford unitary transformations are given., Comment: amsart 48 pages; (v2) minor change, ref. added, (v3) stronger conclusion about topological charges, (v4) comments and ref. added, reproducing the result of 1103.1885

A big open question in the quantum information theory concerns feasibility of a self-correcting quantum memory. A quantum state recorded in such memory can be stored reliably for a macroscopic time without need for active error correction if the memory is put in contact with a cold enough thermal bath. In this paper we derive a rigorous lower bound on the memory time $T_{mem}$ of the 3D Cubic Code model which was recently conjectured to have a self-correcting behavior. Assuming that dynamics of the memory system can be described by a Markovian master equation of Davies form, we prove that $T_{mem}\ge L^{c\beta}$ for some constant $c>0$, where $L$ is the lattice size and $\beta$ is the inverse temperature of the bath. However, this bound applies only if the lattice size does not exceed certain critical value $L^*\sim e^{\beta/3}$. We also report a numerical Monte Carlo simulation of the studied memory indicating that our analytic bounds on $T_{mem}$ are tight up to constant coefficients. In order to model the readout step we introduce a new decoding algorithm which might be of independent interest. Our decoder can be implemented efficiently for any topological stabilizer code and has a constant error threshold under random uncorrelated errors., Comment: 40 pages, 6 figures