| |
|
| | |
|
![[photo of a speaker] (c) D.Nagaj](img/photos/speaker.jpg)
other seminars:
|
:: Mon 10/5/09, 4:00 in 36-428 (QIP seminar) Jacobs,Kurt (University of Massachusetts Boston) I will describe a method to obtain effective non-linearities in quantum resonators by coupling them perturbatively to low-dimensional systems (one or two qubits). The method involves determining sufficiently simple Hamiltonians for the qubits that will generate perturbation expansions with desired properties. A potentially wide range of nonlinearities can be obtained in this way, and results indicate that they are relatively robust against decoherence in the auxiliary system. :: Fri 10/9/09, 11:00 in 36-462 Barry Sanders (University of Calgary) :: Tue 10/13/09, 3:00 in 36-428 (qip-sem) Nayak,Ashwin (U. Waterloo and Perimeter) The two-party communication complexity model formalizes the study of costs involved in distributed computation. Here, two processors aim to jointly solve a task by communicating over a connecting link. In a realistic setting, this link may be subject to noise and we may wonder how reliably we can compute over this link, and what the associated overhead is. An application of the Shannon noisy coding theorem results in a simulation of protocols that is robust against noise, but comes with a logarithmic factor overhead in communication cost. In the 90's, Schulman gave an elegant simulation of interactive protocols that incurs only constant factor overhead, in spite of the fact that we do not have the advantage of long block size for such coding. We consider the problem of coding for interactive protocols with quantum communication. In this setting, the Schulman scheme breaks down for a number of reasons. First, we do not know of a quantum analogue of the "tree codes'' used in the scheme. Second, the scheme relies on re-computation of messages that are corrupted beyond repair, which is not possible for quantum states due to impossibility of cloning. We describe a simulation of quantum communication protocols which overcomes these hurdles while introducing only a constant factor slowdown. (Joint work with Falk Unger, UC Berkeley) :: Mon 10/19/09, 4:00 in 36-428 (qip-sem) Andrew Childs (University of Waterloo) Standard methods for performing an arbitrary N-dimensional unitary operation use a number of elementary operations proportional to N^2. We consider a related problem, the implementation of a unitary operation using a black-box description of its matrix elements. In this model, we show that any unitary can be performed using approximately N^{2/3} queries. Indeed, many unitary transformations can be performed in only about sqrt(N) queries, which cannot be improved in general. Our implementation of black-box unitaries makes use of general methods for black-box Hamiltonian simulation (based on discrete-time quantum walk) and black-box quantum state preparation.This is joint work with Dominic Berry (IQC). :: Mon 10/26/09, 4:00 in 36-428 (qip-sem) Kaiser,David (MIT) In recent years, the field of quantum information science-an amalgam of topics ranging from quantum encryption, to quantum computing, quantum teleportation, and more-has catapulted to the cutting edge of physics, sporting a multi-billion-dollar research program, tens of thousands of published research articles, and a variety of device prototypes. This tremendous excitement marks the tail end of a long-simmering Cinderella story. Long before the big budgets and dedicated teams, the field smoldered on the scientific sidelines. In fact, the field's recent breakthroughs derive, in part, from the hazy, bong-filled excesses of the 1970s New Age movement. Many of the ideas that now occupy the core of quantum information science once found their home amid an anything-goes counterculture frenzy, a mishmash of spoon-bending psychics, Eastern mysticism, LSD trips, CIA spooks chasing mind-reading dreams, and comparable "Age of Aquarius" enthusiasms. For the better part of two decades, the concepts that would,in time, blossom into developments like quantum encryption were bandied about in late-night bull sessions and hawked by proponents of a burgeoning self-help movement-more snake oil than stock option. This talk describes the field's bumpy transition from New Age to cutting edge. :: Mon 11/2/09, 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/09, 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/09, 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. :: Mon 11/30/09, 4:00 in 36-428 (QIP seminar) Pirandola,Stefano (MIT/University of York) The optimal discrimination of quantum states is a central problem in quantum information theory. A problem of equal importance, but more difficult to solve, is the optimal discrimination between different quantum channels. In this seminar we analyze these general problems and we specialize them to the scenario of bosonic systems. First we consider the optimal discrimination between two arbitrary Gaussian states, showing how we can estimate the corresponding error probability via the quantum Chernoff bound. Then, we consider the case of two Gaussian channels. Here we provide a lowerbound for the minimum error probability which affects the "classical discrimination" of these channels, i.e., their optimal discrimination assuming "classical states" as input (defined as states with positive P-representation). Exploiting this bound, we can find channel discrimination problems where the use of a "non-classical" input state (e.g., an entangled state) outperforms the use of any "classical" input state. This enhancement is shown in two paradigmic tasks: the sensing of low-reflectivity targets in bright thermal-noise baths (quantum illumination), and the readout of classical digital memories (quantum reading). Birgitta Whaley (UC Berkeley) |
| |
 |  |
