Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home


Technical Reports


printable version
» 

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

  Click here for full text: PDF

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

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.