Significant performance improvement by implementing __eq__()

[cgogolin]

I recently did some simple profiling with cProfile on circuits that consist mainly of single qubit rotations and CNOTs. It turned out that in my case about half (!) of the accumulated time was spend in BasicGate.__eq__().

The reason for this is that _send_qubit_pipeline() does a lot of operation comparisons when finding the gateloc. As CNOT is the controlled version of XGate() and the latter is a SelfInverseGate, which is a subclass of BasicGate, the __eq__() method of BasicGate is called a lot. Now, the problem is that BasicGate.__eq__() does a comparison of the matrices of the involved gates (!) if they both have one.

When comparing a CNOT or a XGate with another BasicGate with a matrix this is clearly extremely wasteful, as any two XGates that act on the same qubit are equal. By adding the following __eq__() method to XGate

    def __eq__(self, other):
        return isinstance(other, self.__class__)

I was able to reduce the total run time of my circuit from 409.136 seconds to 172.695 seconds!!!

I would directly provide a pull request that adds an __eq__() method to XGate and other similar gates, but would first like to discuss this. I think, that all gates whose matrix property is fixed (i.e., is always the same for any two instances of the respective class) should overwrite __eq__(). As there are many such gates, is is maybe worth introducing a new new subclass (called e.g., FixedMatrixGate) that implements this more efficient __eq__() and then have all those gates inherit from that class. The only downside is that if some other (possibly user-defined) BasicGate or a RotationGate happens to be by chance almost equal to, say, a XGate, then this would no longer by recognized. This however seems to be unlikely in real world code.

[damiansteiger]

That's a very good observation. We lately changed BasicGate to compare matrices as we (and others) have been using it to define custom gates defined by matrices for quick testing. In some applications this might lead to a performance bottleneck and we have been planning to change it in the next release as we noticed this slowdown in a different context, too. It will be a breaking change: probably by adding a special gate class for gates whose matrix is allowed to change and remove matrix comparisons for all others...

This would be a great first pull request to get started to contribute to ProjectQ :-) If you like to do it, I can write a list of changes which I would suggest to compare with your solution and then you could start to work on a pull request. How does this sound?

[cgogolin]

Sounds good :-)

[damiansteiger]

How does the following solution sound to you?

• Remove the matrix comparison from __eq__ of the BasicGate as by default as we don't want to work with matrix comparisons but only return isinstance
• matrix is already a property of gates (such as e.g. XGate). We should move the definition for gates which have a fixed matrix into an attribute _matrix which is returned by the matrix property getter and make the matrix property setter raise an exception so that user cannot change matrices anymore
• Create a derived class MatrixGate from BasicGate whose __eq__ tests for matrix equivalence (slower) but allows a user to set the matrix property. This new gate class can be used in our test codes which sometimes use BasicGate with a custom matrix

Only thing to decide is how to deal with

gate = MatrixGate()
gate.matrix = np.matrix([[0,1],[1,0]])
gate == X  # calls gate._eq__
X == gate  # calls BasicGate.__eq__

1. Maybe we should add to the BasicGate.__eq__ a branch isinstance(other, MatrixGate) and then compare matrices so that it works as expected (could be solved by returning NotImplemented). This might still have slowdown.

2. Or in the long run we don't want MatrixGates and hence don't check for the matrix in the BasicGate.__eq__, that would make it faster but X == gate returns False

I think solution 1) would be nice if the slowdown is not to large compared to 2).

Any opinions or different solutions?

[cgogolin]

That's exactly how I would have proposed to fix it. I will try to find time to implement this soon.