# Seminars

## IQI: Institute for Quantum Information Weekly Seminars

We invite experts to our weekly IQI Seminar Series to tell us about their recent research advances. We also hold more informal group meetings and sponsor IQI Workshops from time to time. Below is a calendar of these and other events of interest to the IQI community.

**Plasmons, chirality, and electron energy-gain spectroscopy**

Ana Asenjo García, ICFO

Tuesday, August 12, 2014, 3:00 p.m. 107 Annenberg

In the first part of this talk, I will present some recent work on the interaction of plasmonic chiral matter with both circularly polarized light and vortex electron beams. For light, we compare the calculations based upon multiple scattering theory with recent observations of circular dichroism in plasmonic nanoparticles assembled using DNA origami. For electrons, we predict strong dichroism in the electron energy-loss spectroscopy (EELS) signal by using vortex beams. These electrons carry orbital angular momentum that can be exchanged in the interaction with chiral plasmons. We also predict a dichroic response when probing chiral biomolecules, which suggests the use of these vortex for resolving different enantiomers.

In the second part of the talk, I will address the phenomenon of plasmon-mediated electron energy gain, in which the interaction of swift electrons with strong evanescent light fields scattered by a nanostructure (e.g., by excitation of a plasmon by an external laser beam) can produce energy gains in the electrons and stimulated photon emission. This electron-light interaction can provide detailed information on the optical properties of the sampled nanostructures in the time and frequency domains. I will show that, taking advantage of plasmonic resonances, spectroscopy can be performed by varying the illumination frequency at remarkably low light intensities.

**Infinite dimensional Adaptive Control for Quantum Systems**

Mark Balas, UWY, College of Engineering and Applied Science

Tuesday, July 29, 2014, 3:00 p.m. 107 Annenberg

Many control systems are inherently infinite dimensional when they are described by partial differential equations or have internal transport delays. Currently there is renewed interest in the control of these kinds of systems especially in flexible aerospace structures, smart electric power grids, and the quantum information and computing field. Since the dynamics of these systems will not be perfectly known, it is especially of interest to control these systems adaptively via low-order finite-dimensional controllers in the presence of persistent disturbances.

In our work, we have developed direct model reference adaptive control and disturbance rejection with very low-order adaptive gain laws for both large-scale finite dimensional systems and infinite dimensional systems whose states reside in a Hilbert Space. In this presentation I want to first give an introduction to some basic ideas in control theory, and then talk about some of our recent work in infinite dimensional control systems, and finally talk about how these ideas can be used in control of quantum systems to improve the transmission of quantum information. I think this will certainly be fun and how much profit, beyond intellectual capital, remains to be seen.

**Robust Quantum Random Number Generation**

Carl Miller, University of Michigan

Tuesday, July 22, 2014, 3:00 p.m. 107 Annenberg

Random numbers have countless applications, and so the kind of

randomness postulated in quantum physics--"true randomness"--may be a

vital resource. A line of research has developed whose goal is to

harness this resource. The central goal is simple: construct a protocol

which uses quantum devices to generate bits, and at the same time,

certify that the bits are truly random. Crucially, the certification

procedure must not depend on any prior trust in the accuracy of the devices.

Colbeck's thesis (2006) proposed a scheme for quantum random number

generation. While the scheme is simple, its security proof was very

challenging--the first (and only) previous full proof was given by

Vazirani and Vidick in 2012.

In our work we have taken several steps forward from Vazirani-Vidick

2012 and brought quantum RNG close to the point of practical

implementation. We have constructed a security proof that is robust

(error-tolerant), that provides cryptographic security, and that is

implementable with constant quantum memory. The proof invents multiple

new techniques which we are hopeful will find applications elsewhere.

Joint work with Yaoyun Shi.

Reference: http://arxiv.org/abs/1402.0489

**Strong converse bounds for quantum communication
**

Mark Wilde, Louisiana State University

Tuesday, July 8, 2014, 3:00 p.m. 107 Annenberg

One of the main goals in quantum information theory is to establish the capacity of a quantum channel for communicating various kinds of information, whether it be bits or qubits. While several communication capacities of quantum channels are now known, the characterization of capacity in many of these cases is often limited to it being a threshold that determines the rates at which reliable communication is or is not possible. This characterization might be satisfactory for some purposes, but it leaves open the possibility for a trade-off between communication rate and error probability (that is, one might think that it would be possible to send data at a higher rate by allowing for errors to occur some of the time). However, we now know that such a trade-off is not possible for many quantum channels and capacities of interest. The seminar will focus on quantum communication capacity and a recent result establishing the Rains information of a quantum channel as a strong converse bound for quantum communication when using the channel many independent times. We also settle an open question posed by Rains, namely, to show that the Rains bound for entanglement distillation represents a strong converse rate for this task. The main application of our first result is to settle the strong converse question for the quantum capacity of all generalized dephasing channels.

This is joint work with Marco Tomamichel and Andreas Winter (arXiv:1406.2946).

**A Non-commuting Stabilzer Formalism**

Oliver Buerschaper, Perimeter Institute

Tuesday, June 24, 2014, 3:00 p.m. 107 Annenberg

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 {α I, X, S}, where α = exp(i π / 4) and S = 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.

** de Finetti Theorems: Quantum and Beyond**

Rotem Arnon-Friedman, ETH, Zurich

****Note Room Change**** Tuesday, June 17, 2014, 3:00 p.m. 213 Annenberg

When analysing quantum information processing protocols one has to deal

with large entangled systems, each consisting of many subsystems. It is
therefore necessary to find some additional structure of the relevant
state space, which can allow us to simplify the analysis. de Finetti
theorems enable a substantially simplified analysis of
information-processing tasks by giving us a way to relate states, which
are symmetric under permutation of the subsystems, to states in which
the subsystems are independent of each other. This relation plays an
important role in various areas, e.g., in quantum cryptography or state
tomography, where permutation invariant systems are ubiquitous. The
known de Finetti theorems usually refer to the internal quantum state of
a system and depend on its dimension. In this talk a different de
Finetti theorem will be presented, where systems are modelled in terms
of their statistics under measurements. This is necessary for a large
class of applications widely considered today, such as device
independent protocols, where the underlying systems and the dimensions
are unknown.

In the talk I will explain the concept of de Finetti theorems, motivate
the need for a device independent de Finetti theorem and present the new
results.

Joint work with Renato Renner

Reference: http://arxiv.org/abs/1308.0312

**Quantum-proof extractors via operator space theory**

Omar Fawzi, ETH, Zurich

****NOTE TIME CHANGE** **Tuesday, June 10, 2014, 2:00 p.m. 107 Annenberg

Randomness extractors are an important building block for classical and quantum cryptography. They are used for privacy amplification which is an essential step in quantum key distribution but also in many other protocols such as device independent randomness amplification and expansion. For most of these applications, it is important that the extractor be quantum-proof, i.e., be secure against quantum adversaries. It is known that some extractor constructions are quantum-proof whereas others are provably not. We argue that the theory of operator spaces offers a natural framework for studying to what extent extractors are secure in the presence of quantum adversaries.

In this talk, I will start by formulating the definition of extractors as a condition on the norm of an associated operator. Then, after introducing the basics of the theory of operator spaces, I will show that the definition of quantum-proof extractors can be formulated as a condition on the completely bounded norm of the same operator. As an application, we use Grothendieck’s inequality to show that very high min-entropy extractors are always approximately quantum-proof.

This is joint work with Mario Berta and Volkher Scholz.

**Rapid Mixing of Quantum Local Dissipative Systems**

Angelo Lucia, Universidad Complutense de Madrid

Tuesday, May 27, 2014, 3:00 p.m. 107 Annenberg

Open quantum systems weakly coupled to the environment are modelled by completely positive, trace preserving semigroups of linear maps. The generators of such evolutions are called Liouvillians, and similarly to the Hamiltonian in the case of coherent evolution, they encode the physical properties of the system. In the setting of quantum many-body systems on a lattice it is natural to consider local or exponentially decaying interactions. We will focus on the case of maps with a unique fixed point, and consider the scaling of the mixing time with respect to the system size. In particular, if such scaling is sub-linear, a number of good properties of the evolution can be obtained: local observables are stable against perturbations, the fixed point has a finite correlation length, and in the case of frustration-free systems, satisfies an area law.

**Symmetry-Protected Topological Entanglement**

Iman Marvian, USC

Tuesday, May 20, 2014, 3:00 p.m. 107 Annenberg

We propose an order parameter for the Symmetry-Protected Topological (SPT) phases which are protected by Abelian on-site symmetries. This order parameter, called the "SPT entanglement", is defined as the entanglement between A and B, two distant regions of the system, given that the total charge (associated with the symmetry) in a third region C is measured and known, where C is a connected region surrounded by A and B and the boundaries of the system. In the case of 1-dimensional systems we prove that at the limit where A and B are large and far from each other compared to the correlation length, the SPT entanglement remains constant throughout a SPT phase, and furthermore, it is zero for the trivial phase while it is nonzero for all the non-trivial phases. Moreover, we show that the SPT entanglement is invariant under the low-depth quantum circuits which respect the symmetry, and hence it remains constant throughout a SPT phase in the higher dimensions as well. Finally, we show that the concept of SPT entanglement leads us to a new interpretation of the string order parameters, and based on this interpretation we propose an algorithm for extracting the relevant information about the SPT phase of the system from the string order parameters.

Reference: http://arxiv.org/abs/1307.6617

**Gauge Color Codes**

Hector Bombin, Perimeter Institute

Tuesday, May 13, 2014, 3:00 p.m. 107 Annenberg

Color codes are topological stabilizer codes with unusual transversality properties. I will show that their group of transversal gates only depends on the spatial dimension, not the local geometry. I will also introduce a generalized, gauge version of color codes. In 3D they allow the effectively transversal implementation of a universal set of gates by gauge fixing, while error-dectecting measurements involve only 4 or 6 qubits. Furthermore, they do not require multiple rounds of error detection to achieve fault-tolerance.

**Local tests of global entanglement and a counterexample to the generalized area law**

Daniel Nagaj, Simons Institute, UC Berkeley

Tuesday, May 6, 2014, 3:00 p.m. 107 Annenberg

We introduce a technique for applying quantum expanders in a distributed fashion, and use it to solve two basic questions: testing whether a bipartite quantum state shared by two parties is the maximally entangled state and disproving a generalized area law. In the process these two questions which appear completely unrelated turn out to be two sides of the same coin. Strikingly in both cases a constant amount of resources are used to verify a global property.

Joint work with Dorit Aharonov, Aram Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, and Umesh Vazirani

**Harnessing Quantum Systems with Long-Range Interations**

Alexey Gorshkov, Joint Quantum Institute

Tuesday, April 22, 2014, 3:00 p.m. 107 Annenberg

AMO (atomic, molecular, and optical) systems with long-range interactions, such as Rydberg atoms, polar molecules, and ions, are arguably the most controllable, tunable, and strongly interacting quantum systems. In this talk, we will first review how precise control over such systems has recently opened a new paradigm for quantum computing and communication, entanglement generation, and engineering of new phases of matter. Motivated by recent experiments, we will then focus on lattice systems with interactions featuring power-law decay with distance. In particular, we will derive a new bound on the propagation of information in such systems and exhibit a simple model that partially saturates the new bound [1]. The new bound is expected to provide crucial insights into numerous equilibrium and non-equilibrium phenomena in long-range-interacting systems and is on the verge of being verified experimentally by the trapped ion community [2,3].

[1] Z.-X. Gong, M. Foss-Feig, S. Michalakis, AVG, arXiv:1401.6174.

[2] P. Richerme, Z.-X. Gong, A. Lee, C. Senko, J. Smith, M. Foss-Feig, S. Michalakis, AVG, C. Monroe, arXiv:1401.5088 (Nature in press).

[3] P. Jurcevic, B. P. Lanyon, P. Hauke, C. Hempel, P. Zoller, R. Blatt, C. F. Roos, arXiv:1401.5387 (Nature in press).

**How "Quantum" is the D-Wave Machine?**

Seung Woo Shin, UC Berkeley

Tuesday, April 15, 2014, 3:00 p.m. 107 Annenberg

Recently there has been intense public interest in research surrounding the D-Wave "quantum computer". While claims about speedups over classical computers have been largely refuted, studies also claim that D-Wave machines exhibit signatures of "quantum behavior." In this talk, I will outline a very simple classical model which explains the published large scale input-output behavior of the D-Wave One machine. While raising serious questions about "how quantum" the D-Wave machine is, the new model also provides insights into the native problem solved by the D-Wave machine.

Joint work with Graeme Smith, John Smolin, and Umesh Vazirani

Reference: http://arxiv.org/abs/1401.7087

**Ultimate Communication Capacity of Quantum Optical Channels**

Raul Garcia-Patron, Universite Libre de Bruxelles

Tuesday, April 1, 2014, 3:00 p.m. 107 Annenberg

Optical channels, such as fibers or free-space links, are ubiquitous in today's telecommunication networks. A complete physical model of these channels must necessarily take quantum effects into account in order to determine their ultimate performances. Specifically, Gaussian bosonic quantum channels have been extensively studied over the past decades given their importance for practical purposes. In spite of this, a longstanding conjecture on the optimality of Gaussian encodings has yet prevented finding their communication capacity. In this talk we will present a recent result that solves this conjecture and establishes the ultimate achievable bit rate under an energy constraint. We will conclude discussing further implications of our result.

Joint work with V. Giovannetti, N. J. Cerf and A. S. Holevo

Reference: http://arxiv.org/abs/1312.6225

**On the Informational Completeness of Local Observables**

Isaac Kim, Perimeter Institute

Tuesday, March 11, 2014, 3:00 p.m. 107 Annenberg

For a general multipartite quantum state, we formulate a locally

checkable constraint, under which the expectation values of certain

nonlocal observables are completely determined by the expectation values

of some local observables. The constraint is satisfied for ground states

of gapped quantum many-body systems in one and two spatial dimensions,

assuming a generic entanglement entropy scaling law holds. Its

implications on quantum state tomography and quantum error correcting

codes are discussed. On the quantum state tomography side, we establish

nontrivial upper bound on the sample/measurement complexities. On the

quantum error correcting code side, we provide an upper bound on the

code distance, which is shown to be tight for a large class of known

models.

**Physical Randomness Extractors**

Xiaodi Wu, MIT

Tuesday, February 18, 2014, 3:00 p.m. 107 Annenberg

How can one be certain that the output of an alleged random number generator is indeed random? This question is important not only for the security and the efficiency of modern day information processing, but also for understanding how fundamentally unpredictable events are possible in the physical world. The mathematical theory of randomness extraction from weak randomness sources shows that such certainty is possible only when two or more *independent* sources are available. However, the independence requirement seems hard to enforce or even just to verify.

To circumvent this fundamental and hard-to-enforce limit, we propose a framework of extracting randomness from physical systems, and base the security on the validity of physical theories --we envision a scenario in which in addition to a weak random source, we have access to (multiple, spatially separated, untrusted) physical devices that may have been prepared by the adversary but are nevertheless constrained by quantum mechanics and special relativity. We require that, when the extraction procedure succeeds, the output randomness is close to uniform against any quantum adversary. We call such extraction procedure a *physical randomness extractor*.

We construct the first physical randomness extractor for arbitrary min-entropy sources. Additionally, our extractor enjoys the desirable properties of being efficient and robustness. Specifically, to produce n-bits of certified randomness, our extractor takes a d=poly-log(n) bits source with d^{0.1} bits of min-entropy (measured against the devices) and poly(n) devices and runs in poly(n) time. Our extractor is robust in the sense that it tolerates a constant level of implementation imprecision of the devices.

Our result enables practical and provably secure randomness generation with a minimal assumption on the randomness source and the generating devices. It also implies that unless the world is deterministic, we can experimentally create inherently random events and be confident of its unpredictability.

This is joint work with Kai-Min Chung and Yaoyun Shi.

**Delegating Private Quantum Computations**

Anne Broadbent, University of Ottawa

Tuesday, February 11, 2014, 3:00 p.m. 107 Annenberg

Given the technological challenge in building quantum computers, it is likely that their initial availability will be in a client-server configuration. We address the question of privacy in this scenario, by showing that an almost-classical client can delegate the execution of any quantum computation, where the data uploaded to the server is encrypted via the one-time pad. In order to do this, the quantum power required of the client is limited to being able to prepare random BB84 states. We give a simulation-based security definition and a rigorous proof of security using a transformation to an entanglement-based protocol.

**Quantum Information, Entanglement, and Many-body Physics**

Fernando Brandao, University College London

Tuesday, January 28, 2014, 4:00 p.m. 114 East Bridge

Quantum information science has been developed in the past twenty years with an eye on future technologies, such as quantum computers and quantum cryptography. In this talk I will argue that the theory is also very useful as a tool for studying other areas of physics.

I will exemplify this feature mainly focusing on the problem of describing low-temperature states of quantum many-body models. I will show how both non-critical states in one-dimension and low-energy states in very large dimensions have a simple entanglement structure, thus being well describable by classical means. Both results will follow from

the theory of entanglement originally developed for understanding the capabilities of quantum systems for information processing (in particular we will employ optimal protocols for entanglement distillation and an information-theoretic characterization of the so-called monogamy of entanglement).

Time permitting I will also briefly mention applications of quantum information theory to the study of the quantum-to-classical transition (in particular to the proposal termed quantum Darwinism) and to thermodynamics on the nanoscale. The talk will be geared at a general physics audience and no background on quantum information will be assumed.

**Good quantum codes with low-weight stabilizers**

Sergey Bravyi, IBM Watson Research Center

Tuesday, January 21, 2014, ** **2:00 pm, this week only** ** 107 Annenberg

Quantum codes with low-weight stabilizers known as LDPC codes have been actively studied recently due to their potential applications in fault-tolerant quantum computing. However, all families of quantum LDPC codes known to this date suffer from a poor distance scaling limited by the square-root of the code length. This is in a sharp contrast with the classical case where good families of LDPC codes are known that combine constant encoding rate and linear distance.

In this talk I will describe the first family of good quantum codes with low-weight stabilizers. The new codes have a constant encoding rate, linear distance, and stabilizers acting on at most square root of n qubits, where n is the code length. For comparison, all previously known families of good quantum codes have stabilizers of linear weight. The proof combines two techniques: randomized constructions of good quantum codes and the homological product operation from algebraic topology. We conjecture that similar methods can produce good stabilizer codes with stabilizer weight n^a for any a>0. Finally, we apply the homological product to construct new small codes with low-weight stabilizers.

This is a joint work with Matthew Hastings

Preprint: arXiv:1311.0885

**Simplified Quantum Compiling with Complex Gate Distillation**

Guillaume Duclos-Cianci, University of Sherbrooke

Tuesday, December 3, 2013, 3:00 pm, 105 Annenberg (different location, this term only)

I will present a scheme to compile complex quantum gates that uses significantly fewer resources than existing schemes. In standard fault-tolerant protocols, a magic state is distilled from noisy resources, and copies of this magic state are then assembled into produced complex gates using the Solovay-Kitaev theorem or variants thereof. In our approach, we instead directly distill magic states associated to complex gates from noisy resources, leading to a reduction of the compiling overhead of several orders of magnitude.

**The Bose-Hubbard model on a graph is QMA-complete
**David Gosset, University of Waterloo

Tuesday, November 19, 2013, 3:00 pm, 105 Annenberg (different location, this term only)

The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. We prove that approximating the ground energy of the Bose-Hubbard model on a graph (at fixed particle number) is QMA-complete. Our QMA-hardness proof encodes an n-qubit computation in the subspace of n hard-core bosons with at most one particle per site, so it holds for any fixed repulsive interaction strength. This feature, along with the well-known mapping between hard-core bosons and spin systems, also allows us to prove a related result for a class of 2-local Hamiltonians defined by graphs (a generalization of the XY model).

This is joint work with Andrew Childs and Zak Webb.

**Exponential Improvement in Precision for Hamiltonian-Evolution Simulation
**Rolando Somma, Los Alamos National Laboratory

Tuesday, November 12, 2013, 3:00 pm, 105 Annenberg (different location, this term only)

I will present a quantum method for simulating Hamiltonian evolution
with complexity polynomial in the logarithm of the inverse error. This is an
exponential improvement over existing methods for Hamiltonian simulation. In
addition, its scaling with respect to time is close to linear, and its scaling
with respect to the time derivative of the Hamiltonian is logarithmic. These
scalings improve upon most existing methods. Our method is to use a compressed
Lie-Trotter formula, based on recent ideas for efficient discrete-time
simulations of continuous-time quantum query algorithms.

This is joint work with Dominic Berry and Richard Cleve.

**Simulation of dynamical abelian and no-abelian lattice gauge theories with cold atoms
**Benni Reznik, Tel-Aviv University

Tuesday, October 8, 2013, 3:00 pm, 107 Annenberg

Quantum simulations of High Energy Physics, and of gauge field theories, is an emerging and exciting direction in quantum simulations. Compared with condensed matter simulations however, such simulations are more demanding because of the additional requirements involving

local gauge symmetries, Lorentz invariance, and the inclusion of both Fermions and Bosons, that are needed for describing matter and force mediators. Explicit models of analog simulators of LGT have been recently proposed for systems of cold atoms in optical lattices.

In particular, it turns out that local gauge invariance, can be based and derived from the fundamental symmetries of the given atomic cold atomic interactions and conservation laws.

This then provides methods for simulating elementary gauge invariant field theories, such as compact-QED (U(1)), and SU(N) Yang-Mills theories. It suggests that fundamental HEP phonomena, such as dynamical quark confinement, and exotic QCD phases, that are currently inaccessible to classical simulations, can be explored in “table-top” experiments with cold atoms.

**Nested quantum walks with quantum data structures** **
**Robin Kothari, University of Waterloo

Tuesday, September 24, 2013, 3:00 pm, 107 Annenberg

I'll talk about a new framework for designing quantum algorithms that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. The new framework extends the known quantum walk framework while retaining its advantages: simplicity, ease of use, and a straightforward understanding of all resources used by the algorithm, such as queries, time or space.

The new framework is also powerful. In particular, the recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including the triangle finding problem and more general subgraph detection problems. I will exhibit the power of the new framework by giving simple explicit constructions that reproduce both the O(n^{35/27}) and O(n^{9/7}) learning graph upper bounds (up to logarithmic factors) for triangle finding.

This is joint work with Stacey Jeffery and Frédéric Magniez.

**Error models in quantum computation: an application of model selection
**Steven van Enk, University of Oregon

Tuesday, July 9, 2013, 3:00 pm, 107 Annenberg

Threshold theorems for fault-tolerant quantum computing assume that errors are of certain types. But how would one detect whether errors of the ''wrong'' type occur in one's experiment, especially if one does not even know what type of error to look for? The problem is that for many qubits a full state description is impossible to analyze, and a full process description is even more impossible to analyze. As a result, one simply cannot detect all types of errors.

Here we show through a quantum state estimation example (on up to 25 qubits) how to attack this problem using model selection. We use, in particular, the Akaike Information Criterion. The example also indicates that the number of measurements that one has to perform before noticing errors of the wrong type scales polynomially both with the number of qubits and with the error size.

This is joint work with Lucia Schwarz.

**CMI and IQI Seminar**

**Fourier sparsity, spectral norm, and the Log-rank conjecture**

Shengyu Zhang, The Chinese University of Hong Kong

Tuesday, May 28, 2013, 3:00 pm, 107 Annenberg

We study Boolean functions with sparse Fourier coefficients or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x\oplus y) --- a fairly large class of functions including well-studied ones such as Equality and Hamming Distance. The rank of the communication matrix M_f for such functions is exactly the Fourier sparsity of f. Let d be the F2-degree of f and D(f) stand for the deterministic communication complexity for f(x\oplus y). We show that 1. D(f) = O(2^{d^2/2} log^{d-2} ||\hat f||_1). In particular, the Log-rank conjecture holds for XOR functions with constant F2-degree. 2. D(f) = O(d ||\hat f||_1) = O(\sqrt{rank(M_f)}\logrank(M_f)). We obtain our results through a degree-reduction protocol based on a variant of polynomial rank, and actually conjecture that its communication cost is already \log^{O(1)}rank(M_f). The above bounds also hold for the parity decision tree complexity of f, a measure that is no less than the communication complexity (up to a factor of 2).

Along the way we also show several structural results about Boolean functions with small F2-degree or small spectral norm, which could be of independent interest. For functions f with constant F2-degree: 1) f can be written as the summation of quasi-polynomially many indicator functions of subspaces with \pm-signs, improving the previous doubly exponential upper bound by Green and Sanders; 2) being sparse in Fourier domain is polynomially equivalent to having a small parity decision tree complexity; 3) f depends only on polylog||\hat f||_1 linear functions of input variables. For functions f with small spectral norm: 1) there is an affine subspace with co-dimension O(||\hat f||_1) on which f is a constant; 2) there is a parity decision tree with depth O(||\hat f||_1 log ||\hat f||_0).**Quantum metrology and many-body physics with optical lattice clocks**

Michael J. Martin, JILA, University of Colorado

Tuesday, May 21, 2013, 4:00 pm, 107 Annenberg **Note time change**

Optical clocks have revolutionized the science of timekeeping, permitting frequency measurements at (and even below) the level of a part in 1017 systematic uncertainty. Neutral atom optical standards based on ultracold lattice-trapped atoms promise an order of magnitude increase in measurement precision over frequency standards based on single ions, but require the highest levels of laser precision to fully realize this improvement and operate near the limit set by quantum fluctuations. In this seminar, I will introduce alkaline earth atoms in the context of precision frequency measurement and describe the features that make this class of neutral atoms desirable for optical frequency standards. I will then describe the JILA 87Sr optical lattice clock, where thousands of essentially decoherence-free 87Sr atoms are probed by a laser with <30 mHz linewidth. This level of precision allows access to a regime in which quantum fluctuations play a significant role, enabling near quantum-limited clock operation and the study of quantum many-body physics, which I will discuss. Such precise atom-laser interactions should permit direct characterization and manipulation of many-body states and explorations of the SU(N) symmetry exhibited by the nuclear spin of fermionic alkaline earth atoms

**Is there life beyond Quantum Mechanics?**

Anton Kapustin, Caltech

Tuesday, May 14, 2013, 3:00 pm, 107 Annenberg

I formulate a system of axioms for a physical theory which are common to both classical and quantum mechanics and incorporate some basic intuition about the laws of physics, such as the existence of composite systems and the relation between symmetries and conservation laws. I prove that if systems with finite-dimensional spaces of observables exist, then Quantum Mechanics is the only possible theory of this sort. Even if some of the axioms are dropped, one can show that Quantum Mechanics cannot be deformed by a small parameter. These results show that the laws of Quantum Mechanics are exact, unless some deeply cherished assumptions about the structure of physical laws are wrong.

**Quantum sparse-graph codes for future quantum computers**

Leonid Pryadko, UCR

Tuesday, May 7, 2013, 3:00 pm, 107 Annenberg

Research in quantum error correction has been heavily dominated by just two classes of codes: concatenated and surface codes. Both code families can only encode a limited number of qubits per block and thus require huge redundancy for any useful quantum computation. I will discuss recently discovered quantum hypergraph-product codes (QHPCs) which generalize the surface codes but can encode many more qubits per block. Just like the surface codes, QHPCs have convenient planar representations, with each encoded qubit corresponding to a pair of topologically non-trivial patterned strings. The allowed patterns correspond to codewords of two classical binary codes which form the QHPC. Further, each of the quantum measurements needed for error correction can involve just a few qubits, these measurements can be done in parallel, and almost all errors affecting a finite fraction of qubits can be corrected.

**Building one-time memories from isolated qubits**

Yi-Kai Liu, NIST

Tuesday, April 30, 2013, 3:00 pm, 107 Annenberg

One-time memories (OTM's) are a simple type of tamper-resistant cryptographic hardware, which can be used to implement one-time programs, a strong form of secure computation. Here we investigate the possibility of building OTM's using "isolated qubits" -- qubits that can only be accessed using local operations and classical communication (LOCC). Isolated qubits can be implemented using current technologies, such as nitrogen vacancy centers in diamond.

We construct OTM's that are information-theoretically secure against one-pass LOCC adversaries using 2-outcome measurements. (Also, these OTM's can be prepared and accessed by honest parties using only LOCC operations.) This result is somewhat surprising, as OTM's cannot exist in a fully-quantum world or in a fully-classical world; yet they can be built from the combination of a quantum resource (single-qubit measurements) with a classical restriction (on communication between qubits).

Our construction resembles Wiesner's old idea of quantum conjugate coding, implemented using random error-correcting codes. Our proof of security uses entropy chaining to bound the supremum of a suitable empirical process. An interesting open problem is to replace our random codes with efficiently-decodable codes, which may yield computationally-efficient OTM's that are secure against computationally-bounded LOCC adversaries.
In addition, we construct data-hiding states, which allow an LOCC sender to encode an (n-O(1))-bit messsage into n qubits, such that at most half of the message can be extracted by a one-pass LOCC receiver, but the whole message can be extracted by a general quantum receiver.

http://arxiv.org/abs/1304.5007

**Continuous-variable quantum cryptography: Current status and future directions**

Christian Weedbrook, University of Toronto

Tuesday, April 23, 2013, 3:00 pm, 107 Annenberg

Quantum cryptography allows two people to communicate in absolute secrecy using unbreakable codes. In this talk I introduce the basics of the continuous-variable version of quantum cryptography and detail recent works and advances along with future opportunities in this exciting field of research.

**Equilibrium value method for optimization problems and its applications in quantum computation**

Xiaodi Wu, University of Michigan

Tuesday, April 16, 2013, 3:00 pm, 107 Annenberg

Semidefinite programming (SDP) is a powerful technique from both an analytic and computational point of view for optimization problems. It is also intimately related to quantum computation, as many optimization problems over density operators (quantum states) could be naturally formulated as SDPs.

In spite of the existence of polynomial time solvers for general SDPs (e.g., interior point method), the black-box use of these solvers is, however, unsatisfactory for many purposes. For instance, the lack of explicitness makes it hard to adapt (or optimize) these solvers for special instances of SDPs. Moreover, these polynomial time solvers provide no guarantee when one requires stronger efficiency, such as space efficiency (or equivalently, efficient computability by a parallel machine).

In this talk, I will present a new approach called “Equilibrium Value Method” (EVM) that provides an explicit and time/space efficient solution to a substantial class of SDPs, which, in particular, includes many examples that arise naturally in quantum computation. The main idea behind EVM is to characterize the procedure to solve a SDP as a zero-sum game, in which one player tries to provide an optimal solution of the SDP while the other player tries to find anything wrong with that solution.

I will focus on the main application of EVM, which serves as a way to obtain PSPACE upper bounds of quantum complexity classes. First, I will show how EVM could lead to a simple and intuitive alternative proof to the recent celebrated result QIP=PSPACE. Second, I will illustrate how EVM could extend to a much more general setting, by proving that the quantum refereed games (i.e., the competing-prover variant of QIP) with two turns (QRG(2)) coincide with PSPACE.

I will also talk about a few additional features of this approach and discuss a little bit about how it can extend to convex optimizations beyond SDPs. No background on either SDP or computational complexity will be assumed.

Based on results by myself and a joint result with Gus Gutoski (IQC, U Waterloo).

**Sequential decoding of general quantum communication channels**

Mark Wilde, Louisiana State University

Tuesday, April 9, 2013, 3:00 pm, 107 Annenberg

Despite the fact that a quantum measurement generally disturbs the state of a quantum system, recent work of Seth Lloyd and collaborators demonstrates that a sender and receiver can communicate at the Holevo rate even when the receiver performs a large number of sequential measurements to determine the message of the sender. The present work contributes to this direction, by addressing three questions that have arisen from the work on sequential decoding. First, we show that Pranab Sen's non-commutative union bound applies for a sequence of general measurements (not merely projective ones). Next, we use this result to prove that sequential decoding works well even in the "one-shot" regime, where we are given a single instance of a channel and wish to determine the maximal number of bits that can be communicated up to a small failure probability. Finally, we demonstrate two ways in which a receiver can recover a state close to the original state after it has been decoded by a sequence of measurements that each succeed with high probability. The second of these methods will be useful in realizing an efficient decoder for fully quantum polar codes, should a method ever be found to realize an efficient decoder for classical-quantum polar codes. This work is available as arXiv:1303.0808.

**Exponential decay of correlations implies area law**

Fernando Brandao, ETH Zurich, Institute for Theoretical Physics

Tuesday, February 12, 2013, 3:00 pm, 107 Annenberg

Quantum states of many particles are fundamental to our understanding of many-body physics. Yet they are extremely daunting objects, requiring in the worst case an exponential number of parameters in the number of subsystems to be even approximately described. How then can multi-particle states be useful for giving predictions to physical observables? The intuitive explanation is that physically relevant quantum states, defined as the ones appearing in nature, are usually much simpler than generic quantum states.

In this talk I will discuss a very recent theorem that gives further justification to this intuition.

The theorem states that exponential decay of correlations, a physically motivated restriction on the set of multi-particle quantum states, implies an area law for the entanglement entropy of systems defined on a line, and thus also an efficient classical description for such systems. The result can be seen as a rigorous justification to the intuition that states with exponential decay of correlations, usually associated with non-critical phases of matter, are simple to describe.

I will outline the main steps in the proof, that relies on several previous tools from quantum information theory and that can also be seen as providing a limitation to the phenomenon of data hiding in quantum states. Based on joint work with Michal Horodecki.

**Quantum information theory as a proof technique**

Fernando Brandao, ETH Zurich, Institute for Theoretical Physics

Friday, February 8, 2013, 3:00 pm, 213 Annenberg
**Note room change**

Quantum information theory emerges naturally from our desire to understand the capabilities of quantum mechanical systems for information processing. However, as for its classical counterpart, the theory turns out to have applications much beyond analysing the efficiency of communication protocols with quantum systems. In this talk I will present two results in this direction.

First I will discuss how the Sum-Of-Squares (Parrilo/Lasserre) hierarchy, one of the most powerful hierarchies of semidefinite programs for approximating optimisation problems, is intimately connected to quantum information theory, with the latter providing a convenient framework for understanding the efficiency of the former.

This leads to new fast algorithms for important quantum-related problems, such as determining whether there is entanglement in a quantum state, as well as improved running-time bounds for approximating problems of interest in theoretical computer science, such as unique games and the small set expansion problem.

Second I will discuss the use of techniques from quantum information theory to understand better the efficiency of mean-field theory, a very useful heuristics in computing properties of certain physical systems (such as in the context of quantum chemistry), and link it to the problem of obtaining a quantum counterpart of the celebrated PCP theorem, which is the central tool in the theory of hardness of approximation.

Both results show how ideas from quantum information theory are useful even outside the quest of building new quantum technologies, forming a powerful new method for arguing about problems ranging from optimization theory and computational complexity theory to numerical physics. No background on quantum information will be assumed.

Based on joint works with Boaz Barak (MRS New England), Matthias Christandl (ETH), Aram Harrow (MIT), Jonathan Kelner (MIT), David Steurer (Cornell), Yuan Zhou (CMU), and Jon Yard (MRS Station Q).

**Device-independent physics: randomness good, communication bad**

Valerio Scarani, Centre for Quantum Technologies and Department of Physics, National University of Singapore

Tuesday, February 5, 2013, 3:00 pm, 107 Annenberg

Bell's theorem rules out the explanation of quantum correlations through pre-established agreement. Most physicists, including the present speaker, view this result as a confirmation of the existence of intrinsic randomness in nature. In the past five years, this lofty view has developed into an unexpected connection with applied quantum information science, hinting to the possibility of "device-independent certification". In the first half of the talk, I shall review some of these developments.

In the second half, I shall try and put myself in the skin of the die-hard of determinism, who have to deny one of the two other assumptions of Bell's theorem. I shall rapidly argue that no scientist can abandon "measurement independence" and shall then focus on abandoning no-signaling. I shall prove a strong result which can be seen as a twin of Bell's theorem (http://arxiv.org/abs/1110.3795): if one tries to explain quantum correlations by a hidden, superluminal influence, this influence must propagate at infinite speed. In other words, any finite-speed influence cannot be hidden and would lead to the possibility of superluminal signaling. This goes as far as one can to prove that, even if intrinsic randomness is puzzling, the alternatives are probably much worse.

**Quantum computational matter**

Stephen Bartlett, University of Sydney

Tuesday, January 29, 2013, 3:00 pm, 107 Annenberg

Low-temperature phases of strongly-interacting quantum many-body systems can exhibit a range of exotic quantum phenomena, from superconductivity to fractionalized particles. One exciting prospect is that the ground or low-temperature thermal state of an engineered quantum system can function as a quantum computer. For this idea to be sensible, the usefulness of a ground or low-temperature thermal state for quantum computation cannot be critically dependent on the details of the system's Hamiltonian; if so, engineering such systems would be difficult or even impossible. A much more powerful result would be the existence of a robust ordered phase which is characterised by its ability to perform quantum computation.

I’ll discuss some recent results on the existence of such a quantum computational phase of matter, working within the measurement-based (cluster state) model of quantum computation. I will show that the ability to perform certain logic gates such as the identity gate over long distances in the model corresponds precisely to the recently-proposed notion of 'symmetry-protected topological order' for an appropriate symmetry group. Using some techniques from fault-tolerance, we can then prove that any perturbation of the cluster state model will result in a ground state that remains universal for quantum computation, provided the perturbation is sufficiently small and respects a certain symmetry.

References:

http://arxiv.org/abs/1201.4877

http://arxiv.org/abs/1207.4805

**Partial-indistinguishability obfuscation using braids**

Stephen Jordan, NIST

Tuesday, January 8, 2013, 3:00 pm, 107 Annenberg

A circuit obfuscator is an algorithm that translates logic circuits into functionally-equivalent similarly-sized logic circuits that are hard to understand. While ad hoc obfuscators exist, theoretical progress has mainly been limited to no-go results. In this work, we propose a new notion of circuit obfuscation, which we call partial indistinguishability. We then prove that, in contrast to previous definitions of obfuscation, partial indistinguishability obfuscation can be achieved by a polynomial-time algorithm. Specifically, our algorithm re-compiles the given circuit using a gate that satisfies the relations of the braid group, and then reduces to a braid normal form. A variant of our obfuscation algorithm can also be applied to quantum circuits.

**On the structure of symmetric quantum measurements **

Jon Yard, Microsoft Station Q

Tuesday, December 11, 2012, 3:00 pm, 107 Annenberg

A central problem in quantum information theory is to understand the apparent existence of d^2 equiangular lines in any d-dimensional complex vector space. Such configurations of lines determine highly-symmetric optimal quantum measurements known as Symmetric Informationally-Complete Positive Operator-Valued Measures (SIC-POVMs). Much evidence indicates that SIC-POVMs can always be obtained as special orbits of finite Heisenberg groups. Exact constructions of Heisenberg-covariant SIC-POVMs are currently known in 22 different dimensions, while numerical evidence indicates that they exist for every dimension up to 67. The elements of Heisenberg-covariant SIC-POVMs correspond to quantum states that are maximally localized in discrete phase space and can be viewed as finite-dimensional analogs of coherent states. They also contain rich algebraic structure, as they are defined over number fields with nonabelian Galois groups - namely, over abelian extensions of quadratic fields. In this talk, I will show how the mathematics of class field theory can explain some of the group-theoretic structure possessed by these known examples while offering predictions for their structure in arbitrary dimensions.

**Emergence and frustration of Magnetism in a trapped ion quantum simulator**

Wes Campbell, UCLA

Tuesday, November 20, 2012, 3:00 pm, 107 Annenberg

Frustration, or the competition between interacting components of a network, is often responsible for the complexity of many body systems. In quantum magnetic systems, frustration arises naturally from competing spin-spin interactions given by the geometry of the spin lattice or by the presence of long-range antiferromagnetic couplings. I will describe work using a trapped atomic ion quantum simulator to simulate strongly-coupled, frustrated quantum systems with up to 16 spins. We control the amount of frustration in the system by continuously tuning the range of an antiferromagnetic coupling in a linear spin chain, and we examine the dynamics and magnetism of the system as it crosses the critical point. In the future, quantum simulations such as these may to shed light on universal behavior of many-body systems in the quantum regime.

**Topological stabilizer codes with a power law energy barrier via welding**

Kamil Michnicki, University of Washington

Tuesday, October 30, 2012, 3:00 pm, 107 Annenberg

A high energy barrier for logical errors is essential for the development of self-correcting quantum memories in the Hamiltonian framework. These devices would have an unbounded storage time at a fixed temperature as a function of the total number of qubits. In order to find a codes with large energy barriers we introduce a new primitive, called welding, for combining two stabilizer codes to produce a new stabilizer code for which the resulting shape of the logical operators is the combination of the former two shapes. We apply welding to construct surface codes and then use the surface codes to construct solid codes, a variant of a 3-d toric code with rough and smooth boundaries. Finally, we weld solid codes together to produce a [O(L^3),1,O(L^{4/3})] stabilizer code with an energy barrier of O(L^{2/3}), which solves an open problem of whether a power law energy barrier is possible for local stabilizer code Hamiltonians in three-dimensions. The previous highest energy barrier is O(log L)$. Previous no-go results are avoided by breaking translation invariance. Despite the large energy barrier, this code is unlikely to serve as a self-correcting quantum memory.

**Efficient distributed quantum computing**

Steve Brierley, University of Bristol

Tuesday, October 23, 2012, 3:00 pm, 107 Annenberg

I'll present algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with low overhead by the more realistic model of a distributed quantum computer. In addition, our results apply to existing memory intensive quantum algorithms. I'll show you a new parallel quantum search algorithm and explain how to improve the time-space trade-off for the Element Distinctness and Collision problems.

**A classical leash for a quantum tiger: Key distribution with miminmal assumptions **

Ben Reichardt, University of Southern California

Tuesday, October 16, 2012, 3:00 pm, 107 Annenberg

Can an experimentalist possibly understand and control an arbitrary quantum system? We give a scheme by which a classical experimentalist, with only classical interactions, can fully control black-box quantum-mechanical systems. The scheme even distinguishes a quantum computer from a classical simulation.

Although partly philosophical, this result has cryptographic applications. The original idea of quantum key distribution (QKD) is to base security on the laws of physics. But in practice QKD systems have been attacked, because real devices deviate from the mathematical models. Mayers and Yao in 1998 suggested that perhaps all these side-channel attacks could be eliminated. Barrett, Hardy and Kent gave the first "device-independent" QKD security proof in 2005, based on the assumption that Alice and Bob each have n devices, that are separately kept isolated but are otherwise arbitrary. We prove security with just one device for Alice and one for Bob. The key theorem studies sequential composition of a two-player game, and argues that nearly optimal strategies are nearly uniquely determined.

As another corollary, QMIP = MIP*.

Based on arXiv:1209.0448 and 1209.0449. Joint work with Falk Unger and Umesh Vazirani.

**Quantum mechanics, cosmology, and self-locating uncertainty **

Sean Carroll, Caltech

Tuesday, October 9, 2012, 3:00 pm, 107 Annenberg

A longstanding issue in attempts to understand the Everett
(Many-Worlds) approach to quantum mechanics is the origin of the Born
Rule: why is the probability given by the square of the amplitude?

Recently, Page has raised another puzzle: the Born Rule itself is insufficient in cases where the wave function includes multiple indistinguishable observers in the same branch. We argue that both problems share a common solution, arising from a proper treatment of self-locating uncertainty (physical situations containing multiple copies of identical observers). This analysis gives a simple, physics-oriented derivation of the Born Rule, as well as a justification for the treatment of identical classical observers.

**Topological order with tensor networks on infinite cylinders: an explicit wavefunction for fractionalized quasi-particle excitations**

Guifre Vidal, Perimeter Institute

Tuesday, October 2, 2012, 3:00 pm, 107 Annenberg

Starting from a microscopic Hamiltonian on an infinite cylinder, In Ref. [Cincio and Vidal, "Characterizing topological order by studying the ground states of an infinite cylinder", arXiv:1208.2623v1], a method to obtain a tensor network representation for the different ground states of a topologically ordered system was proposed. In this talk, I will review that approach and explain how to also obtain a tensor network representation for each of the different quasi-particle excitations of the emergent, topologically ordered medium, including those with fractionalized quantum numbers.

For a complete listing of IQI seminars from 2001 through April 2012, see the archived IQI web page

[IQI Seminar Schedule for 2012]

[IQI Archive - includes IQI Seminars from 2001 through September 2012]