| |
Click here for full text:
On the power of quantum oracles
Kashefi, Elham; Kent, Adrian; Vedral, Vlatko; Banaszek, Konrad
HPL-2001-315R1
Keyword(s): quantum computing; algorithms; query complexity; search problems
Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. A standard quantum oracle Sf for a function f : ZN ? ZN is defined to act on two input states and return two outputs, with inputs and (i, j ZN ) returning outputs and f (i) . For general f, this is the simplest invertible quantum map that allows the evaluation of any f (i ) with one call. However, if f is known to be a one-one, a simpler oracle, Mf , which returns f (i) given , shares these properties. We consider the relative strengths of these oracles. We define a simple promise problem which minimal quantum oracles can solve exponentially faster than classical oracles, via an algorithm which does not extend to standard quantum oracles. We then prove our main result: two invocations of Mf suffice to construct Sf , while ( ) invocations of Sf are required to construct Mf. Notes: Elham Kashefi, Vlatko Vedral & Konrad Banaszek, Optics Section, The Blackett Laboratory, Imperial College, London SW7 2BZ, England. Elham Kashefi & Konrad Banaszek, Centre for Quantum Computation, Clarendon Laboratory, University of Oxford, Parks Road, Oxford OX1 3PU, England.
4 Pages
Back to Index
|
printable version
