Say we want our quantum computer to make calls to a black box function f(x) from bit strings to bits. There’s a couple ways to formalize that. Phase oracle: |x> becomes -|x> if f(x), otherwise |x>. Binary oracle: |x> ⊗ |b> becomes |x> ⊗ |f(x) xor b>. These definitions only say what happens to basis vectors, and are extended to other vectors by linearity.
We can convert from a binary oracle to a phase oracle by using an extra qubit. Start with a state |x> ⊗ (|0> - |1>)/√2 and apply a binary oracle, we end up with (1/√2) ⋅ (|x1> - |x0> if f(x), otherwise |x0> - |x1>). But that’s exactly (-|x> if f(x), otherwise |x>) ⊗ (|0> - |1>)/√2. So |x> has been changed as if by a phase oracle, and the extra qubit was left unchanged.
Grover’s algorithm: we have a black box function from N-bit strings to bits, which returns true for only one possible input. We want to find that input. Classically that requires O(2^N) calls to the black box, because you can’t do much better than brute force. With a quantum algorithm we can get O(√2^N) which is much faster.
Let’s say X is the input we’re trying to find, which is one of the basis vectors of the space. Let’s also define a vector S = (|0> + |1>)/√2 ⊗ … ⊗ (|0> + |1>)/√2, which is the sum of all 2^N basis vectors with equal amplitudes.
Initialize state as S
Apply phase oracle, corresponding to reflection through the plane perpendicular to X
Apply “Grover operator”, corresponding to reflection through the plane perpendicular to S and then central symmetry around 0
Repeat steps 2 and 3 a bunch of times
To understand it geometrically, draw the 2D plane containing the vectors X and S. Their dot product is 1/√2^N, which is a small positive number, so the angle between them is a bit less than 90 degrees. If our state starts out as S, the net effect of (2) and (3) is a slight rotation toward X, and each time we repeat it, we rotate again by the same angle. The angle is 2⋅arcsin(1/√2^N), which is proportional to 2/√2^N, so after (pi/4)⋅√2^N iterations we’re pretty close to X. Then we can measure and get X with high probability.
I glossed over implementing the Grover operator, but that shouldn’t be too hard, since from the first half of this comment it should be kinda clear how to reflect a vector through a plane.
(9/?)
Black box functions and Grover’s algorithm.
Say we want our quantum computer to make calls to a black box function f(x) from bit strings to bits. There’s a couple ways to formalize that. Phase oracle: |x> becomes -|x> if f(x), otherwise |x>. Binary oracle: |x> ⊗ |b> becomes |x> ⊗ |f(x) xor b>. These definitions only say what happens to basis vectors, and are extended to other vectors by linearity.
We can convert from a binary oracle to a phase oracle by using an extra qubit. Start with a state |x> ⊗ (|0> - |1>)/√2 and apply a binary oracle, we end up with (1/√2) ⋅ (|x1> - |x0> if f(x), otherwise |x0> - |x1>). But that’s exactly (-|x> if f(x), otherwise |x>) ⊗ (|0> - |1>)/√2. So |x> has been changed as if by a phase oracle, and the extra qubit was left unchanged.
Grover’s algorithm: we have a black box function from N-bit strings to bits, which returns true for only one possible input. We want to find that input. Classically that requires O(2^N) calls to the black box, because you can’t do much better than brute force. With a quantum algorithm we can get O(√2^N) which is much faster.
Let’s say X is the input we’re trying to find, which is one of the basis vectors of the space. Let’s also define a vector S = (|0> + |1>)/√2 ⊗ … ⊗ (|0> + |1>)/√2, which is the sum of all 2^N basis vectors with equal amplitudes.
Initialize state as S
Apply phase oracle, corresponding to reflection through the plane perpendicular to X
Apply “Grover operator”, corresponding to reflection through the plane perpendicular to S and then central symmetry around 0
Repeat steps 2 and 3 a bunch of times
To understand it geometrically, draw the 2D plane containing the vectors X and S. Their dot product is 1/√2^N, which is a small positive number, so the angle between them is a bit less than 90 degrees. If our state starts out as S, the net effect of (2) and (3) is a slight rotation toward X, and each time we repeat it, we rotate again by the same angle. The angle is 2⋅arcsin(1/√2^N), which is proportional to 2/√2^N, so after (pi/4)⋅√2^N iterations we’re pretty close to X. Then we can measure and get X with high probability.
I glossed over implementing the Grover operator, but that shouldn’t be too hard, since from the first half of this comment it should be kinda clear how to reflect a vector through a plane.