1
$\begingroup$

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): Toffoli gate program using IBM's Quantum Experience

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

$\endgroup$
2
$\begingroup$

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:

Step 1

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

Step 2

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

Step 3

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...:

Done

(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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.