Classical logics visualized with BraKetVue
Truth tables, reversibility and a gate (pun totally intended) to quantum computing.
I’ve seen things you wouldn’t believe. CNOT glitter near the Toffoli gate.
Logic operations are basic building block of any more complicated computing. They are being used as base CPU instructions, and in high-level programming language.
We will use matrix notation for these logical operations - partly to show truth tables in a nice and interactive way, and partly to relate it to physics (reversible computation and quantum computing).
We start with 0 (for false) and 1 (for true).
The simplest operation is negation. Depending on a language, we write it differently:
not a in Python!a in JavaScriptIf we want to explicitly define, we need to define its value for each input:
\[0 \mapsto 1 \hspace{1cm} 1 \mapsto 0\] It reads “0 maps to 1, 1 maps to 0”. We can write the same thing using a matrix:
In this matrix all values are either 1 (red circles) or 0 (well, nothing). When you mouseover an input column, you will see the output.
Conjunction (\(a \wedge b\) in maths, a and b in Python, a && b in JavaScript) is true if and only if both conditions are true:
\[00 \mapsto 0 \hspace{1cm} 01 \mapsto 0 \hspace{1cm} 10 \mapsto 0 \hspace{1cm} 11 \mapsto 1\]
Alternative (\(a \vee b\) in maths, a or b in Python, a || b in JavaScript) is true if at least one condition is true.
\[00 \mapsto 0 \hspace{1cm} 01 \mapsto 1 \hspace{1cm} 10 \mapsto 1 \hspace{1cm} 11 \mapsto 1\]
Exclusive OR (\(a \oplus b\) in maths, a ^ b in Python and JavaScript) means either a or b, and is true if exactly one condition is true.
\[00 \mapsto 0 \hspace{1cm} 01 \mapsto 1 \hspace{1cm} 10 \mapsto 1 \hspace{1cm} 11 \mapsto 0\]
NAND stands for non-AND, \(\neg (a \wedge b)\).
\[00 \mapsto 1 \hspace{1cm} 01 \mapsto 1 \hspace{1cm} 10 \mapsto 1 \hspace{1cm} 0 \mapsto 0\]
We rearely use it directly (in mathematics in programming we typically combine AND and NOT). At the same time, it is an universal logic gate, meaning that ALL other logic gates can be constructed out of it. It has a big meaning in the design of circuits.
There is one catch, though: we need to be able to use one output in a few inputs. If we want to write everything as matrices, we need to be explicit about the copy operation:
\[0 \mapsto 00 \hspace{1cm} 1 \mapsto 11\]
If we want to be explicit about other operations, we can take the first or the second value, discarding the other.
\[00 \mapsto 0 \hspace{1cm} 01 \mapsto 0 \hspace{1cm} 10 \mapsto 1 \hspace{1cm} 11 \mapsto 1\]
\[00 \mapsto 0 \hspace{1cm} 01 \mapsto 1 \hspace{1cm} 10 \mapsto 0 \hspace{1cm} 11 \mapsto 1\]
We may want to change the order of variables:
\[00 \mapsto 00 \hspace{1cm} 01 \mapsto 10 \hspace{1cm} 10 \mapsto 01 \hspace{1cm} 11 \mapsto 11\]
Or, we may want to forget:
\[0 \mapsto 0 \hspace{1cm} 1 \mapsto 0\]
And for the sake of complentess, identity, or an operation that does nothing.
Both NOT are SWAP are reversible - just apply them twice, and you get your original input.
In general, these operations are not reversible. If we know one bit there is no way to guess two bits. For the logic gates that maintain the number of bits, both NOT are SWAP are reversible - just apply them twice, and you get your original input. It is not the general case though - even if we have the same number of bits, we may have lost all information - as it happends with ERASE.
So, there is a different question - can we make a gate reversible by adding extra bits to its output? Let’s check out! For operations FIRST and SECOND it is simple - we just add the missing bit. How about XOR?
Mouseover the columns - you see that for the first output bit we get the same value as in the original XOR. For the second output bit, there are possible options.
To make logic operation reversible, we need to have exactly one dot in each column and each row. That is, we not only guarantee that for each input we get a single, deterministic output, but also that for each output we can get a single, deterministic input.
Can you eliminate some values, so that we get the right combination? Think of it as playing some variant of Sudoku.
(HERE WE NEED SOME PAUSE OR ‘click to reveal’)
In fact, there are 4 different solutions. On the them is a CNOT gate (controlled-NOT) with
So, can we reverse AND by adding ancilla bits?
Well, the task is not harder… it is impossible. Let’s see why! For the output 1 we don’t need any extra information, we know that the input is 11. Sounds good? Not so! For 0 there are three possible possibilities 00, 01, 11, and we cannot encode them in a single bit.
We can give up…. or add one more ancilla bit. So, it’s time for another Sudoku:
(This example broken, as we need to change the first bit to maintain balance. It requires other adjustments. Maybe actually this need to stay, but make add more step. This actually looks didactic.)
There are much more possiblities.
(I need to think about the best / most intuitive solution.)
This note is created with Learn more about using Distill for R Markdown.
As of now, source code is at github.com/stared/bra-ket-vue-art.
This particualr post inspired by Kronecker Product In Circuits by Lei Mao and Quantum Entanglement and Superdense Coding by Victory Omole.