Add architecture aware re-synthesis transpilation passes

[Aerylia]

It has been shown that, under certain conditions, it is more efficient to resynthesis parts of a circuit rather than attempting to route the circuit using SWAPs (https://arxiv.org/abs/1904.00633). It would be nice if the Qiskit transpiler contained one or more passes that do such a thing.

In particular, I would like to implement the PermRowCol algorithm (https://www.qplconference.org/proceedings2022/QPL_2022_paper_99.pdf) as a compiler pass that re-synthesizes the CNOT blocks in a circuit. Later, other passes could be added, such as the re-synthesis of phase polynomials (CNOT+Rz circuits) (https://arxiv.org/abs/2004.06052).

[1ucian0]

Hello Arianne! This seems like a good way to pilot the new transpiler plugin interface and write an external plugin that can be added to the qiskit ecosystem.

What do you think?

[Aerylia]

Hi Luciano! Yeah, that sounds like a great idea. I hadn't heard about the transpiler plugins yet.

Looking a bit closer at the existing code, the project would provide an alternative to LinearFunctionsSynthesis that takes a given topology into account and performs the synthesis up to permutation. I have a few bachelor students working on implementing this as a software engineering project. So I can be responsible for the coding part of the project. If they are fast, the project can be extended to an architecture-aware version of graysynth.

How do you think we should go about building such a plugin? We could base it on UnitarySynthesisPlugin, except that we are not synthesizing from a unitary. And I wonder how easy it would be to interchange LinearFunctionsSynthesis with PermRowCol.

And full disclosure. those papers I linked before are mine ;)

[mtreinish]

There is ongoing work on adding a new plugin interface for more general synthesizing higher level objects like linear functions as a dual of the unitary synthesis plugin interface. You can see that in progress here: https://github.com/Qiskit/qiskit-terra/pull/8548

If you have any thoughts on what that interface should look like please feel free to review the pull request and leave comments.

[alexanderivrii]

It would indeed be great to have additional linear and linear+phase resynthesis methods in Qiskit or in Qiskit ecosystem, so additional contributions are welcome!

As @mtreinish pointed out, the plugin interface from #8548 should in theory enable easy integration of such methods in Qiskit, but it probably misses some key features at the current stage such as coupling_map.

There is also a transpiler pass that collects blocks of CX and SWAP gates into LinearFunctions, and there is ongoing work to improve this pass further by taking commutativity between gates into account: #8319.

FYI, an intern of Dmitri Maslov has also done some recent work on synthesizing linear functions targeting circuit depth, @ShellyGarion is currently working on incorporating these methods into Qiskit: #8568.

[Aerylia]

Sorry it took a bit to get back to you.

Considering all the on-going projects, from which branch can we best start implementing this feature?

[1ucian0]

You can start your own repo from scratch or using this template https://github.com/qiskit-community/quantum-prototype-template. For examples, #8548 is a good starting point.

[1ucian0]

If you have comment or suggestion about the interface, feel free to open a new issue with them. Closing this one as it will be implemented as plugin.