Quantum Information for Quantum Cats (22)

Oracle

The fact we have just shown, that the reversible quantum circuit can handle evrything classical circuit does, is very nice. But of this alone does not constitute a persuasive reason to go through the labor of developing quantum circuits which should entail considerable difficulty both conceptually and technically. Is there any real advantage of using vector and matrix for computation over usual scalar number operation?

To that end, we introduce a novel concept called oracle. But before that, we want to reformulate the procedure of "computation" itself. Computation can be thought of as starting from some quantity x and applying some procedure on it, and obtaining another quantity y as a result. We can express it as calculating a function y = f(x). For simplicity, we consider both x and y to be integer-valued. Then there are only finite possibility for the form of f(x).

As an extreme example, let us limit ourselves to the case of f(x) being a one bit quantity, namely f(x) can take only two values, 0 or 1. Let x be of n bit number taking N=2ⁿ possible values, 0, 1, 2, ... 2ⁿ-1. For the simplest case of n=1, we have N=2 and only 4 possible form of function f(x), which are

So, for this case, we can rephrase the calculation of the function f as the determination of the type of f.

Now imagin we prepare four identically looking contraptions A, B, C and D that eats a number x and output the number f(x) according to the above specification. Suupose you are presented with a set of large number of these contraptions and are asked to pick up one of them. Since they are indistinguishable in their apperence, the only way you can tell which of A, B, C, D you have picked up is by operating it twice by feeding it with x= 0 and x = 1. We call this set of unmarked contraptions "oracle". For example, "Assume the function f to be one of A, B, C, or D, and calculate the quantity z= f(0) .xor. f(1) " could be paraphrased by

"Feed in both 0 and 1 to the oracle of f where f stands for one of A, B, C, or D, and .xor. the numbers resulting from the operations."

We have to operate the oracle twice to determin its identity becasue we have to know f(0) and f(1) to do this. Seems like a mere nonsensical word play, is it not? But how about this asserttion?

If we preapre quantum oracles of A, B, C, D, a single draw with single operation would enable you to calculate z = f(0) .xor. f(1).

You must surely be interested.