Add local complementation function to EGraph class 📌👥

[bestquark]

This issue has been tagged for a bounty during unitaryHACK.

Task

Check if two graph states are equivalent under local Clifford gates (equivalently, if their underlying graphs are equivalent through a sequence of local complementations -- see here).

To do so, you should:

• Add a is_lc_equivalent() method to the EGraph class that compares two EGraph objects. This method should be capable of checking if the two graphs represented by EGraph can be related by a sequence of local complementations, and should return True or False accordingly.

Explanation

It would be a good feature to compare two different graph states and determine if they are equivalent under local Clifford operations. This function would be capable of identifying as equivalent, e.g., a complete_graph state and a star_graph state with the same number of qubits.

Requirements

• You should implement corresponding unit tests to the functions you will introduce.
• See the link above as well as here for the polynomial-time algorithm to achieve this.

[JLenssen]

Hi, I would be interested in working on this. Would require some time though to study the linked papers in more detail.

[bestquark]

Hi @JLenssen, great! :)

[isolatedinformation]

What would be the expected call signature?

@staticmethod
def is_lc_equivalent(graph1: "EGraph", graph2:"EGraph"):
	pass # relevant implementation of the algorithm
# or 
def is_lc_equivalent(self, graph2:"EGraph"):
	pass # relevant implementation of the algorithm

[smtsjhr]

Hello : ) I am here from UnitaryHack and have been trying to prototype an algorithm for this the past couple days! I have made some fair progress, but still have some issues.

Excuse me if this is not the best place to ask, but I am hoping to get in touch with any others interested in working on this together or just share some insights.

@isolatedinformation @JLenssen I couldn't find you in the UnitaryFund discord. No obligation of course, but feel free to find me on discord @smtsjhr or elsewhere.

[bestquark]

Hi @isolatedinformation, thanks for your question! :)

The static method signature might be better

@staticmethod
def is_lc_equivalent(graph1: "EGraph", graph2:"EGraph"):
	pass # relevant implementation of the algorithm

[isolatedinformation]

Is there some doc available behind the concept of macronodes and EGraph? I'm also assuming LC equivalence should also work when macronodes=True

[ilan-tz]

Is there some doc available behind the concept of macronodes and EGraph? I'm also assuming LC equivalence should also work when macronodes=True

Hey @isolatedinformation ! Technically LC equivalence (where the 'C' stands for complementation) is a property of the graph that underlies an EGraph. Therefore, it should work with any EGraph, including one that corresponds to a macronized lattice.

But what does it mean in practice? If you interpret an EGraph as a qubit graph state, equivalence via local complementation on the underlying graph implies equivalence under Clifford gates on the graph state. This is one of the benefits of having such a method.

In FlamingPy, graph states corresponding to QEC codes are represented by (non-macronized) EGraphs, so the above interpretation goes through. Macronized graphs, however, are an intermediate object used to model specific architectures and apply CV-level noise to the QEC code. Therefore, while they can also be interpreted as qubit graph states in a limited sense, there is not as much utility in the LC check method. (More concretely, a macronode EGraph will just be a collection of 'dumbbells' o-o that are completely disconnected from one another. Therefore the only LC equivalent graphs will just be those with local permutations of the nodes).

tl;dr The LC equivalence check should work for any EGraph, including a macronode graph (and I don't think the implementation will change), but it will have limited utility in this case.

For a little more on macronodes, have a look at this ref from our README: DOI:10.1103/prxquantum.2.040353.

[soosub]

Hi @isolatedinformation! If you are interested, the concept of macronodes was introduced in this paper (arXiv) by the architecture team from Xanadu. However, you don't have to worry about it in this PR/issue because the equivalence under local complementation should be a property of the EGraph (and what macronozing essentially does is creating a different EGraph). To understand what the EGraph is, you can have a look at our tutorial on graph states. Essentially, we represent our graph (and cluster) states as "enhanced" NetworkX graphs where the nodes are placed in a 3-dimensional space.

EDIT: also have a look at @ilan-tz's reply which is a bit more elaborate 🐎

[isolatedinformation]

Thanks guys! This is useful. It clears what the domain of the inputs will be.

[smtsjhr]

This issue simply requests the function to return a boolean True or False for the LC equivalence. However, the algorithm referenced in the literature is constructive and can also specify the Local Clifford operation (in binary symplectic form), whenever the equivalence is satisfied.

I would like to inquire if there is any interest or utility in enhancing this functions design requirements to also return the relevant Local Clifford?

If so, we can go even further and express this Local Clifford in various relevant ways. For instance, the Local Clifford can be given as a single global operator acting on all qubits, or a list of single qubit Local Cliffords -- the tensor product of which yields the global operator.

Whether or not this additional functionality is desired in the public method, the info provided by the Local Clifford when it exists could still be useful for testing purposes.

[soosub]

@smtsjhr Yes, that would be great! Since the algorithm is constructive, it's not too much work and can have a host of benefits (like testing as you mentioned). Thanks for sharing the idea 💡

For the others in this thread (@isolatedinformation, @JLenssen): to keep it fair, this is not a must for the completion of this challenge. However, it is definitely nice to have it in your implementation.