scottmckuen
commented
2 months ago Example: two consecutive gates operating on the same wires can be multiplied to make a single operation, without tensoring the I's for the untouched wires.
Example: two simultaneous gates operating on different wires can be tensored to make a single n-wire gate, potentially avoiding the need to do a bunch of identity-tensoring operations
In the n-bit comparator circuit, we end up doing all the identity tensoring up front and the multiplying everything together. This guarantees that the state is always at its maximum possible size and all of our matrix operations are on the largest possible size. Incredibly wasteful.
We are kind of writing a compiler here. We need to treat the circuit as effectively an abstract syntax tree before doing any operations. So the first step of our refactoring is to separate into circuit-defining stages and circuit-executing stages.
Currently we're not able to handle a particular comparator circuit on 4-bit integers (memory use goes over 12GB). The example is a 19-qubit circuit that we fully instantiate as a matrix mid-computation. I think that means 2^38 entries in each matrix - clearly we need some way to reduce the intermediate matrices.