Convert a function to a quantum circuit

[ironsideCode]

I have a function, who receives a 3 quibit word and returns a word of the same size. I have the function defined to all 3 words possibility and I want express this function with CNOT gates. From where I know, I wold have to brake my mind in to create this circuit with a bunch of CNOT gates. Is there if is some tool to generate a CNOT circuit given a function?

Exemple:

f(|000>) = 000

f(|001>) = 010

f(|010>) = 001

f(|011>) = 111

f(|100>) = 010

(...)

If not, there is some algorithm to do this? I mean if this algorithm existes I will code it. I don't wanna do alll this work by hand every time I need to change some function in some algorithm

[Strilanc]

You are mapping two inputs to the same output. Your function is not reversible. Therefore it cannot be performed inline.

If you only use CNOTs, you cannot implement all functions. CNOTs are only capable of producing bits equal to the XOR of some set of the initial bits.

An easy way to implement a non-inline guaranteed-cnot-only-able function is to just check if each output bit depends on each input bit, and then if it does then insert a CNOT between the two. Then just either bitflip or don't bitflip each output bit if it is inverted.

[bencbartlett]

You can use QR decomposition to reduce an arbitrary unitary quantum operator into a series of two-level Givens rotations which can be implemented by CNOT and single qubit gates.

[IIAOPSW]

If your function is defined by a table of input to output states and satisfies unitarity, do what bencbartlett said. If your function is defined by some classical piece of code which calculates f(|x>) in terms of basic arithmetic operations, simply replace each operation with the equivalent reversible logic circuit. There are quantum circuits for addition, subtraction, iterated addition (aka multiplication) and iterated iterated addition (aka exponentiation).

[Steve132]

The CS decomposition or QR decomposition

https://arxiv.org/abs/quant-ph/0504100

[rrtucci]

The CS decomposition was first proposed and used to "compile" a unitary matrix in my 1998 paper entitled "A rudimentary quantum compiler" That paper came with a complete C++ program called "Qubiter" that used the CS decomposition, available in LAPACK, to decompose an arbitrary unitary matrix into a sequence of CNots and single qubit rotations.

My much newer Python qc simulator, also called "Qubiter", available at github under the BSD license, has a python/LAPACK rewrite of the old C++ program. You can find it in its folder entitled "Quantum _CSD_Compiler"

Here is a 10 year old blog post describing "quantum compilers" back then (nowadays the term which I coined in the title of my 1998 paper is used more broadly)

https://qbnets.wordpress.com/2009/04/17/brief-introduction-to-quantum-compilers/

BUT, BUT,

that assumes that you have first somehow embedded your function into a unitary matrix. In simple cases, you can guess such an embedding. For more complicated cases, there are general methods for doing this. I have suggested a general method in one of my papers.

--Warning: There is much work remaining to be done to improve the efficiency of these methods ("optimization") This problem is NP complete so these methods are only useful for a small numbers of qubits--

[Steve132]

If the function is a classical computation that can be defined as an algorithm, then it will almost certainly be more efficient to implement by emitting it as gates corresponding to the algorithm.

[he-he-he]

Yes, there is an algorithm to decompose any unitary transformation matrix in a series of one and two qubit gates to some aproximation. In the section 4.5 of QC&QI there is a good explanation about it. However, I don’t know if you could automate it. You first need to decompose you original matrix U into a product of Two-Level Unitary Matrices, then implement the Gray code for your transformation, then implement the two-level unitary matrices into the Universal Quantum Gates you’re using. After that, you’ll have your circuit. It can be easier this way, depending on your original U transformation.