Oracles in Quantum Computation Ben Schmid Jesse Dhillon Lin Xu Introduction The promise of fast computation of traditionally intractable problems such as number factoring calculating eigenvalues and searching databases have made Quantum Computation and Information Theory hot topics of investigation Current research in quantum computing has been generally focused on various physical schemes and implementations of a number of canonical circuits Most of these circuits can be classified as oracle based i e such algorithms assume the existence of a black box which provides a binary output does the given input satisfy the problem Here we describe three criteria that can be applied to any implementation of oracles and survey some physical implementations with particular emphasis on the scaling issues of each First we will discuss three canonical algorithms for which implementations have been widely attempted DeutschJozsa Grover s search algorithm and BernsteinVazirani These are all oracle based quantum algorithms Shore s algorithm the other quantum algorithm that is widely attempted does not require an oracle and thus is not susceptible to many of the issues we discuss here Still these algorithms promise to provide a highly significant often exponential speedup compared to the best classical solutions to the same problems We compare the computational complexity of each via the number of executions of the oracle classically for example O N calls to the oracle are required in Deutsch Jozsa but only a single call is required in the quantum algorithm This illustrates one chief advantage of an oracle computational complexity comparisons are easy to make by simply counting the number of oracle invocations made It also simplifies algorithms a black box oracle provides an abstraction allowing unencumbered analysis of complexity and implementation issues In this paper we will explicitly consider the issues involved in implementation of oracles Canonical oracle based algorithms Deutsch Jozsa A simple promise problem one which shows the potential advantage of quantum algorithms is the Deutsch problem Consider the class of functions which take an argument of one bit and return 2 one bit The truth table of all such functions is easily constructed X f 0 0 1 f 1 0 0 f 2 0 1 f 3 1 0 1 1 If one imagines executing the functions on a random string of bits sequentially it is clear that for the functions f0 and f3 the output will always be the same while for f1 and f2 half the time the output is 0 and the other half 1 Thus the function pairs f0 f2 and f1 f3 are described as constant and balanced respectively Now suppose you are given a black box oracle which you know implements one of the functions Deutsch asked the question to which class does the function belong In other words is the function inside the oracle constant or balanced Classically one would require two queries to the oracle checking the result for inputs 0 and 1 Deutsch showed that using a quantum algorithm it is possible to determine the class in a single query1 This problem was further generalized by David Deutsch and Richard Jozsa to the case of a function which takes as an input an N bit string and returns a single bit2 In this problem the functions need not actually be exclusively either constant or balanced they could for example return 1 a third of the time and 0 the rest If one restricts the problem to the subset of n bit functions which are either constant or balanced then the advantage of the quantum algorithm becomes very clear Classically one must in the worst case check half of all possible inputs plus one or N 2 1 calling the oracle which evaluates f each time As in the single bit case the DeutschJozsa algorithm promises the result in a single oracle call This stunning result is made possible by the utilization of quantum superposition and interference The quantum circuit is remarkably simple One begins with a single target in state 1 and an N qubit measurement register n in state 0 Passing through Hadamard gates the measurement qubits are all initialized into the superposition state 1 2 n 0 1 n and the target into 12 0 1 After the full N 1 qubit state is operated on by the oracle the measurement register is passed through an n qubit Hadamard Given the simplicity of the algorithm clearly the magic is happening inside the oracle Through the principle of phase kickback each input x acquires 3 a phase of 0 or if f x is 0 or 1 respectively If the function is constant the total state is unaltered up to a global phase and after passing through the 2nd Hadamard gate the measurement state is returned to the initial state A balanced function conversely will yield destructive interference and n the final state will not be 0 The oracle in this case need only evaluate the function for the state given by the measurement register which has been placed into a superposition of all possible bit strings Utilizing this inherent parallelism phase kickback between the target and measurement qubits and interference the algorithm can determine whether or not the function f is balanced in a single call to the oracle Grover s search algorithm Grover s search algorithm3 provides a N speed up over classical searching O N Clearly this search is over a unstructured database since classically we can structure the database such that searches on average could be as low as Figure 1 Deutsch Jozsa circuit Uf is the oracle O 1 The algorithm can be described as a parallelized search we utilize the ability of quantum systems create a superposition of multiple states such that one application of the oracle in principle operates on all possible values in the search space Each iteration of the algorithm boosts the probability of the correct the selected state state being measured when a measurement on the qubit is taken Thus after a number of iterations the algorithm will select with arbitrarily high probability the correct state Prepare a superposition of all input states Y ai i i such that the superposition is equal i e that 1 ai 2n Then the action of the oracle is to take the marked states to ai a i if i is not marked O a i a i if i is marked Grover s algorithm then essentially inverts the a amplitudes i about the mean Repeated iteration results in amplitudes arbitrarily close to ai 0 except for the marked state which now has amplitude close to unity The literature has covered Grover s search and implementations thereof4 5 the algorithm has been shown to be optimal