The ‘Simple’ Simulation Algorithm

MATRICES FOR GATES

It was noted in the background section above that complex matrices can represent gates and that a complex vector can represent the state of the quantum system. The simulation of a gate in the system is then a tensor matrix operation on the state vector.

ORIGINAL DESIGN ERROR

Before describing the simulation algorithm I shall explain an error that I made in my original design. I originally believed that each wire in a quantum circuit would require a separate quantum bit to simulate it. For example, I believed that the circuit shown in Figure 17 would require 17 quantum bits to simulate.

The following is a transcript from my log book entries for the 2^nd to the 4^th March 1997.

The original plan was proving hard to develop as I was not sure of the exact formulae for mapping the state to the system at one step in the simulation to the next state. So I did some research (mainly using P W Shor's paper) and came up with a few new ideas and proofs.

1. Shor stated that each quantum circuit must be reversible. This then implies that there must be an equal number of inputs and outputs to the circuit.
2. It was also stated was that each gate must be reversible. This implies that there must be an equal number of input and output pins on each gate.
3. Further, the computation must be reversible. This implies that there must be no bit loss or gain throughout the computation.
4. Due to the reversible nature of the laws of physics, and that the circuit itself must be reversible, it must be possible to simulate parallel gates sequentially and in any order.

Consider the following circuit.

_{Figure 17}

We can then make the computation sequential (from point number 4, above)

_{Figure 18}

Important Deduction

At the end of each stage there are a constant number of bits, the number being equal to the number of input bits to the circuit. Therefore we can model the circuit with just 2ⁿ complex numbers, where n is the number of input bits. Therefore the computation time is now exponential in the size of the input, not in the size of the circuit as I had first thought. An exponential gain!

I have implemented a simulation algorithm based on the above deductions. A simulation of a circuit with 20 input bits and 40 gates required just 180 seconds. Such a simulation would not have been possible with the original design (it would have required 2⁶⁰ steps and 2⁶⁴ bytes of memory).

Out of the four points listed above the first three follow easily from a variety of quantum texts. It was this that led to the reduction in the memory requirements and steps required in the simulation. Point number four led to enough simplifications to develop the simulation algorithm - I simply needed to iterate the simulation looking at each gate turn. Previously I was unsure as to whether the simulation of a set of parallel gates could be performed in this manner or whether I had to perform some special computational tasks. Each gate can now be considered to act on a set of bits.

In hindsight, all the above points are implicit at the very least in a number of research papers. It took me a long time to recognise some of these points because I was unable to follow much of the complex terminology used in these very mathematical research papers.

It was the above reductions that led to the scrapping of 'Quantum Bit Saving' and superpositioned inputs. If the simulation needed to be exponential in the size of the circuit then each bit saving would have halved the simulation time and workspace - an exponential performance increase in the saving. However, with the simulation being exponential in the size of the inputs such idea would have only lead to a linear increase in the size of the saving. Thus saving one gate in a one hundred-gate circuit would only reduce the processing time by 1% and have had no effect on the size of workspace required.

SINGLE GATE SIMULATION ALGORITHM

The simulation of a gate can be carried out by the multiplication of a gate's matrix on its input amplitudes. Thus the square root of not gate acting on a 100% probability of its input being one results in the following computation.

The circuit is visualised in Figure 19.

_{Figure 19}

What happens when there is more than one bit in the circuit? In Figure 20 we see that the second bit in the circuit must retain its value at the end of the simulation of the first bit.

_{Figure 20}

The state vector for the entire circuit is initially , where the first element in the vector relates to the amplitude of observing |00>, the second to |01>, etc. We can see that this input vector must map to , i.e. there is no possibility of observing the second bit with a value of anything other than |1>, and there is an equal probability of observing the lower bit as |0> or |1>. The process to use is to apply the matrix for the square root of not gate to each possible value that may be observed in the rest of the circuit. We see that the second input may be |0> and then apply the square root of not gate. We then consider that the value of the second bit may be |1> and apply the matrix again. In the above example, this is equivalent to using the operation shown below.

The idea had to be extended to cope with any number of bits in the circuit and any number of bits in the gate being processed.

'FUNNY COUNTING'

The size of the intermediate matrix in the above matrix is 2ⁿ x 2ⁿ, where n is the number of input bits in the circuit. Obviously this matrix would be too big to generate for any reasonable size of inputs. Therefore it was decided to perform the smaller individual matrix operations on a selection of the input vector as opposed to attempting to perform one, large matrix multiplication.

Consider an n-gate system. A vector of length 2ⁿ represents the system, which means that we can access individual elements in the vector via an index that is an n bit number. Imagine attempting to simulate a two-bit gate acting on the first two bits of such a system. If we were to denote the bits that the gate operates on by the letter 'G' and the rest of the bits by the letter 'R', then the map of the bits of the index would look like this.

RRR...RRR GG

In order to simulate the gate we need to apply the gate matrix to every possible combination of the other bits in the system. In the current example that involves iterating through the bits denoted by R. The project source code and other areas of this document denote the value of R at some point in the simulation the 'base amplitude' of that point. The bits denoted by G are iterated over to provide the four input elements for the multiplication by the gate's matrix. Thus every element in the [exponential] state vector that represents the system must be accessed to simulate every gate. The mapping for an arbitrary R is shown below.

The mapping for the entire simulation of the example gate is given below.

Now consider that we wish to simulate a gate in an 8-bit system that acts on the input bits five and two. Obviously, as with gates in classical systems the order of the input connections is important. The mapping for the simulation of this gate is shown below. Notice that the iteration over the bits of the gate is carried out in the correct order.

It is easy to extend this algorithm to cope with bits of an arbitrary size.

I dubbed this task 'funny counting' as the iteration of counter that is used to index the state vector increments in a funny order. Pseudo-code to implement this algorithm is shown in the next section.

SIMULATION ALGORITHM

The above ideas can be used to implement a simulation algorithm. The pseudo-code for this algorithm is shown below.

Care must be taken to ensure that the gates are processed in dependency order. If there are two gates in the system such that the second gate depends on the output of the first gate then we must ensure that the first gate is simulated before the second gate. An ordering function is applied to the list of gates in the circuit before the simulation commences to ensure that this condition is not broken.

The operation $ is used to combine the iterations over the base amplitude and the gate amplitude. Bit x in the gate amplitude is mapped to bit y in the base amplitude, where y is the circuit bit which input pin x works on.

A number of basic tests on the values output by the simulator was performed at this stage. See the Testing section later for an overview of the testing algorithms, though note that not all of the tests listed in that section were implemented at this stage.