Day 2 of the conference. By the way, it is pretty difficult to get all this stuff written down correctly the first time through! So, if you see any mistakes please leave a comment so I can fix them.
Some quantum Hamiltonians have ground states which are amenable to Monte Carlo techniques because of the absence of the sign problem. We say a Hamiltonian is stoquastic iff, given some product basis, the off diagonal elements of each local term are real and non-positive. (One can apply local unitary operations to potentially transform some Hamiltonian into a stoquastic one.) Examples of stoquastic Hamiltonians: ferromagnets, quantum transverse-field Ising model, Jaynes-Cummings, Spin-boson and, importantly, Josephson-junction flux qubit Hamiltonians such as those engineered by D-wave for adiabatic quantum computation (AQC). Given a stoquastic Hamiltonian, we can define for some sufficiently small and is a non-negative matrix. By the Perron-Frobenius theorem the largest eigenvalue eigenvector is a probability distribution. Therefore, we can potentially use quantum Monte Carlo (QMC) to sample from it. Theorem 1: Stoquastic frustration-free AQC can be efficiently simulated classically. Recall the matrix from before. We can sample the matrix elements of efficiently because the Hamiltonian is local. Since the Hamiltonian is frustration-free (FF), the ground state is annihilated term-by-term. We would like to set up a Markov chain which allows us to sample from the ground state. We can define a stochastic matrix from and the weights in the ground state , namely where is the diagonal matrix with the ground state weights on the diagonal. This is a stochastic matrix. Because the Hamiltonian is FF, we can compute the ratio . This doesn’t seem to work in the non-FF case. Now if you iterate and there is a gap you will converge in polynomial time. In the frustrated case, we don’t know how to compute the ratio anymore. An alternative approach: we know the ground state is well-approximated by the Gibbs state at low temperature. The Gibbs matrix is non-negative if the Hamiltonian is stoquastic (but frustrated). The partition function is a sum over non-negative weights now. We can compute each of these weights efficiently, so now we want to estimate the sum with QMC. “World-line QMC.” You can use some kind of Metropolis rule for accepting and rejecting moves.
Spiros Michalakis, Stability of Frustration-free Hamiltonians, arXiv:1109.1588. Joint work with J. Pytel.
The challenge is to find a minimal set of assumptions under which gapped Hamiltonians have a stable spectral gap against weak local perturbations. Not every gapped system is stable. Consider a simple Ising model where the transverse field is a perturbation. This perturbation splits the degeneracy of the ground state. Another example is an Ising model with a defect at the origin. The lesson seems to be that local distinguishability leads to instability of the ground state degeneracy and/or the gap. Now define FF Hamiltonians (FFH). Every FFH on a lattice is the extension of another FFH on some smaller ball . The ground state projectors satisfy where is the global ground state projector. Now define topological quantum order (TQO). Roughly, no sufficiently local operator should be able to distinguish two orthogonal ground states. The toric code is an example of a model with TQO. But TQO is not enough for stability, as a simple counterexample shows (the “Ising toric code with defect”– it’s simpler than it sounds). Let’s define local TQO (LTQO), which says that the local distinguishability between various ground states as measured by the operator norm decays rapidly. This LTQO condition implies an area law (with a possible logarithmic correction, which is what we expect since we haven’t said anything about a spectral gap at this point). Next, we consider another condition called the local gap condition (LG). We want the gap of the local (restricted to some ) Hamiltonians have a gap which decays at most as an inverse polynomial in the size of . Open problem: is LG always satisfied if the global Hamiltonian is a sum of local projections with FF and a spectral gap? The main theorem: If is a FFH satisfying LTQO and LG with sufficiently weak quasi-local perturbations, then the gap is stable and the ground state degeneracy doesn’t split too much. Gave a very brief overview of the proof. Some open problems: how can we prove spectral gaps for 2D FFH? What symmetries of the Hamiltonian imply LTQO? Can we prove LG for all FFH that are sums of local projectors?
Norbert Schuch, Complexity of commuting Hamiltonians for qubits on a square lattice, arXiv:1105.2843.
Commuting Hamiltonians can have highly entangled ground states (e.g. the toric code). They clearly have a constant spectral gap, and we only need to estimate the ground state energy to constant accuracy. Is the complexity of estimating the ground state energy easier than the full quantum problem? Main result: for qubits on a 2D square lattice, the problem of determining if the ground state is FF is in NP. First we need a structure theorem for commuting Hamiltonians due to Bravyi and Vyalyi (2003). This decomposition was used to show that 2-body commuting Hamiltonian problem is in NP. The decomposition does not generally extend to -body for and for qudits. However, if the connectivity is “sparse enough” then the decomposition works. Idea number one: split the lattice into “white” and “black” squares and use the fact that each layer individually can take advantage of the BV decomposition. But we don’t know if these two decompositions are compatible, so we need a new idea. We can tell if the FF ground state exists if we can find states in each layer that have non-trivial overlap… but how can we compute the overlap? We need to take advantage of the structure. The point is that for qubits the overlap can be efficiently computed. When the spins are qubits are only two possibilities for the BV decomposition. One possibility is trivial, whereas the second possibility doesn’t allow any branching structures to form, so the overlap can be computed efficiently. This proof does not provide a constructive procedure for finding the ground state.
Maarten Van den Nest, A monomial matrix formalism to describe quantum many-body states, arXiv:1108.0531.
The motivation is to generalize the Pauli stabilizer formalism in a way which still retains some of the nice properties and captures a large class of states. Some of the nice properties include: efficient description of quantum states via the stabilizers, understanding of properties of the state via manipulation of the stabilizers. We first define a monomial unitary matrix which is a permutation matrix times a diagonal matrix of phases. An M-state is one which is stabilized by (+1 eigenstate of) a set of monomial unitaries. We typically want to restrict to special cases, such as -local, etc. This class of states encompasses e.g. stabilizer states for qudits, all quantum double ground states, AKLT model, W-states, Dicke states, coherent probabilistic computations, coset states of Abelian groups, and so on. We define the monomial stabilizer group to be the group generated by the unitaries. Assume this is finite. There is another group called the permutation group which comes from “forgetting” the phase structure and keeping only the permutation piece. We define the orbits by the orbit of the computational basis states under the action of the operators in . Some simple theorems: Thm 1, all amplitudes of an M-state are zero outside the orbit. Thm 2, all nonzero amplitudes have equal modulus. If you have an entire M-space, then you can find a basis for the space where each basis state is a uniform-amplitude superposition over a single orbit. The orbits are disjoint, so the dimension of the space is bounded by the total number of orbits. Computing some properties such as sampling the state in the computational basis are NP-hard. However, there are many examples that allow an efficient classical simulation.
Hector Bombin, Structure of 2D topological stabilizer codes, arXiv:1107.2707, joint work with D. Poulin and G. Duclos-Cianci.
Topological order can be thought of as equivalence classes of many-body systems under the action of constant-depth local unitary quantum circuits. We say that a state has short range entanglement if such a circuit can map the state to a product state. Other states are said to have long range entanglement. (Wen, Gu, Chen 2009) We will consider topological stabilizer codes (TSC). These are a subset of the stabilizer code Hamiltonians, in which the local terms are stabilizer code generators. The goal of this talk is two-fold: show rigorously that local equivalence “works” as a way of classifying gapped phases and find the general structure of 2D TSC including subsystem codes. This allows us to extend which are well-known for specific models (such as RG error correction for the toric code) to other models. Let’s recall what defines a theory of anyons: topological charges (particle labels), fusion rules and braiding rules. In 2D, string operators play an important role in these models. In fact, we can recover the data specifying the anyon theory from the action of the string operators. In this talk, we are only considering qubit Hamiltonians. We only consider Hamiltonians on an infinite lattice which are translationally invariant. Then TSC are ones where the centralizer of the stabilizer (in the group of Paulis with finite support) is again the stabilizer. TSC with the same anyon model are equivalent. Since we are going to show that everything is equivalent to some number of copies of the toric code, we can get a complete invariant by considering only the topological entanglement entropy. A sketch of the proof:
- Topological stabilizer groups admit local, translationally invariant independent generators (only possible in 2D)
- there are only a finite number of global constraints
- the number of global constraints equals the number of charges in the anyon theory
- the charges are topological, so the have string operators, which means we can extract an anyon model
- we can rule out chirality because the Hamiltonian is commuting (there can be no energy transport along the edge, as can be seen by considering evolution in the Heisenberg picture)
- build a framework for string segments as in multiple copies of the toric code
- other stabilizers (non-plaquette) have no charge
- map string segments to string segments and uncharged stabilizers to single qubit stabilizers
(Hector, if you’re reading this, fill in #9 in the comments. You went waaaay too fast!) Now let’s move on to subsystem codes. There are some complications since there is now also a gauge group as well as a stabilizer group. Gauge charges map naturally to stabilizer charges. Although they are not generally isomorphic, these two groups have the same order. In fact, these two charge groups are naturally dual. When all is said and done, every possible anyon model on qubits is a combination of: the toric code (2 bosons, 1 fermion, semionic statistics); TSCC (3 fermions, semionic interactions, chiral); subsystem toric code (1 boson); honeycomb subsystem code (1 fermion).