Student Post: Transforming Graphs

Today’s mission was to transform K6 into another member of the Petersen Family of graphs using a Δ-Y transform of K6 by identifying 3 vertices and 3 edges connecting them pair-wise, deleting those edges, and adding a new vertex connected to all three points. My starting point for this is my OpenSCAD code from making  K6 . Want I wanted to do was delete the edges in red and add a new vertex in the center and in blue add three new edges to connect the new vertex with the three vertices whose edges I pairwise deleted. The picture below nicely shows the Δ-Y transform of K6 that would be taking place.

My current issue is this: the way my code is set up, I have all my edges being created by a for loop.

I got stuck trying to figure out how to easily delete three edges after they had already been made. I’m going to talk with Dr. Taalman to see if there is a quick fix or how I should efficiently writing code to make this transform happen.

Until next time,

Hannah Critchfield

Disclaimer

The current posting is considered to be a simple example application of the theorems and mathematics discussed in the last post, The Basic Mathematics of Quantum Computing. The information here will be hard to grasp unless you have covered the operations specified previously. For this reason this post, and most postings following this, will be regarded as a continuation.

Background

Deutsch’s Algorithm is the one of the most representable quantum algorithms. This algorithm was developed in order to illustrate the processing of qubit input and the difference in performance when compared to a classical Turing machine. This algorithm covers the testing of black box functions, or modules of which the operations performed upon the input at the time of execution isn’t known.

In this fashion, in order to determine how the black box executes we would have to test multiple inputs and examine patterns in the outputs. However, for this example we limit the possibilities used to only four boolean functions, two being balanced and two constant.

To clarify, a constant function has the same Boolean output for every input. While a balanced function yields as many 0s as it does 1s. We define our functions as such,

$f(0) = f(1) -> constant ->$ Both inputs of 0 and 1 map to the output 0 or 1 alike.

$f(0) = f(1) -> balanced ->$ Both inputs of 0 and 1 map to the opposite output.

In the illustration below, functions one and three are constant, while two and four are balanced.

Normally, with a classic implementation we would need to test at least two inputs to determine if the function inside the black box was constant or balanced. Alternatively, using the principles of superposition on qubits we can evaluate both inputs at once to effectively cut our computational complexity in half.

The computational operations saved by using this algorithm may seem negligible, but when expanded into an algorithmic form the ability to evaluate data to this respect can have a quadratic decrease on the constant running time of a system.

Complexities

Before learning about the procedure of the algorithm, it’s important to review the mathematics needed in order to complete this excersise. If you recall from the last post we covered something known as the Hadarmad matrix, which is the quantum gate used to tranform a qubit into the state of superposition.

Recall:  $= \left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{array}\right)$.

Again this is done through matrix tensor multiplication.

It is important to remember that every qubit in any current state can be evaulated as a column vector made up of $2^n$ probabilites of possible occupying states. These column vectors representing the possible state positions of the qubits are represented as complex numbers where $\left|\varphi\right> = [C_1, C_2, .... C_N]$ and each indicy belongs to the domain of complex numbers, such that $a_{i1} \in \mathbb{C}$.

Lets review the tensor multiplication of two qubits that contain real number probabilites. Such that $\left|0\right>$  has a 100% to occupy state 0 and $\left|1\right>$ has a 100% chance to occupy state 1. Next we apply the tensor product:

$\left|0\right> \otimes \left|1\right> = \left(\begin{array}{c} 1\\ 0\end{array}\right) \otimes \left(\begin{array}{c} 0\\ 1\end{array}\right) = \left|01\right> = \left(\begin{array}{c} 0\\ 1\\0\\0\end{array}\right)$

Once evaulated, he resulting qubit has four possible states but always has a 100% probabilty to be in the state 01.

Following this procedure we can apply the same operations between $\left|0\right>$ and the quantum gate H. Such that,

$H \otimes \left|0\right> = \left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{array}\right) \left(\begin{array}{c} 1\\ 0\end{array}\right) = \frac{\left|0\right> + \left|1\right>}{\sqrt{2}} = \left(\begin{array}{c} \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right)$

Hence, the resulting qubit has a complex probability of 50% being in state 0 and 50% of being in state 1. As shown previoulsy, if we wanted to evaulate these as real number probabilites we take the sqaure of the complex numbers.

Now that we have identified a basis for transitioning qubits into a state of superposition we are ready to evaulate Deutch’s Algorithm. Recall, this is possible because of the qubits ability to occupy both testable inputs at once.

Deutsch’s Algorithm

As we recognized, this algorithm consists of four black box functions with an input of one or zero and an output one or of zero. Again, if $f(0) \neq f(1), \textrm{then} f(x)$ is balanced, otherwise if $f(0) = f(1)$ is constant.

Now consider  the diagram below. First, notice that this graphic is a quantum circuit in which the two qubit inputs on the left are manipulated through the quantum gates denoted by H. They are then passed to the $U_f$ function which is our black box test.

From the diagram above we can see that by applying two qubits as the inputs and subsequently turning them both in a superposition, the value of the qubits becomes negligible as they have equal probability of being in both states.

We now explain the qubit state $\left|\varphi_n\right>$ at each stage of the algorithm.

At  $\left|\varphi_0\right>$  we start with the initial separated qubit inputs  $\left|0 \right>, \left|1 \right>$

Where $\left|\varphi_0\right> = \left|0,1\right>$

Next we examine state $\left|\varphi_1\right>$

First we must apply the matrix H to both our qubits, where

$H \otimes \left|0\right> = \frac{\left|0\right> + \left|1\right>}{\sqrt{2}}$  and  $H \otimes \left|1\right> = \frac{\left|0\right> - \left|1\right>}{\sqrt{2}}.$

Finally we tensor together our two superposition qubits to achieve,

$\left|\varphi_1\right> = H\left|0\right> \otimes H\left|1\right> = \frac{\left|0\right> + \left|1\right>}{ \sqrt{2}} \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}}$.

We use the tensor product to combine these two states to obtain the result $\left|\varphi_1\right> = \frac{\left|00\right> - \left|01\right> + \left|10\right> - \left|11\right>}{2}$ .

Therefore the probability of qubit $\large{\left|\varphi_1\right> = \left(\begin{array}{c} \frac{1}{2}\\ \frac{-1}{2}\\ \frac{1}{2}\\ \frac{-1}{2} \end{array}\right)}$

This combined state can then be applied to our function as one input. We then evaualte the state of qubit $\left|\varphi_2\right>$ as the output after having been applied to the black box function.

Here notice that the sign of this output changes dependent on which function was applied during execution, such that

$\Large{\frac{(-1)^{f(0)} \left|0\right> + (-1)^{f(1)} \left|1\right>}{ \sqrt{2}} \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}}}.$.

From this expression we can see that depending on the values of $f(0), f(1)$ we can determine whether the function is balanced or constant. This is because a constant function always yields  $\left|0\right> + \left|1\right>$

while a balanced always yields  $\left|0\right> - \left|1\right>$ due to the change in sign.

Finally we can put this in terms of a piece wise function where the first qubit is the one that shows the attributes of the function and the second is the static transformation of the bottom qubit.

$\left|\varphi_2\right> = \begin{cases} (\pm 1) \frac{\left|0\right> + \left|1\right>}{ \sqrt{2}} \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}} & f = constant \\ (\pm 1) \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}} \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}} & f = balanced \end{cases}.$

Recall that because unitary, or its own inverse, we then effectively apply our last H to the top qubit in order to move it out of superposition for observation at $\left|\varphi_3\right>$and see the constraint on balanced or constant function.

We see this where $\left|\varphi_3\right> \begin{cases} (\pm 1) \left|0\right> \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}} & f = constant \\ (\pm 1) \left|1\right> \frac{\left|0\right> - \left|1\right>}{ \sqrt{2}} & f = balanced \end{cases} .$

For clarification, the top qubit is the one that was manipulated by the function and brought out of a state of superposition, while the bottom qubit stayed statically bound to superposition in order to preserve the systems level of decoherence.

While this algorithm is simple, it still gives a tangible example of the applications of qubit mathematics and quantum computation. This procedure was later proven to be useful in determining the contents of many block box functions and can be implemented in a variety of different ways. Unfortunately, I cannot delve into all of the specific applications, as there are many other topics that needed to be covered. However, if you are interested in learning more, an extension of Deutsch’s Algorithm is called the Deutsch-Jozsa Algorithm and can be applied to a much larger domain of input. In fact Deutsch’s Algorithm serves as a basis for many algorithms in quantum computing that serve to expand upon evaluating multiple outputs at once.

Written By: Mitchell Mesecher

Citations:

Quantum Computing for Computer Scientists, Noson S. Yanofsky

Student Post: Circle Selection

For the past week or so I was tasked with allowing the user to select a circle and then change the color of the circle when selected. Similarly when a point is a selected, change its color as well. In order to select a circle I calculated if there was a ray-plane intersection. I was able to use the ray-plane intersection because our circles are stored as a plane with the coefficients of the equation of the plane. I was able to get the selection of a circle correct. However, I have been unable to change the color of the circle and point. Originally when we were drawing our objects we looped over a list that contained them all and pulled the style from that list. I think the current issue is that I am not setting the style of the point/circle correctly so when the objects are being drawn as opposed to using the style of the node it is using the default style from the list. I believe that this will be an easy fix.

Until next week.