Reducing Memory Requirements in Cove

With Cove, I've never spent much time on making the simulation efficient. Instead I've been focusing my efforts on creating a usable framework. Furthermore, once we have quantum computers any work spent on efficient simulations is largely a mute point.

Not taking into account tricks for efficient simulation, any simulation of a quantum computer requires exponential memory. This is best illustrated by expressing a quantum register (a collection of qubits) as a matrix. Each cell in the matrix is the probability amplitude of the register collapsing to that state. (These are also complex numbers.) As an example, we can consider a two qubit register:

So that's why we need an exponential number of cells: 1 qubit is expressed by 2 complex numbers, 2 qubits by 4 complex numbers, 3 by 8 complex numbers, and so on.

Operations are expressed by a 2^n x 2^n matrix, when they operate on n qubits. So a controlled not operation is a 4 x 4 matrix. Simple linear algebra shows how the operation is applied, here is an example of performing a not operation:

The math dictates that the operation is that 2^n x 2^n matrix. So what happens when the not operation is applied to a 4 qubit register? In Cove I used explicit matrix expansion [1]. That means that the matrix of the operation is expanded, in this case it would be a 16 x 16 matrix. Obviously this eats up a bunch of memory and this was pretty obvious early on. So to apply an operation on a n qubit register I needed 2n + (2^n)^2 complex numbers: the 2n for the state of the register before and after, and the (2^n)^2 for expanded operation. With this I hit memory limitations with no more than a few handfuls of qubits.

This past week I reduced the memory requirements quite a bit in change set [925]. This is something I've been meaning to do since this past spring. Basically what I did was expand the operation matrix one row at a time instead of all at once. This essentially cut the memory requirements down to 3n for a n qubit matrix. So I should be able to simulate much larger systems now.

References

[1] L. Spector, Automatic Quantum Computer Programming: A Genetic Programming Approach, 1 ed. New York, NY: Springer Science and Business Media, LLC, 2004.