This post summarizes things I've learned over the 8th week of my Quantum Computing Ultralearning challenge, and should be considered as study notes instead of a fully-explained-and-very-detailed article since other experts have done that work (see references).
Classical universal gates #
In classical computer science, a universal gate is a gate that you can use to implement any Boolean function without the need for other gate types. Below are a few universal gates:
- NOR gate: only gives 1 when both inputs are 0.
Example: constructing an XOR gate from NOR gates [4].
- NAND gate: is the inverted AND gate, i.e. only gives 0 when both inputs are 1.
Example: constructing an OR gate from NAND gates [5].
Now, if we add the reversibility to the requirements of our circuit, the gates above won't work. For example, you cannot reverse the NOR gate when its output is 0, since the inputs might be any of (0, 1), (1, 0), or (1, 1).
Thus, we need special universal reversible logic gates, and one of them is the Toffoli gate:
- Operates on
3 bits: 2 inputs and 1 output. - If both the two input bits are 1, it
inverts the output bit, otherwise, nothing happens. - In other words, it maps 3 bits \( \{a, b, c\} \) to \( \{a, b, c \oplus (a \land b) \} \).
- Other names: controlled-controlled-not (CCNOT) gate or Deutsch \(D ( \pi / 2 )\) gate.
- Symbol, truth table, and permutation matrix form [6]:
Quantum universal gates #
In quantum computation, using only the Toffoli gate is not enough for universality, thus we need to combine the Toffoli gate with the singe-qubit Hadamard gate. Illustration from [1]:
How do we build the quantum Toffoli gate using only the basic quantum gates?
Here is an approach from [1], which uses only the H, T, and CNOT gates:
Programming #
https://colab.research.google.com/drive/1zUJZUEiMeZsbXCCs5o9JrRONvomeX62W?usp=sharing
References #
1. Quantum computing for the very curious - Part III: Universal quantum computing
2. https://quantumai.google/cirq/tutorials/basics#unitary_matrices_and_decompositions
3. https://en.wikipedia.org/wiki/Logic_gate#Universal_logic_gates
4. https://en.wikipedia.org/wiki/NOR_logic
5. https://en.wikipedia.org/wiki/NAND_logic
6. https://en.wikipedia.org/wiki/Toffoli_gate
Since you've made it this far, sharing this article on your favorite social media network would be highly appreciated!
For feedback, ping me on Twitter.
All the information on this blog are my own opinions and do NOT represent the views or opinions of any of my past or current employers.
Published