| |
|
| | |
|
![[photo of a speaker] (c) D.Nagaj](img/photos/speaker.jpg)
other seminars:
|
:: Mon 11/2, 4:00 in 36-428 (qip-sem) Daniel Nagaj (RCQI, IoP SAS, Bratislava) Given a verifier circuit for a problem in QMA, we show how to exponentially amplify the gap between its acceptance probabilities in the `yes' and `no' cases, with a method that is quadratically faster than the procedure given by Marriott and Watrous. Our construction is natively quantum, based on the analogy of a product of two reflections and a quantum walk. Second, in some special cases we show how to amplify the acceptance probability for good witnesses to 1, inquiring whether QMA with one-sided error (QMA_1) is equal to QMA and as a side result, show that QCMA_1 is equal to QCMA. Finally, we simplify the filter-state method to search for QMA witnesses by Poulin and Wocjan. [This is joint work with Pawel Wocjan, Yong Zhang and Stephen Jordan] :: Mon 11/9, 4:00 in 36-428 (qip-sem) Ben Reichardt (University of Waterloo) The general adversary bound is a lower bound on the number of input queries required for a quantum algorithm to evaluate a boolean function. We show that this lower bound is in fact tight, up to a logarithmic factor. The proof is based on span programs. It implies that span programs are an (almost) equivalent computational model to quantum query algorithms. One of the consequences is that almost-optimal quantum algorithms can always be designed based on span programs. This is worthwhile because span programs have useful properties, such as composing easily. We apply this to the formula-evaluation problem. For example, evaluating an AND-OR formula is similar to the question of whether white or black has a winning strategy in chess. We give an optimal quantum algorithm for evaluating almost-balanced formulas over any finite boolean gate set. For example, the formula's gate set may be taken to be all functions {0,1}^k --> {0,1} with k <= 1000. Another consequence is a simpler semi-definite program for quantum query complexity. Andy Lutomirski (M.I.T) Public-key quantum money is a cryptographic protocol in which a bank can create quantum states which anyone can verify but no one except possibly the bank can clone or forge. There are no secure public-key quantum money schemes in the literature; as we show in this paper, the only previously published scheme (Aaronson 2009) is insecure. We introduce a category of quantum money protocols which we call collision-free. For these protocols, even the bank cannot prepare multiple identical-looking pieces of quantum money. We present a blueprint for how such a protocol might work as well as a concrete example which we believe may be insecure. :: Mon 11/23, 4:00 in 36-428 (QIP seminar) Aram Harrow (University of Bristol) Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b, find a vector x such that Ax=b. We consider the case where one doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm. This talk is based on arXiv:0811.3171v3, which is joint work with Avinatan Hassidim and Seth Lloyd. |
| |
 |  |
