New OptimizeAnnotated transpiler pass

[alexanderivrii]

Summary

This PR adds a new OptimizeAnnotated transpiler pass that optimizes annotated operations on a quantum circuit, please refer to #11475. At the moment the pass only implements simple optimizations (bringing annotations into canonical form, removing annotations when possible, and combining multiple recursive annotations) and defines the API for the pass.

Details and comments

Here is an example (also appearing in the release notes):

from qiskit.circuit import QuantumCircuit
from qiskit.circuit.annotated_operation import (
    AnnotatedOperation,
    InverseModifier,
    ControlModifier,
)
from qiskit.circuit.library import CXGate, SwapGate
from qiskit.transpiler.passes import OptimizeAnnotated

# Create a quantum circuit with multiple annotated gates
gate1 = AnnotatedOperation(
    SwapGate(),
    [InverseModifier(), ControlModifier(2), InverseModifier(), ControlModifier(1)],
)
gate2 = AnnotatedOperation(
    SwapGate(),
    [InverseModifier(), InverseModifier()]
)
gate3 = AnnotatedOperation(
    AnnotatedOperation(CXGate(), ControlModifier(2)),
    ControlModifier(1)
)
qc = QuantumCircuit(6)
qc.append(gate1, [3, 2, 4, 0, 5])
qc.append(gate2, [1, 5])
qc.append(gate3, [5, 4, 3, 2, 1])

# Optimize the circuit using OptimizeAnnotated transpiler pass
qc_optimized = OptimizeAnnotated()(qc)

# This is how the optimized circuit should look like
gate1_expected = AnnotatedOperation(SwapGate(), ControlModifier(3))
gate2_expected = SwapGate()
gate3_expected = AnnotatedOperation(CXGate(), ControlModifier(3))
qc_expected = QuantumCircuit(6)
qc_expected.append(gate1_expected, [3, 2, 4, 0, 5])
qc_expected.append(gate2_expected, [1, 5])
qc_expected.append(gate3_expected, [5, 4, 3, 2, 1])

assert qc_optimized == qc_expected

In the case of gate1, the modifiers of the annotated swap gate are brought into the canonical form: the two InverseModifier s cancel out, and the two ControlModifier s are combined. In the case of gate2, all the modifiers get removed and the annotated operation is replaced by its base operation. In the case of gate3, multiple layers of annotations are combined into one.

---

I am trying to find some balance between creating too many pull requests vs. making each pull request easier to review. My current plan is to add other optimizations (canceling inverse annotated operations and conjugate reduction) in a follow-up PR.

[qiskit-bot]

One or more of the the following people are requested to review this:

• @Qiskit/terra-core

[coveralls]

Pull Request Test Coverage Report for Build 7607475432

Warning: This coverage report may be inaccurate.

We've detected an issue with your CI configuration that might affect the accuracy of this pull request's coverage report.
To ensure accuracy in future PRs, please see these guidelines.
A quick fix for this PR: rebase it; your next report should be accurate.

• 0 of 0 changed or added relevant lines in 0 files are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage increased (+2.0%) to 89.503%

---

Totals
Change from base Build 7385123694:	2.0%
Covered Lines:	59549
Relevant Lines:	66533

---

💛 - Coveralls

[mtreinish]

Overall this LGTM, it's a straightforward pass to canonicalize any annotated operations and a good start to optimizing things. I left a few inline comments on some small things.

The higher level question is where were you thinking of adding this in the transpilation pipeline. I was thinking in the init stage probably before before we run high level synthesis. We can do that here or in a follow up PR whichever you think would be better.

[mtreinish]

Do you think having an explicit option to recurse into definitions is useful or not? Right now it's only done implicitly based on the presence of a Target or basis gates. But do you think there is value in having an override for it?

[alexanderivrii]

After thinking about this, such an option could definitely be useful and is added in fb7e279.

The current logic is the following (please see if you agree with this):

• If neither basis_gates nor target is specified, then we do not recursively descent into gate definitions, regardless of the recurse option. This is consistent with the behavior of HighLevelSynthesis pass (and previously of UnrollCustomDefinitions pass) which in this case does not descend into the definitions either, i.e. we shouldn't optimize what we are not going to synthesize.
• If either basis_gates or target is specified, and recurse has the default value of True, then we do the recursion.
• But we can override the recursion by setting recurse to False.

This also ties in to the question of where this pass should sit in the transpilation pipeline. I was also thinking about the init stage (just before running high level synthesis). Alternatively, if you think that having yet another recursive pass would be slow, we could use it from within HighLevelSynthesis itself, i.e. when HighLevelSynthesis needs to synthesize a DAGCircuit (possibly as part of its own recursion), it can first call OptimizeAnnotated on this dag circuit with recurse=False. What do you think?

[mtreinish]

Yeah, this logic makes sense to me. I think leaving this as a standalone pass makes sense, just as it seems like a slightly different building block in a pipeline that high level synthesis. However, I do agree there is probably some concern around performance if we're going to run with recurse=True in the init stage and I like your suggestion of calling it internally when it makes sense. I think when we investigate integrating this into the preset pass managers as part of 1.1.0 we can look at all those details.

[alexanderivrii]

Thanks! Please see this comment #11476 (comment) about thoughts on an explicit option to recurse into gate definitions and when in the transpiler flow the pass should sit. If you think that the best way to use this pass is in the init stage, then I will add it to the transpiler flow in this PR. If you think it's best to try to combine it with HighLevelSynthesis then maybe in a quick follow-up PR.

[mtreinish]

This LGTM now, thanks for the updates.

[mtreinish]

Yeah, this logic makes sense to me. I think leaving this as a standalone pass makes sense, just as it seems like a slightly different building block in a pipeline that high level synthesis. However, I do agree there is probably some concern around performance if we're going to run with recurse=True in the init stage and I like your suggestion of calling it internally when it makes sense. I think when we investigate integrating this into the preset pass managers as part of 1.1.0 we can look at all those details.

[mtreinish]

I mentioned this in my inline response, but given the timing we can investigate how to integrate this pass into the preset pass managers for the 1.1 release.