|
Agenda
8:45 - 9:00 |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
|
OPENING |
|
|
|
|
||
9:00 - 9:45 |
TBD |
|||||
9:45 - 10:30 |
||||||
10:30 - 11:00 |
COFFEE BREAK |
|||||
11:00 - 11:45 |
||||||
11:45 - 12:30 |
||||||
12:30 - 2:00 |
LUNCH |
CLOSING |
||||
2:00 - 2:45 |
||||||
2:45 - 3:30 |
||||||
3:30 - 4:00 |
COFFEE BREAK |
|||||
4:00 - 4:45 |
||||||
4:45 - 5:30 |
Yard* |
|||||
5:30 - 5:45 |
BREAK |
|||||
5:45 - 6:30 |
BP Tutorial** |
Discussion 1 |
||||
7:30 |
Banquet |
(*) = 15-minute talk
(**) = Belief-Propagation tutorial, given by Dr. Jonathan Yedidia, Mitsubishi Research.
TBA |
||
|
|
|
|
|
Quantum walks are quantum counterparts of random walks. In this talk, we will define quantum walks and survey the main results about quantum walks. The first set of results describes the behaviour of quantum walks in a line or k-dimensional grid. We will show that quantum walk on a line with no boundaries spreads quadratically faster than a conventional random walk. We also show some interesting properties of quantum walks on a line with absorbing boundaries and quantum walks in presence of decoherence. The second set of results is about quantum algorithms that use quantum walks, in particular, search on k-dimensional grid and its generalization to quantum speedups for arbitrary classical random walks. |
|
|
Quantization Codes Comprising Multiple Orthonormal Bases |
||
|
A quantization code is a set of points (code vectors) on the surface of real or complex M-dimensional sphere of unit radius. A good quantization code has a small size and is organized in such a way that any vector of unit norm is close to some code vector. In this talk I present an algebraic construction of quantization codes that have an additional property - many sets of M code vectors form orthonormal bases in R^M (C^M). For instance in the case M=4 one of the designed codes consists of 60 code vectors and comprises 105 sets of four code vectors that form 105 orthonormal bases in C^4. Next, I consider an application of such quantization codes in MIMO broadcast systems with a feedback. In such systems the base station is equipped with M antennas and each of K mobiles is equipped with a single antenna. The mobiles estimate their channel vectors and have to transmit them back to the base station. Typically, the mobiles have very limited resources allowing them to transmit to the base station only few bits. A standard approach in this case is to use a quantization code Q={v_1, ..., v_L}. The j-th mobile finds the code vector v_i closest to its channel vector h_j and transmits back only the index i. The base station uses v_i as an approximation of h_j. For achieving a high throughput the base station has to identify N (N<=M) mobiles whose channel vectors are orthogonal to each other. A traditional approach is to use a random quantization code and a greedy algorithm for searching mobiles with orthogonal channel vectors. In the talk I show that MIMO Broadcast systems using quantization codes comprising multiple bases outperform MIMO Broadcast systems using random quantization codes. |
|
|
Quantum Simulated Annealing |
||
|
We develop a quantum algorithm to solve combinatorial optimization problems through quantum simulation of a classical annealing process. Our algorithm combines ideas from quantum walks and the quantum Zeno effect, implemented with a new evolution-randomization technique. It can be viewed as a quantum analogue of the discrete-time Markov chain Monte Carlo implementation of classical simulated annealing. The quantum method scales with the inverse square root of the minimum spectral gap of the stochastic matrices used in the clasical method. This outperforms the classical method, which scales with the inverse gap. If time permits, specific applications will be discussed. Joint work with Rolando Somma (PI) and Sergio Boixo (LANL, UNM). |
|
|
Construction of perturbative gadgets with constant-bounded interactions |
||
|
Quantum-mechanical perturbative gadgets introduced originally by Kempe, Kitaev and Regev allow one to simulate low-energy properties of spin Hamiltonians with many-body interactions using spin Hamiltonians with only two-body interactions. An important limitation of this approach is that the magnitude of interactions describing a gadget Hamiltonian must grow polynomially with the size of the system --- a requirement which is difficult to meet in an experiment. In my talk I discuss what kind of simulations can be achieved if only interactions of constant-bounded magnitude are available. Specifically, it is shown that for any spatially local Hamiltonian H_k with constant-bounded k-body interactions acting on N spins and for any constant precision delta>0 one can construct a spatially local Hamiltonian H_2 with constant-bounded two-body interactions acting on O(N) spins such that the ground state energy of H_2 approximates the ground state energy of H_k with an error at most N\delta (it is assumed that k is a constant). Thus the ground state energy density can be reproduced with an arbitrarily good precision. By the spatial locality of a Hamiltonian we mean that each spin can be affected only by a constant number of interactions. In contrast to the original paper by Kempe, Kitaev and Regev our analysis relies on the perturbation theory only to analyze properties of isolated gadgets whereas collective effects caused by interactions between gadgets are treated non-perturbatively. |
|
|
Insight on quantum topological order from finite temperature considerations |
||
|
We investigate the behavior of the entanglement and topological entropy in the two- and three-dimensional toric code at finite temperature. From our results, we infer that quantum topological order is fragile with respect to thermal fluctuations in spite of the presence of a finite energy gap at zero temperature. In two dimensions, all topological order evaporates at any non-vanishing temperature in the thermodynamic limit. On the contrary, in three dimensions not all topological information is lost, although the topologically protected quantum information (qubit) stored in the ground state of the system is immediately degraded to topologically protected classical probabilistic information (pbit) at any infinitesimal temperature, in the thermodynamic limit. All information is eventually lost beyond a finite temperature phase transition. Our result suggest that the topological information stored in these systems, as measured by the topological entropy, has in fact a classical origin, with the quantum mechanical nature resting in the ability to form a coherent superposition of such classical structures. |
|
|
Belief Propagation and Loop Series on Planar Graphs |
||
|
We discuss a generic model of Bayesian inference with binary variables defined on edges of a planar graph. The Loop Calculus approach is used to evaluate the resulting series expansion for the partition function. We show that, for planar graphs, truncating the series at single-connected loops reduces, via a map reminiscent of the Fisher transformation [3], to evaluating the partition function of the dimer matching model on an auxiliary planar graph. Thus, the truncated series can be easily re-summed, using the Pfaffian formula of Kasteleyn. This allows to identify a big class of computationally tractable planar models reducible to a dimer model via the Belief Propagation (gauge) transformation. The Pfaffian representation can also be extended to the full Loop Series, in which case the expansion becomes a sum of Pfaffian contributions, each associated with dimer matchings on an extension to a subgraph of the original graph. Algorithmic consequences of the Pfaffian representation, as well as relations to quantum and non-planar models, are discussed. |
|
|
Joint work with Misha Chertkov and Razvan Teodorescu. |
Renormalization group approach to classifying Boolean functions |
||
|
I will argue that the renormalization group technique used to characterize phase transitions in condensed matter systems can be used to classify Boolean functions. One can define different phases of Boolean functions depending on the behavior upon repeated applications of a renormalization transformation that maps a Boolean function of N Boolean variables to one of N-1 variables. Possible relationships between phases of Boolean functions and computational complexity classes studied in computer science will be discussed. |
|
|
A Quantum Information Approach to Quantum Phase Transitions |
||
|
I will discuss how concepts from quantum information can help us gain better understanding of quantum phase transitions. In particular, I will show how the ground state fidelity and its time evolution can serve to identify critical points and exponents. I will present experimental results of a "critical-point-finder" quantum algorithm using liquid nuclear magnetic resonance, as well as a proposal for its implementation in cold bosonic atoms trapped in an optical lattice. Apart from measuring properties of the quantum phase transition, I will discuss other applications of the experiments such as sensing of small forces. |
|
|
Quenching, relaxation, and a central limit theorem for quantum lattice systems |
||
|
A reasonable physical intuition in the study of interacting quantum systems says that, independent of the initial state, the system will tend to equilibrate. In this talk we will consider a setting where relaxation to a steady state is exact, namely for the Bose-Hubbard model where the system is quenched from a Mott quantum phase to the strong superfluid regime. We find that the evolving state locally relaxes to a steady state with maximum entropy constrained by second moments, maximizing the entanglement, to a state which is different from the thermal state of the new Hamiltonian. Remarkably, in the infinite system limit this relaxation is true for all large times, and no time average is necessary. For large but finite system size we give a time interval for which the system locally "looks relaxed" up to a prescribed error. Our argument includes a central limit theorem for harmonic systems and exploits the finite speed of sound. We also discuss implications on entropy scaling in such quenched systems and the difficulty of simulating them using matrix-product states. The final part of the talk will be concerned with numerical work on strongly interacting systems, using t-DMRG, as well as experimental implications. The idea of local relaxation has led to a joint project with an experimental group which aims at observing local relaxation in non-equilibrium systems using cold atoms in optical lattices. Here, the key idea is that optical superlattices allow for a period two read out of densities and correlations, such that relaxation phenomena can be studied without the need of locally addressing individual sites. |
|
|
Joint work with M. Cramer, T. Osborne, A. Flesch, U. Schollwoeck |
TBA |
||
|
I show how to define quantum loop models which allow for deconfined anyons with non-abelian braiding. For anyons to be deconfined and hence be useful for topological quantum computation, the ground state must be a sum over configurations containing loops of all lengths. This is achieved here by introducing a new inner product which also has desirable topological properties. One consequence is that the anionic fusion matrix is implemented directly on the lattice, even when the degrees of freedom are simply Ising spins on the square lattice. |
|
|
Practical error correction for quantum key distribution |
||
|
Quantum key distribution (QKD) provides a means for securely sharing secret bits among distant parties by using a quantum channel with sufficiently low noise and a public authenticated classical channel for communications. One of the important steps in a QKD protocol is to identify and correct the errors from the quantum transmission. To date, most QKD experiments have utilized some version of Cascade for error correction, which requires many rounds of communication back and forth. In most realistic settings, available bandwidth and desired speed of a QKD system may require forward error correction instead, but it appears to be an open research problem of identifying good error-correcting codes for the practical case. I plan to give an overview of this research problem, highlighting the error sources in QKD systems, and I will present some results utilizing low-density parity-check codes. |
|
|
TBA |
||
|
Abstract. |
|
|
Pseudo-random quantum states and operations |
||
|
The idea of pseudo-randomness is to use little or no randomness to simulate a random object such as a random number, permutation, graph, quantum state, etc... The simulation should then have some superficial resemblance to a truly random object; for example, the first few moments of a random variable should be nearly the same. This concept has been enormously useful in classical computer science. In my talk, I'll review some quantum analogues of pseudo-randomness: unitary k-designs, quantum expanders (and their new cousin, quantum tensor product expanders), extractors. I'll talk about relations between them, efficient constructions, and possible applications. |
|
|
Some of the material is joint work with Matt Hastings and Richard Low. |
Counterexamples to the maximal p-norm multiplicativity conjecture |
||
|
The maximal p-norm multiplicativity conjecture is a natural strengthening of the additivity conjecture of quantum information theory. The additivity conjecture implies, among other things, that using entangled codewords can't improve the classical information carrying capcity of a quantum channel. A proof of the multiplicativity conjecture for p in a neighborhood (1,1+x) would have implied the more important additivity conjecture. The multiplicativity conjecture, however, is false. In this talk I'll present counterexamples for all p>1. I'll then discuss the curious obstinacy of the additivity conjecture and why it seems to be unscathed by these examples. |
|
|
Entanglement in Spin Chains |
||
|
Different measures of entanglement are considered. A popular measure is entropy of a subsystem. Subsystem can be chosen as a block of spins in the ground state of a Hamiltonian [XY, AKLT...]. I will discuss von Neumann entropy and Renyi entropy as measures of entanglement for different models. The density matrix of the block (including eigenvectors) are also interesting. See arXiv:0711.3882, arXiv:0707.2534, arXiv:quant-ph/0609098, arXiv:quant-ph/0606240, arXiv:quant-ph/0606178, arXiv:quant-ph/0409027, arXiv:quant-ph/0406067, arXiv:cond-mat/0311056, arXiv:quant-ph/0304108 |
|
|
Routing & Communication on Wireless Network as a Quantum Spin Problem |
||
|
Abstract. |
|
|
Entanglement and noise suppression in on-demand electron sources |
||
|
In currently developed single electron sources, localized electrons are coherently transferred into a Fermi sea at well-controlled times, creating current pulses carrying quantized electric charge. We analyze particle/hole excitations created in the process of such transfer and identify optimal transfer protocols that help to minimize the number of produced excitations. Interestingly, we find that under certain conditions it is possible to create totally clean, excitation-free current pulses. The underlying mechanism of excitation suppression is linked with entanglement suppression due to Fermi statistics. |
|
|
Nonequilibrium Statistics of Geophysical Flows From Cumulant Expansions and Flow Equations |
||
|
The probability distribution function of non-linear dynamical systems is governed by a linear framework that resembles quantum many-body theory, in which stochastic forcing and/or averaging over initial conditions play the role of Planck's constant. Besides the well-known Fokker-Planck approach, there is a related Hopf functional method; in both formalisms, zero modes of linear operators describe the stationary non-equilibrium statistics. The approach is illustrated here by application to the calculation of equal-time statistics of a barotropic flow on a rotating sphere. Such prototypical geophysical problems are typically less non-linear than homogeneous turbulence due to the presence of mean flows, making direct calculation of the statistics tractable. The flow is driven by linear relaxation toward an unstable zonal jet. For relatively short relaxation times, it is dominated by critical-layer waves. For sufficiently long relaxation times, the flow is turbulent. Statistics obtained from a second-order cumulant expansion are compared to those accumulated in direct numerical simulations, revealing the strengths and limitations of the expansion for different relaxation times. Deficiencies in the cumulant expansion can be overcome by employing the method of continuous unitary transformations, also known as the Wegner's flow equation approach, to access the fixed point that governs the steady-state statistics. |
|
|
On the Chernoff distance for asymptotic LOCC discrimination of bipartite quantum states |
||
|
Motivated by the recent discovery of a quantum Chernoff theorem for asymptotic state discrimination, we investigated the distinguishability of two bipartite mixed states under the constraint of local operations and classical communication (LOCC), in the limit of many copies. While for two pure states a result of Walgate et al. shows that LOCC is just as powerful as global measurements, data hiding states (DiVincenzo et al.) show that locality can impose severe restrictions on the distinguishability of even orthogonal states. We have determined the optimal error probability and measurement to discriminate many copies of particular data hiding states (extremal d x d Werner states) by a linear programming approach. Surprisingly, the single-copy optimal measurement remains optimal for n copies, in the sense that the best strategy is measuring each copy separately, followed by a simple classical decision rule. We also put a lower bound on the bias with which states can be distinguished by separable operations. |
|
|
TBA |
||
|
Abstract. |
|
|
Quantum algorithms for manifold invariants |
||
|
Suppose we are given two triangulations, in which a set of d-dimensional simplices are glued together along shared faces and edges. How can we tell whether these are actually two triangulations of the same d-dimensional manifold? Recently, Aharonov, Jones, and Landau gave quantum algorithms for additive approximations of the Jones polynomial. Our goal is to produce analogous algorithms for topological invariants of manifolds. For example, if M is a 2-manifold, we can obtain an additive approxiation to |G|^{\chi-1} #(M,G) where #(M,G) is the number of homomorphisms from the fundamental group of M into G, and \chi is the Euler characteristic of M. Extending these results to the 3-manifold invariants derived from topological quantum field theories (TQFTs) presents interesting technical issues. |
|
|
This is joint work with Zeph Landau and Alex Russell. |
Dynamical localisation and information propagation |
||
|
In this talk I will describe a method to study dynamical localisation in interacting quantum systems: I will show how the non-Markovian dynamics of a general statically disordered system can be reduced to the Markovian dynamics of a related continuously-measured system. Thus problems of dynamical localisation can be understood by studying information propagation in decohering systems. This method is applied to study dynamical localisation in the Anderson model in low dimensions and to interacting spin systems. In the latter case dynamical localisation manifests itself in the low order correlators giving rise to a bound on information propagation stronger than that given by the Lieb-Robinson bound. |
|
|
Quantum graphical models and belief propagation |
||
|
Belief propagation algorithms acting on graphical models of classical probability distributions, such as Markov networks, factor graphs and Bayesian networks, are amongst the most powerful known methods for deriving probabilistic inferences amongst large numbers of random variables. In this talk, I will present a generalization of these concepts and methods to the quantum case, based on the idea that quantum theory can be thought of as a noncommutative, operator-valued, generalization of classical probability theory. The use of quantum belief propagation as a heuristic algorithm in cases where it is not known to converge will be discussed. I will present applications of QBP to the decoding of quantum error correcting codes and to the simulation of many-body quantum systems. |
|
|
Fault-tolerant quantum computation versus realistic noise |
||
|
I review and assess rigorous estimates of the accuracy threshold for fault-tolerant quantum computation, with emphasis on the applicability of these results to realistic noise models. I explain (based on joint work with Panos Aliferis) how to formulate a fault-tolerant scheme that works effectively against highly biased noise, where phase errors in the computational basis are much more likely than bit-flip errors. I also describe an improved analysis of non-Markovian noise that yields a new threshold estimate which is less sensitive than previous estimates to the properties of very high frequency noise. |
|
|
A classical versus quantum paradigm for the topological model |
||
|
The question of universality of a given topological quantum computer hinges upon the density of the images of the (unitary) braid group representations realized by adiabatic particle exchange, in the group of unitaries. This, in turn, appears to be closely tied to the computational (classical and quantum) complexity of the link invariants that are naturally computed by the given quantum computer. I will discuss these connections in the form of a paradigm and some recent results supporting it. |
|
|
Some aspects of information-driven networks |
||
|
This talk will consider several aspects of
networks driven by information without spatial range. Much
information on the internet or the news is of this kind. One type
of problem is where many “agents” react to such globally
available information, albeit in individual ways, with their
subsequent collective behaviour influencing all participants. This
exchange provides an effective mutual interaction which is
quasi-disordered but range-free, opening the problem of the
macroscopic behaviour to techniques analogous to those developed
for the dynamics of mean-field spin glasses. An illustration of
such application will be discussed in the context of an idealized
model stockmarket (the minority game). |
|
|
This talk will involve work done in collaboration with Tobias Galla, Heiko Bauke and Cris Moore. |
Codeword Stabilized Quantum Codes |
||
|
I will describe an approach to quantum error correcting code design that encompasses additive (stabilizer) codes, as well as all known examples of nonadditive codes with good parameters. Our quantum codes are described by a single graph state, together with a classical binary code. The graph state may be thought of as mapping quantum errors to an exotic classical error model, which we must then arrange to correct with our classical code. Stabilizer codes arise naturally as those quantum codes with a linear classical code. I will show how to use this framework to generate new codes with superior parameters to any previously known, as well construct encoding circuits for all codes within this family. |
|
|
Cavity method for quantum spin glasses on the Bethe lattice |
||
|
We propose a generalization of the cavity method to quantum spin glasses on fixed connectivity lattices. Our work is motivated by the recent refinements of the classical technique and its potential application to quantum computational problems. We numerically solve for the phase structure of a connectivity q=3 transverse field Ising model on a Bethe lattice with couplings of fixed magnitude but random sign, and investigate the distribution of various classical and quantum observables. |
|
|
TBA |
||
|
Abstract. |
|
|
Stoquastic Hamiltonians and Their Complexity |
||
|
MA is a class of decision problems for which `yes'-instances have aproof that can be efficiently checked by a classical randomizedalgorithm. We prove that MA has a natural complete problem which we callthe stoquastic k-SAT problem. This is a matrix-valued analogue of the satisfiability problem in which clauses are k-qubit projectors with non-negative matrix elements, while a satisfying assignment is a vectorthat belongs to the space spanned by these projectors. Stoquastic k-SAT is the first non-trivial example of a MA-complete problem. We also discuss the minimum eigenvalue problem for local stoquastic Hamiltonians, stoquastic LH-MIN. Stoquastic local Hamiltonians are those Hamiltonians that can be mapped onto non-negative matrices. This implies that Perron-Frobenius theory and other classical stochastic methods can be used to analyze these Hamiltonians. I will discuss various rigorous results on the complexity of determining the ground-state energy of these Hamiltonians and the role of techniques used in physics such as Green's function Monte Carlo and quantum-to-classical mappings. |
|
|
On the computational complexity of simulating quantum many-body systems |
||
|
Abstract. |
|
|
Quantum shock waves and emergence of quantized edge states in Fractional Quantum Hall Effect |
||
|
Propagating wave packets along
the edge of FQHE semiconductor is essentially non-linear. At a
finite time a wave packet collapses through a shock wave
singularity emanating oscillatory features which in its turn
evolve into regularly |
|
|
Hamiltonian Quantum Cellular Automata in 1D |
||
|
We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of 10-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process, requiring only initial product state preparation. Both the quantum circuit and its input are encoded in an initial canonical basis state of the qudit chain. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time greater than a polynomial in the size of the quantum circuit has passed, the result of the computation can be obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless BPP=BQP). |
|
|
This is joint work with Daniel Nagaj. |
Approximating quantum group link invariants on quantum computers |
||
|
I will report on joint work with Cris Moore (UNM/SFI) showing how quantum computers can be used to approximately evaluate some polynomial invariants of links associated with quantum groups. These invariants include the Jones, HOMFLYPT and Kauffman polynomials. The method uses local quantum circuits for braid group representations derived from the path algebra approach to centralizer algebras of tensor powers of quantum group representations. |
|
|
Iterative
Linear-Programming-Based Route Optimization for |
||
|
We develop linear-programming
(LP) based route optimization techniques for networks of relays
that employ mutual information accumulation (accomplished, for
example, using fountain codes). Given a network, a source, and a
destination, our objective is to minimize end-to-end transmission
delay under energy and bandwidth constraints. We provide an
algorithm that determines which nodes should participate in
forwarding the message and what resources (transmission time,
energy, and bandwidth) should be allocated to each. Our approach factors into two sub-problems, both of which can be solved efficiently. For any node decoding order, we show that solving for the optimum resource allocation can be formulated as a linear program. We then show that the decoding order can be improved systematically be swapping nodes based on the solution of the linear program. Solving a sequence of linear programs leads to a locally optimal solution in a very efficient manner. We observe that compared to our cooperative routes, conventional shortest-path multi-hop routes typically incur additional delays and energy expenditures on the order of 70%. |
|
|
Forward message passing detector for probe storage |
||
|
We propose a simple soft-output detection scheme for communication channels characterized by data-dependent noise and/or inter-symbol interference (ISI). The proposed detection algorithm is based on the idea of forward message passing. We discuss a particular embodiment of the corresponding detector for a thermomechanical probe storage read channel. We perform an extensive performance investigation of the forward message passing detector using a simplified probe storage channel model characterized by non-linear inter-symbol interference and non-linear jitter distortion. |
|
|
Quantum origins of information and ignorance: Deriving probabilities from the symmetries of entanglement. |
||
|
I will discuss quantum origin of quantum jumps (which define ?events? such as measurement outcomes). I shall then show that events occur with probabilities which can be deduced from symmetries of entangled quantum states ? form envariance (entanglement ? assisted invariance). I shall focus on implications of envariance for the origin and nature of ignorance, and, hence, for the origin of probabilities and information in physics. While derivation of Born's rule for probabilities (p_k=|\\psi_k|^2) is the principal result, I shall note that other symptoms of quantum - to - classical transition that follow from decoherence can be justified directly via envariance -- i.e., without decoherence, and without invoking Born's rule. References: W. H. Zurek, Phys. Rev. Lett. 90, 120404 (2003); Rev. Mod. Phys. 75, 715 (2003); Phys. Rev. A71, 052105 (2005); Phys. Rev. A76, 052110 (2007); arXiv:0707.2832. |
|
|