Transpile failure with unitary synthesis for targets with heterogeneous basis gates

[mtreinish]

Environment

• Qiskit Terra version: 0.24.0rc1
• Python version: 3.10
• Operating system: Linux

What is happening?

Running transpile() with optimization_level=3 using a custom target is generating an error message:

TranspilerError: "Encountered a bad synthesis. Target has no Instruction(name='u', num_qubits=1, num_clbits=0, params=[2.0293072715139053e-17, -3.141592653589793, -3.141592653589793]) on qubits (0, 2)."

How can we reproduce the issue?

from qiskit import QuantumCircuit
from qiskit.compiler import transpile
from qiskit.circuit import Parameter, Measure
from qiskit.transpiler import Target, InstructionProperties
from qiskit.circuit.library import UGate, RZGate, RXGate, RYGate, CXGate, CZGate

target = Target(num_qubits=3)
target.add_instruction(CXGate(), {(0, 1): InstructionProperties(error=.0001, duration=5e-7)})
target.add_instruction(UGate(Parameter('theta'), Parameter('phi'), Parameter('lam')), {(0,): InstructionProperties(error=.00001, duration=5e-8), (1,): InstructionProperties(error=.00002, duration=6e-8)})
target.add_instruction(RZGate(Parameter('theta')), {(1,): InstructionProperties(error=.00001, duration=5e-8), (2,): InstructionProperties(error=.00002, duration=6e-8)})
target.add_instruction(RYGate(Parameter('theta')), {(1,): InstructionProperties(error=.00001, duration=5e-8), (2,): InstructionProperties(error=.00002, duration=6e-8)})
target.add_instruction(RXGate(Parameter('theta')), {(1,): InstructionProperties(error=.00001, duration=5e-8), (2,): InstructionProperties(error=.00002, duration=6e-8)})
target.add_instruction(CZGate(), {(1, 2): InstructionProperties(error=.0001, duration=5e-7), (2, 0): InstructionProperties(error=.0001, duration=5e-7)})
target.add_instruction(Measure(), {(0,): InstructionProperties(error=.001, duration=5e-5), (1,): InstructionProperties(error=.002, duration=6e-5), (2,): InstructionProperties(error=.2, duration=5e-7)})

qc = QuantumCircuit(3)
qc.h(0)
qc.ecr(0, 1)
qc.ecr(0, 2)
qc.cx(2, 1)
qc.measure_all()
qc.draw('mpl')

transpile(qc, target=target, optimization_level=3)

What should happen?

This shouldn't error. I encountered this re-running a notebook I had written as part of the 0.22.0 release. This is a regression for 0.24.0 and I expect is tied to the changes made to unitary synthesis in: https://github.com/Qiskit/qiskit-terra/pull/9175 (https://github.com/Qiskit/qiskit-terra/commit/a8f83c4469f55a62f958f3eed2df10a598811eae)

Any suggestions?

I expect the code that detects which decomposers to use isn't correctly handling that UGate works on qubit 0 only and not on any other qubit. I don't think our built in synthesizers can handle this edge case which is why we run the basis translator and 1q optimizers as part of the optimization loop. To convert any out of basis gates that might get introduced. I think whichever check is result in raising the TranspilerError should be relaxed to not fail in this case and let other passes clean up after synthesis.

[mtreinish]

@jlapeyre will this be fixed by #10008 or is there another fix that's needed?

[jlapeyre]

I don't think it will be fixed by #10008. I'll check.

[jlapeyre]

Happens both on main and #10008. Here is closer to minimal code to trigger this. The error is stochastic, so I added a loop

from qiskit import QuantumCircuit
from qiskit.compiler import transpile
from qiskit.circuit import Parameter
from qiskit.transpiler import Target, InstructionProperties
from qiskit.circuit.library import UGate, CXGate, CZGate

target = Target(num_qubits=3)
target.add_instruction(CXGate(), {(0, 1): InstructionProperties(error=.0001, duration=5e-7)})
target.add_instruction(UGate(Parameter('theta'), Parameter('phi'), Parameter('lam')), {(0,): InstructionProperties(error=.00001, duration=5e-8), (1,): InstructionProperties(error=.00002, duration=6e-8)})
target.add_instruction(CZGate(), {(1, 2): InstructionProperties(error=.0001, duration=5e-7), (2, 0): InstructionProperties(error=.0001, duration=5e-7)})

qc = QuantumCircuit(3)
qc.cx(2, 1)

for i in range(100):
    transpile(qc, target=target, optimization_level=3)

[jlapeyre]

Looks like what you said. Below are two candidate synthesized circuits. They're wrong because they have U on the wrong wires.

The error is raised when trying to look up the error for the gate on the wrong wire.

        ┌──────────────────┐       ┌──────────────────┐ 
q10_0: ─┤ U(π/2,-1.0326,0) ├───■───┤ U(π/2,-π,1.0326) ├─
       ┌┴──────────────────┴┐┌─┴─┐┌┴──────────────────┴┐
q10_1: ┤ U(π/2,-π,0.079071) ├┤ X ├┤ U(π/2,-0.079071,0) ├
       └────────────────────┘└───┘└────────────────────┘
     ┌──────────────────┐     ┌──────────────────┐
q_0: ┤ U(π/2,-2.109,-π) ├──■──┤ U(π/2,0,-1.0326) ├
     └──┬────────────┬──┘┌─┴─┐└─┬──────────────┬─┘
q_1: ───┤ U(π/2,0,0) ├───┤ X ├──┤ U(π/2,-π,-π) ├──
        └────────────┘   └───┘  └──────────────┘  

Getting around the error computations won't fix the problem because the circuits are wrong to begin with.

[mtreinish]

I don't think we can expect the 2q synthesis routines on their own to know how to translate that 2q unitary in terms of u on qubit 0 and rz, ry, rx on qubit 1 with cx on 0->1 on its own. That's potentially a lot of nuance to add on top of some pretty tricky code and math. We have other passes that we run immediately after UnitarySynthesis which will see the gates out of the target specification and convert them to the correct gates. That's how this worked in earlier version before the error rate checking logic, before 0.24.0 it just output the U on both qubits and the basis translator or 1q optimizer pass would translate that to the appropriate gates.

[jlapeyre]

Are you saying that if we let these wrong circuits go through, maybe choosing one by gate count rather than error, they will be corrected in a later pass? EDIT This does not happen.

Some detail: Both of the 2q decomposers run in this case (each one could appear more than once, but not in this case). Each one gives a wrong circuit. They both take 1q synthesizers in construction or information on which to choose (not 100% sure) and run them. Maybe not clever enough though. XXDecomposer constructs a circuit representing the decomposition including 1q U gates and then runs a 1q synthesizer as the last step: https://github.com/Qiskit/qiskit-terra/blob/73c1e1c4d020ddc0ed68910a2d30bfd78e2f1647/qiskit/quantum_info/synthesis/xx_decompose/decomposer.py#L297-L307

Hmmm. if we know it's going to do it wrong, we could include a flag to omit running the 1q synthesizer because its a waste. And let a further pass do it. But we would not be able to use basis-set gate errors to choose from candidates in this case.

[mtreinish]

Yeah using gate count as a fallback metric would work. I was just thinking of pick the first one, but using some other metric is probably a better way. Prior to #9175 (which is new for 0.24.0) it didn't do any of this checking at all and just always used a single decomposer based on the gates available. So I think having a fallback in the case where we don't have any matching gate errors in the target would be the best behavior here.

The issue with the logic around calling self._decomposer1q there is the constraints for calling the pass like that are incomplete because of the conflicting contexts. Inside XXDecomposer we don't have access to the full Target because it doesn't make sense there as the class is isolated to just unitary in, circuit out, and doesn't really understand physical qubits, or that you might need to use different gates on different qubits. The Optimize1qGatesDecomposition is fully capable of handling the heterogeneous basis gates when its given a Target but the only context XXDecomposer has to give it is the 1q basis gate . Thinking out loud, looking at that code snippet it probably wouldn't be too hard to add 2 optional arguments to on the XXDecomposer for a Target and another argument to specify the physical qubits class to handle this edge case. But that's probably a layer violation (also we definitely wouldn't be able to include the fix doing this for 0.24.0).

[jlapeyre]

I tried just picking the first one. I didn't follow the logic except to see that it enters UnitarySynthesis one more time. But the circuit that's returned (it's a one gate circuit so only one unitary to synthesize) is the same as the one chose nfrom the list. We'd have to do more work to get it to synthesize properly.... I haven't felt like I needed a debugger for this code. But maybe now is the time.