We've already met the quantum equivalent of the classic NOT gate: the X gate. 3SAT requires the logical AND and logical OR of variables, so we will need the quantum equivalent of the logical AND and logical OR to formulate 3SAT in a quantum computer. All quantum gates are reversible, which was no problem for translating the classic NOT gate directly into a single quantum gate, as the classic NOT gate is itself reversible. To reverse the classic NOT gate, simply apply it twice to get back to where you started. The same goes for the quantum gate.
However, the classic OR gate and the classic AND gate are not reversible. To see this, we can draw out their truth tables:
|
a |
b | a AND b |
|
0 |
0 | 0 |
|
0 |
1 | 0 |
|
1 |
0 | 0 |
|
1 |
1 |
1 |
And the truth table for the OR gate is as follows:
|
a |
b | a OR b |
|
0 |
0 | 0 |
|
0 |
1 | 1 |
|
1 |
0 | 1 |
|
1 |
1 | 1 |
We can see that in the case of the classic AND gate, the output 0 could have resulted from bits a and b being 00, 01, or 10 respectively, so given only the output information, it is impossible to uniquely determine the input (unless the output is 1). We can see that for the OR gate, the output 1 could have resulted from bits a and b being 01, 10, or 11. This means, that given only the output information, it is impossible to uniquely determine the input (unless the input is 0). Neither of these functions is fully reversible and thus we would have to extend them to be, so we translate them into their quantum equivalents. The way we will do this is to introduce an additional third input.