ZX calculus optimization pass

1ucian0 commented 3 years ago

@levbishop recently asked my about a the status hackathon project to integrate ZX calculus in Qiskit Terra. From what I remember, it there was some coding challenges and their pass was doing DAG->CIRCUIT->QASM->pyZX(with some modifications)->QASM->CIRCUIT->DAG.

So... the question is if there is interest for a proper ZX calculus. If so, we should discuss the size of that technical challenge. Maybe @eliasrg, @the-wag, @we-taper, @chunlam-chan, and @jean-philippe-arias-zapata have comments?

ewinston commented 3 years ago

@the-legend-of-lia worked on this a couple of years ago and currently is in Aleks Kissinger's group so she might have some comments as well.

lia-approves commented 2 years ago

I worked with Emma Dasgupta ( @edasgupta ) and @ewinston on this in 2019 when Emma and I interned at IBM Q as undergrads. At the time, PyZX was GPL license and Qiskit is Apache 2.0, so their licenses weren't compatible and so we couldn't integrate the code bases to add a PyZX transpiler pass to Qiskit. Since then PyZX has changed to Apache 2.0, so without that legal obstacle a PyZX transpiler pass in Qiskit should be implementable. It would be good to re-create and maintain such a pass. In the next comment I'm linking to the relevant code of the pass by me and Emma in 2019 and a writeup. These are out of date with present-day PyZX and Qiskit, but more importantly I believe it describes the approach of how to implement a PyZX transpiler pass in Qiskit. I think to get it up and running with the latest Qiskit and PyZX versions is an exciting and feasible project for, say, one or two undergraduate students. There is a PhD student working with Aleks Kissinger to implement PyZX functionalities including symbolic angles.

lia-approves commented 2 years ago

A writeup summarizing our 2019 PyZX transpiler pass in Qiskit is at https://src.acm.org/binaries/content/assets/src/2020/lia-yeh.pdf The code structure was kept simple so it builds on top of Qiskit and PyZX, rather than changing the existing code and potentially breaking backwards compatibility.

In PyZX, we added two files to the folder at https://github.com/lia-approves/pyzx/tree/master/pyzx/circuit :

qiskitqasmparser.py which extends the QASMParser class to QiskitQASMParser, to add additional functionality of many cases that the QASMParser at the time couldn't parse, as detailed in the above writeup. Another approach could be to directly modify QASMParser, which would be a decision that should be made by maintainers of PyZX like @jvdwetering .
qiskittranspilerpass.py , the transpiler pass itself which takes in a QASM string, parses it with QiskitQASMParser to PyZX graph, optimizes the PyZX graph, extracts a quantum circuit, and returns the QASM of the quantum circuit Since 2019, the present version of PyZX's QASMParser supports some more of but not all of QASM. The exact optimization routine call in PyZX should be an external function call of the pass so the user can tweak it as desired, and because the exact function calls has changed and will continue to change as PyZX is improved.

In Qiskit, we have a few examples which ran the transpiler pass to optimize various types of circuits, in the folder at https://github.com/lia-approves/qiskit-terra/tree/master/qiskit/transpiler/pyzxpass :

rbpyzx.py , qvpyzx.py , and feynmanpyzx.py respectively generate Qiskit QuantumCircuits for randomized benchmarking, quantum volume, and the Feynman quantum circuit benchmarks, then call to pyzxbenchmark.py to optimize them
pyzxbenchmark.py decomposes the quantum circuits into QASM, runs the transpiler pass imported from PyZX, and from the optimized QASM reconstructs a Qiskit QuantumCircuit. The output is pickled so that it can be subsequently analyzed.
analyzebenchmark.py takes in the pickled outputs, and generates plots to compare for instance gate depth or gate count of the original circuit and the circuit with PyZX transpiler pass and/or Qiskit optimization.

mtreinish commented 2 years ago

In general if you're going to propose adding a transpiler pass directly to terra to leverage pyzx I think that you'll need to remove the intermediate qasm representation. There shouldn't be any requirement on going through qasm as if you take the topological ordering of the DAGCircuit input to pass.run() you'll have basically a superset of the information available in a qasm representation. So the pass should go from a DAGCircuit to a PyZX graph/circuit directly using the pyzx python api (you probably could refactor the custom qasm parser fairly easily to just remove the qasm piece and just iterate over the dag and create the pyzx object in the same way).

ewinston commented 2 years ago

I briefly looked at benchmarking this again in Nov 2021 using small circuits from QASMBench. I compared the depth compression ratio of pyzx against optimization_level=3 in qiskit.

I also looked at ratio of non-local gates,

The main improvement seems to be in the UCC circuits. There is a paper on handling UCC circuits in zx, so it may be a special case optimization was incorporated.

arXiv:2007.10515 arXiv:2003.13599

dlyongemallo commented 8 months ago

What's the status of this issue? Has the code to add a ZX-calculus pass to Qiskit been submitted?

1ucian0 commented 8 months ago

As far as I know, the closes to it was https://github.com/gprs1809/ZX_to_DAG_QAMP_fall_2022, in the context of https://github.com/qiskit-advocate/qamp-fall-22/issues/27

I didn't take a look to the code yet. If you do, let us know if this issue can be closed!

dlyongemallo commented 8 months ago

That project was never completed due to its being blocked by https://github.com/Quantomatic/pyzx/issues/102 which I recently fixed. That is why I'm following up here, to see if such a pass has already been added, and if not, whether there is interest in doing so now that the blocking issue has been resolved.

1ucian0 commented 8 months ago

Sure! Qiskit currently handles this form of integration through transpiler plugins, which offers a flexible and efficient approach: eliminates the need to submit a pull request to the Qiskit codebase, making it easier to maintain and sets a clear owner. You can take a look at a similar project, qiskit-tket-passes, to get a better idea of how it would work.

dlyongemallo commented 7 months ago

to leverage pyzx I think that you'll need to remove the intermediate qasm representation

Maybe I'm missing something. I can see that in general the DAG has more information than the qasm representation, but is there any advantage to using the DAG directly specifically for pyzx? What information is available and usable to pyzx in the DAG, which isn't also already in the qasm representation? I have written up a zx transpiler using qasm as an intermediary format and I'm wondering what can be improved by using the DAG directly.

mtreinish commented 7 months ago

There are two factors to consider. The first is that a DAG <-> QASM translation is inherently lossy, not because of the DAGCircuit but because Qiskit can represent objects in a circuit that are not representable in QASM. When this happens the qasm exporter goes to some effort to try and translate them into something qasm can express. The best example is something like UnitaryGate in QASM 2.0 there is no way to represent a unitary matrix in a qasm file, so the circuit qasm exporter will run a unitary synthesis method on the matrix and use the synthesized circuit in place of the matrix. This might be at odds with what the transpiler is expected to do, continuing the UnitaryGate example if the user specifies a custom synthesis method is used, that won't be respected by the qasm transformation. Once you make that transform there is not a way to get back the information you've thrown away in the qasm file. If PyZX can't deal with these objects we can detect that if we do the conversion directly and either skip the PyZX optimization pass or potential identify a subcircuit to pass to pyzx and optimize just that.

The second concern is just from a practical PoV, things will be unnecessarily inefficient going from DAGCircuit -> QuantumCircuit -> QASM String -> PyZX object -> QASM string -> QuantumCircuit -> DAGCircuit. You're just spending a lot of wasted effort doing conversions when it is possible to go straight from a DAGCircuit to PyZX and cut out all those extra steps.

dlyongemallo commented 7 months ago

I've uploaded my implementation of a ZX transpiler for Qiskit here: https://github.com/dlyongemallo/qiskit-zx-transpiler

This implementation converts directly between DAGCircuit to PyZX's own circuit format (without going through qasm), and leaves unsupported operations like UnitaryGate alone (by removing them and then adding them back after optimisation).

As a sanity check, I re-created the benchmark from https://github.com/Qiskit/qiskit/issues/4990#issuecomment-1157858632 above.

Depth compression ratio Ratio of non-local gates

As both Qiskit and PyZX have changed in the interim, there are some slight differences, but the results look mostly the same. There was one major difference, though. I had to leave out dnn_n2 as the Qiskit depth compression ratio was over 19, and including it would've made the rest of the plot hard to see.

What else should I do to test or benchmark the implementation? Does anyone have suggestions for anything to improve?

dlyongemallo commented 4 months ago

What work remains to be done to close this issue?

1ucian0 commented 3 months ago

indeed... This issue can be closed. Would you like to present your ZX transpiler for Qiskit in Qiskit Demoday?

dlyongemallo commented 3 months ago

indeed... This issue can be closed. Would you like to present your ZX transpiler for Qiskit in Qiskit Demoday?

Sure. I need some time to work on exposing the transpiler as a plugin, though, so maybe we can aim for the May date?

Qiskit / qiskit

ZX calculus optimization pass #4990