Classic Logic
Contents
Classic Logic¶
A Quantum Computer isn’t very powerful if we can’t do traditional computations on it. The Quantum Computer should be able to do everything a classical computer can do and more. We will start by showing how a quantum computer can replicate classical computer calculations.
We will need three gates for these experiments. Each circuit will generate every possible outcome of a traditional logic gate.
We will three quantum gates in these examples. The X Gate flips the values of \(\alpha\) and \(\beta\). The CCX Gate takes three qubits and applies X to the third qubit if and only if the first two qubits are both \(\left| 1 \right>\). The H Gate puts the circuit into a 50/50 superposition.
Since every circuit needs to be reversable, we cannot destroy or create any qubits along the way. In most cases, we will use input qubits and result qubits. We reserve qubit wires set to \(\left| 0 \right>\) to put the result on.
Negation¶
We have already seen that the X gate can replicate the classical Negation \(\neg A\).
The truth table for the not gate is show below.
A |
\(\neg A\) |
|---|---|
0 |
1 |
1 |
0 |
We can just apply the X gate to a qubit.
If we need to put the result of the not on a second wire, we can use a CX gate. This will only apply the X gate if the control qubit is 1. We set the target qubit to start at 1. If the control is 0, the result is one. If the control is 1, the qubit it flipped back to zero.
The circuit code in qiskit is shown below.
qc = QuantumCircuit(2, 2)
qc.h(0)
qc.x(1)
qc.cx(0,1)
qc.measure(0,0)
qc.measure(1,1)
If we run this circuit through the simulator we get the following results.
{'01': 1048, '10': 1000}
Converting the results to truth table format we get.
\(q_0\) |
\(q_2=\neg q_0\) |
Count |
|---|---|---|
0 |
1 |
1000 |
1 |
0 |
1048 |
This allows us to put the result of the not onto a different wire or to leave it on the same wire. In many cases, using the initial wire and undoing the X so the wire can be reused it more efficient.
Conjunction¶
The conjunction is true when both inputs are true. The CCX gate basically covers this one for us. We use the two control qubits as our input. We start the result qubit at \(\left| 0 \right>\). If both control qubits are \(\left| 1 \right>\), we flip the result qubit to \(\left| 1 \right>\).
The truth table for a conjunction is shown below.
A |
B |
\(A \wedge B\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
We use \(q_0\) and \(q_1\) as \(A\) and \(B\). Then we put the result on \(q_2=A \wedge B\).
#Make a Circuit
qc = QuantumCircuit(3,3)
#Add a CCX Gate
qc.h(0)
qc.h(1)
qc.ccx(0,1,2)
#Measure out results
qc.barrier(range(0,3))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
The circuit is shown below.
The results are displayed by the simulator.
{'010': 542, '001': 466, '000': 516, '111': 524}
Converting this back to truth table format we get.
\(q_0\) |
\(q_1\) |
\(q_2=A \wedge B\) |
Count |
|---|---|---|---|
0 |
0 |
0 |
516 |
0 |
1 |
0 |
542 |
1 |
0 |
0 |
466 |
1 |
1 |
1 |
524 |
We replicated all four rows of the truth table with roughly equal probability. In reality, the circuit has a perfectly split probability. In any set of random tests, we won’t see the perfect split. If you flip a coin 4 times, you probably won’t get exactly 2 head and 2 tails.
Disjunction¶
The Disjunction is true when either of the two inputs are true. It’s truth table be given below.
A |
B |
\(A \vee B\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
We can build this circuit out of conjunctions and negations. Remember Demorgan’s law.
\( \begin{align} \neg ( A \vee B) = \neg A \vee \neg B \end{align} \)
Also, remember that double negatives cancel.
\( \begin{align} \neg \neg A = A \end{align} \)
We can put these together.
\( \begin{align} A \vee B =& \neg \neg (A \vee B) \\ =& \neg( \neg A \wedge \neg B) \end{align} \)
We need to apply the a negation to each input qubit. We also need to apply a negation to the result qubit after computing the conjunction. We want the final results to show the original inputs. To accomplish this, we undo the negations on the input qubits. This is important because we might need those qubits later in their original states for another gate.
We use \(q_0\) and \(q_1\) as \(A\) and \(B\). Then we put the result on \(q_2=A \vee B\).
#Make a Circuit
qc = QuantumCircuit(3,3)
#Add a CCX Gate
qc.h(0)
qc.h(1)
#Apply X to the inputs
qc.x(0)
qc.x(1)
qc.ccx(0,1,2)
#Undo input
qc.x(0)
qc.x(1)
#Negate result
qc.x(2)
#Measure out results
qc.barrier(range(0,3))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
The circuit is shown below.
The results are displayed by the simulator.
{'110': 528, '101': 492, '111': 515, '000': 513}
Converting this back to truth table format we get.
\(q_0\) |
\(q_1\) |
\(q_2=A \vee B\) |
Count |
|---|---|---|---|
0 |
0 |
0 |
513 |
0 |
1 |
1 |
528 |
1 |
0 |
1 |
492 |
1 |
1 |
1 |
515 |
We replicated all four rows of the truth table with roughly equal probability.
Conditional¶
The conditional or implies is true unless true implies false.
A |
B |
\(A \implies B\) |
|---|---|---|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
We know the definition of the conditional.
\( \begin{align} A \implies B = \neg A \vee B \end{align} \)
We just need to plug in the definition we already came up with for the disjunction.
\( \begin{align} A \implies B =& \neg A \vee B \\ =& \neg( \neg (\neg A) \wedge \neg B) \\ =& \neg( A \wedge \neg B) \\ \end{align} \)
We use \(q_0\) and \(q_1\) as \(A\) and \(B\). Then we put the result on \(q_2=A \implies B\).
#Make a Circuit
qc = QuantumCircuit(3,3)
#Add a CCX Gate
qc.h(0)
qc.h(1)
#Apply X to the inputs
qc.x(1)
qc.ccx(0,1,2)
#Undo input
qc.x(1)
#Negate result
qc.x(2)
#Measure out results
qc.barrier(range(0,3))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
The circuit is shown below.
The results are displayed by the simulator.
{'001': 512, '110': 502, '100': 513, '111': 521}
Converting this back to truth table format we get.
\(q_0\) |
\(q_1\) |
\(q_2=A \implies B\) |
Count |
|---|---|---|---|
0 |
0 |
1 |
513 |
0 |
1 |
1 |
502 |
1 |
0 |
0 |
512 |
1 |
1 |
1 |
521 |
We replicated all four rows of the truth table with roughly equal probability.
Exclusive Or¶
The exclusive or is true when either A or B is true, but not both.
A |
B |
\(A \oplus B\) |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
We can define the exclusive or using only conjunctions.
\( \begin{align} A \oplus B = \neg (A \wedge B) \wedge \neg ( \neg A \wedge \neg B) \end{align} \)
This has more conjunctions than we have seen before. We can’t compute all this using only one gate. We need working qubits. We will add extra qubits to store partial results. We will not measure these qubits. We want them to be true temporary qubits. We completely ignore their final values.
This example shows how important it is to undo out actions. We need to use the value of \(q_0\) multiple times. If we don’t result it after each use, our later computations will be wrong.
We will use 5 qubits.
\(q_0\) is for \(A\)
\(q_1\) is for \(B\)
\(q_2\) is for \(A \oplus B\)
\(q_3\) is for \(\neg (A \wedge B)\)
\(q_4\) is for \(\neg ( \neg A \wedge \neg B)\)
#Make a Circuit
qc = QuantumCircuit(5,3)
#Add a CCX Gate
qc.h(0)
qc.h(1)
#q_3 is for -(A and B)
qc.ccx(0,1,3)
qc.x(3)
#q4 is for -(-A wedge -B)
qc.x(0)
qc.x(1)
qc.ccx(0,1,4)
qc.x(4)#Not the result
qc.x(0)#undo action
qc.x(1)#undo action
#q2 is for q3 and q4
qc.ccx(3,4,2)
#Measure out results
qc.barrier(range(0,5))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
This is the most complex circuit so far.
The results are displayed by the simulator.
{'110': 520, '011': 511, '000': 499, '101': 518}
Converting this back to truth table format we get.
\(q_0\) |
\(q_1\) |
\(q_2=A \oplus B\) |
Count |
|---|---|---|---|
0 |
0 |
0 |
499 |
0 |
1 |
1 |
520 |
1 |
0 |
1 |
518 |
1 |
1 |
0 |
511 |
We replicated all four rows of the truth table with roughly equal probability. Notice that the temporary qubits don’t appear because they are not measured.
Bi-Conditional¶
The Bi-Conditional is the logical equivelance operator. It tells us if two values are equal.
A |
B |
\(A \iff B\) |
|---|---|---|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
This is the opposite of the exclusive or. We can just negate an exclusive or to create it.
\( \begin{align} A \iff B = \neg (A \oplus B) \end{align} \)
All we need to do for our circuit is throw an extra X Gate on the result qubit.
#Make a Circuit
qc = QuantumCircuit(5,3)
#Add a CCX Gate
qc.h(0)
qc.h(1)
#q_3 is for -(A and B)
qc.ccx(0,1,3)
qc.x(3)
#q4 is for -(-A wedge -B)
qc.x(0)
qc.x(1)
qc.ccx(0,1,4)
qc.x(4)#Not the result
qc.x(0)#undo action
qc.x(1)#undo action
#q2 is for q3 and q4
qc.ccx(3,4,2)
#Not the Final Result
qc.x(2)
#Measure out results
qc.barrier(range(0,5))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
The circuit is shown below.
The results match the Bi-Conditional operator.
{'111': 494, '100': 532, '010': 519, '001': 503}
Converting this back to truth table format we get.
\(q_0\) |
\(q_1\) |
\(q_2=A \iff B\) |
Count |
|---|---|---|---|
0 |
0 |
1 |
532 |
0 |
1 |
0 |
519 |
1 |
0 |
0 |
503 |
1 |
1 |
1 |
494 |
We replicated all four rows of the truth table with roughly equal probability.
Working Qubits¶
It is often the case that we need working qubits to compute a final value. In the pervious examples, we just threw these qubits away. That is not a very efficient use of them. It we are doing a long computation, we don’t want to make tons of extra wires if each are only used one time.
It is a better plan to rest any working qubits to \(\left| 0 \right>\) when we are done we them. Since very gave has an inverse, we can also undo our actions. The following circuit is a new version of the XOR gate. It works the same way as before, but clears all the working qubits.
We measure all 5 qubits just to see the working qubits are set back to zero when we are done.
#Make a Circuit
qc = QuantumCircuit(5,5)
#Add a CCX Gate
qc.h(0)
qc.h(1)
#q_3 is for -(A and B)
qc.ccx(0,1,3)
qc.x(3)
#q4 is for -(-A wedge -B)
qc.x(0)
qc.x(1)
qc.ccx(0,1,4)
qc.x(4)#Not the result
qc.x(0)#undo action
qc.x(1)#undo action
#q2 is for q3 and q4
qc.ccx(3,4,2)
#Clear q3 by doing gates backwards
qc.x(3)
qc.ccx(0,1,3)
#Clear q4 by doing gates backwards
qc.x(1)#undo action
qc.x(0)#undo action
qc.x(4)#Not the result
qc.ccx(0,1,4)
qc.x(1)
qc.x(0)
#Measure out results
qc.barrier(range(0,5))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
qc.measure(3,3)
qc.measure(4,4)
The circuit is much bigger, but this component would fit better into a larger circuit.
Notice that the first two qubits always measure 0. Nothing we do effected their outcome because we always undid our actions.
{'00011': 491, '00101': 505, '00000': 553, '00110': 499}
This is a critcal skill to keep the number of qubits small during our computation. Our Quantum Computer will only have a certain number of qubits available for use. We can’t create infinite temporary wires.