Quantum Oracles Jesse Dhillon Ben Schmid Lin Xu CS Phys C191 Final Project December 1 2005 Introduction An oracle is the portion of an algorithm which can be regarded as a black box whose behavior can be relied upon Theoretically its implementation does not need to be specified However in practice the implementation must be considered Introduction Why do we use oracles Allows complexity comparisons between quantum and classical algorithms Conceptually simplifies algorithms Oracle Challenges Criteria for a good oracle implementation Speed Generality Feasibility Speed Oracle has to be fast or it may simply be hiding exponential expense of your algorithm in a black box For example imagine an oracle for an algorithm for finding primes in a given range Generality Oracles test for answer Implies reconfiguration of the oracle for each question Feasible Consider 1940s classical computers compared to modern ones First computers could only do specific tasks Feasibility QC supposed to be exponential speedup However when n is small exponential speedup is lost in overhead Intimately tied to method of physical realization Physical Implementations Survey of different proposed and realized oracle implementations Optical Josephson junctions Optical Is optical truly quantum Exponential increase in hardware requirements as qubit count increases Entanglement Effects of entanglement without ability to test Bellinequality Optical But Very long coherence times Single qubit gates are easy to implement Scalable cNOT and cSIGN have been demonstrated Grover s Optical Oracle Oracle in used in optical implementation of Grover s search Encoded with a marked state flips the sign of that state Grover s Optical Oracle Oracles demonstrated so far Toy implementations do not actually search through a database Has a significant failure rate Optical Oracles Programming an optical oracle is currently achievable Uses beam splitters wave plates diffraction gratings etc Research suggests in certain cases sub exponential scalability may be possible Josephson Charge Qubits Superconducting islands coupled via Josephson junctions Control of Voltage and Flux allow construction of any single or 2 qubit gate 4 qubit Deutsch Jozsa 1 Initialize 2 H n 3 Oracle x 1 f x x 4 H n 5 Measure Determine whether a function f 0 1 N 0 1 Oracle encodes a single function How many possible oracles for general n qubit test Many Single Qubit Gates Z rotations generated via charging voltage time X rotations with zero charging voltage and controlled by Josephson energy and time These two gates allow construction of any single qubit gate i e Hadamard 2 Qubit Gates Control Flux in interaction SQUID Control time of interaction CNOT is universal now we can build the Oracle Constructing the Oracle Constructed of CNOT and controllable phase shifts Note only nearest neighbor 2 qubit gates Ring geometry Need 2n 1 controllable phase gates to implement any n qubit Deutsch Jozsa Oracle Josephson v Optical Optical is cheap simple Exponential increases with N Josephson qubits can be entangled Can construct any D J oracle with multiple 2 qubit gates Josephson seems to offer better scalability and true quantum entanglement Requires more research Difficult to manufacture Reconfigurability References N Schuch J Siewert Phys Stat Sol b 233 No 3 482 489 2002 J L Dodd T C Ralph G J Milburn Phys Rev A 68 042328 2003 P G Kwait et al quant ph 9905086 v1 P Londero et al Phys Rev A 69 010302 R 2004 end
View Full Document
Unlocking...