A subexponential-time quantum algorithm for the dihedral hidden subgroup problem

Debbie Leung:

Applications of the quantum composability theorem

Frederic Magniez:

Quantum Algorithms for the Triangle Problem
We present two new quantum algorithms that either finds a triangle in an undirected graph G on n nodes, or rejects if G is triangle free.
The first algorithm uses combinatorial ideas with Grover Search and makes \tilde{O}(n^{10/7}) queries. The second algorithm uses O(n^{13/10}) queries, and it is based on a new design concept of Ambainis that incorporates the benefits of quantum walks into Grover search. The first algorithm uses only O(log n) qubits in its quantum subroutines, whereas the second one uses O(n) qubits.
Note: joint work with Miklos Santha and Mario Szegedy

Serge Massar:

Non locality
We describe the geometry of the space of non local correlations and we show how it is possible to interconvert between different types of non local correlations. This should form the basis for developping an information theory of non local correlations.

Ueli Maurer:

On the Power of Quantum Memory
A qubit can be used to implement a classical memory bit, but not vice versa. We address the question whether quantum memory can be more powerful than classical memory in a classical information context where some relevant information X (e.g. an n-bit string) must be stored in memory of insufficient size s (e.g. s We discuss an information-theoretic model of memory, which includes quantum memory, and show that in a quite general context, quantum memory is only marginally more powerful than classical memory. In particular, classical privacy amplification by universal hashing remains secure even against an adversary with (the same amount of) quantum rather than classical memory. It remains a general open problem to prove certain classical information-theoretic cryptosystems, for instance schemes secure in the bounded-storage model, secure in presence of a quantum adversary.
This is joint work with Robert Koenig and Renato Renner.

Jaikumar Radhakrishnan:

The bounded-round quantum communication complexity of set disjointness
In the set disjointness problem, there are two parties A and B, each with a subset of {1,...,n}. They wish to communicate to determine if their sets are disjoint. For this problem quantum protocols do provably better than classical protocols. Recently, Aaronson and Ambainis showed a protocol for this problem where the two parties exchange O(sqrt{n}) qubits, matching the previous lower bound of Omega(sqrt{n}) shown by Razborov. (The classical randomized communication complexity of this problem is theta(n).)
We consider bounded-round quantum communication protocols for the set disjointness problem, and show that in any communication protocol with k rounds, the two parties must exchange Omega(n/k^2) qubits. This lower bound is obtained by adapting the the information theoretic proof technique of Bar-Yossef, Jayram, Kumar and Sivakumar to the quantum setting. An upper bound of O(n/k) follows easily from the O(sqrt{n}) upper bound due to Aaronson and Ambainis. For protocols with no restriction on the number of rounds, we can conclude that the two parties must exchange Omega(n^{1/3}) qubits. This, however, falls short of the optimal Omega(sqrt{n}) lower bound shown by Razborov.

Ran Raz:

Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size
I will talk about recent lower bounds for multi-linear arithmetic formulas. A surprising and beautiful application of these bounds in the field of quantum computation was recently found by Scott Aaronson [Scott Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing"], and will be discussed in his talk. In my talk, I plan to give a short introduction to the problem as well as the main ideas of the lower bounds proof. Some more details are given below:

Arithmetic formulas for computing the determinant and the permanent of a matrix have been studied since the 19th century. Are there polynomial size formulas for these functions? Although the determinant and the permanent are among the most extensively studied computational problems, polynomial size formulas for these functions are not known. An outstanding open problem in complexity theory is to prove that polynomial size formulas for these functions do not exist. Note, however, that super-polynomial lower bounds for the size of arithmetic formulas are not known for any explicit function and that questions of this type are considered to be among the most challenging open problems in theoretical computer science.

An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear, that is, in each of its monomials the power of every input variable is at most one. Multi-linear formulas are restricted, as they do not allow the intermediate use of higher powers of variables in order to finally compute a certain multi-linear function. Note, however, that for many multi-linear functions, formulas that are not multi-linear are very counter-intuitive. Note also that both the determinant and the permanent are multi-linear functions and that many of the well known formulas for these functions are multi-linear formulas.

We prove that any multi-linear arithmetic formula for the determinant or the permanent of an n dimensional matrix is of size super-polynomial in n. Previously, no lower bound was known (for any explicit function) even for the special case of multi-linear formulas of constant depth.

Oded Regev:

Recent connections between quantum computation and lattice problems
I will describe a result obtained together with Dorit Aharonov on lattice problems in quantum NP and a more recent result showing how to dequantize the construction in order to obtain containment in NP. Time permitting, I will also comment on the possibility of applying Kuperberg's algorithm to solve lattice problems in subexponential time.

Alex Russell:

Quantum Computation in Groups
This talk will survey some recent developments in the theory of quantum computation in groups, focusing on two primary research efforts: development of efficient quantum Fourier transforms and development of efficient solutions to hidden subgroup problems.

Quantum Fourier transforms. The talk will describe a "quantization" of the successful separation of variables technique, the generic framework responsible for most known efficient classical Fourier transform algorithms. This results in a wide family of efficient quantum circuits for the quantum Fourier transform, recovering all known efficient quantum Fourier transforms and providing efficient transforms for many new groups. In addition, it gives the first subexponential quantum circuits for the Fourier transform over several interesting linear groups.

Hidden subgroup problems. The talk will discuss some recent advances in our understand of the hidden subgroup problems, discussing new closure properties and solutions for families of groups which appear to require the strong standard method.

Leonard Schulman

Physical limits of heat-bath algorithmic cooling

Peter Shor:

Additivity questions in quantum information theory
There are a number of interesting, open additivity questions in quantum information theory. Recently, I have been able to show that some of these are equivalent. I will discuss open additivity questions in general and this proof of equivalence in particular.

Kiyoshi Tamaki:

Unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel
We prove the unconditional security of the Bennett 1992 quantum key distribution protocol over lossy and noisy channel. We assume that Alice has an ideal single photon source and Bob has detectors that discriminate between single photon states on one hand and vacuum state or multiphoton states on the other hand. We use a reduction to an entanglement distillation protocol initiated by a local filtering process in our proof. The bit errors and the phase errors are correlated after the filtering, and we can bound the amount of phase errors from the observed bit errors by an estimation method involving nonorthogonal measurements.

Leslie Valiant:

Holographic Algorithms

John Watrous:

Stronger Error Reduction for QMA
The complexity class QMA is a bounded-error quantum computational variant of the class NP, where a quantum state plays the role of a certificate. It is known that the error of a given QMA protocol can be reduced exponentially at the cost of a polynomial increase in the length of the certificate. In this talk, I will prove that such a reduction in error is in fact possible with no increase in the length of the certificate whatsoever. Applications of this fact include a proof that logarithmic-length quantum certificates give no increase in power over BQP and a simple proof that QMA is contained in the class PP.

Andreas Winter:

From entanglement to secret key and back
The last year has seen a series of dramatic progresses in the areas of quantum channel capacities, entanglement distillation and our understanding of how these problems relate to secret communication. In this talk I will first review the analogy between the theories of entanglement and key distillation. Then I go on to explain the elements of the recent progress, first describing Devetak's recent reduction of quantum state transmission to private communication and our subsequent joint work generalising this to entanglement/secret key distillation. These findings put into a new light the earlier observations (by Acin et al.and Bruss et al.) of qualitative equivalence between these two tasks, and also prepared the ground for the recent step forward by Horodecki et al., to formulate key distillation strictly within the LOCC paradigm and then to exhibit bound entangled states which nevertheless contain secret key.

Contributed Talks


Howard Barnum:

Query complexity & semidefinite programming
We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices.
Using the new formulation we do the following:

1. We show that as far as query complexity is concerned, the workspace of a quantum computer used to evaluate f(x) by querying the bits of an n-bit string x can be limited to n + k, where f takes k bit strings as values.
2. We give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm that attempts to evaluate f in t queries.
3. We use semidefinite programming duality to formulate a dual SDP Phat(f, t, e) that is feasible if and only if f cannot be avluated within error e by a t-step quantum query algorithm. Using this SDP we derive a general lower bound for query complexity that encompasses a lower bound method of Ambainis and its generalizations.
4. We give an interpretation of the primal SDP as a generalized form of branching in quantum computation.

1. A single unitary solution R to the Yang-Baxter equation.
2. Local unitary single qubit operations.