Search Talks

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability 1 - p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classic) algorithm which optimally solves both variants together, up to an additive term of O(log log (n)), and prove matching information theoretic lower bounds. We use the algorithm with the results of Farhi et al. (FGGS99)presenting a quantum search algorithm in an ordered list of expected complexity less than log(n)/3, and some improved quantum lower bounds on noisy search, and search with an error probability. Joint work with Michael Ben-Or.

After almost a century of observations, the ultra-high energy sky has finally displayed an anisotropic distribution. A significant correlation between the arrival directions of ultra-high cosmic rays measured by the Pierre Auger Observatory and the distribution of nearby active galactic nuclei signals the dawn of particle astronomy. These historic results have important implications to both astrophysics and particle physics.

Roughly speaking, the more Alice is entangled with Bob, the harder it is for her to send her state to Charlie. In particular, it will be shown that the squashed entanglement, a well known entanglement measure, gives the fastest rate at which a quantum state can be sent between two parties who share arbitrary side information. Likewise, the entanglement of formation and entanglement cost is shown to be the fastest rate at which a quantum state can be sent when the parties have access to side-information which is maximally correlated. A further restriction on the type of side-information implies that the rate of state transmission is given by the quantum mutual information. This suggests a new paradigm for understanding entanglement and other correlations in terms of quantum Shannon theroy. Different types of side-information correspond to different types of correlations with the squashed entanglement and the mutual information being two extremes. Furthermore, there is a dual paradigm: if one distributes the side-information as aliciously as possible so as to make the sending of the state as difficult as possible, one finds maximum rates which give interpretations to known quantities as well as new ones.

In any attempt to construct a Quantum Theory of Gravity, one has to deal with the fact that Time in Quantum Mechanics appears to be very different from Time in General Relativity. This is the famous (or actually notorious!) \"Problem of Time\", and gives rise to both conceptual and technical problems. The decoherent histories approach to quantum theory, is an alternative formulation of quantum theory specially designed to deal with closed (no-external observer or environment) systems. This approach has been considered particularly promising, in dealing with the problem of time, since it puts space and time in equal footing (unlike standard QM) . This talk develops a particular implementation of the above expectations, i.e. we construct a general set of \"Class Operators\" corresponding to questions that appear to be \"Timeless\" (independent of the parameter time), but correspond to physically interesting questions. This is similar to finding a general enough set of timeless observables, in the evolving constants approach to the problem of time.

I will describe the emergence of geometric (Berry) phases in supersymmetric systems. In theories with degenerate states, non-Abelian geometric phases can arise. I show how supersymmetry helps to ensure the existence of this phenomenon by invoking the examples of systems with (2,2) and (4,4) supersymmetry. In the former, I show how instantons contribute crucially to the form of the non-Abelian phase. The latter system applies to D0-D4 brane dynamics in string theory, leading to a surprising re-interpretation of the Berry phase in terms of gravitational precession of a probe brane. Towards the end will comment on some work in progress on the geometric phase in (8,8) SUSY systems.