This week was largely spent on cleaning up my code for the Petersen graph and the graph of K₆ (also I changed how K₆ looks as a 3-D model completely). Since I am very new to OpenSCAD, my code was very length and a lot of it was unnecessary. I saved well over 40 lines in total between the two graph codes. Over spring break I hope to work on the other members of the Petersen family of graphs, now that I know how to speed up the process with for loops in OpenSCAD.

New K₆ Graph and Code

In last week’s post, the gif of K₆ was all over the place. There wasn’t much symmetry to the graph in my model of it. Dr. Taalman suggested I position the points around a circle, rather than just winging the coordinates. this resulted in a much better representation of K₆ (see gif below).

And here is the (much shorter) code that made the new representation of K₆! 

For the Petersen graph, I tidied up the code in the same fashion. The actual representation of it looks the same overall, just a bit bigger now that my code has a parameter section and due to the fact we are looking to print out these models.

Until next time,

Hannah Critchfield

This week I was tasked with trying to ‘highlight’ a circle if selected. Currently, I am struggling with how to calculate the intersection if a user selects an edge because a disk has three incoming edges in which the other endpoint is a point and thus was not able to complete this task. However, I was able to streamline some of the code for the tools that are currently available. Last week I added buttons to the screen which allowed the user to click on which tool they wanted as opposed to using the keyboard. However, in order to draw a circle the letter ‘C’ still needed to be clicked. One issue that I encountered with still using the key for the circle tool was that it changed the point editing tool to the circle tool indefinitely which resulted in no longer being able to drag points. Now the circle tool is a subclass of the point editing tool. The two different buttons for point and circle switch between the tool and thus we have returned to our functionality below I have included a picture of what the current tool bar looks like.  Next week, I will have it so when I user selects a circle it will change colors and also that when the user selects a point those will change a color before an object is drawn with them.

Until then,

Maddie Brower

Graphs can be a funny thing. When you say “graph”, some people will thing of a line or some other function in 2-D. Other people will think of marvelous planes and surfaces in 3-D. Fewer people will think of “standard” graph theory type graphs represented in 2-D. And even fewer people will think of those graph theory type graphs represented in 3-D. My goal is to change that.

Throughout the semester, I want to highlight the Y-Δ and Δ-Y transforms that allow you to go between graphs within the Petersen family of graphs. The names Y-Δ and Δ-Y are quite visual. In Y-Δ you are replacing 4 vertices that make a Y shape with 3 that make a triangle shape and in Δ-Y you are replacing 3 vertices that make a triangle shape with 4 that make a Y shape. Now, when the Petersen family of graphs are represented in 2-D, these Y-Δ and Δ-Y transforms are not quite apparent. I am hoping that representing these graphs in 3-D will make these transforms a bit clearer.

Since this is my first exposure to OpenSCAD (and really my first exposure to modeling something in 3-D all my own), I’m going to start off the semester by getting the Petersen family of graphs in 3-space and then go from there. This week we have the famous Petersen graph and K₆ being featured.

The Petersen Graph

Bringing the Petersen graph into 3 dimensions was quite exciting. The Petersen graph is classically portrayed as a big pentagon with a small star in the middle, like this:

As you might be able to guess, the Petersen graph is nonplanar. We can’t draw it on a plane without its edges overlapping. However, if we allow ourselves an extra dimension, we can represent the Petersen graph without any edges overlapping. 

Just like in 2-D, there are different ways to represent the Petersen graph in 3-D. Above is the one I chose to start my OpenSCAD intro with. I created it using an edge code my mentor, Dr. Taalman, sent me. Here’s a picture of my code!

K₆

Now, even though K₆ doesn’t look as complicated as the Petersen graph (it only has 6 vertices!), it is much more complicated to graph in 3-D while avoiding edges crossing over. The view from the top down doesn’t look like K₆ ,but when you move ever so slightly, you can see edges that weren’t visible before.

With the Petersen graph, I only had to adjust the height of a few points. However, K₆ is a completely different beast in that regard. Here is a spin around the graph! As you’ll be able to see, K₆ in 3-D (or at least how I’ve represented it, there are probably cleaner ways) gets pretty intricate compared to the Petersen graph above!

 

Hopefully next time I will have the other 5 graphs from the Petersen family to show you all, since I am much more familiar with OpenSCAD. I can tell that showing of the Y-Δ and Δ-Y transforms will be a challenge — but I’m excited!

Until next time,

Hannah Critchfield

 

The figure on the left is a convex polyhedron, while the figure on the right is non-convex. What makes the cube on the left convex is that any two points can be connected by a line segment within the interior of the polyhedron. Looking at the figure on the right, we can see that two points can be connected on its exterior making the polyhedron non-convex.

Let’s quickly define polyhedron. A polyhedron is a three-dimensional figure made up of flat polygonal faces joined by straight edges. Polyhedra can be classified by the number of faces they have. For instance, a 4-sided polyhedron is called a tetrahedron, 5-sided is a pentahedron, 8-sided is an octahedron, and so on.

What makes a polyhedron rigid, you ask?

A polyhedron is rigid if you cannot bend it into another configuration and it remain the same shape. Bending a polyhedron into a congruent configuration would mean that as you move the figure the faces do not change and the edges preserve their length. With rigid polyhedra, however, trying to bend it would result in a tear or break. Take a cube, for example.

If you had this cube in your hands, then you could easily find that bending or deforming it could not be done.

This brings us to the Cauchy Rigidity Theorem (1813), in which Cauchy states that any convex polyhedron is rigid. No convex polyhedron can be bent or deformed.

So, what about non-convex polyhedra? It turns out that there exists non-convex polyhedra that can in fact be bent into another configuration and remain the same shape. This is called flexibility. You have a polyhedron (which must be non-convex), you bend it, and you have a polyhedron that is congruent to the one you started with but arranged in a different way. A simple definition of flexibility is continuously moveable. A flexible polyhedron can be moved in a continuous motion.

Raoul Bricard, a French mathematician, constructed the first flexible polyhedron that had self-intersections in 1897. A self-intersection means that two or more edges cross each other. This construction is called the Bricard octahedron and consists of six vertices, twelve edges, and eight triangular faces (hence the name).

Fast forward about 8 decades later when in 1977 an American mathematician by the name of Robert Connelly constructs the first flexible polyhedron that did not have self-intersections. Connelly actually disproved Leonhard Euler, who argued in what is known as the Rigidity Conjecture (1766) that all polyhedra are rigid.

The best and simplest construction of a flexible polyhedron was built by German mathematician, Klaus Steffen. This construction consists of 9 vertices, 21 edges, and 14 triangular faces.

I have made Steffen’s polyhedron and you can as well! Follow this template along with the following instructions so that you may physically feel the flexibility. This model is meant to be made out of paper. Note that even if you made Steffan’s flexible polyhedron out of metal plates with the edges as hinges that it would remain flexible.

Now that we have covered rigid and flexible polyhedra, we can discuss the bellows conjecture. Does the volume inside of a flexible polyhedron vary while we bend it? Ijad Sabitov proved in 1995 that there does not exist a construction of a flexible polyhedron that has variable volume as you move it. A flexible polyhedron has the same volume regardless of its state of flex. In other words, a flexible polyhedron would make a terrible bellow.

I have been told that “the bellows conjecture” is quite a misleading name.

 

Written By: Brittany Braswell

References:

Figure 1. liam.flookes.com/cs/geo/

Figure 2. By Tomruen at en.wikipedia [Public domain], via Wikimedia Commons

Figure 3. en.wikipedia.org/wiki/Bricard_octahedron

Figure 4. By Unknown at en.wikipedia [Public domain], via Wikimedia Commons

 

The Discrete Fourier Transform

The Fourier Transformation is a high level mathematical function using the integrals over a continuous wave to compute the component that make up such a wave. As this is done in a continuous fashion, the Discrete Fourier Transform(DFT) is not. The DFT uses the summation of real numbers representing points in time of wave motion. Which makes it an extremely powerful tool to computers because of their discrete nature.

This transformation is accomplished by computing the value of each signal component using every point in time chosen. Every signal value is made of a summation of all the points in time chosen with the value of the signal applied. This is done in the form of circle rotation. Euler’s formula allows us to recognize a basis of imaginary polar coordinates where , thus creating an arbitrary point in . This basis allows us to apply an exponential rotation to all of our points , where K is the signal component being evaluated and n is the point in time. After the transformation is complete we are left with a “list” containing all of the signal components of the original wave.

Written as:

When the DFT is implemented on an algorithmic level it becomes quickly apparent that this runs at an time complexity belonging to . That is because to compute every value K we must add together all of the point by point computations. Also, because of the discrete computation this algorithm is implemented using arrays. Where every index in array K is filled with the summation of points stored in array n. Finally, array K contains the value of every signal component spanned by the wave points chosen. While isn’t inapplicable, the Fast Fourier Transform creates a one layer speed up in time complexity to reach .

The Fast Fourier Transform

The Fast Fourier Transform, or FFT, is a proven way to implement a substantial array transformation on a large amount of data, due to its time complexity of . This speed up was possible due to the amount of redundant calculations made by the Discrete Fourier Transform. These redundant calculations come from the periodic nature of imaginary numbers, where . Due to this property, by splitting the data up into even and odd indices, we are then able to apply the logarithmic time complexity. Using our original equation

,

and denoting as . So we have

,

Now that we’ve condensed the formula, it becomes possible to split between indices  and , as halves of the array n respectively, to perform the Fourier transform as:

Now that the formula has been established and we are aware of the properties of W as

…

Where N is equal to 8.

We define the even summation of the FFT as $latex  G[m] $ and the odd summation as . Therefore we can see that:

…

Given that the input is a power of 2, we can then perform the operation know as the decimating-in-time-algorithm. This is, recursively breaking down every set of transforms into even and odd inputs until only two point DFT’s remain. That is, point transformations, where we implement the recursion until hitting summations or arrays of length 1. At each stage of the algorithm complex operations are needed to build the previous level. Because of the stage construction in \log N, we only have to compute the summations of values themselves N,  while recycling the complex computations.

Quantum Fourier Transform

Now that this basis has been firmly established and we have denoted the fastest time complexity of the Fourier transform using classical computing as , we can further use Quantum gate transformations to a achieve a time complexity such as . Needless to say, this is an exponential speed up of an entire magnitude. To define the transform we first note that can also be defined as set of column matrices denoted as , where s the index of the “array”. We then form the formula as

While this may seem complex, it is important to realize this is a re-representation of the previously defined FFT formula in order to define as a form of column matrices. As we know from the previous post, qubits are defined as column vectors representing system  state probability. If we can reform our input array to be represented as such then we can apply our gate matrices in order to introduce a state of superposition.

Following this the form of basis P is proven under a few propositions, however for the sake of this article we will assume the propositions as true while giving a brief explanation for each.

1.   Each row of matrices  only contains two non zero entries

In the matrices of  we see that the non zero entries are located in the main diagonal and the sub-diagonal depending on the column values of . If we look at this a little closer it becomes clear why this. Putting at this in terms of a double array, if indices and j are equal at all times then we will receive only the diagonal values stored in the array and the same for our matrices. When we traverse all indices in the main diagonal of each matrix, when we receive all entries in the lower sub-diagonal, and yields all entries in the upper sub-diagonal. Because we assumed proposition one we can now say each matrix has been defined depending on the piece-wise function of the indices i and j.

2.  The matrices of P are unitary

If you refer from the last post, unitary is defined as a square matrix where the conjugate transpose is also its inverse. Recall, we need this to be true in order to evaluate output transformations as we due input, in our time steps denoted by t. Subsequently, this allows these quantum gates to be implemented on a quantum computer. However, we must determine what these gates are first. We do this by whats called QR decomposition. The decomposition states that any matrix belonging to  can be broken up into the product of a unitary matrix  and an upper triangular matrix . This then brings us to our next proposition.

3. For any matrix s belonging to    can be made up of the matrices and 

Because the depth of the proofs are being conceded right now, I am going to use proposition three in order to explain the mathematical composition of both  and . Firstly, by multiplying the matrices M and N before traversing the matrix on the left side of the solution we can see that these sets of matrices build  , such as

We then denote that matrix can be written as its form of induction using the Identity and the Hadamard matrix H. By recursively using the formula

for every matrix of matrices we can see this induction compose to

Thus, building every matrix belonging to and completing the unitary requirement of

Lastly, we form our matrices of N as triangular matrices. This is simply the product of all triangular matrices in reverse using R at time denoted by

Finally, we are able to build the Quantum Fourier Transform from the defined decomposition. We first prepare our quantum state as and every complex matrix in  such as,

Where contains every value of the input in the form of ket complex matrices.

Thus we can say, 

The algorithm takes a complex array X as input and uses our quantum gates in to output a quantum state that correspond the probabilities of the real values and amplitudes, given by the original DFT. Thus, we prepare our quantum register of input as

We then move in reverse as an outer loop from

and as an inner loop from

.

At every step in t, we apply our unitary gate operation of as

After applying the quantum gate operation to every matrix at step t, we apply the Hadamard matrix H to the value of at time step s.

After completing every matrix in the reverse time step of s, we have completed the algorithm, this yielding a quantum state $latex \left|\varphi_n \right> $ corresponding to elements of the complex matrix Y.

If we evaluate the time complexity of this transformation we see that the outer loop as steps or equivalently . We see that classically this is equal to the original DTF, however every qubit operation compounds the probabilistic superposition to . Due to this we can say that the operation becomes . This incredible exponential speed up becomes the driving factor of the algorithm and the reason it must be defined in terms of qubits and quantum space.

Written By: Mitchell Mesecher

 

This week and the previous week I was tasked with adding buttons to our user interface. Currently when the buttons A, P, or C were clicked it selected a certain “tool” that you could use. This week I was attempting to create buttons so that instead of having to click a keyboard key the user could click a button. I was able to create buttons, however, I unintentionally over wrote the frame for the Python Interpreter so the buttons are on the wrong screen. I believe that this will be a quick fix and that all I need to do is create a new content pane and add that to the frame with the arcball because currently it is adding buttons to the content pane of the python interpreter. A picture of the issue is included below. The reason we are making this change is because as we add more features the use of keyboard keys would become too extensive. That is all for this week.

Until next week,

Maddie Brower

My first ever exposure to any sort of graph theory was through this paper by Flapan, Mattman, Mellor, Naimi, and Nukkuni. If you’ve already clicked on the link, you might see how someone could get overwhelmed with terminology early on in the paper. Since I had no prior knowledge to graph theory, that person was me. The goal of this post is to provide some casual definitions and some examples showing off certain properties. (Note: this will not cover all definitions in the paper, and certainly not all definitions in graph theory, just some ones that I wish I knew before reading the paper/some ones I think need extra attention.)

[Note: all images are either from the paper linked above, or are from the wikipedia article linked in the definition title preceding the image.]

Definitions and Examples

Planar Graph: A graph is planar if it can be drawn on the plane without any of its edges crossing. (Note: only one way of drawing the graph without the edges crossing has to exist for it to be planar.)

K_n: This is a complete graph with n vertices. It will also have n(n-1)/2 edges. Below is a picture showing off K_n for n=1…12 along with the number of edges the graph has._for 

Minor: Let G be a graph and H be a subgraph. A minor of a graph is created by deleting edges and vertices, and contracting zero or more edges. (Note: when you contract an edge, the two vertices at the end of that edge merge.) Below is a diagram of a G: graph, H: minor of G, and how the minor was formed. The dotted line represents the deletion of an edge, while the grey line represents the contraction of an edge.

Y-Δ Transform/Move: Let G be a graph that has a vertex, v, and let v have exactly three other vertices surrounding it. A Y-Δ transform of G at v is achieved by removing v from G and adding edges between each pair of the neighboring vertices.

Δ-Y Transform/Move: Let H be a graph that has a triangle of vertices, uvw. A Δ-Y transform of H at uvw is achieved by removing the edges uv, vw, and uw from H and adding a new vertex, z,  and new edges uz, vz, and wz.

So, in Y-Δ transforms you are deleting a vertex and in Δ-Y transforms you are adding a vertex. These transforms will be useful for understanding an upcoming definition.

Petersen Graph: This is a graph with 10 vertices and 15 edges. Click on the link and scroll to read about some neat properties Petersen Graphs have. If I listed them all here, this definition would be the length of the blogpost.

Petersen Family of Graphs: This is a set of seven undirected graphs (graphs in which the edges don’t have direction) that includes the Petersen graph, the complete graph K₆  and 5 other graphs that are formed by Y-Δ and Δ-Y transforms. Below are two images: one from the paper mentioned at the beginning of this post and one from the Wikipedia page linked in this definition. Both show the Petersen family of graphs, but the Wikipedia picture shows which graphs can be formed by performing Y-Δ and Δ-Y transforms.

Upcoming

If you clicked on the paper mentioned at the beginning of the blog post, you may have noticed that the definitions featured here only cover the first three pages. These definitions and examples were chosen because they are going to be heavily used in what I want to do next. Past posts by Ben Flint have shown off Petersen graphs represented in 3-dimensions. My goal for the semester is to represent K₆ , K_3,3,1 , a Petersen graph, and the other 4 graphs in the Petersen family in 3-dimensions. A stretch goal/side project is to create some sort of program that will perform those Y-Δ and Δ-Y transforms on the Peterson family of graphs (and potentially others as well).

 

Until next time,

Hannah Critchfield

Hello,

For the past several months I have been working an interactive interface for the construction of inversive geometry of circles. Currently the working features are adding points, dragging points, and selecting three points to draw a disk. The past few weeks I was tasked with altering the code in order to implement a construction graph for the objects that were being drawn. Once completed this alteration will update any object if what it is composed of is changed. For example, a disk is composed of 3 points with the construction graph when one of the points is moved the disk updates accordingly.

 

 

Currently in order to utilize the features such as adding a point or drawing a disk I am using keyboard commands (P : point editor mode, C : to draw a disk, A : to move the arcball). As the interface acquires more features the addition of more keyboard commands will become inconvenient to remember all of the keyboard keys and thus currently I am attempting to add buttons to the screen so those can be clicked as opposed to a keyboard key being selected.

Until next week,

Madelaine Brower

Outline

This blog post is purposed with denoting and recognizing the basic principles involving the mathematics behind quantum computing. This write up is directed towards upper level undergraduates, as well as graduate students, with backgrounds in mathematics or computer science.

This article will cover the simulation and representation of quantum physics using specialized computer bits and linear algebra. These specialized bits are called qubits. As the nature of these bits was covered in the last post, here we will describe the basic operations that can be performed on them. These operations are the beginning to understanding how quantum exponential speed up is possible.

Along with the qubit, we will cover the mathematics behind quantum gate manipulation. Using quantum gates we allow our system to enter into a state of superposition. By applying one of these gates to a qubit we hence alter the probabilistic complexities of that qubit, allowing our qubit system to be derived with varying probabilities for its position.

An Overview

As discussed in the last post, the nature of superposition can be interpreted by the implementation of qubits. A qubit can be interpreted as a matrix. Each qubit represents a probabilistic quantum state, where each indincy of the matrix can be viewed as the probability of the system being in said state. As a reminder, it is important to create a basis for a qubit to possibly occupy multiple states at once, as we are trying to emulate the quantum theory of superposition (Refer to First Post). From a qubits static state, we can perform operations to transform a qubit. Qubit transformations are completed by applying whats called a quantum gate. These quantum gates take the form of square matrices, as they must also be what is called, unitary. In order to transform a qubit into a subsequent state we must apply the quantum gate with matrix multiplication. The indices of the new matrix after performing the multiplication now represent the probabilities of the system residing in each position of the new state. We will see examples of this further on.

Before reaching the mathematical theory, there are a few notations that must be defined. One of the most important being the ket, generically as . This is considered to be the shorthand notation for representing the probabilistic state of a qubit. Using this notation, it becomes easier to perform a quantum gate multiplication on a particular qubit without drawing out the matrices themselves, as these can get quiet large. At this point it is important to note that all qubits take the form of column vectors. In computer science terms, this can be seen as a one-dimensional array rotated to be viewed vertically. Let us know recognize the most simple of qubits,  and  Where    and 

Let us recognize that qubit  holds a 100% chance of being in state 0 and qubit    holds a 100% chance to be in state 1.

We can denote any qubit as  containing number of rows.  Notice we use to denote each indicy of the qubit. This is due to the fact that qubit state probabilities are represented as complex numbers. However, we will learn the ropes first using real numbers.

Throughout this article we recognize M as a matrix with entries denoting the probability of a movement between positions, or more simply a quantum gate and X as a qubit matrix representing the static probabilities for the systems current position. When in reference to quantum computations these matrix entries will be in terms of complex numbers where . Lastly, we want to recognize the Hadamard matrix, which is the controlled quantum gate used to transform the ket matrix into superposition. The Hadamard matrix will be denoted with H where H .

Principle Operations

First, it is important to note the sizes of matrices M and X. M is always a square matrix made up of size where N is the number of possible positions. Qubit X is always a column vector denoting the state of the state of the system. Next, we must cover the matrix multiplication of , were the product is equal to the state of the system after one movement. This matrix can be denoted as Y which itself is a qubit. The number of movements, K, is equal to the number of times M is multiplied by itself. Therefore, the column vector, or qubit, Y with constraints entries for probability of the system being in each position after K movements, equal to .

Lets look at an example.

Movement between position t and described by matrices

.

M describes the probability of movement between the three positions. Probability of moving from positions . Qubit X describes the static probabilities of the positions the state is currently occupying. While qubit Y describes those same static probabilities after a movement. Notice the sum of all columns or rows is equal to 1.

Let us quickly touch upon the notation for a complex quantum gate such as H, which is the form all quantum gates must take. When in relation to the set  we will denote M with U as unitary where the sum of all entries modules squared is equal to one, this allows us to fill our matrix with complex numbers, correctly representing the qubit transformation of superposition when applying matrix H.

By definition the conjugate transpose of a unitary matrix is also its inverse, we will take its conjugate transpose, or adjoint, as U(cross). The importance of this is that by taking the adjoint of U at position and applying it our state we will effectively receive the qubit at the state of . By doing this, we allow in the analysis of results without analyzing input, substantially cutting down on the level of system decoherence.

Let us now practice an example using a qubit that only contains complex probabilities. The importance of this example is to notice how we evaluate a qubit that contains indices of complex numbers.

Finding the norm of the matrix by taking the dot product of square roots of its vector rows and vector columns is most crucial. Then by applying this value as a scalar to the original qubit matrix and taking the square modules, we receive the probability of being in each position at time .

First we again notice , where there is a zero probability that the qubit is in state 0. Now lets consider a qubit that has been moved through a few quantum states and has different probabilities correlating to the possibilities of being in states 0 and 1. We can define such a qubit as, 

Here we evaluate the norm and then re-apply this to our original qubit.

Now we divide S by and then evaluate the qubit by taking . Such as:

From the transformed matrix we can see the probability of qubit S being in state  and the probability of state . We can see this is correct because the two probabilities add to one.

The Tensor Product

Finally, we must address the operation of quantum entanglement. Quantum entanglement is the process of intertwining two separable states with their individual complex probabilities into one state, or qubit, with a new set of static probability. This quantum operation may be the most important principle, as it allows for all the matrix manipulation previously described. In addition, we can even “multiply” or append qubits that are of different rows and columns, something that is not normally achievable.

The principle notation involving the joining of two qubits is denoted as the tensor product. This is the scalar multiplication of one matrix by another, in order to combine the probability of being in both states at once. The tensor product is denoted by and is the main operation applied to qubits in order to combine states.

Let us once again look at the two most basic qubits,  and  As you recall these qubits are denoted as two column matrices of probabilities 1 and 0. However let us supposed we wanted combine our two quantum states into one.

Lets evaluate,

Where the system has a 100% probability to be in state 01.

While this may seem counter intuitive to the complexity involved, this allows the for quick combination between qubits, especially when applying quantum gates. Here we can create any size multitude of a column vector qubit. It is important to note that the column vector representing a qubit grows exponentially with the number of bits allocated. That is a matrix.

For instance, take the operation:

Normally, this scalar multiplication would just be as such, but we can represent this using tensor products.

Firstly, notice that positions All have 100% probability to be their respect states.

But consider this in ket notation as,

Now we can see that all three positions of the qubit have an equal complex probability by being divided by

From here we apply our gate operations in the same respect, by using the tensor product we can apply our unitary matrices of the probability of state movement, such as H, to the matrix of a qubit. Where represents the system at position , if then the qubit system at position would be in superposition.

This final concept of the Tensor Product is relatively hard to grasp especially without a practical example. For that reason, the next post will center around implementing what is known as Deutsch’s Algorithm and combination of quantum input.

Written By: Mitchell Mesecher

References: 

An Introduction to Quantum Computing, Noson S. Yanofsky