Add `rustworkx` as a backend for the graph state simulator

[king-p3nguin]

TODO:

• [x] benchmarking page

Details

Description of the change:

• Use rustworkx for GraphState when it is installed

I added five classes as follows:

• GraphState class
  • A factory class that returns an instance of either NXGraphState or RXGraphState.
  • If rustworkx is installed and use_rustworkx=True, it returns RXGraphState.
  • If rustworkx is not installed and use_rustworkx=True, it returns NXGraphState and throws a warning.
  • If rustworkx is installed and use_rustworkx=False, it returns NXGraphState.
  • use_rustworkx=True is the default.
• BaseGraphState class
  • It implements methods that do not depend on the backend and defines abstract methods for maintainability.
• NXGraphState class
  • A graph state simulator based on networkx.Graph.
• RXGraphState class
  • A graph state simulator based on rustworkx.PyGraph
• NodeList and EdgeList class
  • It provides functionality similar to NodeView and EdgeView in networkx.
  • rustworkx.PyGraph stores the information of the node by its index, not by the name like in networkx.Graph which is a major difference. This class will make it possible to specify the node by its name.

    from rustworkx import PyGraph
    nodes = [1, 2, 3]
    graph = PyGraph()
    graph.add_nodes_from(nodes)
    graph[0] # returns 1

  • Note that when you add nodes to NodeList, you need to call the node data {"loop": False, ...} by reference otherwise, modification of the node data like g.node[0]["loop"] = True will not affect the node data in graph object (i.e. it will still be g.graph[0][1]["loop"] = False)

I also:

• Added tests to test the graph state simulator for both backends.
• Changed setup.py to install rustworkx while testing

Related issue:

79

[king-p3nguin]

It seems like there is an issue in inheriting rustworkx classes. Running the following code will throw TypeError:

from rustworkx import PyGraph

class A(PyGraph):
    def __init__(self, nodes=None) -> None:
        super().__init__()
        if nodes is not None:
            self.add_nodes_from(nodes)

x = A(nodes=[0, 1, 2])  # TypeError: PyGraph.__new__() got an unexpected keyword argument 'nodes'

Instead of inheriting a graph object, I will put a graph object in self.graph to avoid this.

[king-p3nguin]

I think it is ready for review. I updated the description.

[masa10-f]

@king-p3nguin

Thanks for your great contributions!! I will review the details of the code tomorrow.

Just a quick review, the current implementation does not work without rustworkx installation although it is not required in the requirements.txt. This is because rx.PyGraph is called at graphix.graphsim.basegraphstate.py l.25. Could you check the whole code without rustworkx installation?

[masa10-f]

Also, would you take a performance comparison between the both graph backends?

[king-p3nguin]

@masa10-f

@king-p3nguin

Thanks for your great contributions!! I will review the details of the code tomorrow.

Just a quick review, the current implementation does not work without rustworkx installation although it is not required in the requirements.txt. This is because rx.PyGraph is called at graphix.graphsim.basegraphstate.py l.25. Could you check the whole code without rustworkx installation?

Oops, I forgot to check that. Thank you for pointing it out. I fixed it and changed the tox.ini to make the test work both with and without rustworkx. (I noticed that setup.py test is deprecated, so fixing that is also included in the change)

[masa10-f]

I benchmarked the performance of both graphsim backends for random quantum(first fig) and QFT(second fig) circuits. For graphs smaller than $10^3$ nodes, rustworkx performs better. However, for larger graphs, its performance was the same as or worse than the networkx backend. I wonder why rustworkx's performance is not as good as networkx's. If we can not resolve this problem soon, we would address it in a separate issue.

[masa10-f]

It looks like there is an error occurs in tests/test_pattern.py::TestPattern::test_minimize_space_with_gflow. The issue seems to be that the quantum circuit for this test is generated randomly, so the output of pattern.minimize_space varies each time we run the test. Also, the maximum space of a pattern with measured Pauli nodes doesn't have a non-trivial upper limit, unlike regular patterns. We could fix this error by reducing the circuit width or fix the random seed. Could you update the test code to address this?

[king-p3nguin]

It looks like there is an error occurs in tests/test_pattern.py::TestPattern::test_minimize_space_with_gflow. The issue seems to be that the quantum circuit for this test is generated randomly, so the output of pattern.minimize_space varies each time we run the test. Also, the maximum space of a pattern with measured Pauli nodes doesn't have a non-trivial upper limit, unlike regular patterns. We could fix this error by reducing the circuit width or fix the random seed. Could you update the test code to address this?

I changed the implementation of tests/random_circuit.py. rc.set_seed(seed_value) will fix the seed throughout the testing process. Related to #65 .

[king-p3nguin]

I think there is a problem with RustworkX graph state's .perform_pauli_measurements(). The following code will not throw assertion error when use_rustworkx=False. I will look into it.

from tests import random_circuit as rc
import numpy as np
from copy import copy
nqubits = 5
depth = 5
pairs = [(i, np.mod(i + 1, nqubits)) for i in range(nqubits)]
circuit = rc.generate_gate(nqubits, depth, pairs, seed=42)
circuit_copy = copy(circuit)

pattern = circuit.transpile()
pattern.standardize(method="global")
pattern.shift_signals(method="global")
pattern.perform_pauli_measurements(use_rustworkx=True)

pattern2 = circuit_copy.transpile()
pattern2.standardize(method="global")
pattern2.shift_signals(method="global")
pattern2.perform_pauli_measurements(use_rustworkx=True)

assert pattern.seq == pattern2.seq  # AssertionError

[masa10-f]

I suggest you check at the state vectors of two patterns instead of pattern sequence. This is because there is a bunch of graph states that are essentialy the same in terms of the quantum state, even if their structures look different. Also, I do not think Rustworkx may contain a mistake because one of the unit tests fails in the Networkx environment.

py38: FAIL code 1 (156.56=setup[44.78]+cmd[111.78] seconds) lint: OK (32.89=setup[31.76]+cmd[1.12] seconds) with_rustworkx-py38: OK (75.67=setup[33.77]+cmd[41.91] seconds) evaluation failed :( (265.30 seconds)

[masa10-f]

@shinich1 I have a question about the graph state simulator. When it receives the same measurement pattern, will the processed graph state always be the same, or can they vary?

[shinich1]

@shinich1 I have a question about the graph state simulator. When it receives the same measurement pattern, will the processed graph state always be the same, or can they vary?

Pauli measurements in the graphs state simulator do have some degree of freedom (for example, depending on the order of node coming up in neighbors the resulting graph structure can change via this code). so if you have different backend you might end up with equivalent graph states with different underlying graph and LC.

[king-p3nguin]

As you say, it looks like .neighbors() in rustworkx returns a different result each time, making a difference in the pattern. The algorithm does not seem to have a problem, so I just reduced the circuit size in the tests.

[king-p3nguin]

(I will add the benchmarking page later.)

[masa10-f]

@king-p3nguin Great job! Thanks a lot for your fantastic contribution. Just checking, have you made all the changes you wanted to? If that's the case, please update the CHANGELOG.md before we go ahead with the merge.

[shinich1]

@king-p3nguin how about comparing with Anders&Briegel graph sim? e.g. https://github.com/libtangle/graph-state in principle, we could also compare with stabilizer simulators (e.g. stim) but that might be too much work and functionalities are a bit too different (no direct extraction of graph). Also long shot but pyzx/quizx could be compared with good amount of coding..

[king-p3nguin]

@shinich1 Thank you for the suggestion! I added their graph state simulator to the benchmark.

[shinich1]

@king-p3nguin thanks! interesting that graph-state works so much better. perhaps the restriction to only three types of graph decorations in the Elliot et al., is adding the complexity.

[shinich1]

@king-p3nguin another point - I tried to implement from Anders&Briegel paper some time ago but never managed to make it return the correct result - and graph-state do not seem to have unit tests.

it might be tricky due to LC and local complementation degree of freedom, but could you check that the graph-state is always returning the correct result (compare with our graph sim, by turning them into statevec)?

[shinich1]

@king-p3nguin have you built benchmarks page on readthedocs (did it pass)? since you're working on fork you will have to start build on your own rtd account (it's easy).

[king-p3nguin]

@masa10-f Thank you for the review! @shinich1 Actually, I always build the document locally to check it (that's why I forgot to push the requirements.txt). Should we make ci to test building the document (only when it is modified)?

[shinich1]

@masa10-f Thank you for the review! @shinich1 Actually, I always build the document locally to check it (that's why I forgot to push the requirements.txt). Should we make ci to test building the document (only when it is modified)?

it's good to check on RTD because it always start with a fresh environment defined by requirements.txt (for example, it would not have worked without addition of graph-state as pointed out above by @masa10-f). CI is not really necessary for this.

[masa10-f]

I've tested the same benchmark for larger graphs and it looks like our graph sim scales a little worse than Anders and Briegel's. We have to accurately figure out this issue stems from the graphsim algorithm or from other part of implementation. But, this is out of scope of this PR. Let's discuss it in a separate issue before we start coding.

Regarding the performance, rustworkx hasn't shown a siginificant improvement over networkx, but @king-p3nguin 's modifications have greatly enhanced the performance of pauli measurements(in my environment, pauli measurements in example/qft_with_tn.py improved from 34.4sec -> 12.9sec!). Thanks for the fantastic contribution! Additionally, rustworkx would perform its true potential when we use more complex graph algorithms, I think we will use some of them in the future, for example graph embedding problem(?)

I think this branch can be merged into master. Do you have any comment or review on the current branch? @shinich1 Have you done all the modifications you plan? @king-p3nguin

[king-p3nguin]

@king-p3nguin another point - I tried to implement from Anders&Briegel paper some time ago but never managed to make it return the correct result - and graph-state do not seem to have unit tests.

it might be tricky due to LC and local complementation degree of freedom, but could you check that the graph-state is always returning the correct result (compare with our graph sim, by turning them into statevec)?

@masa10-f I have not finished the validation of Anders & Briegel's graph state simulator as in @shinich1's comment, and I may need to implement an algorithm to check the equivalence of two graph states (e.g. https://arxiv.org/abs/quant-ph/0405023), but it's getting off-topic, so we could put this task into issue and merge this PR.