## WQACT2008 Titles and Abstracts

**Session: Monday-0945hr**

Speaker: Ambainis Andris

Title: Quantum and classical query complexities are polynomially related for all symmetric functions

Abstract:

However, there are many partial problems for which quantum speedups are at most polynomial, for example, the collision problem in which we have to distinguish whether the input is a 1-1 or a 2-1 function. The key property that distinguishes Simon's problem from the collision problem is that collision problem is symmetric (permuting the input elements does not affect the function's value) while Simon's problem is not symmetric.

In this talk, we will show that this holds in general: for any (partial or total) symmetric function f(x_1, ..., x_N) of inputs x_1, ...,x_N with values in an arbitrary finite set, the quantum query complexity is at most polynomially better than the classical complexity.

**Session: Monday-1030hr**

Speaker: Kazuo Iwama

Title: Quantum Counterfeit Coin Problems

Abstract:

This is a joint work with Harumichi Nishimura and Raymond Rudy.

**Session: Monday-1145hr**

Speaker: Lee Troy

Title: Quantum ordered search: is (1/pi) ln(n) the right answer?

Abstract:

We show that the best lower bounds achievable by quantum adversary method, even the more recent variant using negative weights, is (1/pi) ln(n) + O(1).

Joint work with Andrew Childs.

**Session: Monday-1630hr**

Speaker: Reichardt Ben

Title: Quantum algorithm for evaluating span programs

Abstract:

The main new tool is a correspondence between span programs and weighted bipartite graphs. A span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. A quantum computer can therefore evaluate the span program by applying spectral estimation to the graph.

Joint work with Robert Špalek

**Session: Monday-1715hr**

Speaker: Spalek Robert

Title: Designing efficient span programs

Abstract:

In this talk, we show how to design span programs with optimal witness length. We present several functions and show how to exploit the structure of their automorphism group to obtain very symmetric span programs, which turn out to be optimal. We then speculate about a general framework based on the representations of the automorphism group, which we would like to develop.

Joint work with Ben Reichardt.

**Session: Tuesday-0945hr**

Speaker: Ivanyos Gabor

Title: Hidden subgroups in certain solvable groups

Abstract:

**Session: Tuesday-1030hr**

Speaker: Shparlinski, Igor

Title: Quantum Noisy Rational Function Reconstruction

Abstract:

Some open problems will be discussed as well. Joint work with: Sean Hallgren, Alexander Russell and Arne Winterhof

**Session: Tuesday-1145hr**

Speaker: Hoyer Peter

Title: Computing time ordered operator exponentials efficiently and accurately

Abstract:

To be updated

**Session: Wednesday-0945hr**

Speaker: Massar Serge

Title: Secret keys and random numbers based on quantum non locality

Abstract:

**Session: Wednesday-1030hr**

Speaker: Sen Pranab

Title: Making classical zero knowledge proofs secure against quantum verifiers

Abstract:

Zero knowledge about zero knowledge is required for this talk.

This is joint work with Sean Hallgren, Alexandra Kolla and Shengyu Zhang.

**Session: Wednesday-1145hr**

Speaker: Wehner Stephanie

Title: Robust Cryptography in the Noisy-Quantum-Storage Model

Abstract:

Joint work with Christian Schaffner and Barbara Terhal.

**Session: Wednesday-1630hr**

Speaker: Raymond Rudy

Title: Average/Worst-case Gaps of Quantum Query Complexities

Abstract:

In this talk, we show a super-linear tight gap between the average- and worst-case quantum query complexities over the families of Boolean functions defined by a natural parameter. More concretely, we consider the size of the "on-set" of a Boolean function f, i.e., the number of inputs for which f = 1, as the parameter, and give tight gaps over the families of N-variable Boolean functions whose on-set size is M for poly(N) <= M <= 2^{N-1}.

A direct application of our upper bound enables us to bound the number of queries for graph property testing by simply counting the number of graphs with a given property. Surprisingly, this already gives several new and interesting results. For example, we can show O(N^{3/4}) number of queries is sufficient (and essentially necessary) to decide if a given graph G is isomorphic to an arbitrary fixed graph G'. Moreover, we also prove that the same number of queries is also necessary and sufficient to test planarity, one of the most fundamental graph properties. We also prove that the lower bound of the classical query complexity is Omega(N), thus adding a new nontrivial property into the class of graph properties for which there is a significant gap between the quantum and classical query complexities.

This is a joint work with Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Seiichiro Tani and Shigeru Yamashita.

**Session: Wednesday-1715hr**

Speaker: Zhang Shengyu

Title: Lower bounds of quantum communication complexity

Abstract:

In the proofs of these results, the dual polynomial seems to be tailored (by God) for the discrepancy method to work. To understand this better, we consider functions passing through a group, i.e. f(g(x,y)) where g maps the input set to a group G. This encompasses all previously studied functions. We hope to identify what properties of g enable us to use the discrepancy method. Some preliminary results along this line will be reported in this talk.

**Session: Thursday-0945hr**

Speaker: Buhrman Harry

Title: A generalized Grothendieck inequality and entanglement in XOR games

Abstract:

Joint work with Jop Briet and Ben Toner

**Session: Thursday-1030hr**

Speaker: de Wolf Ronald

Title: Quantum computing as a proof tool

Abstract:

**Session: Thursday-1145hr**

Speaker: Toner Ben

Title: Unique Games with Entangled Provers are Easy

Abstract:

Joint work with Julia Kempe and Oded Regev.

**Session: Thursday-1630hr**

Speaker: Magniez Frederic

Title: On the hitting times of quantum versus random walks

Abstract:

Further, we prove a quadratic gap between the hitting times of any reversible ergodic Markov chain and its quantum analogue. We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk.

Finally, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of Tulsi from his recent theorem for the 2D grid.

Joint work with: Ashwin Nayak, Peter C. Richter, Miklos Santha

**Session: Friday-0945hr**

Speaker: Keiji Matsumoto

Title: Prohibiting correlations between provers

Abstract:

**Session: Friday-1030hr**

Speaker: Laplante Sophie

Title: Communication complexity of simulating quantum distributions (and beyond)

Abstract:

Finally, we give upper bounds for the simultaneous messages model in terms of our measures.

Joint work with J. Degorre, M. Kaplan, and Jeremie Roland.

**Session: Friday-1145hr**

Speaker: Kerenidis Iordanis

Title: Non-Local Box Complexity

Abstract:

We study how many non-local boxes are needed to compute a function f(x,y), where much in the way of communication complexity, Alice gets x and Bob gets y, and at the end of the protocol, Alice
outputs a bit a and Bob outputs b such that f(x,y)=a?b. We de?ne four different variants denoted by NL, NLe , NL|| , NL||e , where the ?rst two are the deterministic and randomized non-local
box complexity and the latter two are where the non-local boxes are only used in parallel.

For the deterministic parallel non-local box complexity, we show that NL||(f) is exactly equal to the rank of the function f over Z2 . This also shows that it is equivalent to the communication
complexity of the function in the following model: Alice and Bob send to a referee one message each and the referee outputs the Inner Product of the two vectors mod 2. Moreover we show that NL||(f)
is always greater than the deterministic communication complexity D(f) and less than 2^D(f) .

In the randomized case, we de?ne a notion of approximate rank over Z2 which is equal to NL||e(f), under the assumption that the output of the protocol is the XOR of the outcomes of the non-local
boxes. The notion of approximate rank over R is a strong upper bound on communication complexity. For the deterministic non-local box complexity NL(f), we show that it is at least the communication
complexity D(f) and smaller than NL||(f), which is again a tight bound. In the randomized case, we prove that it is bounded above by the communication complexity R||,MAJ(f) in the following model:
Alice and Bob send to a referee one message each and the referee outputs 1 if for the majority of indices, the two messages are equal. This is a natural model of communication complexity that has
appeared repeatedly in the simulation of quantum protocols by classical ones, as well as various upper bounds on simultaneous messages. This model is also bounded above in terms of ?28,a quantity
which has been used for upper and lower bounds on communication complexity.

Last, using the recent result of Regev and Toner, we show that traceless two-outcome measurements on maximally entangled states can be simulated with 3 non-local boxes. Previously, no ?nite bound
was known for this case.