April 11, 2016

CCNOT on a Feyman's quantum computer

I finally managed to publish this Mathematica notebook: a work I did back in 2012[1]. The course where I had the occasion to do this work (Probabilistic methods), was mostly focused on foundation of probability theory and geometrical interpretation of statistics, but Diego de Falco <3, our Prof. arranged a few lectures on qubits. For the laboratory, I did a simulation of a universal quantum gate, the CCNOT, for which I was under the supervision of Dario Tamascelli <3. To make this project exciting, I had to model the gate on a particular kind of quantum computer: the Feynman's Quantum Mechanical Computer. Diego once told us that Gianni Degli Antoni used to leave papers - that he thought might be interesting - in the mail boxes of his colleagues, and so Diego did with us, giving from time to time a few articles from high quality journals. GDA passed away a few days ago. I never had the chance to have a real conversation with him, but I feel I have been influenced by him, at least indirectly. This post is dedicated to his memory.

CCNOT is a pretty  important gate: it is universal for quantum computation (i.e., you can express all the other quantum gates and thus quantum circuits using only CCNOT gates). The "common shape" for a CCNOT matrix should be this:

$$M= \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,1,0,0 \\
0,0,0,0,0,0,0,1 \\
0,0,0,0,0,0,1,0 \\
\end{bmatrix} $$

The matrix above corresponds to a CCNOT the circuit model of quantum computation... but writing the simulation for the physical realization of the gate.. means something different. The matrix we are going to compose is the Hamiltonian for a physical system implementing the logical gate.  You can think of a gate as a controlled evolution over time of our physical system, and our aim is to simulate one.


 Quantum mechanical computer

For this work I spent plenty of times on the much quoted paper Quantum Mechanical Computer. Reading this and similar articles you might realize that the Feynman's model was studied to:
  • understand how small can we get with computers  
  • understand the minimum cost for performing a computation
  • have intellectual exploration / fun (see bottom of the page)
  • ultimately, simulate quantum mechanics efficiently with a computer.
At that time, (1985) was already known that CCNOT was universal for classical computation (if you don't believe me, see how CCNOT resemble a NAND, and try to obtain one from another), and he starts the article creating an Half Adder and a Full Adder. Then, he show how to implement this gate with quantum mechanics, (focusing on the fact that the computation is reversible), and then deriving the Hamiltonian for a system of particles that can used to model such system physically. He start with to operators ($a$ and $a^*$)for turning on and off a qubits.

In the further pages he show how to build the Hamiltonian $H$ from scratch for a quantum mechanical system which can represent a logical (hermitian) operator $M$ defined as the sequential combination of the logical gates $A_n..A_2A_1$. Setting $\phi_0$ as initial state, you have that the state of the system at time $t$ is:

$$\phi_t = e^{-iHt}\phi_0$$.
or, at a "higher level"
$$\phi_{out} = M\phi_{in}$$.
Where $\phi_{in}$ is the input of our computation and $\phi_{out}$ is the output.

He show how to rewrite the Hamiltonian of the whole system using only those $A_i$ matrices, and an additional chain of $k$ atoms/qubits/spin $1/2$ systems, which act as a sort of program counter. You can think of this chain as an electron moving from one site to another. If you find the electron at position $j$, you are sure that the operation $A_j...A_2A_1$ has been computed. More or less, is the movement of the electron along the spin chain ( that generate the electromagnetic field that) does the actual computation on the other qubits.

Rephrased, he shows how to create the Hamiltonian for a set of a two level systems which evolves according to a logical set of given gates.

That's exactly what we are going to do: compute (half symbolically, and half numerically, when needed), the Hamiltonian for a quantum physical system that computes logically our logical CCNOT gate. We start from scratch, by composing $\mathbb{C}^2$ system with successive tensor products. Sounds like a supercazzola but is not. (I remember I struggled a lot :D)

The article continue taking into consideration physical imperfection of the system and further optimization, but we got the gist.


Quantum CCNOT for fun and profit:

Everything is for fun and profit. 

Unfortunately, the notebook I made is in Italian, but if you read it, you might recognize the the following steps:
  1. In principio era l'algebra di Spin $1/2$ I need space. I start by defining the "home" for the most basic bricks of our system: the qubit (a unitary vector in $\mathbb{C}^2$), and the space of all the unitary operation that we can do on on such vector: a space spanned by the Pauli's matrices with the identity.  Commutation laws between these operators are tested.
  2. La base computazionale. We know that a qubit is a vector in $\mathbb{C}^2$. By which base is the space spanned? Our computational base of choice is the $z$ axes of the Bloch Sphere: the eigenvector of the $\sigma_z$ matrix.
  3. Un paio di osservazioni. We test some basic rules of quantum mechanics (i.e. observable are selfadjoint matrices, vectors are unitary, and so on..)
  4. Passiamo a k-spin: I use the previous single qubit operators, tensored with the identity to create the operator to move the excitation over the chain of spin. Practically, there's a function $\Sigma$ which has this parameters:
    1. length of the chain
    2. matrices  $k$ to apply
    3. position in the the matrix
  5. Una parentesi: costruzione della base computazionale: Many complex thing to have a (messy, not canonical) base. It is obtained by the lexicographic order of the possible combination of $\left\{ -1, +1\right\}^s$ where $s$ is the dimension of our system. We then verify the operation of the previous matrix on the basis vectors.
  6. Operazioni $\Sigma_{+}$ e $\Sigma_{-}$: we create (and test) the operators for tuning on and off the qubits of our chain. Composing two of those matrices, we can "move" an excitation along the spin. w00t w00t!
  7. Riduzione dimensionale del clock: This was subtle (for me). Since we know that each physical entity that commutes with the Hamiltonian is a conserved quantity, we can consider only operations under a proper subspace of the original space. This space is made by the spin-up qubit of the chain, and has dimension 1 ( there's is only one spin-up qubit at a time).
    1. Diagonalizzazione della matrice. Exploiting spectral theorem for fun and profit. I diagonalize my matrix to improve the efficiency of the calculation of the matrix exponentiation. (i.e. it's easier to exponentiate diagonal matrices)
    2. La matrice C$^n$NOT: CNOT and C$^n$NOT's matrix's "logical form".
    3. Creazione del CNOT: Here we build the CNOT's Hamiltonian according to the scheme on the paper: [Fig 8]. 
    4. Creazione degli stati iniziali e finali. Creation of the initial and final state of the computation (that is: the initial qubit given as input, the initial configuration of the spin's chain as $|1>$, and the final configuration for the spin chain, with only the qubit, the last one, in a spin up position.
    5. Esempio di esecuzione del CNOT: Execution of the CNOT through the evolution of it's Hemiltonian (diagonalized and non-diagonalized)
    6. Verifico graficamente che i due risultati siano uguali, ... Here we can see that the evolution of the CNOT and the diagonalized version of the CNOT is the same. 
    7. Creazione del CCNOT Creation of CCNOT's Hamiltonian. I found helpful the paper  "Grover's algorithm on a Feynman computer. ", made by - what a coincidence -  by Diego and Dario. :D
    8. Creazione degli stati iniziali e finali. As before.
    9. Execution of the CCNOT trhought the evolutions of it's Hemiltonian with the diagonalized and non-diagonalized matrix.
    For CNOT and CCNOT, in my notebook you can find a graph showing how evolve the probability of finding a $1$ in the $k$-th position/qubit along the spin's chain. You may notice that you'll never be 100% sure the computation has terminated (lol). Green peaks in the graphs are the final states. As you can see, letting time pass, our system evolves, eventually reaching the green state with high probability: it means that if we make a "lecture" and we find a $1$ in the last position of the program counter, we are sure the computation has been done. 



      If you always wanted to see concretely what does it mean when people say "quantum computer does not have only $0$ and $1$ but all the possibile numbers between them", take this simulation and start the qubits with non-basis vectors :)



      Even if the article does not involve "advanced" mathematics, Diego told me that sometimes he still read it: it happened multiple time that he spot a new meaning reading "between the line" and spot new meaning, ideas, and so on. And so I did. I find this article inspiring because mathematics and imagination are always interleaved: each thing Feynman is able to imagine is stated formally immediately thereafter.

      "Finalmente lo farò" ... I had in draft this post from 2012!

      Whoops! I forgot:

      Feynman writes - regarding the idea of using atoms to store information -  "Such nonsense is very entertaining for professors like me". When I hear questions like: "but why do we do quantum computers? what is the real advantage over classical computation/cryptography?"[2], I think of that sentence, and then the answer is clear - and is always the same - "Because we can".

      Thanks Antonio Miti for the review! (and Happy Birthday to him!)

      [1] Time files!!!.
      [2] It happened that recently I heard an important and respected scientist/mathematician doing this question to a quantum colleagues of her. I am no-one to judge what happened, but I was pretty puzzled by the sole fact that a mathematician could ask a question as such. Mathematicians questioning the utility of other sciences, lol...