Conjugate reduction in optimize annotated pass

[alexanderivrii]

Summary

Addresses #11810.

This PR adds a new optimization to the OptimizeAnnotated transpiler pass. The reduction looks for annotated operations (objects of type AnnotatedOperation that consist of a base operation B and a list M of control, inverse and power modifiers) with the following properties:

• the base operation needs to be synthesized (i.e. it's not already supported by the target or belongs to the equivalence library)
• the definition circuit for B can be expressed as P -- Q -- R with R = P^{-1}.

For such annotated operations, we can move the modifiers to be over the Q-part only, i.e. replace M - [P -- Q -- R] by P -- M-[Q] -- R.

Example: Controlled Draper QFT Adder

This has been one of the main motivating examples. Consider the controlled_adder circuit constructed below:

basis_gates = ['cx', 'id', 'u']
equivalence_library = SessionEquivalenceLibrary
num_state_qubits = 3
num_controls = 2

adder = DraperQFTAdder(num_state_qubits=num_state_qubits, kind="half")
controlled_adder = adder.control(num_controls)
synthesized_adder = HighLevelSynthesis(basis_gates=basis_gates, equivalence_library=equivalence_library)(controlled_adder)

The synthesized adder has the following operations: [('cx', 746), ('p', 630), ('cp', 237), ('h', 84), ('ry', 16), ('ccx', 16)]. (Note that HighLevelSynthesis is the transpiler pass that within transpile that decomposes the circuit into 1- and 2-qubit gates).

On the other hand, the controlled adder is of the form control - [QFT -- U -- QFT^{-1}], which can be simplified to QFT -- control-[U] -- IQFT. By removing the controls over QFT`` and ``IQFT parts of the circuit, one obtains significantly fewer gates in the transpiled circuit. The following is still not 100% perfect but showcases this reduction:

adder = DraperQFTAdder(num_state_qubits=num_state_qubits, kind="half")
adder = adder.decompose().decompose().decompose()
controlled_adder = adder.control(num_controls, annotated=True)
controlled_adder = adder.control(num_controls, annotated=True)
optimized_adder = OptimizeAnnotated(basis_gates=basis_gates, equivalence_library=equivalence_library)(controlled_adder)
synthesized_adder = HighLevelSynthesis(basis_gates=basis_gates, equivalence_library=equivalence_library)(optimized_adder)

Now the synthesized adder has the following operations: [('cx', 306), ('p', 270), ('cp', 93), ('h', 44)].

Example: CSWAP gate

CSwapGate in Qiskit has the following definition:

q = QuantumRegister(3, "q")
qc = QuantumCircuit(q, name=self.name)
rules = [
    (CXGate(), [q[2], q[1]], []),
    (CCXGate(), [q[0], q[1], q[2]], []),
    (CXGate(), [q[2], q[1]], []),
]
for instr, qargs, cargs in rules:
    qc._append(instr, qargs, cargs)

self.definition = qc

We get exactly the same decomposition for SwapGate().control(1, annotated=True) by writing Swap as 3 CXs and moving the control to the middle CX (as the two outer CXs are inverse of each other).

Details and comments

There are many interesting discussion points related to all this.

There is still a question of how the OptimizeAnnotated pass should be integrating into the transpile flow; I am now exploring several options.

The key part of the PR is the code (currently in optimize_annotated.py) that matches nodes at the front of a DAGCircuit with nodes at the back of the DAGCircuit; currently the check is simply fn.op == bn.op.inverse(); inverse nodes are collected into P and R respectively. Would something like this be uesful in other contexts?

We want to have a more general function that checks whether two DAG nodes A and B are inverse of each other. Currently I am checking that A.qargs = B.qargs. A.cargs = B.cargs and A.op = B.op.inverse(). What is the most general check we could do? For instance, we could relax to check to set(A.qargs) = set(B.qargs) but that would also require checking inverse up to a specific permutation of qubits, and that seems hard. In addition, the check A.op = B.op.inverse() is very constrained: it does detect that S is the inverse of Sdg or that CX is the (self-) inverse of CX, but it does not detect that QFT is the inverse of IQFT in the Draper adder example, because in draper_qft_adder.py the inverse-QFT is defined as QFT(num_qubits_qft, do_swaps=False).inverse().to_gate() and not QFT(num_qubits_qft, do_swaps=False).to_gate().inverse(). This is one of the reasons that we needed to decompose the circuit 3 times before the optimization became applicable. It would also currently not detect that SomeGate.inverse(annotated=True) is the inverse of SomeGate.

Yet another problem with DraperQFTAdder(num_state_qubits=num_state_qubits, kind="half").control(num_controls, annotated=True) is that the definition of the base operation (aka of DraperQFTAdder) is not yet of the form QFT -- U -- IQFT, but a circuit consisting of only a single gate, whose definition in turn is of the form above. So again the optimization does apply without decomposing the circuit a few times.

Also please take a look at how I have implemented the circuit P - M-[Q] - R with modifiers M moved to the middle part. It's quite ugly, and the question is whether this can be simplified? (It works, and as we saw the HighLevelSynthesis pass works correctly on such circuits).

[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 8927040115

Warning: This coverage report may be inaccurate.

This pull request's base commit is no longer the HEAD commit of its target branch. This means it includes changes from outside the original pull request, including, potentially, unrelated coverage changes.

• For more information on this, see Tracking coverage changes with pull request builds.
• To avoid this issue with future PRs, see these Recommended CI Configurations.
• For a quick fix, rebase this PR at GitHub. Your next report should be accurate.

Details

• 116 of 122 (95.08%) changed or added relevant lines in 2 files are covered.
• 19 unchanged lines in 3 files lost coverage.
• Overall coverage increased (+0.01%) to 89.586%

---

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit/transpiler/passes/optimization/optimize_annotated.py	112	118	94.92%
<!--	Total:	116	122

Files with Coverage Reduction	New Missed Lines	%
qiskit/transpiler/passes/synthesis/unitary_synthesis.py	1	88.02%
crates/qasm2/src/lex.rs	6	92.62%
crates/qasm2/src/parse.rs	12	97.15%
<!--	Total:	19

Totals
Change from base Build 8926762316:	0.01%
Covered Lines:	61935
Relevant Lines:	69135

---

💛 - Coveralls

[alexanderivrii]

Update: this PR extends the OptimizeAnnotated transpiler pass, however the pass does not currently appear in the transpiler flow, largely because we don't (yet) commonly create quantum circuits with annotated operations.

When the new optimization is applicable, it can give significant reduction, however the quantum circuit has to be of a somewhat special form for that to happen (see the second form of the controlled-adder example from the PR description).

I do believe that this is a useful reduction, however this needs to be followed up by (1) constructing various standard library circuits using modifiers (annotated operations), (2) extending the applicability of the pass.

[alexanderivrii]

Jake, many thanks for the review. I have addressed your comments and added more tests.