CQT: Workshop on Quantum Algorithms and Complexity Theory 2008

WQACT2008 Titles and Abstracts

Session: Monday-0945hr

Speaker: Ambainis Andris

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

Abstract:

In the quantum query model, exponential speedups are achievable for some problems (e.g., Simon's problem) but not others (Grover's search). Usually, this is explained via Beals et al. (FOCS'98) result that says that the quantum and the classical query complexities are polynomially related.

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:

In the counterfeit coin problem, we are given n coins and also the (usually small) number k of counterfeit coins in them whose weights are different from that of good coins. We are required to identify all the counterfeit coins using balance scales in the minimum number of weightings. In this talk, we discuss the quantum version of this problem, i.e., it is allowed to use a "quantum balance," which can be modeled as a certain type of oracles. The performance measure is then the query complexity, which is one of the most standard and popular topics in our field. Several upper and lower bounds are given. For example, only one weighing is enough for k=1 and k=2, but a bit interestingly, this single-weighing algorithm no longer exists for k=3.

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:

The ordered search problem is to find the location of an item x in an ordered list x_1 < ... < x_n of n items by making queries of the form, is x >= x_i? Classically this can be done with log n queries using binary search. We know that quantum algorithms can do better, but the exact complexity of this problem has not been pinned down: currently the best upper bound, due to Childs, Landahl, and Parillo, is about 0.433 log n, whereas the best lower bound, due to Hoyer, Neerbeck, and Shi, is (1/pi) ln(n) or about 0.221 log n. This latter result is shown via the quantum adversary method, one of the most powerful tools available for showing lower bounds.

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:

We give a quantum algorithm for evaluating span programs over the complex numbers. In particular, by exhibiting and composing span programs for individual gates, the algorithm can be applied to evaluate formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3- majority). The algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense. For example, it is optimal for evaluating the balanced ternary majority formula.

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:

A span program is a linear algebraic object that can be tied to an evaluation of a Boolean function. In an earlier talk, Ben Reichardt has shown how to transform a span program to a bounded-error quantum algorithm evaluating the same function, or, more generally, any formula using this function as a gate. The running time of this algorithm is related to a property of the span program, which we coin the witness length.

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:

We expose the main ideas of a recursive quantum algorithm of Friedl, Magniez, Santha, Sen and the speaker for finding hidden subgroups of certain solvable groups and discuss some open questions related to possible extensions of the result.

Session: Tuesday-1030hr

Speaker: Shparlinski, Igor

Title: Quantum Noisy Rational Function Reconstruction

Abstract:

A survey will be given of classical and quantum algorithm of recovering a rational function f(X) over a finite field from a sequence of ``corrupted values'' f(x_i), i =1, ..., N.

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:

We discuss how non local correlations shared by two parties can be used to generate a secret key. We also discuss how non local correlations can be used to generate random numbers. Using non locality allows a higher degree of security than in the more traditional approaches, indeed it is no longer necessary to trust one's devices, nor even to trust quantum mechanics.

Session: Wednesday-1030hr

Speaker: Sen Pranab

Title: Making classical zero knowledge proofs secure against quantum verifiers

Abstract:

A zero knowledge proof is an interactive protocol by which a prover can convince a verifier about the truth of a statement without revealing any additional information about it. A classical zero knowledge proof may fail to be zero knowledge if the verifier cheats by doing quantum computation internally. Some time ago, Watrous showed that two specific classical zero knowledge proofs for graph isomorphism and graph 3-colouring continue to be secure against quantumly cheating verifiers. In this talk, we shall see how any classical zero knowledge proof satisfying a mild condition can be converted into another classical proof zero knowledge against all cheating verifiers, classical or quantum.

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:

Previously, we demonstrated that cryptographic primitives can be implemented based on the assumption that quantum storage of qubits is noisy [Phys.Rev.Lett. 100, 220502 (2008)]. In this work, we analyze a protocol for theuniversal task of oblivious transfer that can be implemented using quantum-key-distribution (QKD) hardware in the practical setting where honest participants are unable to perform noise-free operations. We derive greatly improved trade-offs between the amount of storage noise, the amount of noise in the operations performed by the honest participants and the security of oblivious transfer with individual-storage attacks. As an example, we show that for the case of depolarizing noise in storage we can obtain secure oblivious transfer as long as the quantum bit-error rate of the channel does not exceed 11% and the noise on the channel is strictly less than the quantum storage noise. This is optimal for the protocol considered. Finally, we show that our analysis easily carries over to quantum protocols for secure identification.

Joint work with Christian Schaffner and Barbara Terhal.

Session: Wednesday-1630hr

Speaker: Raymond Rudy

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

Abstract:

The difference between average-case and worst-case complexities is one of the central topics in theoretical computer science that has been studied for decades. Nevertheless, in the quantum setting only a few results are known. Some of them are, e.g., (i) for a MAJORITY function, there is an almost quadratic gap between theaverage- and worst-case query complexities over all inputs of the function, and (ii) however, if we consider the average- and worst-case behaviors of complexities over all Boolean functions (for the worst input of each function), only a linear gap is possible.

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:

A recently active line of research in quantum communication complexity is to prove lower bounds by the (generalized) discrepancy method, with the dual matrix constructed by a dual polynomial. Examples include Sherstov's pattern matrix and extensions to the multiparty case, and Shi and Zhu's block composition functions. Sherstov's result is used to reprove Razborov's celebrated lower bound result for functions S(|x AND y|).

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:

Suppose Alice and Bob make local two-outcome measurements on a shared entangled state. For any d, we show that there are correlations that can only be reproduced if the local dimension is at least d. This resolves a conjecture of Brunner et al. and establishes that the amount of entanglement required to maximally violate a Bell inequality must depend on the number of measurement settings, not just the number of measurement outcomes. We prove this result by establishing the first lower bounds on a new generalization of Grothendieck's constant.

Joint work with Jop Briet and Ben Toner

Session: Thursday-1030hr

Speaker: de Wolf Ronald

Title: Quantum computing as a proof tool

Abstract:

Quantum computing provides us with new algorithms and cryptography, but the techniques developed in this field can also be used as tools for proving results about *classical* algorithms and mathematical constructions. This is analogous to the use of complex numbers to prove statements about real functions, or the use of the probabilistic method. In this talk I will survey some examples of such "quantum proofs for classical theorems", focusing on some recent developments where quantum algorithms are used to construct low-degree polynomials with various desired properties.

Session: Thursday-1145hr

Speaker: Toner Ben

Title: Unique Games with Entangled Provers are Easy

Abstract:

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers. Using our approximation by a semidefinite program we also show a parallel repetition theorem for unique entangled games.

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:

In this talk we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions.

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:

Recently, research of quantum interactive proof system attracts more and more attention. Different from classical provers, quantum provers are correlated in quite couter-intuitive manner. Here I'd like to present how to prohibit various kind of correlations between provers. As a result, I will show that IP can be accepted by a one-round multi-prover 2-provers interactive proof system.

Session: Friday-1030hr

Speaker: Laplante Sophie

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

Abstract:

We study the question of how much communication is required to simulate quantum distributions, and more generally, any bipartite conditional distribution that respects causality. This includes distributions arising from quantum measurements on bipartite quantum states, but also encompasses the standard model of classical and quantum communication complexity of (partial) functions and relations. Most previous work on simulating quantum distributions has focused on proving upper bounds on communication. We provide lower bound techniques for the classical and quantum communication complexity of simulating non-signaling distributions. One formulation of our lower bounds is in terms of Bell and Tsirelson inequalities. We show that our technique is an extension of the recent factorization norm method of Linial and Shraibman, for the standard communication complexity model.

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.

Connect with us:

Name:
Email: