IndexError in `XXDecomposer` during `FakePrague` `transpile()` with optimization level 3

mtreinish commented 1 year ago

Environment

Qiskit Terra version: 0.24.0 main (@ 5672c70649b4f83a6c7146c68a6a543d4a3908fd)
Python version: 3.10
Operating system: Linux

What is happening?

During transpile() with optimization level 3 on some circuits targeting FakePrague the 2q unitary synthesis code is raising an index error with the main branch. This code works fine on the most recent release.

How can we reproduce the issue?

from qiskit.circuit import QuantumCircuit
from qiskit.compiler import transpile
from qiskit.providers.fake_provider import FakePrague

backend = FakePrague()
num_qubits = 10
# Circuit creation
qc = QuantumCircuit(num_qubits)
qc.h(0)
for i in range(num_qubits - 1):
    if i % 2 == 0:
        qc.cy(0, i + 1)
    else:
        qc.cx(0, i + 1)
qc.measure_all()
tqc = transpile(
    qc, backend, seed_transpiler=2023, optimization_level=3
)

What should happen?

The transpile() shouldn't error and it should successfully run 2q synthesis and return a compiled circuit.

Any suggestions?

This is a bug that has been introduced since the 0.23.0 release (as it still works on the released version). Looking at the git log this is likely a bug that was introduced in #9175 (https://github.com/Qiskit/qiskit-terra/commit/a8f83c4469f55a62f958f3eed2df10a598811eae)

mtreinish commented 1 year ago

I think the fix for this might be simple and just a matter of changing: https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/quantum_info/synthesis/xx_decompose/decomposer.py#L153 to while priority_queue instead of while True because the error is occurring because priority_queue is empty after the first iteration. But, I'm not familiar enough with the code in the decomposer class to know if that's just a band-aid and there is a deeper issue, or that's sufficient.

jlapeyre commented 1 year ago

I agree with the discussion closing #9937. Here is the call to the XXDecomposer https://github.com/Qiskit/qiskit-terra/blob/c4f1b0bd0b3873bcc5807a3c55b7eeceedd18193/qiskit/transpiler/passes/synthesis/unitary_synthesis.py#L784-L786 No basis fidelity map is passed here, which means that XXDecomposer uses the one supplied at construction. In the example program here, this is an empty dict. I did not yet find where XXDecomposer is constructed with this empty dict.

My best guess after looking at this for a while is that XXDecomposer was not intended to work when passed an empty fidelity map on construction. And likewise here: https://github.com/Qiskit/qiskit-terra/blob/c4f1b0bd0b3873bcc5807a3c55b7eeceedd18193/qiskit/quantum_info/synthesis/xx_decompose/decomposer.py?rgh-link-date=2023-04-10T20%3A32%3A40Z#L139

it is assumed that available_strengths is not empty. But it is.

I think the map should be validated somewhat on construction (at least check its not empty) so that an error is thrown earlier and closer to the real problem. That still doesn't completely solve the problem. I'll look at it again tomorrow.

jlapeyre commented 1 year ago

Adding a check for empty basis_fidelity dict passed to the constructor of XXDecomposer causes no failures in tox -epy -- test.python.compiler. I propose adding this check and changing the test suite to fail if this check is not present. This would require changing the doc string as well to explicitly state that the dict can't be empty. In fact the check should be more stringent.... a minimum of one entry? I don't know yet.

The instance is created in this method https://github.com/Qiskit/qiskit-terra/blob/c4f1b0bd0b3873bcc5807a3c55b7eeceedd18193/qiskit/transpiler/passes/synthesis/unitary_synthesis.py#L594 This method has a lot of logic and is rather long. As part of fixing this, it should probably be cleaned up or replaced with more than one method.

mtreinish commented 1 year ago

Fwiw, our existing test suite does not have coverage of this error case. You can add a test like what I added in: https://github.com/Qiskit/qiskit-terra/pull/9937/files#diff-1c5c5726481cd10ea5ac1b5abaf9898c2a3e6b58f7b4f1b19b569d8a7c9c24d9R866 (which is just based on the reproduce I put in the OP) and I would expect that to fail.

jlapeyre commented 1 year ago

I planned to add coverage along with a fix. But if we are not able to fix it soon, I'll add a test for the failure.

jlapeyre commented 1 year ago

It looks like this bug is caused by faulty data in FakePrague. See #9983. The consequences should probably be caught in more than one place. For example

check that the backend has a controlled gate in its list of operations early in the transpilation.
in unitary synthesis, throw an error if the list of operations received does not include a 2q controlled gate
In the constructor XXDecomposer raise an error on invalid input, in case it somehow gets called with bad input despite the checks above.

jlapeyre commented 1 year ago

Maybe @levbishop can weigh in again on this.

The XXDecomposer relies on there being at least one controlled (up to local unitaries) gate in the basis set. All 2q gates that are not controlled are filtered out of the set sent to XXDecomposer https://github.com/Qiskit/qiskit-terra/blob/a461a913c2e5bd51b307f38b89d2ab37117b7bf4/qiskit/transpiler/passes/synthesis/unitary_synthesis.py#L677

So far we have run into two examples where the basis set in a target has no controlled 2q gates and thus XXDecomposer gets no gates.

FakePrague includes a Target that erroneously has no controlled gate (#9983)
This test https://github.com/Qiskit/qiskit-terra/blob/a461a913c2e5bd51b307f38b89d2ab37117b7bf4/test/python/transpiler/test_unitary_synthesis.py#L840-L842

This test creates a Target with a 1q gate and a custom 2q gate with no properties (no matrix etc.), which is filtered out of the set before calling the 2q synthesiszers. The test then synthesizes a trivial 2-qubit circuit, with a single explicit identity unitary using this target. This succeeds only because no 2q basis gates need to be supplied. My best understanding is that the "canonical point" corresponding to 2q identity (in fact any non-entangling 2q unitary) is [0,0,0]. That is what is calculated here: https://github.com/Qiskit/qiskit-terra/blob/a461a913c2e5bd51b307f38b89d2ab37117b7bf4/qiskit/quantum_info/synthesis/xx_decompose/decomposer.py#L250-L258

The optimization loop seeds the priority queue with this point [0,0,0]. And it can't put anything else in the queue because the set of basis gates sent was empty. The bottom line (as near as I can tell) is that if your basis set has no controlled gates, you can only synthesize (with this path thats called on opt level 3) certain trivial circuits, like a 2q circuit with one identity gate. It looks like the author explicitly expected this possibility or something like it, because this code branch is chosen when there are no "strengths" found by the optimization loop: https://github.com/Qiskit/qiskit-terra/blob/a461a913c2e5bd51b307f38b89d2ab37117b7bf4/qiskit/quantum_info/synthesis/xx_decompose/circuits.py#L261-L263

Furthermore, insisting on calling XXDecomposer with an empty basis set (because there are no controlled gates) and a non-trivial (entangled) circuit throws the index error in the title of this issue. If you implement #9937 , that is quit when the priority queue is empty, you get a wrong result. The "point" used for synthesis is [0,0,0] , ie. the identity, which results in the entangling part of synthesis being an empty 2q circuit. This is fixed up with the 1q parts of the weyl decomposition, but its still wrong.

What to do? Disallow basis sets with no entangling gates? At present, at least in unitary_synthesis.py this means disallowing basis sets with no controlled gates. This means that trivial circuits would have to be optimized some other way.

Or... I looks like the empty priority queue is one failure mode of XXDecomposer, it implies that the supplied unitary can't be synthesized with the basis set sent. If that basis set was empty, we know that the unitary is entangling and can't be synthesized by any method. So we would throw an error. This way, we would still allow the trivial circuit to be synthesized on this path.

levbishop commented 1 year ago

XXDecomposer could check for empty controlled basis set and throw a more helpful error in this case, but to me its really a problem with the driving logic that lead to XXDecomposer being called in the first place. If another (non-controlled) basis is available where we have a synthesis method (eg the supercontrolled decomposer) then the higher-level logic (eg DefaultUnitarySynthesis or other circuit-rewriting) should use that. If no synthesis methods are implemented for the available bases than that is unrecoverable.

jlapeyre commented 1 year ago

But this is really about handling edge cases. Currently, if there are no super-controlled gates then TwoQubitBasisDecomposer is not called. If there are no controlled gates, then XXDecomposer is still called, but with an empty basis set. In this case and if you are only synthesizing non-entangling unitaries it returns (sometimes, maybe always) a correct result. So it's unusual to have no entangling gates that we know how to use (if we have others, I dont find them in unitary_synthesis.py and unusual to have no nontrivial 2q gates to synthesize. But XXDecomposer can do it. The constraints are set by the basis set in the target and the gates in the circuit to be synthesized. I don't see how changes to the driver logic can get around this.

Qiskit / qiskit