Quantum Information for Quantum Cats (25)

Hadamard Operator and Quantum Parallelism

Up to now, you might be feeling puzzled for the reason of going throughthe trouble of constructing the quantum phase oracle V_f from the function f(x), since what we obtain from operating V_f on | 0 > or | 1 > is just the phase information f(0) or f(1), and this appears to be just the same thing as calculating f(0) and f(1) in different language. Specifically, two draings of oracle

determins the f(0) and f(1). Is the "oracle" just a vacuous mystification? Or do we have any better use of V_f that takes advatage of its matrix characteristics. To answer this question, we consider another quantum operation H which is defined by

H =1/\sqrt2 [1 1] [1 -1]

This H is usually called Hadamard operator, whose action on states |0 > and | 1 > is given by

The result is the equal weight mixture of | 0 > and | 1 >. You might recall the resulting states as "right" and "left" states which appeared in cryptography. The trick is that operating V_f after Hadamard operation enables a parallel operation of evaluating f(0) and f(1) simultaneously.

We can generalize the Hadamard operator to the case of more than one qubit easily. For example, for two qubits, we define H as

and obtain the mixture of all two qubit basis as

The power of quantum oracle is hidden if it is used for "pure" states like | 0> and | 1 >. Its full glory is seen only when it is operated after Hadamard operator has generated all possible states for a given number of bits.