A new quantum lower bound method, with an application to strong direct product theorem for quantum search

Simple item page
dc.creatorAmbainis, Andris
dc.date2005-08-26
dc.date2005-09-07
dc.date.accessioned2026-07-07T06:13:25Z
dc.date.available2026-07-07T06:13:25Z
dc.descriptionWe present a new method for proving lower bounds on quantum query algorithms. The new method is an extension of adversary method, by analyzing the eigenspace structure of the problem. Using the new method, we prove a strong direct product theorem for quantum search. This result was previously proven by Klauck, Spalek and de Wolf (quant-ph/0402123) using polynomials method. No proof using adversary method was known before.
dc.description20 pages, v2 typos corrected
dc.identifierhttps://arxiv.org/abs/quant-ph/0508200
dc.identifierhttp://arxiv.org/abs/quant-ph/0508200
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/93098
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleA new quantum lower bound method, with an application to strong direct product theorem for quantum search
dc.typetext

Files

Collections

arXiv