Summary

This PR significantly improves the high-level-synthesis plugin for synthesizing AnnotatedOperation objects and in particular the synthesis of hierarchical circuits involving controlled subcircuits. Addresses #13566. Should be rebased on top of #13813. Does not need #13870, but serves as a basis to that PR explaining why we want to change the default handling of controlled gates to annotated gates.

In addition, the PR improves synthesis of multi-controlled CZ-gates and synthesis of controlled QFT-adders.

Details and comments

Multi-controlled X-gates

Here are experiments for the following 4 simple quantum circuits. All of these circuits are equivalent to a 6-controlled X-gate, however they are constructed in somewhat different ways: circuit1 is a 6-controlled X-gate; circuit2 is a 5-controlled CX-gate; circuit3 is a 2-controlled quantum circuit that contains a 3-controlled CX-gate; circuit4 is the same as circuit3, however the controls are added as annotations rather than being eagerly synthesized.

# circuit1: 6-controlled X
qc = QuantumCircuit(15)
qc.append(XGate().control(6), [0, 1, 2, 3, 4, 5, 6])

# circuit2: 5-controlled CX
qc = QuantumCircuit(15)
qc.append(CXGate().control(5), [0, 1, 2, 3, 4, 5, 6])

# circuit3: hierarchical circuit morally equivalent to 5-controlled CX
inner = QuantumCircuit(5)
inner.append(CXGate().control(3, annotated=False), [0, 1, 2, 3, 4])
controlled_inner_gate = inner.to_gate().control(2, annotated= False)
qc = QuantumCircuit(15)
qc.append(controlled_inner_gate, [0, 1, 2, 3, 4, 5, 6])

# circuit4: hierarchical circuit morally equivalent to 5-controlled CX
inner = QuantumCircuit(5)
inner.append(CXGate().control(3, annotated=True), [0, 1, 2, 3, 4])
controlled_inner_gate = inner.to_gate().control(2, annotated=True)
qc = QuantumCircuit(15)
qc.append(controlled_inner_gate, [0, 1, 2, 3, 4, 5, 6])

We are going to transpile these circuits with HighLevelSynthesis(basis_gates=["cx", "u"]).

MAIN:

CIRCUIT1: {'u': 57, 'cx': 30}
CIRCUIT2: {'u': 57, 'cx': 30}
CIRCUIT3: {'u': 1575, 'cx': 974}
CIRCUIT4: {'u': 849, 'cx': 574}

THIS PR:

CIRCUIT1: {'u': 57, 'cx': 30}
CIRCUIT2: ({'u': 57, 'cx': 30}
CIRCUIT3: {'u': 1543, 'cx': 990}
CIRCUIT4: {'u': 57, 'cx': 30}

As we can see, both circuit1 and circuit2 are efficiently synthesized before and after this PR (note that the synthesis algorithm uses available ancillary qubits). However, the hierarchical circuit3 is synthesized very poorly: due to eagerly synthesizing control logic, we first construct the circuit for a 3-controlled CX-gate, and then control every gate in this circuit using 2 additional controls. To improve the above, we need to do two things: create controlled gates as annotated gates (using annotated=True) and improving the HighLevelSynthesis pass to handle annotated operations, which is done in this PR by improving the AnnotatedSynthesisDefault plugin. With both of these changes, circuit4 is synthesized just as efficiently as circuit1 and circuit2.

Multi-controlled Z-gates

We repeat experiment with multi-controlled Z-gates instead of multi-controlled X-gates. Let circuits 5, 6, 7, 8 be the versions of circuits 1, 2, 3, 4 with Z/CZ gates instead of X/CX. One important difference is that we don't have native MCZ gates in Qiskit as compared to native MCX-gates, and in particular we don't have dedicated plugins for MCZ-gates. In theory, a multi-controlled Z-gate is equivalent to a multi-controlled X-gate with just two additional H-gates, and so we should get the same quality of results as above.

MAIN:

CIRCUIT5: {'u': 59, 'cx': 30}
CIRCUIT6: {'u': 159, 'cx': 78}
CIRCUIT7: {'u': 2549, 'cx': 1586}
CIRCUIT8: {'u': 5719, 'cx': 3626}

THIS PR:

CIRCUIT5: {'u': 59, 'cx': 30}
CIRCUIT6: {'u': 59, 'cx': 30}
CIRCUIT7: {'u': 1573, 'cx': 1002}
CIRCUIT8: {'u': 59, 'cx': 30}

However, in practice circuit6 is worse than circuit2: this is because a CZ-gate is translated to a CX-gate with 2 Hadamards, and adding 5-controls creates two 5-controlled Hadamard gates instead of their non-controlled versions. This PR improves this behavior by providing an explicit decomposition for multiply-controlled CZ-gates in _add_control.py, similarly to how other controlled gates are currently handled. As before, creating a hierarchical circuit using annotated=True and using the improved AnnotatedSynthesisDefault plugin allows to synthesize circuit8 using 30 CX-gates as compared to 1586.

Controlled QFT-adders

A long discussed optimization (actually available as a part of unused by default OptimizeAnnotated transpiler pass) is to simplify control-[U -- V -- U^{-1}] to U -- [control-V] -- U^{-1}. This immediately applies to controlled QFT-adders, where the logic is precisely of this form: control-[QFT -- V -- QFT^{-1}]. With AnnotatedSynthesisDefault adapting two simple optimizations from OptimizeAnnotated pass and after allowing in the construction of the QFT-based adder to create the inverse QFT^{-1} as annotated (hence a new argument to adder_qft_d00), a controlled QFT-adder can be synthesized much more efficiently than before:

#circuit 9: our old friend controlled QFT-based adder
gate = HalfAdderGate(3).control(2, annotated=True)
qc = QuantumCircuit(gate.num_qubits)
qc.append(gate, qc.qubits)

MAIN:

CIRCUIT9: {'u': 1607, 'cx': 1310}

THIS PR:

CIRCUIT9: {'u': 539, 'cx': 450}