QIP 2015 live-blogging, Day 2

From the team that brought you “QIP 2015 Day 1 liveblogging“, here is the exciting sequel. Will they build a quantum computer? Will any complexity classes collapse? Will any results depend on the validity of the Extended Riemann Hypothesis? Read on and find out!
Praise from a reader of “day 1”:
QIP 2015 liveblogging — it’s almost like being there. Maybe better.

David J. Wineland abstract
Quantum state manipulation of trapped ions

Rather than “bore us” (his words) with experimental details, Dave gave a broad-brush picture of some of the progress that his lab has made over the years at improving the coherence of quantum systems.
Dave gave a history of NIST looking for more accurate clocks. Recently, a trapped near-UV transition of Hg ions at last did better than the continually improving microwave Cs standard.
At a 1994 conference at NIST, they invited Artur Ekert to speak about quantum gates. Cirac and Zoller gave the first detailed proposal for quantum computing with a linear ion trap at about this time. They were quickly able to demonstrate one of these gates in a linear ion trap.
He showed and discussed a picture of the racetrack planar ion-trap array, where ions are moved into position to perform gates throughout the trap. They can move an manipulate the ions using a scheme due to Milburn, Schneider, James, Sorenson, and Molmer that uses position dependent dipole forces. The transverse Ising model can be simulated by applying a moving standing wave to ions in a linear trap; this is a test case for useful simulations.
Other groups at NIST have also done impressive work on quantum simulation. Bollinger’s group has made a self-assembled triangular lattice with Ising-type couplings that we talked about previously here on the Pontiff.
Everyone in the ion trap business is plagued by something called “anomalous heating”, of unknown origin, which gets worse as the length scale gets smaller. Colleagues studying surface science have suggested using an argon ion cannon (damn, that sounds impressive) to blast away impurities in the surface trap electrodes, scrubbing the surface clean. This has reduced anomalous heating 100 fold, but it’s still above all known electronic causes. Using cryogenic cooling helps too, as has been done by Ike Chuang’s group at MIT.
Laser intensity fluctuations at the site of the ions is another continual source of error. Optical and IR beams can be efficiently transmitted and positioned by optical fibers, but UV beams create color centers and degrade optical fiber on a timescale of about an hour. Recent work by the group has shown that this degradation timescale can be extended somewhat.
Dave showed a list, and there are about 30+ groups around the world working on ion-trap quantum information processing. Pretty impressive!
Dave showed this Time magazine cover that calls D-Wave the “Infinity Machine” that no one understands. In contrast, he says, we know how quantum computing works… and how it doesn’t. Sober experimentalists seem to be in rough agreement that

• A factoring machine is decades away.
• Quantum simulation may be possible within the next decade.
• The real excitement will be a simulation that tells us something new about physics.

---

Joel Wallman and Steve Flammia
Randomized Benchmarking with Confidence
abstract arXiv:1404.6025

Randomized benchmarking is a standard method whereby experimental implementations of quantum gates can be assessed for their average-case accuracy in a way that doesn’t conflate the noise on the gates with the noise of state preparation and measurement (SPAM) errors.
The protocol is simple:

• Choose a random sequence of $latex m$ Clifford gates
• prepare the initial state in computational basis
• Apply the Clifford gate sequence and then the inverse gate at the end
• Measure in computational basis.

Repeat this for many random sequences and many repetitions of the each sequence to get statistics. Under a certain noise model called the “0th order model”, the averages of this procedure for different values of $latex m$ will fit to a model of the form $latex F_m = A + B f^m$ where $latex f$ is a quantity closely related to the average quality of the gates in the sequence. Define $latex r$ to be the average error rate. (Morally, this is equivalent to “1-f”, in the above model, but the actual formula is more complicated.) To understand the convergence of this protocol to an estimate, we need to understand the variance as a function of $latex m,r$.
The main contribution is to reduce the variance bound from the trivial bound of $latex O(1)$ to $latex O(mr)$. This provides a good guide on how to choose optimal lengths $latex m$ for experiments, and the bounds are nearly exact in the case of a single qubit. In the parameter range of interest, this improved over previous estimates of the sample complexity by three orders of magnitude.

---

Fernando Brandao, Marcus Cramer and Madalin Guta
A Berry-Esseen Theorem for Quantum Lattice Systems and the Equivalence of Statistical Mechanical Ensembles
abstract

The full version is not yet on the arxiv, but due to an author mistake, the above link gives the long version of QIP submission. Download it there while you still can!
Quantum many-body systems are pretty wild objects, with states in $latex 2^{10^{23}}$ dimensions or even worse. But we often have a mental models of them as basically like non-interacting spins. In some cases, the renormalization group and other arguments can partially justify this. One thing that’s true in the case of non-interacting spins is that the density of states is approximately Gaussian. The idea here is to show that this still holds when we replace “non-interacting spins” with something morally similar, such as exponentially decaying correlations, bounded-range interactions, etc.
This way of writing it makes it sound trivial. But major open questions like the area law fit into this framework, and proving most statements is difficult. So technical advances in validating our “finite correlation length looks like non-interacting spins” intuition can be valuable.
Today’s technical advance is a quantum version of the Berry-Esseen theorem. The usual Berry-Esseen theorem gives quantitative bounds on the convergence to the mean that we get from the central limit theorem. Here we consider a lattice version, where we consider spins on a d-dimensional lattice and local observables A and B that act on subsets of spins separated by a distance L. We require a finite correlation length, as we get for example, for all Gibbs states above some critical temperature (or at any nonzero temperature in D=1).
What does a (quantitative) CLT give us beyond mere large deviation bounds? It shows that the density of states (at least those inhabited by the particular state $latex \rho$) is roughly Gaussian thereby roughly matching what we would get from a tensor power state. This is somewhat stronger than the “typical subspace”-type guarantees that we would get from a large deviation bounds.
The main application here is an equivalence theorem between the canonical and microcanonical ensembles: i.e. between the Gibbs state and a uniform mixture over an energy band of width $latex O(\sqrt N)$. These states are far apart in trace distance, but this paper shows that they look similar with respect to sufficiently local observables. If you think this sounds easy, well, then try to prove it yourself, and then once you give up, read this paper.

---

Michael Kastoryano and Fernando Brandao
Quantum Gibbs Samplers: the commuting case
abstract arXiv:1409.3435

How efficiently can we prepare thermal states on a quantum computer? There is a related question: how does nature prepare states? That is, what is the natural rate for thermalization given a quantum lattice system? There are two possible ways to model thermalization, both of which are computationally efficient. “Davies generators” mean local jumps that can be modeled as local interactions with a Markovian bath at a fixed temperature, while “heat-bath generators” mean that we repeatedly apply the Petz recovery map to small blocks of spins. Call both “Gibbs samplers.”
Consider the setting where you have a system living on a lattice with a bit or qubit on each site, and some memoryless, spatially local, dynamics. Classically the powerful tools of DLR (Dobrushin-Lanford-Ruelle) theory imply a close relation between properties of the dynamics and properties of the stationary state. Specifically, spatial mixing (meaning decaying correlations in the stationary state) can be related to temporal mixing (meaning that the dynamics converge rapidly to the stationary state). (The best reference I know is Martinelli, but for a more CS-friendly version, see also this paper.)
An exact quantum analogy to this cannot be reasonably defined, since the classical definition involves conditioning – which often is the reason classical information theory ideas fail to translate into the quantum case.
One of the first contributions of this work then is to define quantum notions of “weak clustering” (more or less the familiar exponential decay of correlations between well-separated observables) and “strong clustering” (a more complicated definition involving overlapping regions). Then the main result is that there is an intimate connection between the rate of convergence of any quantum algorithm for reaching the Gibbs state and the correlations in the Gibbs state itself. Namely: strong clustering (but not weak clustering) is equivalent to rapid mixing of the Gibbs sampler. Everything here assumes commuting Hamiltonians, by the way. Also, “rapid mixing” is equivalent to the Gibbs sampler being gapped (think of this like the quantum version of being a gapped Markov chain).
One direction is fairly straightforward. To show that strong clustering implies a gapped Gibbs sampler, we directly apply the variational characterization of the gap. (The dynamics of a continuous-time Gibbs sampler can be written as $latex \dot\rho = -\mathcal{A}[\rho]$ for some linear superoperator $latex \mathcal{A}$, which we will assume to be Hermitian for convenience. $latex \mathcal{A}$ has all nonnegative eigenvalues because it is stable, and it has a single eigenvalue equal to 0, corresponding to the unique stationary distribution. The gap is given by the smallest positive eigenvalue, and this “smallest” is what gives rise to the variational characterization. See their paper for details.) The variational calculation involves a minimization over (global) states and strong clustering lets us reduce this to calculations involving local states that are much easier to bound.
In the other direction (gap implies strong clustering), we relate the Gibbs sampler to a local Hamiltonian, and use the detectability lemma, which in fact was originally used in part to prove a statement about decay of correlations. The idea is to construct an AGSP (approximate ground-state projector) which is a low-degree polynomial of the Hamiltonian. Because it’s low degree, applying it does not increase the entanglement across any cut by much (useful for proving area laws) or does not propagate correlations far (along the lines of Lieb-Robinson; useful for correlation decay).
When can these results be applied? In 1-D, strong and weak clustering are equivalent (because boundary terms can be removed), and therefore both are implied by (Hamiltonian) gap. Also in any number of spatial dimensions, above a universal critical temperature the Gibbs samplers are always gapped.
Some open questions:

• If in 2-D, one could also show strong=weak clustering (as is known classically in <3 dimensions), it would nail the coffin of 2d quantum memory for any commuting Hamiltonian.
• Classically, there is a dichotomy result: either there is very rapid mixing (log(N) time) or very slow (exp(N)) time. Here they can only get poly(N) mixing. Can these results be extended to the log-Sobolev type bounds that give this type of result?

---

Mehmet Burak Şahinoğlu, Dominic Williamson, Nick Bultinck, Michael Marien, Jutho Haegeman, Norbert Schuch and Frank Verstraete
Characterizing Topological Order with Matrix Product Operators
MERGED WITH
Oliver Buerschaper
Matrix Product Operators: Local Equivalence and Topological Order
abstract-137 arXiv:1409.2150 abstract-176

Characterizing topological quantum order is a challenging problem in many-body physics. In two dimensions, it is generally accepted that all topologically ordered ground states are described (in a long-range limit) by a theory of anyons. These anyonic theories have characteristic features like topology-dependent degeneracy and local indistinguishability in the ground space and string-like operators that map between these ground states.
The most famous example of this is Kitaev’s toric code, and we are interested in it at a quantum information conference because of its ability to act as a natural quantum error-correcting code. The four ground states of the toric code can be considered as a loop gas, where each ground state is a uniform superposition of all loops on the torus satisfying a given parity constraint.
The goal in this talk is to classify types of topological order using the formalism of matrix product states, and their slightly more general cousins, matrix product operators (MPO). The authors define an algebra for MPOs that mimics the algebra of loop operators in a topologically ordered material. Because matrix product operators have efficient descriptions classically, they are well suited to numerical studies, and their structure also allows them to be used for analytical investigations.
The main idea that the authors introduce is a condition on MPO operators so that they behave like topological operators. In particular, they obey a “deformation” condition that lets them be pushed around the lattice, just like Wilson loops.
The authors used this idea to study models that are not stabilizer codes, such as the double semion model and more generally the class of string-net models. This looks like a very promising tool for studying topological order.

---

Dorit Aharonov, Aram Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy and Umesh Vazirani
Local tests of global entanglement and a counterexample to the generalized area law
abstract 1410.0951

Steve: “Counterexamples to the generalized area law” is an implicit admission that they just disproved something that nobody was conjecturing in the first place. 😉
Aram: I’ll blog about this later.

---

Xiaotong Ni, Oliver Buerschaper and Maarten Van Den Nest
A non-commuting Stabilizer Formalism
abstract arXiv:1404.5327

This paper introduces a new formalism called the “XS stabilizer” formalism that allows you to describe states in an analogous way to the standard stabilizer formalism, but where the matrices in the group don’t commute. The collection of matrices is generated by $latex X, S, \alpha$, where $latex \alpha = \sqrt{i}$ and $latex S = \sqrt{Z}$ on $latex n$ qubits. A state or subspace that is stabilized by a subgroup of these operators is said to be an XS stabilizer state or code. Although these are, as Xiaotong says, “innocent-looking tensor product operators”, the stabilizer states and codes can be very highly entangled.
One of the applications of this formalism is to classify the double semion model, which is a local Hamiltonian model with topological order. There are sets of general conditions for when such states and codes can be ground states of local commuting XS Hamiltonians. Unfortunately, not all of these properties can be computed efficiently; some of these properties are NP-complete to compute. There are some interesting open questions here, for example what class of commuting projector Hamiltonians ground states are in NP?

---

Dave Touchette
Direct Sum Theorem for Bounded Round Quantum Communication Complexity and a New, Fully Quantum Notion of Information Complexity (Recipient of the QIP2015 Best Student Paper Prize)
abstract arXiv:1409.4391

“Information complexity” is a variant of communication complexity that measures not the number of bits exchanged in a protocol but the amount of “information”, however that is defined. Here is a series of tutorials for the classical case. Entropy is one possibility, since this would put an upper bound on the asymptotic compressibility of many parallel repetitions of a protocol. But in general this gives up too much. If Alice holds random variables AC, Bob holds random variable B and Alice wants to send C to Bob then the cost of this is (asymptotically) $latex I(A:C|B)$.
This claim has a number of qualifications. It is asymptotic and approximate, meaning that it holds in the limit of many copies. However, see 1410.3031 for a one-shot version. And when communication is measured in qubits, the amount is actually $latex \frac{1}{2} I(A:C|B)$.
Defining this correctly for multiple messages is tricky. In the classical case, there is a well-defined “transcript” (call it T) of all the messages, and we can define information cost as $latex I(X:T|Y) + I(Y:T|X)$, where X,Y are the inputs for Alice and Bob respectively. In the quantum case we realize that the very idea of a transcript implicitly uses the principle that (classical) information can be freely copied, and so for quantum protocols we cannot use it. Instead Dave just sums the QCMI (quantum conditional mutual information) of each step of the protocol. This means $latex I(A:M|B)$ when Alice sends $latex M$ to Bob and $latex I(B:M|A)$ when Bob sends $latex A$ to Alice. Here $latex A,B$ refer to the entire systems of Alice/Bob respectively. (Earlier work by Yao and Cleve-Buhrman approached this in other, less ideal, ways.)
When minimized over all valid protocols, Dave’s version of Quantum Information Complexity represents exactly the amortized quantum communication complexity. This sounds awesome, but there are a bunch of asterisks. First “minimized over all valid protocols,” is an unbounded minimization (and some of these protocols really do use an infinite number of rounds), although it is in a sense “single-shot” in that it’s considering only protocols for calculating the function once. Also “amortized” here is not quite the same as in Shannon theory. When we talk about the capacity of a channel or its simulation cost (as in these sense of reverse Shannon theorems) we usually demand that the block error rate approach zero. In this case, the information complexity is defined in terms of an error parameter $latex \epsilon$ (i.e. it is the minimum sum of QCMI’s over all protocols that compute the function up to error $latex \epsilon$). This then corresponds to the asymptotic cost of simulating a large number of evaluations of the function, each of which is allowed to err with probability $latex \epsilon$. The analogue in Shannon theory is something called rate-distortion theory.
Before you turn up your nose, though, the current talk gets rid of this amortized restriction. QIC (quantum information complexity) is easily seen to be a lower bound for the communication complexity and this work shows that it is also an upper bound. At least up to a multiplicative factor of $latex 1/\epsilon^2$ and an additive term that also scales with the number of rounds. Since QIC is also a lower bound for the above amortized version of complexity, this proves a direct sum theorem, meaning that computing $latex n$ function values costs $latex \Omega(n)$ as much as one function evaluation. Here the weak amortized definition actually makes the result stronger, since we are proving lower bounds on the communication cost. In other words, the lower bound also applies to the case of low block-wise error.
The technical tools are the one-shot redistribution protocol mentioned above (see also this version) and the Jain-Radhakrishnan-Sen substate theorem (recently reproved in 1103.6067 and the subject of a press release that I suppose justifies calling this a “celebrated” theorem). I should write a blog post about how much I hate it when people refer to “celebrated” theorems. Personally I celebrate things like Thanksgiving and New Year’s, not the PCP theorem. But I digress.

---

Toby Cubitt, David Elkouss, William Matthews, Maris Ozols, David Perez-Garcia and Sergii Strelchuk
Unbounded number of channel uses are required to see quantum capacity
abstract arXiv:1408.5115

Is the quantum capacity of a quantum channel our field’s version of string theory? Along the lines of this great Peter Shor book review, quantum Shannon theory has yielded some delightful pleasant surprises, but our attempts to prove an analogue of Shannon’s famous formula $latex C=\max_p I(A:B)$ has turned into a quagmire that has now lasted longer than the Vietnam War.
Today’s talk is the latest grim news on this front. Yes, we have a capacity theorem for the (unassisted) quantum capacity, the famous LSD theorem, but it requires “regularization” meaning maximizing a rescaled entropic quantity over an unbounded number of channel uses. Of course the definition of the capacity itself involves a maximization over an unbounded number of channel uses, so formally speaking we are not better off, although in practice the capacity formula can often give decent lower bounds. On the other hand, we still don’t know if it is even decidable.
Specifically the capacity formula is
$latex \displaystyle Q = \lim_{n\rightarrow\infty} Q^{(n)} := \lim_{n\rightarrow\infty} \frac{1}{n} \max_\rho I_c(\mathcal{N}^{\otimes n}, \rho)$,
where $latex \rho$ is maximized over all inputs to n uses of the channel and $latex I_c$ is the coherent information (see paper for def). In evaluating this formula, how large do we have to take n? e.g. could prove that we always have $latex Q^{(n)} \geq (1-1/n)Q$? If this, or some formula like it, were true then we would get an explicit upper bound on the complexity of estimating capacity.
The main result here is to give us bad news on this front, in fairly strong terms. For any $latex n$ they define a channel for which $latex Q^{(n)}=0$ but $latex Q>0$.
Thus we need an unbounded number of channel uses to detect whether the quantum capacity (ie the regularized coherent information) is even zero or nonzero.
The talk reviews other non-additivity examples, including classical, private, zero-error quantum and classical capacities. Are there any good review articles here?
Here’s how the construction works. It builds on the Smith-Yard superactivation result, which combines an erasure channel (whose lack of capacity follows from the no-cloning theorem) and a PPT channel (whose lack of capacity follows from being PPT). The PPT channel is chosen to be able to send private information (we know these exist from a paper by H3O) and by using the structure of these states (further developed in later three-Horodecki-and-an-Oppenheim work), one can show that combining this with an erasure channel can send some quantum information. Specifically the PPT channel produces a “shield” which, if faithfully transmitted to Bob, enables perfect quantum communication.
This new construction is similar but uses a shield with many parts any one of which can be used to extract a valid quantum state. On the other hand, the erasure probability is increased nearly to one, and noise is added as well. Proving this is pretty tough and involves sending many things to zero or infinity at varying rates.
During question period prolonged jocular discussion triggered by John Smolin saying title was inappropriate, since the authors had clearly shown that by examining the parameters of the channel the quantum capacity was positive, so detecting positivity of capacity required no channel uses.
D. Gottesman suggested a more operational interpretation of title, given a black box, how many uses of it are needed to decide whether its quantum capacity was positive. If it was, e.g. an erasure channel with erasure probability very close to 1/2, arbitrarily many uses would be needed to confidently decide. It’s not clear how to formalize this model.
By the way, better Shannon theory news is coming in a few days for bosonic channels with the talk by Andrea Mari.