TemplateOptimization fails for some templates

[gideonuchehara]

Environment

• Qiskit version: '0.46.0'
• Python version: 3.12.3
• Operating system: Ubuntu

What is happening?

four_qubits = QuantumRegister(4, name="q")
temp_go = QuantumCircuit(four_qubits)
temp_go.cx(four_qubits[1], four_qubits[2])
temp_go.cx(four_qubits[0], four_qubits[1])
temp_go.cx(four_qubits[2], four_qubits[3])
temp_go.cx(four_qubits[1], four_qubits[2])

temp_go.cx(four_qubits[2], four_qubits[3])
temp_go.cx(four_qubits[1], four_qubits[3])
temp_go.cx(four_qubits[0], four_qubits[2])
temp_go.cx(four_qubits[0], four_qubits[1])

The above circuit is a matching template for the circuit below

four_qubits = QuantumRegister(4, name="q")
unknown_temp = QuantumCircuit(four_qubits)
unknown_temp.cx(four_qubits[1], four_qubits[2])
unknown_temp.cx(four_qubits[0], four_qubits[1])
unknown_temp.cx(four_qubits[2], four_qubits[3])
unknown_temp.cx(four_qubits[1], four_qubits[2])

The expected behaviour is that the result of applying TemplateOptimization to unknown_temp should be temp_go

How can we reproduce the issue?

from qiskit import QuantumRegister, QuantumCircuit

from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import TemplateOptimization

four_qubits = QuantumRegister(4, name="q")
unknown_temp = QuantumCircuit(four_qubits)
unknown_temp.cx(four_qubits[1], four_qubits[2])
unknown_temp.cx(four_qubits[0], four_qubits[1])
unknown_temp.cx(four_qubits[2], four_qubits[3])
unknown_temp.cx(four_qubits[1], four_qubits[2])

four_qubits = QuantumRegister(4, name="q")
temp_go = QuantumCircuit(four_qubits)
temp_go.cx(four_qubits[1], four_qubits[2])
temp_go.cx(four_qubits[0], four_qubits[1])
temp_go.cx(four_qubits[2], four_qubits[3])
temp_go.cx(four_qubits[1], four_qubits[2])

temp_go.cx(four_qubits[2], four_qubits[3])
temp_go.cx(four_qubits[1], four_qubits[3])
temp_go.cx(four_qubits[0], four_qubits[2])
temp_go.cx(four_qubits[0], four_qubits[1])

matcher = PassManager(TemplateOptimization([temp_go]))

transpiled_unknown_temp = matcher.run(unknown_temp)
transpiled_unknown_temp.draw("mpl")

What should happen?

The actual behaviour is that applying TemplateOptimization to unknown_temp does not return temp_go, instead it returns the original circuit unknown_temp.

Any suggestions?

No response

[jakelishman]

Your template matches, but making the inverse replacement would be 4 CX, just like the input, so are you sure that TemplateMatching is not just choosing not to make the replacement, since it's the same cost?

[gideonuchehara]

In the situation where I want to prioritise the template, how can I achieve this? @glassnotes

[gideonuchehara]

Also, there are some templates in Qiskit that have the same number of CNOTs. For example this:

def template_nct_4a_1():
    """
    Returns:
        QuantumCircuit: template as a quantum circuit.
    """
    qc = QuantumCircuit(5)
    qc.ccx(1, 2, 4)
    qc.ccx(0, 2, 3)
    qc.ccx(1, 2, 4)
    qc.ccx(0, 2, 3)
    return qc

[jakelishman]

It's not about the number of cxs in the template, it's the fact that the number of gates there's be after applying the template is the same as it was before (4 CX on input, 8 CX in the template, so 4 CX on the output). The effect of applying the template isn't better than not applying it.

If you have different sets of gates in your template, you can apply different weightings to them, so the "score" of applying each template takes that into account, but the TemplateOptimization algorithm at the moment doesn't have a mechanism to say "break ties in favour of applying the template", it just defaults to "break ties in favour of leaving things as-is".

I haven't looked into this issue in detail, but assuming that what I think is happening is actually the case, it feels like there might be a sensible option we could add to control it.

[gideonuchehara]

Thanks, @jakelishman, for your comment. When I referred to cx, I was specifically talking about gates in the context of the Qiskit template I provided. For the template_nct_4a_1, there are 2 CCX gates in the input, 4 CCX gates within the template, and 2 CCX gates in the output. Applying the template to the input, for example, produced the output even though the number of CCX gates remained the same.

[alexanderivrii]

Mostly repeating @jakelishman's answer, let's say that you are running the following code:

circuit = QuantumCircuit(5)
circuit.ccx(1, 2, 4)
circuit.ccx(0, 2, 3)

template = template_nct_4a_1()

optimized = TemplateOptimization([template])(circuit)

Printing out the circuits involved, circuit is:

q_0: ───────■──
            │  
q_1: ──■────┼──
       │    │  
q_2: ──■────■──
       │  ┌─┴─┐
q_3: ──┼──┤ X ├
     ┌─┴─┐└───┘
q_4: ┤ X ├─────
     └───┘     

template is:

q_0: ───────■─────────■──
            │         │  
q_1: ──■────┼────■────┼──
       │    │    │    │  
q_2: ──■────■────■────■──
       │  ┌─┴─┐  │  ┌─┴─┐
q_3: ──┼──┤ X ├──┼──┤ X ├
     ┌─┴─┐└───┘┌─┴─┐└───┘
q_4: ┤ X ├─────┤ X ├─────
     └───┘     └───┘     

and optimized is

q_0: ──■───────
       │       
q_1: ──┼────■──
       │    │  
q_2: ──■────■──
     ┌─┴─┐  │  
q_3: ┤ X ├──┼──
     └───┘┌─┴─┐
q_4: ─────┤ X ├
          └───┘

We do not expect the TemplateOptimization pass to do anything because applying the template does not reduce the "cost" of the circuit. You have made a valid point that the circuits before and after the pass differ, and this is probably because internally the pass works on a DAGDependency representation of a circuit, that takes gate commutativity into account. In our case, both gates in the circuit commute and may become ordered differently when translating the DAGDependency back to a DAGCircuit. I hope this explains the remaining "mystery". :)

Note that if you change the circuit to

circuit.ccx(1, 2, 4)
circuit.ccx(0, 2, 3)
circuit.ccx(1, 2, 4)

then the substitution will take place, as applying the template now produces a circuit with only 1 CCX-gate instead of 3.