Classical Gates
Contents
Classical Gates¶
Warning
This page is not yet finished/polished.
We’ve discussed a number of quantum gates and even described some subroutines which you can build out of quantum gates. But suppose instead we want to build a quantum circuit which implements a classical function - say some python function you’ve written.
Q: Why is this an interesting question?
Well, first we might want to know if a quantum computer is, at least, as powerful as a classical computer. Naively, you might think this is completely obvious but there is an important limitation to quantum computers which don’t exist for classical computers: quantum computers have to be reversible while classical computers don’t.
Secondly, suppose we have a classical python function \(f(x)\) which can take any number from \(0\) to \(2^{100}\). Classically, it would be impossible to run your function on all those numbers. If you had a set of quantum gates which was implementing \(f\) though, you could take \(\sum_i |i\rangle\) (generated by Hadamards on \(|0...0\rangle\)) and then generate \(\sum_i |f(i)\rangle\) which is a linear superposition over \(2^{100}\) function evaluations. Unfortunately, this state by itself isn’t useful. If we were to measure now we would just got a random value of \(f(x)\) (easy to get classically also by just running \(f\) on a random \(x\)). But, maybe there are some situations where we can post-process this state which has all \(2^{100}\) values of \(f\) in it and do something.
<– Aside: This single fact makes quantum mechanics look pretty powerful. Suppose that I have a function \(f\) I want to compute. In the time that classically I can do \(f(0)\), in quantum mechanics I can get a superposition \(\sum_i f(i)\). It’s as if I did all the calculations in parallel! But what happens if I measure the system now? –>
Reversible Classical Circuits¶
In this section, we want to learn how to take a python function and generate a quantum circuit for it.
If I have a python function, the first thing I should do is convert it to a classical circuit. In particular, I want the circuit to only use nand gates. Any classical python function can be made out of nand gates because nand gates are universal. If the python function can run in time \(O(T)\) the number of NAND gates you need is going to be \(O(T \log T)\).
A nand gate (not-and) is a two bit gate which outputs 0 if the two inputs are 1. Otherwise it outputs 0 - i.e.
0 NAND 0: 1
0 NAND 1: 1
1 NAND 0: 1
1 NAND 1: 0
Unfortunately, nand gates aren’t reversible. If I told you the output of a nand-gate is 1, you don’t know whether the two inputs were 0,0 or 0,1 or 1,0. Consequently, a circuit made out of nand gates are also not going to be reversible.
To start fixing this problem, we are going to replace the nand gate with a gate that’s reversible. We are going to use a control-control-not (also called a toffeli gate). The control-not does nothing on the first two wires. The not happens on the third wire if the first two wires are 1 - i.e.
0 0 a: 0 0 a
0 1 a: 0 1 a
1 0 a: 1 0 a
1 1 a: 1 1 not a
Grading
The NAND gate has two inputs and one output. The toffeli has three inputs and three outputs. Choose two toffeli inputs and (either a \(|0\rangle or \)|1\rangle$ to map to (which order?) the three inputs of the toffeli so that one of the toffeli outputs is a NAND b.
The first thing we are going to do is replace each NAND gate with toffeli gates.
Consider when we do this. We then get
This isn’t quite what we want. Ideally we wanted \( |x\rangle \rightarrow |f(x)\rangle\). That’s not possible though. Imagine we had an adding circuit. If we ended up with \(|2\rangle |3\rangle \rightarrow |5\rangle\) we couldn’t reverse the \(|5\rangle\). The most we could hope for is something like \(|2\rangle |3\rangle |0\rangle \rightarrow |2\rangle|3\rangle |5\rangle\) or more generically \(|x\rangle|0\rangle \rightarrow |x\rangle |f(x)\rangle\). We will (essentially) be able to get this latter thing. If we are using \(k\) NAND gates and \(f(x)\) is written on \(p\) bits and \(|x\rangle\) is written on \(b\) bits, we will end up with
$\(|x\rangle |0^k\rangle |0^p\rangle \rightarrow |x\rangle |0^k\rangle |f(x)\rangle\)$.
There are an intermediate \(k\) wires that start and end 0 (and so can be re-used).
The next step is to take a unitary \(U\) which acts on \(b+k\) bits and gives \(U|x\rangle|0\rangle = |junk\rangle|f(x)\rangle\) and fix it up.
The first step is to figure out how to get
The second step is to figure out how to get
Notice that to accomplish this we can essentially ignore the last register. The we really need to draw a circuit which takes