Deutsch-Jozsa Algorithm
Contents
Deutsch-Jozsa Algorithm¶
The Deutsch-Jozsa Algorithm has almost no practical use. It is famous and important for two reasons. It is one of the first algorithm that definately showed a quantum computer could do something a classical computer could not. Secondly, it is a straightforward application of phase kickback that provided the inspiration for many later algorithms.
Classical Problem¶
We can look at the classic problem statement. We can solve this problem classically, a quantum solution is just more efficient.
We start with a boolean function \(f(x)\). The function takes an \(n\)-bit binary number as input. The function returns either \(0\) or \(1\). The function is either constant or balanced.
Balanced: \(f(x)\) returns \(0\) for exactly half the inputs and \(1\) for the other half.
Constant: \(f(x)\) either returns 0 for all inputs or returns 1 for all inputs.
We can use logic to come up with some simple examples of functions that meet these properties. We need to know that \(f(x)\) can only be constant or balanced ahead of time. This limits the practical applications of the algorithm.
Let n-bit binary number \(x\) be represented by bits \(a_0,a_1,\cdots,a_{n-1}\).
Balanced: \(f(a_0,a_1)=a_0 \iff a_1\)
Constant All Ones: \(h(a_0,a_1)=(a_0 \implies a_1) \vee (a_1 \implies a_0) \)
The function \(f(x)\) is a Black Box. That means we do not know how it works, we can only get the answer.
How many possible inputs does the function have?
1-bit function has 2 possible input sequences
2-bit function has 4 possible input sequences
3-bit function has 8 possible input sequences
n-bit function has \(2^{n}\) possible input sequences
The only experiment we can run on a classical computer is execute \(f(x)\). The best case is that we need to run \(2\) tests regardless of \(n\). We run a first test and get \(0\) then on the second test we get \(1\). We can immediately conclude that the function is balanced. We can also conclude that if we get the two results in opposite order.
What about the worst case? We might get many repeated values before getting a different value. If the function is balanced, it is possible we will get \(\frac{2^{n}}{2}=2^{n-1}\) constant values. When we tested the \(2^{n-1}+1\)-th value, we would finally know the answer. Either we would get a different results which means the function is balanced or the same result meaning it is constant.
On a classical computer, we cannot be sure of the answer until we test \(2^{n-1}+1\) input values. This gives us a worst case runtime of \(O(2^{n})\).
We can easily implement this puzzle in Python. First, we need some functions to test with.
#Implement f(a0,a1)= a0 <-> a1
def f(x):
a0=x[0]
a1=x[1]
return a0==a1
#Implement h(a0,a1)=(a0 -> a1) v (a1->a0)
def h(x):
a0=x[0]
a1=x[1]
return (not a0 or a1) or (not a1 or a0)
We also need a function to convert an integer into an array of bits. This gives us a easy way to generate a specific row of the truth table.
#Convert an Integer to an n-bit array
def intToBin(num,bits):
#Prefill all zeros
B = [0 for x in range(0,bits)]
#Compute Bits
i=0 #Track Current Bit
while num > 0:
B[i]=num%2
num=num//2
i+=1
return B
We can implement a function that determines if an input is constant. We can imply that any non-constant function must be balanced from the problem statement. This loop needs to run at most \(2^{n-1}+1\) times.
#Determine Constant or Balanced
#Returns true on constant
#and false on balanced
def isConstant(func, bits):
start = 0
stop = (2**(bits-1))+1
trueCount=0
falseCount=0
while start <= stop:
myInput = intToBin(start,bits)
if func(myInput)==0:
trueCount+=1
else:
falseCount+=1
if trueCount>0 and falseCount>0:
return False
start+=1
return True
We can test this code with our two example functions.
if __name__=="__main__":
print("Test Function f")
if isConstant(f,2):
print("Function is Constant")
else:
print("Function is Balanced")
print("Test Function h")
if isConstant(h,2):
print("Function is Constant")
else:
print("Function is Balanced")
The output we get is correct.
Test Function f
Function is Balanced
Test Function h
Function is Constant
The algorithm itself is very straightforward. The problem is that it does not scale well. A growth rate of \(O(2^{n})\) is to high for practical problems. If the input function had thousand bits as input, this would eventually become computationally intractable.
As far as we currently know, this is the best solution possible on a classical computer. It is possible that a better solution exists, but it seems unlikely.
Quantum Approach¶
This algorithm was created by David Deutsch and Richard Jozsa. The basic algorithm is based on the phase kickback we saw in the previous section.
We first need to implement our input function as a quantum circuit. It must be implemented as an \(n+1\) qubit circuit. The first \(n\) qubits will be the input to the function. The final qubit is the result qubit (\(y\)). In practice, the result qubit \(y\) start with the value 1 and be placed in a superposition. When the circuit is complete the value of the result qubit will be \(y=y \oplus f(x)\). The \(\oplus\) symbol means the XOR of the two values.
\(y\) |
\(f(x)\) |
\(y \oplus f(x)\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
The circuit may also include any number of temporary qubits as long as they start and end with \(0\).
Note
A temporary qubit is a qubit that is needed to temporarily store a partial answer. It will start and end with a known value of zero. Any usage it has in the circuit is only temporary. These are sometimes called working qubits.
If \(f(x)\) always returns zero then only two rows of the truth table will be possible.
\(y\) |
\(f(x)\) |
\(y \oplus f(x)\) |
|---|---|---|
0 |
0 |
0 |
1 |
0 |
1 |
If \(f(x)\) always returns one then only two rows of the truth table will be possible.
\(y\) |
\(f(x)\) |
\(y \oplus f(x)\) |
|---|---|---|
0 |
1 |
1 |
1 |
1 |
0 |
Notice that in both these cases, only two of the rows are possible. If \(f(x)\) is balanced then have the following truth table.
\(y\) |
\(f(x)\) |
\(y \oplus f(x)\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
All the rows can appear in this situation.
The Deutsch-Jozsa Algorithm uses the same pattern we saw with the phase kickback example. We are scaling that example up to a multi-qubit input function from the single CX in that example. We apply an X gate to the result bit and H gates to all wires. This is generalized for any number of input wires.
The \(U_{f}\) circuit is an implementation of the function \(f(x)\). It must meet the following requirements.
The first \(n\) bits are the input \(x\).
The \(f(x)\) function makes does not change the input bits.
The last wire enters as \(y\) and leaves as \(y \oplus f(x)\).
It may have temporary qubits as long as they start and end as 0.
The Hadamard gate is not applied to the temporary bits as part of the Deutsch-Josza Algorithm.
Balanced Example¶
We can create a balanced example using the XOR function. We can implement \(f(x)=x_0 \oplus x_1\). This expression has a balanced truth table.
\(x_0\) |
\(x_1\) |
\(x_0 \oplus x_1\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
We can implement the XOR using the CX gate. We initially store the result of \(q_0 \oplus q_1\) on wire \(q_1\). We then use another CX gate to XOR the result with the y qubit.
This circuit will accomplish our goals.
In (\(q_0\), \(q_1\), \(q_2\)) |
Out (\(q_0\), \(q_1\), \(q_2\)) |
\(f(q_0,q_1) \oplus q_2\) |
|---|---|---|
000 |
000 |
\((0 \oplus 0)\oplus 0=0\) |
010 |
011 |
\((0 \oplus 1)\oplus 0=1\) |
100 |
101 |
\((1 \oplus 0)\oplus 0=1\) |
110 |
110 |
\((1 \oplus 1)\oplus 0 = 0\) |
We can test this circuit with H gates on the two inputs.
This provides the following results.
{'110': 489, '011': 514, '101': 547, '000': 498}
We know that the last qubit is always starts as 0. We can read these results as follows.
Value |
\(q_0\) |
\(q_1\) |
Input \(q_2\) |
Result \(q_2\) |
|---|---|---|---|---|
‘110’: 489 |
0 |
1 |
0 |
1 |
‘011’: 514 |
1 |
1 |
0 |
0 |
‘101’: 547 |
1 |
0 |
0 |
1 |
‘000’: 498 |
0 |
0 |
0 |
0 |
We can do the same experiment with \(q_2\) initially starting at \(1\).
This time we get the following.
{'001': 525, '010': 501, '111': 505, '100': 517}
This also matches the expectations of \(y \oplus f(x)\).
Value |
\(q_0\) |
\(q_1\) |
Input \(q_2\) |
Result \(q_2\) |
|---|---|---|---|---|
‘001’: 525 |
1 |
0 |
1 |
0 |
‘010’: 501 |
0 |
1 |
1 |
0 |
‘111’: 505 |
1 |
1 |
1 |
1 |
‘100’: 517 |
0 |
0 |
1 |
1 |
If we apply the Deutsch-Jozsa Algorithm’s circuit to this component, then we will get one of two outcomes.
The first \(n\)-qubits will all be 0 if and only if the function is constant.
The first \(n\)-qubits will not all be 0 if and only if the function is balanced.
One important thing to note in this circuit is that the result wire is never measured. Its value does not matter for determining the final outcome. We only need to examine the input qubits.
The result of running this simulation is shown below.
{'11': 2048}
All 2048 tests return with \(q_0=1\) and \(q_1=1\). The first \(n\)-qubits will be zero only when the function is constant. Since the function must be either constant or balanced, we can conclude that the function must be balanced.
In theory, we could confirm this with just a single test run. In practice, we would want more test runs to account for any possible error introduced by the system.
Constant Example¶
The easiest way to make a constant function is to just do nothing. This is the same as setting \(f(x)\) to a constant 0. We can see by the table below that \(y \oplus 0 = y\).
y |
\(f(x)\) |
\(y \oplus f(x)\) |
|---|---|---|
0 |
0 |
0 |
1 |
0 |
1 |
This first constant circuit does nothing for \(f(x)\).
The result of this circuit is {'00': 2048}. Both the input bits are 0 for all cases, this tells us the function was constant.
If we apply the CX gate controlled by \(q_0\) onto \(q_1\) then no changes are made. This provides a circuit that is slightly more interesting then doing literally nothing.
Again, the result is always 00 on the input qubits. The result we get it {'00': 2048}.
What if we wanted a constant 1 as our output. Then the table would need to look like the following.
y |
\(f(x)\) |
\(y \oplus f(x)\) |
|---|---|---|
0 |
1 |
1 |
1 |
1 |
0 |
This is just the opposite of \(y\). We have \(y \oplus 1 = \neg y\). We can also try implementing this circuit.
Again, we are left with {'00': 2048}. The input qubits are all zero.
If we build a Deutsch-Josza circuit correctly, then there are only two outcomes possible.
The first \(n\)-qubits will all be 0 if and only if the function is constant.
The first \(n\)-qubits will not all be 0 if and only if the function is balanced.
Linear Algebra¶
Next, let’s examine how the linear algebra applies to these circuits.
We always start with \(I \otimes (I \otimes X)\).
\( \begin{align} I \otimes (I \otimes X) =& \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \end{align} \)
We also need to apply \(H \otimes (H \otimes H)\).
\( \begin{align} H \otimes (H \otimes H) =& \frac{1}{2\sqrt{2}}\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ \end{bmatrix} \end{align} \)
The final column of gates has two H and one I.
\( \begin{align} (H \oplus (H \oplus I)) =& \frac{1}{2} \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \\ 1 & 0 & 1 & 0 & -1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 1 & 0 & -1 & 0 & -1 \\ 1 & 0 & -1 & 0 & -1 & 0 & 1 & 0 \\ 0 & 1 & 0 & -1 & 0 & -1 & 0 & 1 \\ \end{bmatrix} \end{align} \)
Case 1: Constant 0¶
If the function \(f(x)\) returns a constant 0, then we can ignore the circuit entirely. It will not make any changes to wires \(q_0\) or \(q_1\). The output of \(q_2\) will be the same as its input.
We start with the \(\dirac{000}\) state.
\( \begin{align} v=&\begin{bmatrix} 1 \text{ (q0=0,q1=0,q2=0)}\\ 0 \text{ (q0=0,q1=0,q2=1)}\\ 0 \text{ (q0=0,q1=1,q2=0)}\\ 0 \text{ (q0=0,q1=1,q2=1)}\\ 0 \text{ (q0=1,q1=0,q2=0)}\\ 0 \text{ (q0=1,q1=0,q2=1)}\\ 0 \text{ (q0=1,q1=1,q2=0)}\\ 0 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \end{align} \)
We apply \(I \otimes (I \otimes X)\).
\( \begin{align} (I \otimes (I \otimes X))v =& \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \text{ (q0=0,q1=0,q2=0)}\\ 0 \text{ (q0=0,q1=0,q2=1)}\\ 0 \text{ (q0=0,q1=1,q2=0)}\\ 0 \text{ (q0=0,q1=1,q2=1)}\\ 0 \text{ (q0=1,q1=0,q2=0)}\\ 0 \text{ (q0=1,q1=0,q2=1)}\\ 0 \text{ (q0=1,q1=1,q2=0)}\\ 0 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \\ =& \begin{bmatrix} 0 \text{ (q0=0,q1=0,q2=0)}\\ 1 \text{ (q0=0,q1=0,q2=1)}\\ 0 \text{ (q0=0,q1=1,q2=0)}\\ 0 \text{ (q0=0,q1=1,q2=1)}\\ 0 \text{ (q0=1,q1=0,q2=0)}\\ 0 \text{ (q0=1,q1=0,q2=1)}\\ 0 \text{ (q0=1,q1=1,q2=0)}\\ 0 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \end{align} \)
Then we apply the Haramard gates.
\( \begin{align} (H \otimes (H \otimes H)) v =& \left( \frac{1}{2\sqrt{2}}\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ \end{bmatrix} \right) \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{bmatrix} \\ =& \frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \text{ (q0=0,q1=0,q2=0)}\\ -1 \text{ (q0=0,q1=0,q2=1)}\\ 1 \text{ (q0=0,q1=1,q2=0)}\\ -1 \text{ (q0=0,q1=1,q2=1)}\\ 1 \text{ (q0=1,q1=0,q2=0)}\\ -1 \text{ (q0=1,q1=0,q2=1)}\\ 1 \text{ (q0=1,q1=1,q2=0)}\\ -1 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \end{align} \)
If the \(f(x)\) function is a constant 0, then nothing it does will change this state vector. We can immediately jump to the final \((H \otimes (H \otimes I)) v\).
\( \begin{align} (H \otimes (H \otimes I)) v =& \left( \frac{1}{2} \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \\ 1 & 0 & 1 & 0 & -1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 1 & 0 & -1 & 0 & -1 \\ 1 & 0 & -1 & 0 & -1 & 0 & 1 & 0 \\ 0 & 1 & 0 & -1 & 0 & -1 & 0 & 1 \\ \end{bmatrix} \right) \left( \frac{1}{2\sqrt{2}} \begin{bmatrix} 1\\ -1\\ 1\\ -1 \\ 1 \\ -1 \\ 1 \\ -1\\ \end{bmatrix} \right) \\ =& \frac{1}{4\sqrt{2}} \begin{bmatrix} 1 +0 +1 +0+1+0+1+0=4 \\ 0 -1 +0 -1 +0-1+0-1=-4 \\ 1 +0 -1 +0 +1+0-1+0=0 \\ 0 -1 +0 +1 +0-1+0+1=0\\ 1 +0 +1 +0 -1+0-1+0=0\\ 0 -1 +0 -1 +0+1+0+1=0\\ 1 +0 -1 +0 -1+0+1+0=0\\ 0 -1 +0 +1 +0+1+0-1=0\\ \end{bmatrix} \\ =& \begin{bmatrix} \frac{1}{\sqrt{2}} \text{ (q0=0,q1=0,q2=0)}\\ \frac{-1}{\sqrt{2}} \text{ (q0=0,q1=0,q2=1)}\\ 0 \text{ (q0=0,q1=1,q2=0)}\\ 0 \text{ (q0=0,q1=1,q2=1)}\\ 0 \text{ (q0=1,q1=0,q2=0)}\\ 0 \text{ (q0=1,q1=0,q2=1)}\\ 0 \text{ (q0=1,q1=1,q2=0)}\\ 0 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \end{align} \)
We are left with only one possible for the first two qubits. \((q_0=0,q_1=0)\).
Case 2: Constant 1¶
The first two application are the same. We can immediately start at that vector.
\( \begin{align} \frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \text{ (q0=0,q1=0,q2=0)}\\ -1 \text{ (q0=0,q1=0,q2=1)}\\ 1 \text{ (q0=0,q1=1,q2=0)}\\ -1 \text{ (q0=0,q1=1,q2=1)}\\ 1 \text{ (q0=1,q1=0,q2=0)}\\ -1 \text{ (q0=1,q1=0,q2=1)}\\ 1 \text{ (q0=1,q1=1,q2=0)}\\ -1 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \end{align} \)
If the function is a constant 1, it will have the same effect as applying \(I \otimes (I \otimes X)\) to this state vector.
\( \begin{align} (I \otimes (I \otimes X))v =& \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \left( \frac{1}{2\sqrt{2}} \begin{bmatrix} 1\\ -1 \\ 1 \\ -1 \\ 1 \\ -1 \\ 1 \\ -1 \\ \end{bmatrix} \right) \\ =& \frac{1}{2\sqrt{2}} \begin{bmatrix} -1 \text{ (q0=0,q1=0,q2=0)}\\ 1 \text{ (q0=0,q1=0,q2=1)}\\ -1 \text{ (q0=0,q1=1,q2=0)}\\ 1 \text{ (q0=0,q1=1,q2=1)}\\ -1 \text{ (q0=1,q1=0,q2=0)}\\ 1 \text{ (q0=1,q1=0,q2=1)}\\ -1 \text{ (q0=1,q1=1,q2=0)}\\ 1 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \end{align} \)
All this does it swap all the positions of positive and negative ones. When we apply the Hadamard Gate sequence, values will still cancel out in a similar way.
\( \begin{align} (H \otimes (H \otimes 1)) v =& \left( \frac{1}{2} \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \\ 1 & 0 & 1 & 0 & -1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 1 & 0 & -1 & 0 & -1 \\ 1 & 0 & -1 & 0 & -1 & 0 & 1 & 0 \\ 0 & 1 & 0 & -1 & 0 & -1 & 0 & 1 \\ \end{bmatrix} \right) \left( \frac{1}{2\sqrt{2}} \begin{bmatrix} -1 \\ 1 \\ -1 \\ 1 \\ -1 \\ 1 \\ -1 \\ 1 \\ \end{bmatrix} \right) \\ =& \left( \frac{1}{4\sqrt{2}} \begin{bmatrix} -1+0-1+0-1+0-1+0=-4\\ 0+1+0+1+0+1+0+1=4\\ -1+0+1+0-1+0+1+0=0\\ 0+1+0-1+0+1+0-1=0\\ -1+0-1+0+1+0+1+0=0\\ 0+1+0+1+0-1+0-1=0\\ -1+0+1+0+1+0-1+0=0\\ 0+1+0-1+0-1+0+1=0 \\ \end{bmatrix} \right) \\ =& \begin{bmatrix} \frac{-1}{\sqrt{2}} \text{ (q0=0,q1=0,q2=0)}\\ \frac{1}{\sqrt{2}} \text{ (q0=0,q1=0,q2=1)}\\ 0 \text{ (q0=0,q1=1,q2=0)}\\ 0 \text{ (q0=0,q1=1,q2=1)}\\ 0 \text{ (q0=1,q1=0,q2=0)}\\ 0 \text{ (q0=1,q1=0,q2=1)}\\ 0 \text{ (q0=1,q1=1,q2=0)}\\ 0 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \end{align} \)
We still end up with a result \((q_0=0,q_1=0)\) for every possible test.
Case 3: Balanced¶
There are may ways to get a balanced function. We will look at the example use used earlier.
We start by applying the \(X\) gate to \(q_2\).
\( \begin{align} (I \otimes (I \otimes X))v=& \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{bmatrix} \\ =& \begin{bmatrix} 0 \text{ (q0=0,q1=0,q2=0)}\\ 1 \text{ (q0=0,q1=0,q2=1)}\\ 0 \text{ (q0=0,q1=1,q2=0)}\\ 0 \text{ (q0=0,q1=1,q2=1)}\\ 0 \text{ (q0=1,q1=0,q2=0)}\\ 0 \text{ (q0=1,q1=0,q2=1)}\\ 0 \text{ (q0=1,q1=1,q2=0)}\\ 0 \text{ (q0=1,q1=1,q2=1)}\\ \end{bmatrix} \end{align} \)
We apply the Hadamard gate to all three wires.
\( \begin{align} (H \otimes (H \otimes H))v=& \left( \frac{1}{2\sqrt{2}}\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ \end{bmatrix} \right) \begin{bmatrix} 0\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{bmatrix} \\ =&\frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \text{ (q0=0,q1=0,q2=0)} \\ -1 \text{ (q0=0,q1=0,q2=1)} \\ 1 \text{ (q0=0,q1=1,q2=0)} \\ -1 \text{ (q0=0,q1=1,q2=1)} \\ 1 \text{ (q0=1,q1=0,q2=0)} \\ -1 \text{ (q0=1,q1=0,q2=1)} \\ 1 \text{ (q0=1,q1=1,q2=0)} \\ -1 \text{ (q0=1,q1=1,q2=1)} \\ \end{bmatrix} \end{align} \)
Our perfect split circuit applied \(CX \otimes I\).
\( \begin{align} (CX \otimes I)v=& \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{bmatrix} \left( \frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \\ -1\\ 1 \\ -1 \\ 1 \\ -1 \\ 1 \\ -1 \\ \end{bmatrix} \right) \\ =\frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \\ -1\\ 1 \\ -1 \\ 1 \\ -1 \\ 1\\ -1 \\ \end{bmatrix} \end{align} \)
Next we applied \(I \otimes CX\).
\( \begin{align} (I \otimes CX)v=& \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix} \left( \frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \\ -1\\ 1 \\ -1 \\ 1 \\ -1 \\ 1\\ -1 \\ \end{bmatrix} \right) \\ =&\frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \text{ (q0=0,q1=0,q2=0)} \\ -1 \text{ (q0=0,q1=0,q2=1)} \\ -1 \text{ (q0=0,q1=1,q2=0)} \\ 1 \text{ (q0=0,q1=1,q2=1)} \\ 1 \text{ (q0=1,q1=0,q2=0)} \\ -1 \text{ (q0=1,q1=0,q2=1)} \\ -1 \text{ (q0=1,q1=1,q2=0)} \\ 1 \text{ (q0=1,q1=1,q2=1)} \\ \end{bmatrix} \end{align} \)
Finally we apply a second circuit applied \(CX \otimes I\).
\( \begin{align} (CX \otimes I)v=& \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{bmatrix} \left( \frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \\ -1\\ -1 \\ 1 \\ 1 \\ -1 \\ -1\\ 1 \\ \end{bmatrix} \right) \\ =&\frac{1}{2\sqrt{2}} \begin{bmatrix} 1 \text{ (q0=0,q1=0,q2=0)}\\ -1 \text{ (q0=0,q1=0,q2=1)}\\ -1 \text{ (q0=0,q1=1,q2=0)}\\ 1 \text{ (q0=0,q1=1,q2=1)}\\ -1 \text{ (q0=1,q1=0,q2=0)}\\ 1 \text{ (q0=1,q1=0,q2=1)}\\ 1\text{ (q0=1,q1=1,q2=0)}\\ -1 \text{ (q0=1,q1=1,q2=1)} \\ \end{bmatrix} \end{align} \)
We leave the last qubit and apply H to the \(q_0\) and \(q_1\). Note that \(\frac{1}{2} * \frac{1}{2\sqrt{2}} =\frac{1}{4 \sqrt{2}}\).
\( \begin{align} (H \oplus (H \oplus I))v =& \frac{1}{4\sqrt{2}} \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \\ 1 & 0 & 1 & 0 & -1 & 0 & -1 & 0 \\ 0 & 1 & 0 & 1 & 0 & -1 & 0 & -1 \\ 1 & 0 & -1 & 0 & -1 & 0 & 1 & 0 \\ 0 & 1 & 0 & -1 & 0 & -1 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 \\ -1\\ -1 \\ 1 \\ -1 \\ 1 \\ 1\\ -1 \\ \end{bmatrix} \\ =&\frac{1}{4\sqrt{2}} \begin{bmatrix} 0 \text{ (q0=0,q1=0,q2=0)} \\ 0 \text{ (q0=0,q1=0,q2=1)} \\ 0 \text{ (q0=0,q1=1,q2=0)} \\ 0 \text{ (q0=0,q1=1,q2=1)} \\ 0 \text{ (q0=1,q1=0,q2=0)} \\ 0 \text{ (q0=1,q1=0,q2=1)} \\ 4 \text{ (q0=1,q1=1,q2=0)} \\ -4 \text{ (q0=1,q1=1,q2=1)} \\ \end{bmatrix} \\ =& \begin{bmatrix} 0 \text{ (q0=0,q1=0,q2=0)} \\ 0 \text{ (q0=0,q1=0,q2=1)} \\ 0 \text{ (q0=0,q1=1,q2=0)} \\ 0 \text{ (q0=0,q1=1,q2=1)} \\ 0 \text{ (q0=1,q1=0,q2=0)} \\ 0 \text{ (q0=1,q1=0,q2=1)} \\ \frac{1}{\sqrt{2}} \text{ (q0=1,q1=1,q2=0)} \\ \frac{-1}{\sqrt{2}} \text{ (q0=1,q1=1,q2=1)} \\ \end{bmatrix} \end{align} \)
We absolutely cannot get any outcomes where \(q_0=0\) and \(q_1=0\). This result indicates the function must be balanced.
General Algorithm¶
Conclusion¶
The matrix/vector can have negative values. This cause some positions to cancel out. This is called phase kickback. The constant function caused a regular balance of 1 and -1. The 50/50 split function caused a different pattern. Different rows canceled out in both cases.
The quantum particles are not independent. Their quantum states are linked. The quantum particles are in a superposition, all their outcomes are interconnected.