BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Exact quantum algorithms - Ambainis\, A (University of Latvia)
DTSTART:20130906T143000Z
DTEND:20130906T153000Z
UID:TALK46979@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:A quantum algorithm is exact if\, on any input data\, it outpu
 ts the correct answer with certainty (probability 1) - in contrast to the 
 usual model in which a quantum algorithm is allowed to output an incorrect
  answer with a small probabilities. Coming up with exact quantum algorithm
 s is a difficult task because we have to ensure that no amplitude ends up 
 in a state corresponding to an incorrect answer - on any input.\n\nWe pres
 ent the first example of a Boolean function f(x1\, ...\, xN) for which exa
 ct quantum algorithms have superlinear advantage over the deterministic al
 gorithms. Any deterministic algorithm that computes our function must use 
 N queries but an exact quantum algorithm can compute it with O(N^{0.8675..
 .}) queries.\n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR