A k-copy expander consisting of D unitaries cannot be closer than \Omega(D^{-1/2}) to the ideal superoperator in the spectral norm on linear operators, in what is known as the Ramanujan bound. No explicit construction of even 1-copy quantum expanders was known earlier, that was provably close to the Ramanujan bound. In this work, we give an explicit construction of k-copy quantum expanders that have distance c_k D^{-1/2 + o(1)} to the ideal superoperator, where c_k is a constant depending on k. This leads to better constructions of approximate k-designs of unitaries. Our construction is a quantum analogue of a construction of classical 1-copy expanders by Ben-Aroya and Ta-Shma, which in turn was a generalisation of a combinatorial construction called zig-zag graph product by Reingold, Vadhan and Wigderson.

Seminar co-sponsored by the MITACS Quantum Information Processing program.

A k-copy expander consisting of D unitaries cannot be closer than \Omega(D^{-1/2}) to the ideal superoperator in the spectral norm on linear operators, in what is known as the Ramanujan bound. No explicit construction of even 1-copy quantum expanders was known earlier, that was provably close to the Ramanujan bound. In this work, we give an explicit construction of k-copy quantum expanders that have distance c_k D^{-1/2 + o(1)} to the ideal superoperator, where c_k is a constant depending on k. This leads to better constructions of approximate k-designs of unitaries. Our construction is a quantum analogue of a construction of classical 1-copy expanders by Ben-Aroya and Ta-Shma, which in turn was a generalisation of a combinatorial construction called zig-zag graph product by Reingold, Vadhan and Wigderson.

Peter Marbach was born in Lucerne, Switzerland. He received the Eidg. Dipl. El.-Ing. (1993) from the ETH Zurich, Switzerland, the M.S. (1994) in electrical engineering from the Columbia University, NY, U.S.A, and the Ph.D. (1998) in electrical engineering from the Massachusetts Institute of Technology (MIT), Cambridge, Massachusetts, U.S.A. He was appointed as assistant professor in 2000, and associate professor in 2005, at the Department of Computer Science of the University of Toronto. He has also been a visiting professor at Microsoft Research, Cambridge, UK, at the Ecole Polytechnique Federal at Lausanne (EPFL), Switzerland, and at the Ecole Normale Superieure, Paris, France, and a post-doctoral fellow at Cambridge University, UK. Peter Marbach has received the IEEE INFOCOM 2002 Best Paper Award for his paper "Priority Service and Max-Min Fairness". He is on the editorial board of the ACM/IEEE Transactions of Networking. His research interests are in the fields of communication networks, in particular in the area of wireless networks, peer-to-peer networks, and online social networks.

Seminar sponsored by the MITACS Quantum Information Processing program.

A classical problem in combinatorial optimization is that of maximum multiflows. We are given an undirected graph G=(V,E), and a set of terminals A subset of V. A multiflow is defined as a set of |A|(|A|-1)/ 2 flows between all pairs of distinct terminals. The goal is to maximize the total size of the multiflow, that is the sum of the size of all the |A|(|A|-1)/2 flows, subject to certain capacity constraints. Variations of the problem arise from edge- or node- capacities, and/or adding a (half-)integrality constraint. The problem is really interesting even for the special case of all-one node capacities, which is characterized by Mader's min-max formula, and solved by Lovász' linear matroid matching algorithm. Mader's formula also applies for arbitrary capacities, but matroid matching, in the obvious way of expanding the graph, only implies an exponential time algorithm.

The main result presented in this talk is a strongly polynomial time algorithm to find a maximum integral multiflow subject to node- capacities (the most general of all these variations). This improves on a result of Ibaraki, Karzanov and Nagamochi for the edge- capacitated, half-integral version, and on Keijsper, Pendavingh and Stougie's weakly polynomial time algorithm for the edge-capacitated, integral version. These results are generalized to the node- capacitated version, although using completely different tehniques. The half-integral node-capacitated multiflow problem is solved based on a recent result saying that the polytope of shortest maximum multiflows is half-integral, which implies a strongly polynomial algorithm via ellipsoid method and Frank and Tardos' diophantine approximation. To solve the integral node-capacitated multiflow problem, we first solve it to half-integrality, and then use a scaling- type argument motivated by Gerards' proximity lemma for b-matching to reduce the problem to small capacities. In the presentation we will also take a look at related results and techniques, such as a splitting-off algorithm for Lov\'asz' and Cherkassky's result, a divide-and-conquer-type argument for the edge-capacitated version.

Patrick was a B.Sc. and M.Sc. student at McGill. He then did his Ph.D. at MIT with Martin Rinard and then a post-doc back at McGill. He is currently an Assistant Prof at Waterloo.

The counterfeit coin problem is a well-known puzzle whose origin dates back to 1945; in the American Mathematical Monthly, 52, p.~46, E. Schell posed the following question which is probably one of the oldest questions about the complexity of algorithms: ``You have eight similar coins and a beam balance. At most one coin is counterfeit and hence underweight. How can you detect whether there is an underweight coin, and if so, which one, using the balance only twice?'' The puzzle immediately fascinated many people and since then there have been several different versions and extensions in the literature.

In this talk, we study the quantum query complexity for this problem. We assume that the balance scale gives us only ``balanced'' or ``tilted'' information and that we know the number $k$ of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). Let $Q(k,N)$ be the quantum query complexity of finding all $k$ false coins from the $N$ given coins. We show that for any $k$ and $N$ such that $k < N/2$, $Q(k,N)=O(k^{1/4})$, contrasting with the classical query complexity, $\Omega(k\log(N/k))$, that depends on $N$. Some bounds for small $k$ are also investigated: (i) $Q(1,N)=1$, (ii) $Q(2,N)=1$, and (iii) $2\leq Q(3,N) \leq 3$.

Professor Iwama received the B.E., M.E. and Ph.D. degrees from Department of Electrical Engineering, Kyoto University in 1973, 1975 and 1980, respectively. His reseach interets are mainly algorithms and complexity theory.