Note: This is quite lengthy and I have not put in much effort to double-check everything, so there may be some minor errors throughout.
Introduction
Quantum computers have very different behavior from classical computers allowing them to have significantly better performance on certain algorithms. However, quantum computers are still quite far off, we likely will not have one reasonably priced for home consumption for a long time. This shouldn’t stop you from experimenting with them, because a very simple quantum computer can be easily simulated through classical code.
Now, when I say “simulate,” I do not mean the physics of a quantum computer, but the logic. I also do not plan to cover the most efficient methods for doing this, but the simplest method that is the easiest to wrap your head around and then replicate in code. This will allow you to write simple quantum algorithms and then simulate them on a classical computer.
Code on a quantum computer is typically represented with a language called QASM described in the paper “Open Quantum Assembly Language” from Cornell University. Learning to simulate a quantum computer will allow us to execute QASM code and determine what the results would be. QASM is a simple programming language designed to represent quantum computational operations. Let’s compare it to regular assembly code.
Here is some assembly code written for a Zilog Z80 classical computer.
Every line of assembly code effectively takes on the same form. Each line in the code above could be separated into two parts, the first being the “operation,” and the second being the “parameters.” The operation usually comes first, and then the parameters second. Many operations can take multiple parameters, and so the parameters are then separated by commas.
In the code above, we see four unique operations, those being LD, PUSH, CALL, and INC. Each operation will take in some parameters, and based on those numbers, the CPU will perform some sort of computation and then a memory operation to store the results somewhere.
The LD operation, for example, loads the second parameter’s value (in this case the hex value 30) into a memory register (a small memory unit capable of holding 1 byte of data). There are many unique registers on the CPU, so they are designated by a letter, such as A being the first register. However, in the actual binary code, the letter A is not used, but a number. Both parameters are simply numbers.
It has INC which increases the number stored in a register by 1. In the case of the code above, the SP register (stack-pointer) is being incremented. The Zilog Z80 CPU has a very large number of different operations. Such as, it also has the ADD operation which can add the value of two numbers together and store the results into a register.
In most programming languages, you have functions which allow for the reusing of a block of code. The functions usually have a name and some parameters they take as input. The operations in a CPU can be thought of as functions like this, however, these functions do not exist as a block of code in the CPU anywhere. These functions are actually part of the physical hardware. When an “ADD” operation is called, the physical hardware is arranged in such a way to be capable of carrying out this operation.
As a programmer, you do not need to worry about the actual physical implementation of a CPU in order to know how to code for it. You only need to know the logic of it. You don’t need to be a PhD physicist or computer engineer to know how to program a computer. Each CPU is designed from a physical level to achieve some abstract logic, and all you need to know is that abstract logic. How the ADD operation in the CPU actually physically adds numbers together is none of our concern. All we need to know is that it does add numbers together, and then we can use this in our code.
In the same sense, we will often see quantum computer programs represented in its own form of assembly language called QASM. We do not need to know quantum physics to understand how to interpret this code. We only need to understand the abstract logic of how quantum computers process information. Just like in classical assembly, quantum assembly represents each operation in a quantum computer with a name of the operation and then some parameters, typically being the qubits to apply the operation to.
Here is some assembly code written for a quantum computer taken from the paper mentioned previously.
Here we see a similar pattern to classical assembly. Two operations we will be seeing later in this post are “CX” and “h” which represent the controlled-NOT and the Hadamard operation respectively. The parameters are the qubits in memory to apply the operation to. In order to simulate this, you would simply need to know how to mathematically apply this operation to those qubits. You would then need to simply iterate down this list of instructions and apply each one in the order represented, and then the final state of the memory in the quantum computer would be the final results.
Quantum Superpositions
Quantum computers differ drastically from classical computers because the entire computer always exists in a state of superposition. Classical computers are deterministic, meaning that each bit can be described independently of the system as a whole. If I apply the NOT gate to some bit, that bit will have its value inverted, and this would have no “side effects,” it would not affect any other bit in the system except for the one I specifically applied it to.
Since quantum computers are not deterministic, qubits can become entangled with each other, causing the value of one qubit to affect another. This would mean that every operation, even if applied to only a single qubit, can have side effects on the entire system. Therefore, each operation in a quantum computer cannot simply be applied to a specific bit, but must be applied to the entire system.
This is why quantum computers are difficult to simulate. Let’s say a quantum computer has 100 qubits. If I were to apply a NOT gate to a single qubit, I cannot simply flip the value of that qubit. I have to apply this operation to the entire system of all qubits to account for how it may affect other qubits entangled with it. Each operation, no matter how simple, has to be applied to the system as a whole.
To understand entanglement, one must understand quantum superpositions. A superposition simply refers to the fact that for quantum computers, no qubit has a definite value until it is measured. This doesn’t mean we don’t know the value of the qubit because we lack knowledge, but that it quite literally does not have a defined value until measurement.
Consider the double-slit experiment. Light is made up of particles called photons. Let’s say photons are fired from a light source in two directions from a light source through two separate slits in a barrier. On the other side, those photons then hit a screen where they can be observed.
One would expect on the other end to have two streaks of light where the photons hit the wall on the other side. In practice, however, this is not what is seen, but instead an interference pattern appears on the wall on the other side, which are characteristics of waves and not particles.
Photons, rather than behaving like particles, behave like waves. Each photon passes through both slits at the same time. How can a single photon go two directions at the same time? That is just how quantum mechanics works. The photon exists in a superposition between both slits, it quite literally passes through both at the same time with different probabilities of each (50% either slit if individual photons are observed). These superpositions then interfere with each other. When the photons finally hit the wall on the other side and can be observed, the pattern is not what one would expect if the particles behaved in a classical and deterministic way.
To describe a system like this, then, you cannot simply describe the path of the individual photons. If you did so, then you would not expect an interference pattern to appear on the screen on the other side. In the diagram above, the two arrows represent the path of the particles. One would expect those arrows to continue on until they hit the screen, forming only two blocks of light on the other end.
This is not what is observed, however, and the only way to correctly represent this is to not simply represent the photons as classical particles which can have their behavior described independently from one another, but rather as superpositions which can interfere with one another.
A qubit is represented not as a 0 or a 1 as in classical computers, but as a superposition. The superposition can have 0, 1, or any number in between. This is typically represented in the notation |ψ〉= a|0〉+ b|1〉. This notation may seem confusing, but it is quite simple. The left-hand side of the equation is just the symbol to represent a superposition. The right-hand side is its superposition described in terms of the superpositions |0〉and |1〉, which refer to the superpositions of 100% chance of the qubit, when measured, having the values 0 or 1 respectively. Each are multiplied by a constant, to allow for variations in the probability away from 0 or 1.
For example, here are some equations to show how this is used.
|ψ〉= 0|0〉+ 1|1〉= |1〉= 100% chance of being a 1
|ψ〉= 1|0〉+ 0|1〉= |0〉= 100% chance of being a 0
|ψ〉= 1/√2|0〉+ 1/√2|1〉= 50% chance of 0 or 1
The last equation here is important. The constants do not translate directly into probabilities, such as, 0.5 does not mean 50%. In the paper “On the Quantum Mechanics of Collisions” by Max Born, it says, “the probability is proportional to the square of the quantity.” In other words, the constants are squared. Before they are squared, an absolute value is also taken. In this case, the absolute value of 1/√2 is itself, and this number squared is 1/2 or 50%.
The reason for this is that these constants are complex numbers. Complex numbers can contain an imaginary component. A percentage is not a complex number, it cannot contain an imaginary component. Taking the absolute value then squaring these constants gets rid of any imaginary components in these complex numbers, converting them into a percentage.
Since each qubit can be represented simply by these two constants, the qubit’s superposition can be represented in the simplified notation of |ψ〉= [a, b]. In this case, we simply represent the superposition as a vector containing the two constants. Each individual qubit can thus be represented by a simple vector of two numbers.
Quantum entanglement simply refers to the fact that because each qubit exists in a superposition, superpositions can become entangled with each other, and thus a change in one qubit can affect the entire memory of the quantum computers and all other qubits.
A simple example is the Bell state. Think of a NOT gate in classical computers, this has 1 input and 1 output. It simply flips the value of the bit.Extend the NOT gate to have a second input. This input is the “control.” If it is 1, then NOT gate flips the value of the first input, but if it is a 0, then the value is left unchanged. Also consider that this NOT gate has two outputs, where the first output is the first input flipped or not flipped, and the second output is always the second input left unchanged. This NOT gate therefore would have a “control” input to turn the NOT gate on or off, we will call this the CNOT (or controlled-NOT) gate.
The diagram below is how this is typically represented. The second input is shown here at the top, which is the control which remains unchanged. The first input is shown at the bottom, where the transformation applied to this input to get the output depends on whether on the first input.
Let’s say the first input is a qubit in the state [0, 1], so it is a 100% chance of being a 1. The input of the second input is a qubit in the state [1/√2, 1/√2], so it has a 50% chance of being a 0 or a 1. What is the chance of the first input after this CNOT operation is applied? If the second input is 0, then the first input is not flipped, so its state remains [0, 1]. If the second input is 1, then the input is flipped, so its state transforms into [1, 0].
This would mean that the first output’s new state is a 50% chance of either 0 or 1. It’s true state thus is neither [0, 1] or [1, 0], but is instead [1/√2, 1/√2]. The states of the two output qubits now are identical, with both having a 50% chance of being 0 or a 1.
The important bit to note, however, is these identical states are not independent of one another. If the first input was a 0 and its output was a 0, this could have only occurred if the second input was a 0 and thus its output is a 0. If the second input’s value is a 1 and its output is a 1, then if the first input was a 1, it will be transformed into a 0, if it is a 0, then it will be transformed into a 1.
That is to say, if we know the value of two input qubits, and then we know only a single one of the output values, then we can logically deduce what the second one must be. These two qubits depend on each other, so their values are interrelated. If these two qubits are then used as inputs to a completely different and independent algorithms, the results of these two algorithms cannot be described indecently from one another, as they both rely on probabilistic inputs which are interrelated. Thus, even though both inputs have a 50% chance of being a 0 or a 1, if we measure the results of one of the algorithms, we immediately know the results of the other without measuring it.
Kronecker Product
Previously, we had shown that each qubit can be represented by a single vector of two numbers. We also explained that individual qubits cannot be represented in isolation from one another in a quantum computer. Qubits can become entangled with one another, such that the value of one qubit depends on the value of another.
We showed how you can represent a single qubit as a vector. But no useful quantum computer will have a single qubit. If we have, let’s say, 2 qubits, then how would be represent this mathematically? Very simply, we take the Kronecker product of the 2 qubits, and this produces a single vector which describes the entire system.
Let’s say we have 2 qubits, the first being in the state [1, 0] and the second being in the state [1/√2, 1/√2]. Given there are 2 qubits, what are all the possible outputs of this system? Well, there is 00, 01, 10, and 11. For n bits, even in a classical computer, there are 2ⁿ potential patterns these bits can be arranged in. Similar to how we initially described superpositions, we could describe the superposition of this entire system with the equation below.
|ψ〉= a|00〉+ b|01〉+ c|10〉+ d|11〉
Here, rather than 2 constants, we need 4 to describe the entire system. In the case of the 2 qubits we provided, the most significant qubit we will say is the one in the [1, 0] state, and the least significant qubit is the one in the [1/√2, 1/√2] state. Since the most significant qubit is definitely 0, then there is no chance of the latter two states occurring when measured. However, since the least significant qubit has a 50% chance of being a 0 or a 1, then the first two states can occur at a 50% chance. We could fill in the constants then like so.
|ψ〉= 1/√2|00〉+ 1/√2|01〉+ 0|10〉+ 0|11〉
Since this entire superposition can be described in terms of 4 constants, we could again simplify the notation down to a vector. Rather than this lengthy notation, we could represent the superposition simply as a vector.
|ψ〉= [1/√2, 1/√2, 0, 0]
The size of the vector needed to represent the superposition of n number of qubits is thus the amount of potential outputs there could be, or in other words, 2ⁿ potential patterns. This is one of the reasons why simulating quantum algorithms on a classical computer is so difficult, as the complexity of the superposition grows exponentially the more qubits you have. If you have 75 qubits, then the size of this vector is 2 to the power of 75. This would be a vector of length 37,778,931,862,957,161,709,568. If each value in the vector was a single byte, this would correspond to roughly 38 zettabytes of memory. By contrast, there are only 18 zettabytes of memory in all computers in the world. If you have 250 qubits, then the number of elements in the vector would roughly be equivalent to the number of atoms in the entire observable universe.
Hence we can see why simulating a quantum computer is difficult and inherently limited. The more qubits, the more complex the superposition of the whole system is. And remember, we have to represent the entire superposition. We cannot ignore any states because if we treat them in isolation, we will miss certain side effects some operations can have on other qubits due to entanglement. The complexity of representing quantum computers is why the world record for simulating a quantum computer is only 46 qubits. By contrast, IBM already has a 64 qubit quantum processing unit.
It is important not to represent a system of n qubits as n independent vectors, but instead a single vector of size 2ⁿ. In order to “combine” vectors, so to speak, we can simply use the Kronecker product of the two vectors. The output produces the combined vector.
The Kronecker product is a simple algorithm represented below. Each element of the vector is the second vector multiplied by one of the constants of the first vector. Each element is represented by a different constant in the first vector. depending on the element.
Notice how the output is not necessarily a vector but a matrix. The Kronecker product is not just used on vectors but also vectors-of-vector, in other words, matrices. The algorithm when applied to two matrices of size MxN and PxQ gives an output matrix of size MPxNQ where the rows and column lengths are simply the multiplies of the row and column lengths of the input.
If A is a vector, then it has a row for each constant it represents and only 1 column. Since qubits are vectors with 2 constants in them, then the number of rows would be 2. If the size of 2 qubit vectors in the form MxN and PxQ are 2x1 and 2x1, then the resulting MPxNQ would be 4x1. Recall how when we represented the 2 qubit system, we used a vector of 4 constants. This could also be thought of as a matrix with 4 rows and 1 column.
Let’s actually try out this algorithm. Let’s say A = [1, 0] and B = [1/√2, 1/√2].
As we can see, taking the Kronecker product of both individual superposition produces a single superposition representing the entire state of all qubits in the entire computer. For the rest of this, I will not bother doing Kronecker product by hand, but will instead use this online tool so you can try it yourself.
Quantum Operations and Logic Gates
Previously, we mentioned the quantum operation of the CNOT gate. Let’s say we have a system of 2 qubits both with the values [0, 1] and [0, 1] respectively and these are the inputs to the CNOT operation. Since both are 1, then one of the outputs must be flipped.
Think of each operation as a logic gate, similar to in classical computers. In this case, we are working with the CNOT logic gate. Most Wikipedia articles for different quantum logic gates contain that same gate represented in matrix form.
What does this mean? The same Wikipedia article also kindly provides us a truth table for the CNOT gate. Let’s compare the matrix to the truth table.
At first, there seems to be no relation from the truth table to the matrix representation. Let’s add the different 4 different potential patterns each of the two qubits can be along the rows and columns of this matrix.
Notice in the truth table, there are 4 potential input →output pairs, being 00 →00, 01 →01, 10 →11, and 11 →10. If we remove the arrow to combine these pairs, we get 0000, 0101, 1011, and 1110. Notice the matrix table above. We have a 1 in the location of this table where each input →output pair occurs.
Let’s say we have a different logic gate, the AND gate. In classical computers, the AND gate is represented by this truth table below.
How can we convert from this classical notation to matrix notation? We have to recognize that all quantum logic gates are bi-directional. For this to be true, they must all have the same number of inputs as outputs. Thus, this classical logic gate cannot work in its current form, as there are 2 inputs yet only 1 output.
If there are two outputs and each correspond to one of the two qubits as inputs, then where does the output listed above go? It must be stored in one of the two qubits. Let’s say the output A AND B is stored in qubit A, and then qubit B is left unchanged. We would thus get a new truth table looking like this.
Here we can clearly see the input →output pairs. In order, they would be 00 →00, 01 →01, 10 →00, 11 →11. Thus, using the method shown before, we can then construct the matrix corresponding to this logic gate.
This is how quantum matrices relate to the actual quantum logic gates. They are simply representations of the input →output pairs.
Next, we have to discuss how to actually apply a quantum logic gate. That is, how to actually apply one of these operations to a quantum computer.
Let’s say we have a system of 2 qubits both with the values [0, 1] and [0, 1] respectively and these are the inputs to the CNOT operation. Since both are 1, then one of the outputs must be flipped. If we were to take the Kronecker product of both of these, we would get the matrix [0, 0, 0, 1], which tells us that if we measure the output qubits of this system, there is a 100% chance of measuring a 11.
In order to apply the quantum logic, we simply need to simply matrix multiply this superposition matrix by the quantum logic gate matrix.
If you have two matrices of size MxN and PxQ, then the resulting dimensions of a matrix multiplication will be MxQ. A matrix multiplication can only occur if N=P, that is to say, the number of columns in the first matrix equals the number of rows in the second matrix.
In our case, we said that a vector of 4 elements can be thought of as a matrix of size 4x1. Our logic gate is size 4x4. In this case, N≠P, so a matrix multiplication cannot occur. However, we could “rotate” the vector, so to speak, to instead represent it as a 1x4 matrix where each element represents a column with only a single row of elements, and then matrix multiplication becomes possible.
I will use a simple matrix multiplication calculator online which can be found here to then multiply the vector representing the superposition of the entire quantum computer with the CNOT gate matrix.
Notice how the input is 1x4 and the output is also 1x4. The “result” of this operation is simply the logic gate applied to the system. In this case, we have an input with a 100% chance of being 11, and an output with a 100% chance of being 10 instead. Why? Because in the CNOT gate matrix, the most significant qubit is the control which remains unchanged, and the least significant qubit is the one that will potentially be negated. Since our control qubit was a 1, then the other qubit got negated.
Let’s try something a bit more complicated. Let’s go back to our bell state where the most significant qubit had a 50% chance of being a 0 and a 50% chance of being a 1, or in other words, [1/√2, 1/√2], and the least significant qubit has a 100% chance of being a 0, or in other words, [1, 0]. The Kronecker product of these two give us the state of the entire system, being [0, 1/√2, 0, 1/√2]. The outputs 01 and 11 have a 0% chance because the least significant qubit has a 100% chance of being a 0, so nothing ending in a 1 can possibly occur.
Now, let’s apply the CNOT operation to it. We online calculator I linked cannot take square roots, so let’s just represent 1/√2 as 0.707.
The most significant qubit has a 50% chance of being a 0 or a 1, and since the least significant qubit is negated based on the value of the most significant, then it has a 50% chance of being negated or not, meaning it also has a 50% chance of being a 0 or a 1.
Despite this, however, the results do not show that each pattern of qubits is 25% likely. Rather, two are 0% likely, and two are 50% likely, those latter two being 01 and 10. Since the most significant qubit negates the least significant, then the two must always be opposite of one another. It is not possible, for example, for the pattern 00 to occur as an output, since the least significant qubit had 1 as an input, and if 0 was the input for the control, then the output would be 01 and not 00.
Thus, if you know the value of the output of one of the qubits, you know the output of the other, since their values depend on one another. This is quantum entanglement represented very simply in the form of the Bell state. This also demonstrates how we can apply logic gates represented as matrices to a quantum computer. The Wikipedia articles of most quantum logic gates lists their respective matrices.
The Quantum Logic Filter
The previous section here explained how to apply a quantum logic gate with 2 inputs and 2 outputs to a simple quantum computer with 2 qubits. However, if you try to implement this, you will find that it does not work on any quantum computer with a different number of qubits than there are inputs/outputs to the logic gate.
For example, let’s say we have a quantum computer with 4 qubits. The vector would be 1x16 yet the logic gate would still be 4x4, so you could not do a matrix multiplication. Let’s say we want to apply our CNOT gate to the first and second qubit. How can we accomplish this?
To accomplish this, we have to construct one giant logic gate to represent the transformations applied to the entire system. I like to refer to this as the “logic filter” since you can imagine it being a very large screen which you shake all the qubits through, and the correct answer falls out of the bottom.
If there are 4 qubits and we want to apply the CNOT gate to only the first 2, then the second 2 remain unchanged. In matrix multiplication, an “unchanged” operation is the identity matrix, usually represented by the letter I. For any given matrix M, M=MI. Multiplying by the identity matrix does nothing to the original matrix. A 2x2 identity matrix for a single qubit would correspond to the matrix below.
One simple way to construct the logic filter is thus our old good friend, the Kronecker product. Remember, this is used to “combine” probabilities, and so it can be used to even combine logic matrices to build a “combined” logic gate.
Let’s say our 4 qubits are A, B, C, and D. We have said only the first 2 will be passed through the CNOT gate. Therefore, C and D are unchanged, we can say they are being passed through the identity matrix. The logic filter could thus be represented by the equation below.
F = CNOT ⊗ I ⊗ I
This would produce a 16x16 logic gate that we need. This works, however, it only works for adjacent qubits. What if we want to apply the CNOT gate to the second and fourth qubit? We cannot use such a simple method as this cannot simply be represented as the combination of simpler logic gates. The logic filter for 4 qubits will be a 16x16 matrix, so it must take on the form below.
We could construct this using what I call the “truth table method.” First, we have to construct a truth table of inputs →outputs. This can be constructed by applying the logic gates to all the qubits independently.
In this case, the only qubit that changes is the least significant. This is because we are only applying the CNOT gate to the second and fourth qubit, and since the most significant is the control, it doesn’t change from the input to the output. However, the fourth qubit, the least significant, does change, but only if the control qubit is a 1. We can then easily use the truth table to construct the logic filter as shown prior.
Thus, a more “universal” way to construct the logic filter is to first apply the logic gates in every possible combination independently, and then use the truth table to construct a logic filter.
You may think this method would be particularly slow as constructing an entire truth table would require O(n²) computational time. However, remember that in order to apply the truth table, we have to do a matrix multiplication of a 1x16 and 16x16 matrix, which is also a O(n²) matrix. So while this is slow, it’s also the same order of magnitude of “slowness” as the matrix multiplication itself. What this means is that pre-computing these tables will not make your program significantly faster.
Truth Table Method w/ Non-Classical Gates
The truth table method as shown before works with simplistic logic gates as I have shown. Logic gates like AND and CNOT can also exist in classical computers. However, this truth table method, as I have explained it, may be confusing how it works with more complicated logic gates which are non-classical. It needs to be explained a bit further. Let’s take a non-classical logic gate, such as the Hadamard gate. The Wikipedia listing for its logic matrix is the one below.
It does not provide us a truth table, but we can derive the truth table simply by applying the logic gate to the individual qubits.
Thus, the truth table would be as follows.
With a NOT gate, our truth table would be something simple with input →output pairs of 0 →1 and 1 →0 and thus would be fairly trivial to convert into a matrix. However, this truth table is not so simple, it has input →output pairs of 0 →[1/√2, 1/√2] and 1 →[1/√2, -1/√2]. In order to build our logic filter, we have to know how to convert from the truth table into a logic gate matrix. The logic gate matrix has the dimensions of 2x2 for a single qubit.
For the top-left cell, our input is 0 since it is on row 0. It is also on column 0. The output in the truth table has two numbers, but we are only concerned with the 0 output, and thus, the top-left cell becomes 1/√2. For the bottom-right cell, our input is 1, so we choose from the row corresponding to 1 in the truth table. Since the column is also 1, we are only concerned with the 1 output, so the bottom-right cell becomes -1/√2. In other words, we produce what is shown below.
Thus, this is how we would derive a matrix from a truth table if the truth table is non-classical and it has superpositions as outputs.
A somewhat neater way to represent the truth table is thus not simply a single column for all the 0s and1s as they would become confused if you have many with complex, non-classical outputs. Rather, have two columns specific to each output qubit, one for the 0 probability and one for the 1 probability.
This is how I like to represent the truth tables for quantum logic gates. The columns are arranged as “X_|0〉” and “X_|1〉” where the X represents the bit in question, and the “|0〉” or “|1〉” represent which probability we are talking about. This truth table is somewhat more explicit than the simpler truth table, and is likely how you will want to store the truth table in memory if you are actually writing a program to use these.
We can also more explicitly represent the truth table for the CNOT gate in this same format as shown below.
Recall that the CNOT logic gate matrix is the one shown below.
How can the extended truth table be easily converted into the logic gate matrix? It is not as obvious as it was last time. The solution is simple. Look at the 10 row for example. The truth table would tell us that the corresponding input →output is 10 → [1, 0][1, 0]. We know from the logic gate matrix this is supposed to be represented as a single vector for the probabilities of all 4 states, in the form [A, B, C, D].
How do we combine two separate qubit matrix into a single vector that represents both of them? The Kronecker product!
That is to say, converting the extended truth table into the logic gate filter is simply a matter of calculating the Kronecker product for each row.
Let’s take a system with 3 qubits where we want to apply the CNOT gate to the first and third and Hadamard to the middle qubit. How would we then construct this logic filter? We already have the Hadamard and CNOT logic gates. We need to use these to then construct a logic filter of a matrix of size 2³x2³, or 8x8.
Let’s use the truth table method, which first involves constructing a truth table. The truth tables always have 2ⁿ rows since it has to represent every potential input. However, unlike the logic filter, it only has N columns to show how every input is transformed into an output, so one column per output. Although, for clarity, we have chosen to use 2 columns to represent each output, so it would be 2N columns. In this case, we have 8 rows and 6 columns.
Now all you have to do is run through the truth table and for each row, you are given a set of values for the input bits, then you have to run those input bits through each gate you wish to apply independently. In this case, A and C will be ran through the CNOT gate and B will be ran through the Hadamard gate. The outputs of the gates provides the superposition for the bits, telling you what their values should be. This should be rather simple to implement manually.
The truth tables for all the different gates should not be something you calculate. They should either be hard-coded or provided in a file or in the QASM code itself. Calculating this larger truth table simply requires many calls to the individual truth tables.
Once we have produced our truth table, we can then produce the logic filter from the truth table. We can then use the truth table method to convert this into our logic filter. For example, what does in row 010 and column 010? In our truth table, we know that 010 →[1, 0][1/√2, -1/√2][1, 0]. The first row would thus be [1, 0]⊗[1/√2, -1/√2]⊗[1, 0]. Using the same calculator shown before, we can do this in two steps.
In simple terms, this shows us that the probabilities of 000 and 010 are both 50% while the probabilities of everything else are 0%. This makes sense because our input was 010 and the CNOT gate was applied to the first and third bit, and if they are both 0, then nothing will change. The middle bit, however, had the Hadamard gate applied to it, and thus is now in a superposition. Which superposition? There are two options given our truth table for the Hadamard gate. Since the middle bit is 1 and not 0, it is the second option in the truth table.
If we go through each row and find the Kronecker product and then build out an entirely new table, we get our logic filter.
This is a single large logic gate that will apply the CNOT gate to the first and third qubit, using the first qubit as the control, and the Hadamard gate to the middle qubit. We would begin by taking the initial states of all our qubits and finding the Kronecker product of all of them, forming a single vector representing the entire quantum computer as one single superposition. We would then matrix multiply that vector by this logic filter matrix. We could then compute the probabilities of each combination of qubits when measured by squaring then finding the absolute value of each element in the resulting vector.
QASM
We have seen how we can mathematically apply logic gates to the “memory” of a quantum computer and then compute what the probability of the different results would be. How would this translate to QASM code, or quantum assembly code?
Let’s take something a simple test program, a quantum half-adder. A half-adder could add two bits together, producing an output and a carry. There is a paper “Quantum half-adder” from Physical Review A which describes the two logic gates needed for a half-adder.
Here, we have three qubits and two logic gates. We could represent these as two separate operations in an assembly language code. For example, to represent the Toffoli gate being applied to qubits b1, b2, and b3, we would use a line of QASM code “toffoli b[1], b[2], [b3];” and for the CNOT gate, the line of code “cnot b[1], b[2];” could be used.
Sometimes the CNOT gate is also written as “CX” which if you scroll back up to the top, that is the code used in the paper. This is because if the qubit is represented as a Bloch sphere, the “x” operation refers to flipping it on its x-axis, while the “CX” is the “controlled” version of it. Flipping on its x-axis is known as the “Pauli-X” gate. It may be useful to make this distinction because there is also a Pauli-Y gate which would also flip a |0〉 to a |1〉 and vice-versa as it flips along the y-axis, and thus there could be a “CY” gate that would be very similar to the CNOT, and thus “CX” is sometimes used instead of “CNOT” to avoid confusion.
The reason there are two ways to negate a qubit is because the numbers used to represent the qubits are complex numbers, meaning the flip can occur either by flipping on the real number plane or the imaginary number plane. This has no difference between CX and CY when dealing with simple superpositions like |0〉and |1〉, but if there is a more complex superposition, then there can be a real difference.
Here is some QASM code written in OpenQASM 2.0.
Line 1 specifies the version. Line 2 specifies the include file which defines all the gates that the quantum computer supports. In this case, I’m running this code on a real quantum computer from IBM known as the IBMQ Santiago, and this is the library for the operations it supports.
The fourth and fifth line specify what quantum registers we are using. The “qreg” registers are our qubits. The “creg” registers are for measuring qubits. We may have a program with many qubits, but not necessarily need to measure them all. You can see on lines 11–13, I go ahead and measure all of them. This is how you specify a measurement in QASM, by using the “measure” operation and specify the value of which qubit and which register you want to hold that value. In this case, we specify that we have 3 qubits we are calling “q” and 3 measurement registers we are calling “c” here.
Typically, a quantum computer assumes all qubits start in the superposition of |0〉. I want to see what happens if I add 2 numbers together using this half-adder and I want both numbers to be 1. So I flip them both into the |1〉superposition by applying the Pauli-X gate to both of the inputs.
Now, I want to do the simple addition. The first gate I need to specify is the Toffoli gate. The Toffoli gate in QASM is typically not called “toffoli” but instead “ccx” as it can be thought of as a Controlled-Controlled-Pauli-X gate. It is Pauli-X gate but unlike the CNOT gate that has one control required for it to flip the qubit, it has two controls. I then pass in my three qubits. into the Toffoli gate, shown on line 9. Note that in QASM, typically registers are zero-indexed rather than one-indexed. Then, I apply the CNOT (“cx”) gate on line 10, just like the diagram in the paper shows.
Finally, I measure all three qubits on lines 11–13.
What should we expect the result of this code to be if we ran it on a real quantum computer? The qubits all start in superposition |0〉, or in other words, [1, 0]. If we take the Kronecker product of all three qubits, we get the entire system represented as [1, 0, 0, 0, 0, 0, 0, 0]. We then need to generate four logic filters for this. Luckily, none of these logic filters are with non-adjacent qubits, so the calculation for the logic filters is rather simple.
Remember, if they are adjacent, you do not need to use the more complicated truth table method. You simply can construct the logic gate filter from simpler logic gates using the identity matrix for unchanged qubits. Also recall that all these matrices are on Wikipedia.
CCX (Toffoli):
Pauli-X (NOT):
CX (CNOT):
2x2 Identity Matrix:
Line 7: F₀ = X ⊗ I ⊗ I
Line 8: F₁ = I ⊗ X ⊗ I
Line 9: F₂ = CCX
Line 10: F₃ = CX ⊗ I
Once we have all our logic filters, we can easily simulate this QASM code. If we say the initial state of our quantum computer is ψ ₀and the state after the code is ran is ψ₁, then we can calculate the final state of the quantum computer would be ψ₁ = ψ₀F₀F₁F₂F₃. That is to say, you simply matrix-multiply the initial state of the quantum computer by all the logic filter matrices in the correct order.
Here we see our final predicted rersults after applying all logic gates. In this case, we have a vector [0, 0, 0, 0, 0, 1, 0, 0]. Remember that you can interpret this as probabilities of 000, 001, 010, 011, 100, 101, 110, and 111 respectively. Thus, this is telling us that we should have 100% chance of getting an output of 101.
According to the paper cited, the most significant bit is basically junk. The middle bit is our summation. The least significant bit is our carry bit. Remember, our inputs were 1 and 1. Thus, if this half-adder worked correctly as the paper told us, then the middle bit should be a 0 since 1+1=2 and 2 is too big to be stored in a summation bit and thus will overflow to 0. However, the carry bit will then carry that overflow, and thus the least significant bit should be a 1.
According to our calculations, the code worked! We added two bits together in QASM. But does this work in real life? Here are the results I got from running this QASM code on a real quantum computer.
It turns out that IBM’s quantum computers are not perfect and have some error. Because of this, they do not run the program a single time, but run it multiple times and then average the results. Here we can clearly see 101 has the highest probability.
Let’s also take a look at the code for a simple Bell state. This time we are only dealing with a system of 2 qubits. We talked about the Bell state prior, so let’s actually setup a Bell state of entangled qubits.
The particular Bell state we are going to try is described in the paper “The Importance of Bell States in Quantum Computing” from 16th International Conference on Information Technology-New Generations (ITNG 2019).
In order to set this up, I wrote the QASM code below. Their CNOT gate is “flipped” from my code. This does not make a difference, I simply moved the Hadamard gate to q[0] and the control for the CNOT gate is ony q[0] rather than q[1].
Line 7: F₀ = H ⊗ I
Line 8: F₁ = CX
Now let’s simulate a quantum computer by multiplying these two matrices by an initial state of [1, 0, 0, 0].
Here our outputs have a 50% chance of being 00 or a 50% chance of being 11. Therefore, if we measure the output of one of the qubits, we immediately know the output of the other. One qubit depends on the other.
I ran this one as well on IBM’s IBMQ Santiago and here are real-world results.
As we can see, the results are very noisy, but generally they seem to be what we calculated. The two qubits are entangled and the results of one depends upon the results of the other.
Conclusions
Simulating the logic of a quantum computer is not very difficult. You simply need truth tables for each logic gate, and then when a particular operation is requested, you construct a logic filter based on the logic gate and the requested qubits to apply the operation on. You then simply matrix-multiply the current state of the quantum computer by that logic filter.
I did not use any code in this since I was more concerned about demonstrating how this could be done, although none of this code should be too difficult to implement. You want to first implement code to allow you to deal with imaginary numbers, then you want matrix multiplication and Kronecker product code built on top of that. None of these are particularly difficult nor require any extensive education.
Both the Kronecker product and matrix multiplication are also very easy to parallelize. Doing so is essential if you want to maximize how many qubits you can simulate. Although, this is not the most efficient method to begin with. If you really need efficiency, you should use something that already exists rather than write your own.
