[WIP] restructuring MCX synthesis code

[alexanderivrii]

Summary

This is an experiment to restructure the code for MCX gates. In particular:

• we aim to separate the synthesis algorithms for MCX gates from the definition of the MCX gate
• make adding new synthesis algorithms for MCX gates easier

Currently the code is there to allow discussing APIs, etc.

Details and comments

There is a new file qiskit.synthesis.mcx_synthesis.py which has the actual synthesis algorithms

There is only one MCXGate class, but with different synthesis algorithms (MCXSynthesisGrayCode, MCXSynthesisRecursive, MCXSynthesisVChain)

The classes MCXRecursive, MCXVChain, MCXGrayCode remain for backward compatibility, and under the hood create an MCXGate with the matching synthesis algorithm.

The code for QuantumCircuit.mcx is also simplified, and in particular avoids building all different gate types when constructing the dict available_implementations

[coveralls]

Pull Request Test Coverage Report for Build 1722743718

• 246 of 258 (95.35%) changed or added relevant lines in 3 files are covered.
• 266 unchanged lines in 12 files lost coverage.
• Overall coverage increased (+0.01%) to 83.156%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/circuit/quantumcircuit.py	6	8	75.0%
qiskit/circuit/library/standard_gates/x.py	63	68	92.65%
qiskit/synthesis/mcx_synthesis.py	177	182	97.25%
<!--	Total:	246	258

Files with Coverage Reduction	New Missed Lines	%
qiskit/assembler/run_config.py	1	95.45%
qiskit/utils/run_circuits.py	1	30.79%
qiskit/circuit/add_control.py	2	95.28%
qiskit/pulse/instruction_schedule_map.py	5	95.39%
qiskit/test/base.py	5	83.17%
qiskit/compiler/assembler.py	6	96.2%
qiskit/execute_function.py	6	90.63%
qiskit/qobj/qasm_qobj.py	20	83.01%
qiskit/pulse/schedule.py	35	86.4%
qiskit/qobj/pulse_qobj.py	39	76.79%
<!--	Total:	266

Totals
Change from base Build 1700054446:	0.01%
Covered Lines:	52034
Relevant Lines:	62574

---

💛 - Coveralls

[Cryoris]

One additional comment about naming: the names of the synthesis classes, like MCXSynthesisVChain, seem a bit long to me now. That they are "synthesis" classes should be clear from the import path so we can probably drop that and reduce e.g. to MCXVChain:

from qiskit.synthesis import MCXVChain

Maybe we can even go a step further and drop the MCX prefix since that should be visible from the directory:

from qiskit.synthesis.mcx import VChain

[alexanderivrii]

@Cryoris: I am happy to change names of the synthesis classes. However, calling a synthesis algorithm MCXVChain is bad as this clashes with the already existing gate name. VChain is better, but then (following the same logic) I should call the other algorithm GrayCode and Recursive, and somehow the word "recursive" seems not specific enough. So please suggest what I should call these.

[Cryoris]

Yeah I agree "recursive" is not the best name, in particular since there are many schemes you could classify as recursive (see e.g. sections 7.2 and 7.3 in https://arxiv.org/pdf/quant-ph/9503016.pdf). Looking at the structure, this particular recursion always halves the number of controls, so how about SplitRecursion or BinarySplit (referring to binary search which halves the search interval) or just TrickleDown? Other suggestions are very welcome!

[alexanderivrii]

@Cryoris, many thanks for your feedback! Actually, I will ask: would you like to work on this together? In a sense, we are doing this already. :)

One tricky complication (that I do not quite know how to resolve) is: given an MCX gate with some kind of a synthesis algorithm gate = MCXGate(num_control_qubits, some_synthesis_algo), what should be the synthesis algorithm for the controlled version of this gate, for example for gate.control(3)? Previously, controlled versions of CCX, C3X and C4X gates automatically used the "noancilla" synthesis algorithm, while controlled versions of MCXGrayCode, MCXVChain and MCXRecursive were also respectively MCXGrayCode, MCXVChain and MCXRecursive. I am trying to keep it the same way by using the same synthesis algorithm for the controlled version as for the original version. However this probably does not offer the full flexibility of doing things. Additionally, once we define a special synthesis class for X gates controlled by 3 qubits, it does not make sense to use it for controlled versions of C3XGate. Maybe we should extend the abstract synthesis interface with a method to return a synthesis algorithm for the controlled version of the gate? Or is there a better solution? And what about inverse of a gate? Currently we always use the same synthesis algorithm as for the original gate, but maybe we want to use the "inverse" algorithm to allow more pairwise cancellations?

Another problem (the test failure above) happens because I wanted to move the method __array_ from C3X and C4X gates to the MCX gate, however this only works when there are no ancilla qubits. So my last change was to allow __array__ to return None, but this is also problematic since there are multiple places in code which check hasattr("__array__"), and expect the method to return a real numpy array.

[Cryoris]

One tricky complication (that I do not quite know how to resolve) is: given an MCX gate with some kind of a synthesis algorithm gate = MCXGate(num_control_qubits, some_synthesis_algo), what should be the synthesis algorithm for the controlled version of this gate, for example for gate.control(3)? Previously, controlled versions of CCX, C3X and C4X gates automatically used the "noancilla" synthesis algorithm, while controlled versions of MCXGrayCode, MCXVChain and MCXRecursive were also respectively MCXGrayCode, MCXVChain and MCXRecursive. I am trying to keep it the same way by using the same synthesis algorithm for the controlled version as for the original version. However this probably does not offer the full flexibility of doing things. Additionally, once we define a special synthesis class for X gates controlled by 3 qubits, it does not make sense to use it for controlled versions of C3XGate. Maybe we should extend the abstract synthesis interface with a method to return a synthesis algorithm for the controlled version of the gate? Or is there a better solution?

Generally I would say users should use the MCXGate directly if they need full flexibility. We don't have to break a leg to allow changing synthesis algorithms at different points -- it's better to keep the code simple.

For the controlled versions of MCXGrayCode, Recursive and VChain I think we should just use the same synthesis for the controlled versions. For the ones with a fixed number of controls that's more tricky... We could

(1) extend the interface with a control method, as you suggested or (2) extend it with some property checking if it supports that number of control qubits, and if not fall back to a default.

And what about inverse of a gate? Currently we always use the same synthesis algorithm as for the original gate, but maybe we want to use the "inverse" algorithm to allow more pairwise cancellations?

I think the inverse should just use the same synthesis for simplicity.

[ShellyGarion]

Another synthesis method for MCX gates is mentioned in this issue: #5872

If we also allow ancillas, then I think that the best method appears here: https://arxiv.org/abs/1508.03273

[ShellyGarion]

Note that there are some related PRs on multi-controlled gates: https://github.com/Qiskit/qiskit-terra/pull/9574 https://github.com/Qiskit/qiskit-terra/pull/9687 https://github.com/Qiskit/qiskit-terra/pull/9688

[adjs]

Thanks @ShellyGarion. There is also #8710.

[alexanderivrii]

We definitely need to rethink this, but this specific PR is outdated and can be closed.