Quantum algorithms Andrew Childs Institute for Quantum Computing University of Waterloo 11th Canadian Summer School on Quantum Information 8–9 June 2011 Based in part on slides prepared with Pawel Wocjan (UCF) 12th Canadian Summer School on Quantum Information 11–16 June 2012 Institute for Quantum Computing University of Waterloo http://cssqi2012.iqc.uwaterloo.ca Outline IV. Unstructured search V. Quantum walk VI. Adversary lower bounds Part IV Unstructured search Unstructured search Quantum computers can quadratically outperform classical computers at a very basic computational task, unstructured search There is a set X containing N items, some of which are marked We are given a Boolean black box f : X → {0, 1} that indicates whether a given item is marked The problem is to decide if any item is marked, or alternatively, to find a marked item given that one exists Unstructured search as a model for NP Unstructured search can be thought of as a model for sol
