Mar. 29: Special Seminar
     Andris Ambainis, Berkeley
     4:00 p.m., 102 Steele

Title: Lower bounds on quantum computing

Abstract:
Quantum computation is an exciting new field which touches on the foundations of both computer science and quantum mechanics. It provides a new model of computation that is both physically reasonable and more powerful than conventional (classical) computing.

Shor gave a polynomial time quantum algorithm for factoring integers, a problem which is suspected to be very hard classically. Since most of public key cryptography is based on hardness of factoring, building a quantum computer would undercut the foundations of today's cryptography. Another major achievement is Grover's quantum algorithm which can speed up the solution of an arbitrary exhaustive search problem. Given those developments, it is very important to understand the limitation of quantum computing.

This can be done in the quantum query model where we restrict the algorithm to accessing the input by queries and count the number of queries needed to solve the problem.

In this talk, I will present a new `quantum adversary' method for proving lower bounds on quantum algorithms in the query model. Using this method, I will show that Grover's algorithm is optimal both for the original search problem considered by Grover and several other related problems. Besides giving better lower bounds, the new method also allows to unify a number of results that were previously shown using a variety of different techniques.

Host: Leonard Schulman

Apr 27: IQI Seminar
     Lorenza Viola, LANL
     3:30 p.m., 102 Steele

Title: Theory (and practice) of noiseless quantum subsystems

Abstract:
Noiseless subsystems provide a general tool for realizing the emergence of noise-protected degrees of freedom in open quantum systems. Starting from the simplest prototype example based on three symmetric spin 1/2 particles, I will show how noiseless subsystems can be defined for generic open-system evolutions and how they allow a unified understanding of existing noise control strategies. Special attention will be devoted to the connections
between noiseless subsystems and quantum error-correcting codes. Finally, I will describe an experimental implementation via nuclear magnetic resonance of the above three spin noiseless subsystem to demonstrate the preservation of one qubit against collective noise.

Host: John Preskill

May 4: IQI Seminar
     Gerard Milburn, University of Queensland
     3:30 p.m., 102 Steele

Title: Quantum computation in linear bosonic and fermionic interferometers

Abstract:
Two qubit gates for photons are generally thought to require exotic materials with huge optical nonlinearity. I will describe a scheme that uses only linear optical interferometers to implementing reliable quantum algorithms. The scheme requires: two qubit gates that only work conditionally, near deterministic teleportation, single photon sources, and fast electro-optics feedforward. I will discuss one proposed single photon source based on the surface acoustic wave guiding of single electrons. The scheme can be extended to linear fermionic interferometers.

Host: John Preskill


May 11: IQI Seminar
     Debbie Leung, IBM Watson Research Center
     3:30 p.m., 102 Steele

Title: Hiding classical data in quantum states

Abstract:
We consider methods to encode a classical secret as a quantum state shared by two parties, such that the secret is still hidden even if the two parties communicate classically but is opened if the two parties perform joint quantum operations. This exhibits a hiding capability stronger than is possible in any classical scheme. This capability originates from known rules of entanglement manipulations. General methods to derive upper and lower bounds of the information obtained by the two sharers will be described, and applied to prove the security of a proposed scheme. Other questions concerning the security and implementation, and extensions to this proposed scheme will be discussed.

Host: John Preskill


May 25: IQI Seminar
     Alexei Kitaev, Microsoft Research
     3:30 p.m., 102 Steele

Title: Some results about parallel quantum computation

Abstract:
Parallelism of quantum computation can be quantified by circuit depth. I consider a model in which unitary operations are performed by braiding sufficiently nontrivial anyons; the reduction between this model and the standard circuit model is size- and depth-effective both ways. It is shown that computation with depth $O(\log n)$ is equivalent to measuring the anyonic charge in a (specially shaped) domain of polynomial size.

Host: John Preskill

June 1: IQI Seminar
     Michael Nielsen, University of Queensland
     3:30 p.m., 102 Steele

Title: Entanglement and universal quantum computation

Abstract:
What interactions are required to simulate arbitrary dynamics in a composite quantum system? I explain an efficient algorithm to simulate any desired Hamiltonian evolution using any single fixed entangling Hamiltonian and local unitary evolution. It follows that universal quantum computation can, in principle, be performed using any system with an entangling interaction and the ability to do local unitary operations.

Host: John Preskill

August 3: IQI Seminar
     Yoshihisa Yamamoto, Edward L. Ginzton Laboratory, Stanford
     3:30 p.m., 102 Steele

Title: Generation and detection of triggered single photons

Abstract:
A source of single photons, each arriving within a known time interval, and high-efficiency/low-noise single photon counters, would be useful in the new fields of quantum key distribution and quantum computation with photonic qubits. In this talk, I will discuss our method or generating triggered single photons based on a single InAs quantum dot in a
three-dimensional microcavity. The system is also expected to produce an entangled EPR-Bell photon pair. I will also describe efficient and low-noise detection of single photons with an As-doped Si avalanche detector.

Host: Hideo Mabuchi

August 24: IQI Seminar
     Tommaso Calarco, University of Innsbruck
     3:30 p.m., 102 Steele

Title: Dynamical and holonomic quantum computation with quantum optical systems
        T. Calarco, L.-M. Duan, D. Jaksch, A. Recati, I. Cirac and P. Zoller

Abstract:
We present and compare several schemes, among those recently developed by our group, for the scalable implementation of quantum computation by using atomic systems (either neutral or charged, i.e. ions) in microscopic potentials (optical lattices, magnetic and
electromagnetic microtraps). First, we review schemes based on conditional dynamical phase shifts, obtained by means of different kinds of interactions (cold collisions, dipole-dipole interactions, electrostatic forces) either with single atoms/ions or with atomic
ensembles. Then we discuss more recent proposals exploiting non-Abelian phases
generated by quantum holonomies, either with trapped ions or neutral atoms.

Host: Hideo Mabuchi

November 1: Preskill group meeting
     Lawrence Ip, Berkeley
     5:30 p.m., 156 Jorgensen

Title: Finding unknown shifts and hidden cosets: or how to fix a quantum hubble space         telescope

Abstract:
We present a class of shift problems with efficient quantum algorithms. This class of problems includes the Shifted Legendre Symbol Problem considered by van Dam and Hallgren. We show that shift problems, just like hidden subgroup problems, have direct links to well studied problems in signal processing.

Host: Leonard Schulman

November 7: IQI Seminar
     Ronald de Wolf, UC Berkeley
     3:00 p.m., 102 Steele

Title: Quantum communication complexity: some recent results

Abstract:
In the setting of communication complexity, Alice receives an input x, Bob receives an input y, and together they want to compute some function f(x,y), while minimizing the amount of communication between them. In recent years, it has been found that quantum communication is much more efficient than classical communication for various functions. In this talk we will discuss three quantum communication complexity results that were obtained the past year:
(1) quantum fingerprinting, which gives rise to an exponential quantum-classical improvement in a constrained communication model;
(2) a precise algebraic characterization of a "non-deterministic" variant of quantum communication complexity;
(3) slightly improved bounds for the bounded-error quantum communication complexity of the disjointness problem (whose complexity is one of the main open problems in qcc).

This talk is based on 2 papers:
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, "Quantum Fingerprinting", Physical Review Letters, 87(16), September 2001, quant-ph/0102001
P. Hoyer and R. de Wolf, "Improved Quantum Communication Complexity Bounds for Disjointness and Equality", quant-ph/0109068

Host: John Preskill

November 13: IQI Seminar
     Wim van Dam, UC Berkeley
     3:00 p.m., 74 Jorgensen **NOTE NEW LOCATION**

Title: Playing games against theories: the statistical strength of arguments against locality

Abstract:
I will analyze the strength of a nonlocality argument in the setting of a game between an experimental physicist and an inventive believer in local theories. The experimentalist tries to collect evidence that the Bell inequality is indeed violated by Nature, whereas the local theorist tries to come up with local explanations of the observed phenomena. In a sense, this game can never be won completely by either party because there is always a local theory in combination with the argument that we just witnessed an unlikely, yet possible, series of outcomes. Clearly, the more experiments we do the more improbable such explanations become. It will be this 'increase of unlikeliness per experiment' that I will consider the strength of the nonlocality argument. To quantify this, I will look at the Kullback-Leibler distance between the probabilities that the theory of quantum mechanics
predicts and the set of probability distributions stemming from the set of local theories. The local theory that comes closest to quantum mechanics is the strongest argument in favour of locality, whereas the experimental physicist tries to widen this gap. We thus reach a setting very familiar in the theory of zero-sum games where one party tries to minimize the quantity that the other party attempts to minimize. For a given nonlocality inequality, the 'strategy' of the physicist is determined by the probability distribution over the measurement settings that are involved. The optimal strategy is thus the one that establishes the largest possible Kullback-Leibler distance, which in turn defines the value
of the nonlocality argument. Using this analysis I will consider a number of Bell inequalities and will present a tentative ranking of them.

Host: John Preskill

November 21: Mathematical Physics Seminar
     Mary Beth Ruskai, University of Massachusetts Lowell
     12:00 - 1:00 p.m., 351 Sloan (Lounge)

Title: Capacity of noisy quantum channels

Abstract:
Quantum particles can be used to transmit classical information, typically encoding messages as strings of 0 and 1 represented by a pair of input states from a two level quantum system or "qubit". As with classical communication, channels may have noise, and the capacity is a measure of the maximum information per bit that can be transmitted. The Holevo capacity measures the information per bit that can be transmitted through a memoryless channel when product inputs are used, but entangled measurements are permitted to determine the output. It is known that this can be strictly greater than the capacity restricted to product measurements and that, in such cases, the optimal input states are generally not orthogonal. It is somewhat surprising that that there are situations for which the optimal inputs are not a pair of states, but a triplet of non-orthogonal states.
This does NOT mean that a single photon or spin 1/2 particle can be used to send information distinguishing between 3 possible inputs, but that more information can be transmitted using long strings when the product inputs are chosen from among three states.

This talk will begin with a gentle introduction to the different types of channel capacity possible in quantum situations and the mathematical model for noise. It will emphasize a view in which states are represented by points on the Bloch sphere, and the noise
shrinks the sphere to an ellipsoid. This picture can be useful for understanding how the two competing quantities contributing to the capacity can be optimized, and can explain our construction of channels for which three inputs are needed. It also shows the fundamental difference between unital channels, which are essentially classical and non-unital channels which show a rich variety of quantum effects.

If time permits, recent progress on some open questions regarding the additivity of product channels will be discussed, along with related question on the additivity of maximal l_p norms.

Host: Barry Simon

November 27: IQI Seminar
     Andris Ambainis, Berkeley
     3:00 p.m., 74 Jorgensen

Title: Generating quantum states and quantum communication complexity

Abstract:
Consider the following two communication problems. The first is to generate (or approximate) a bipartite quantum state. The second is computing a classical function (or sampling from a classical probability distribution) using quantum communication. In both cases, we try to minimize the amount of communication needed.

We will discuss the communication complexity of the first problem and then show two implications of it for the second problem. The first is an example where quantum protocols can solve a certain problem (sampling disjoint subsets) with exponentially less communication than classical protocols. The second is proving lower bounds on quantum communication complexity of computing a function by proving lower bounds on the amount of communication needed to approximate a bipartite quantum state. In particular, this gives a simple proof of recent lower bounds on quantum communication complexity by Klauck (FOCS'01).

The first result appeared in A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson. Quantum communication complexity of sampling. FOCS'98. The second result is new.

November 29: IQI Seminar
     Scott Aaronson, Berkeley
     2:00 p.m., 100 Powell-Booth

Title: Quantum lower bound for the collision problem

Abstract:
The collision problem is to decide whether a function X:{1,..,n}-> {1,..,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Theta(n^{1/5}) on the number of queries needed by a quantum computer to solve this problem with bounded error probability. The best known upper bound is O(n^{1/3}), but obtaining any lower bound better than Theta(1) was an open problem since 1997. Our proof uses the polynomial method augmented by some new ideas. We also give a lower bound of Theta(n^{1/7}) for the problem of deciding whether two sets are equal or disjoint on a constant fraction of elements. Finally we give implications of these results for quantum
complexity theory.

December 18 : IQI Seminar
     Andrei Soklakov, University of London
     3:00 p.m., 74 Jorgensen

Title: Variational principles of physics from the point of view of inductive inference

Abstract:
This talk is an overview of a recent proposal to establish a formal connection between the fundamental principles of physics and those of inductive inference. Given a physical system, we construct a hypothesis space as a collection of all possible laws that define system dynamics. Using the methods of algorithmic information theory we introduce the notion of complexity of a dynamical law. We show that the celebrated principle of least action can be viewed as a consequence of Occam's Razor principle. We speculate how the laws of quantum dynamics may arise in the context of Solomonoff's induction theory. We suggest that both physics and compute science may benefit from the proposed approach. The technical part of the talk is directly relevant to the general theory of induction by Occam's razor.

January 15: IQI Seminar
     Andrew Doherty, Caltech 
     3:00 p.m., 74 Jorgensen

Title: Distinguishing separable and entangled states

Abstract:
Although it is straightforward to define a separable quantum state as a mixture of product states, it is not known in general how to decide whether any given mixed state is in fact separable. I will discuss some new families of operational criteria that distinguish entangled from separable quantum states. The simplest of these tests is the well-known Peres-Horodecki or positive partial transpose criterion and the more complicated tests are strictly stronger. The new criteria are tractable due to powerful computational and theoretical methods for a class of convex optmization problems, termed semidefinite programs, that have found broad applicability in fields such as control theory. I will discuss theoretical background and perspectives on semidefinite programs that might have wider application in quantum information theory.

Host: John Preskill

January 22 : IQI Seminar
     Antonio Acin, University of Geneva   
     3:00 p.m., 74 Jorgensen

Title: Distillability and Bell inequalities in N qubit systems

Abstract:
We analyze the relation between distillability and Bell inequality violation. We consider quantum systems composed of N qubits, and the family of all Bell correlation inequalities for N qubits with two local measurements per site. If a N-qubit state violates any of these inequalities, then it is bipartite distillable.

Host: John Preskill

January 29 : IQI Seminar
     Andreas Winter, University of Bristol   
     3:00 p.m., 74 Jorgensen

Title: How much information is obtained by a quantum measurement?

Abstract:
We study the problem of separating the data produced by a given quantum
measurement, described by a positive operator valued measure (POVM) acting on a state ensemble, into a "meaningful'' (intrinsic) and a "not meaningful'' (extrinsic) part. After reviewing the existing results on this problem, we propose a new notion of this separation, which appears to be the strongest possible, and which encompasses the previous notions: it is an asymptotic version of the convex decomposition of a POVM into extremal ones. The central results are: a data separation theorem, achieving the same rate of intrinsic data as the compression result of this paper's precursor [A. Winter and S. Massar, Phys. Rev. A, vol. 64, 012311, 2001], which is the Holevo mutual information of a particular ensemble associated to the measurement and the source average state, and the optimality of this result in the form of a strong converse. We apply this result to a similar decomposition of quantum instruments and quantum operations, in their Kraus form. This is used to give a refined notion of the entropy exchange of a quantum map. Other applications include a rederivation of the Holevo information bound and a first version of the Quantum Reverse Shannon Theorem.

Host: John Preskill

Title: Anyons for quantum computation

Abstract:
Anyons are special particles that occur in certain two-dimensional systems (e.g. in fractional quantum Hall systems). They feature unusual statistics and quantum numbers. I will describe a simple model with Abelian anyons, a mathematical version of which is known as the toric code. The existence of anyons is related to the ground state degeneracy on the torus. In general, this degeneracy is not exact, but the energy level splitting is
exponentially small in the system size.

With less trivial non-Abelian anyons, a degenerate state occurs when several particles are positioned on the plane far apart from each other. This provides an exciting possiblility of decoherence-protected quantum memory. Read-out is performed by fusing two particles and detecting whether they annihilate or not. (One can even compute with certain types of anyons by simply moving them around. Such computation is fault-tolerant due to its topological nature).

Host: John Preskill

To warm up, you can try thinking of the following mind boggling problem:
Consider a party at Caltech in which miraculously there happened to be exactly the same number of men and women. How can we generate a uniform superposition over all possible matchings of men with women for the swing couple dances that are being planned?

Host: Leonard Schulman

March 12: IQI Seminar
     Barbara Kraus, University of Queensland   
     3:00 p.m., 74 Jorgensen

Title: Separable, distillable and activatable states

Abstract:
We introduce a formalism that connections entanglement witnesses and the distillation and activation properties of a state. We apply this formalism to two cases: First, we rederive the results presented in {\bf quant-ph/0104095} \cite{Eg01} by Eggeling et al., namely that one copy of any bipartite state with non--positive partial transpose (NPPT) is either distillable, or activable. Second, we show that there exist three--partite NPPT states, with
the property that two copies can neither be distilled, nor activated.

Host: John Preskill

Joint work with Richard Jozsa and Andreas Winter.

[1] B. Demoen, P. VAnheuverzwijn, and Verbeure, Lett. Math. Phys. 2, 161 (1977).
[2] G. Giedke and J.I. Cirac, submitted to Phys. Rev. A, quant-ph/0204085.

Large photon-number path entanglement is an important resource for Heisenberg-limited measurement protocols. We present a general constructive protocol to create any large photon number path-entangled state based on the conditional detection of single photons. The influence of imperfect detectors is considered and an asymptotic scaling law is derived.

Another important application of projective measurements in linear optics is the interferometer that signals the presence of a single photon in a particular input state (c_0|0> + c_1|1> + c_2|2>) without destroying it. This quantum nondemolition device can be used to create practical, efficient, quantum repeaters,
employing double-photon guns, for long-distance optical quantum communication. The guns create polarization-entangled photon pairs on demand. One such source might be a semiconducter quantum dot, which has the distinct advantage over parametric down-conversion that the probability of creating a photon pair is close to one, while the
probability of creating multiple pairs vanishes. The swapping and purifying components are implemented by polarizing beam splitters and probabilistic optical CNOT gates.

Host: John Preskill

In this paper we will introduce the basic ideas of quantum walks and mixing times, and will present recent results on the n-dimensional hypercube. We show that this walk is very close to uniform after (pi/4) n steps, even though this is less than the diameter of the graph. We will discuss possible quantum algorithms for the Knapsack problem, and open
problems on other spaces as well.

Host: John Preskill

We present a principle that gives a definite distinction between the operations that preserve the states of the system and those that disturb the states. The principle is derived by alternately applying a fundamental property of classical signals and a fundamental property of quantum ones. The principle can be cast into a simple form by using a decomposition of the relevant Hilbert space, which is uniquely determined by the set of possible states. The decomposition implies the classification of the degrees of freedom of the system into three parts depending on how they store the information on the initially chosen state: one storing it classically, one storing it nonclassically, and the other one storing no information. Then the principle states that the nonclassical part is inaccessible and the classical part is read-only if we are to preserve the state of the system.

The principle can also be applied to problems of data compression and teleportation, in which the input state is almost faithfully reproduced in the output. For a rather general source including mixed states, the blind optimal compression rates for various scenarios
and the required amount of entanglement in the teleportation can be easily derived from the above decomposition.

Host: John Preskill

Host: John Preskill

There is an analogous question for the product of two unitary matrices, which contains the Hermitian question as one "corner''. We will state a conjectural puzzle answer to this too, so far exhaustively checked up to 12x12 matrices.

This work is joint with Terry Tao of UCLA.

September 27: IQI Special Seminar      *Friday*
     Jose Latorre, University of Barcelona
     2:00 p.m., location TBD

Title: Majorization and quantum algorithms

Abstract:
Majorization theory establishes a far more refined relation of order between probability distributions than the concept of entropy. The solutions to quite a number of problems in quantum information have been proven to rely on majorization relations. We shall show that the known efficient quantum algorithms do carry a step-by-step majorization in their computational basis.

October 22: IQI Seminar
     Yasser Omar, University of Oxford
     3:00 p.m., 74 Jorgensen

Title: Entanglement transfer and entanglement concentration using particle statistics

Abstract:
Using two pairs of entangled particles we show that particle indistinguishability can enforce a transfer of entanglement from the internal to the spatial degrees of freedom without any
interaction between these degrees of freedom. Moreover, sub-ensembles selected by local measurements of the path will in general have different amounts of entanglement in the internal degrees of freedom depending on the statistics (either fermionic or bosonic) of the particles involved.

We also propose an entanglement concentration scheme which uses only the effects of quantum statistics of indistinguishable particles. This establishes the fact that useful quantum information processing can be accomplished by particle statistics alone.

Host: John Preskill

October 29: IQI Seminar
     Andrew Childs, MIT
     3:00 p.m., 74 Jorgensen

Title: Exponential algorithmic speedup by quantum walk

Abstract:
We construct an oracular problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our oracular setting. We then show how this quantum walk can be used to solve our