How do I figure out how to combine simpler quantum gates to create the gate I want?

Question

I want to create other quantum gates from the basic building blocks of a universal quantum gate set. I've been playing with IBM's quantum computing interface for that.

I wanted to create a Toffoli gate, which I managed to in the end, but part of it was by trial and error. I want to create some other gates now, and I want to avoid the long arduous process of trial and error.

Is there a better way?

Is there also a way to how to construct the gate from the minimum number of gates necessary?

I'm going to add my work on the Toffoli here for anyone to see / critique.

% Matlab / Octave code
q=[1 0];
X=[0 1;1 0];
Y=[0 -1i; 1i 0];
Z=[1 0;0 -1];
H=[1 1;1 -1]/sqrt(2);
S = [1 0;0 1i];
St = [1 0;0 -1i];
C = [1 0 0 0;0 1 0 0; 0 0 0 1; 0 0 1 0];
Cgap = [1 0 0 0 0 0 0 0; 0 1 0 0 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 1 0];
T = [1 0; 0 exp(pi*1i/4)];
Tt = [1 0; 0 exp(-pi*1i/4)];
I = eye(2);
I2 = eye(4);
I3 = eye(8);

CS = kron(T,Tt)*C*kron(Tt,Tt)*C*kron(T,S);
CSt = kron(Tt,St)*C*kron(T,T)*C*kron(Tt,T);
CgapS = kron(T,kron(I,Tt))*Cgap*kron(Tt,kron(I,Tt))*Cgap*kron(T,kron(I,S));

Toffoli = kron(I2,H)*kron(I,CS)*kron(C,I)*kron(I,CSt)*kron(C,I)*CgapS*kron(I2, H)

Toffoli gate program using IBM's Quantum Experience (the two X gates on the very left are used to set the values of the qubits to 1; they can be removed to run the gate with 0 values):

The way I figured it out was I found some lecture notes with the gate expressed as seven building blocks, but I didn't have some of the blocks, so I constructed those by trial and error. Here's the pdf: https://inst.eecs.berkeley.edu/~cs191/fa07/lectures/lecture9_fa07.pdf

Answer 1

There are standard ways to approximate any unitary operation with just CNOTs, Hs, and Ts. In the specific case of the Toffoli gate you don't need something so general.

Start with the Toffoli gate:

Use a construction that relies on operations having a square root to cut the worst-case number of controls from 2 to 1:

Use a construction that moves controls off of arbitrary single-qubit operations and onto CNOTs:

Oh hey that looks kinda familiar ;)

Now simplify by sliding gates around so that some of them cancel. Zs can move over controls, but not over NOTs (but can hop over the space between two NOTs that undo each other). It's also useful to know how to move a CNOT over another CNOT's control by introducing a third CNOT. Hadamards cancel when paired, and turn Zs into Xs (and vice versa) when hopping since $HX = ZH$. Anyways, after some fiddling...:

(Note: $T = Z^{1/4}$ and $T^\dagger = Z^{-1/4}$)

You can confirm the circuit works by toying with it in Quirk.

These constructions are explained in more detail in textbooks such as Nielsen and Chuang. The 'moving controls' one is particularly tricky, because you have to find $A$, $B$, $C$ such that $ABC=I$ but $AXBXCe^{i\theta}=U$. Or you can read a few blog posts about making a controlled-by-every-other-wire NOT using $O(n)$ basic gates that also uses these constructions but explains them in more detail.