• current month / next month
• this year / past

• Tue 11:00-12:00, 6-310
  Farhi Group Meeting
  contact: Eddie Farhi
• Mon 4:00-5:00, 36-428
  Quantum Information Processing Seminar (subscribe to their email announcement list)
  
• Tue 4:15, 32-G449 (Kiva, Stata Center)
  Theory of Computation Seminar
  
• Thu 4:15, 10-250
  Dept. of Physics Colloquium

other seminars:

• CTP seminars
• RLE optics & quantum electronics seminar
• Center for Ultracold Atoms seminar
• EECS seminars
• LIDS seminars
• Boston Area Physics Calendar

:: Mon 11/2, 4:00 in 36-428 (qip-sem)

Daniel Nagaj (RCQI, IoP SAS, Bratislava)
Fast QMA Amplification

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)
Span Programs and Quantum Query Algorithms

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.

:: Mon 11/30, 4:00 in

Aram Harrow (University of Bristol)
TBD

home :: people :: seminars :: courses :: visitors :: links