00722nas a2200133   4500000000100000008004100001100001700042700001700059700002300076245009700099300001400196490000700210520037100217       2012                            d1 aPiotr Gawron1 aJerzy Klamka1 aRyszard Winiarczyk00aNoise effects in the quantum search algorithm from the viewpoint of computational complexity  a493–4990 v223 aWe analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on computational complexity of the quantum search algorithm. We show that only for small amounts of noise the quantum search algorithm is still more efficient than any classical algorithm.