Is there a procedure for designing some quantum circuits?

[Haorong Wu]

TL;DR Summary

Given a transformation matrix, is there a procedure for designing a circuit for the matrix?

In Nielsen's book, the chapter of quantum circuits does not describe explicitly any procedures to design a circuit.

For example, given the matrix of Fredkin gate, $\begin{bmatrix} 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 & 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 & 1 \end{bmatrix}$, I think, the first step is to identify the transformation for every qubit. In this case, $\left | x_1 , x_2 , x_3 \right> \rightarrow \left | x_1, \bar x_1 x_2 \oplus x_1 x_3 , \bar x _1 x_3 \oplus x_1 x_2 \right >$. Then how can I implement this transformation? Of course, according to the hint after the exercise, I know it can be designed by 3 controlled-swap gates.

However, in another exercise, the matrix of a partial cyclic permutation operation is $\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 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 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix}$. Again, I calculated the transformation for every qubit which is $\left | x_1 , x_2 , x_3 \right> \rightarrow \left | x_1 \oplus x_2 x_3 , x_2 \oplus x_3, \bar x _3 \oplus x_1 x_2 x_3 \oplus \bar x _1 \bar x _2 \bar x _3 \right >$. Then, without a hint, I can't figure out how to implement it, especially on the #### qubit.

So, is my procedure suitable? Or is there a better procedure I can follow? This kind of exercises give me a headache. I've tried them all day. Thanks for reading.

 

[jedishrfu]

I couldn't find anything on a "boolean algebra" for quantum computing but did find this presentation:

https://people.maths.bris.ac.uk/~csxam/presentations/talk-bfa.pdf
and this short discussion on Quantum logic:

http://math-it.org/Quantum/survey/logic.html
The basis for quantum computation is not Boolean logic, but quantum logic. To date, there is still no appropriate quantum-logical calculus comparable to the classical calculus based on Boolean algebra. There are at least two essential differences between quantum and Boolean logic. One is that any quantum gate has to be reversible, i.e., input and output must always correspond uniquely to one another. In particular, the number of input and output qubits have to be equal. This is different than in the Boolean case, where most gates have two input bits and only one output bit. In fact, all basic binary operations of Boolean algebra (∧, ∨, ¬, XOR, NAND, NOR, ...) are 2-1 valued, which implies that they are not reversible: in fact, since 1 ∧ 0 = 0 ∧ 1 = 0 ∧ 0 = 0, you cannot deduce from the result “0” which values the input bits have had.3

Another difference between quantum and Boolean logic is that quantum gates can transform a qubit basis, say {|0>, |1>}, to another, for instance {|0> + |1>, |0> - |1>}, just as a vector basis can be changed by reflections or rotations. This property is impossible in Boolean logic, where any operation transforms to one of the two values 0 or 1. In other words, the basis is never changed in Boolean logic.

Years ago when I first learned digital electronics, I learned to convert truth tables to boolean expressions, reduce them using boolean algebra rules and then transformed the reduced expression into a simple circuit. I've not seen something similar in Quantum Computing perhaps because of the nature of the game.

One last reference :

http://oxfordquantum.org/

 

[Truecrimson]

This problem in general is known as quantum gate/circuit synthesis, or quantum compiling. This paper from 2004 that I found has been cited almost three hundred times.

As for your questions, 1) Isn't the Fredkin gate already a controlled SWAP? What are the sets of gates allowed for your compiling? 2) Can you find a circuit for just the cyclic permutation? The quantum Fourier transform turns the permutation into a phase gate on each individual qubit.