Transpiler slow to raise when attempting to target an unreachable basis #5539
Description
What is the expected enhancement?
When attempting to transpile to a set of basis_gates that the transpiler can't reach, the BasisTranslator will eventually fail with an error like
qiskit.transpiler.exceptions.TranspilerError: "Unable to map source basis {('cx', 2)} to target basis {'delay', 'reset', 'snapshot', 'measure', 'barrier', 'u'} over library <qiskit.circuit.equivalence.EquivalenceLibrary object at 0x124755ba8>."
but it is very slow to do so.
>>> import qiskit as qk
>>> qc = qk.QuantumCircuit(2)
>>> qc.cx(0,1)
>>> from time import time
>>> def t(basis):
... start = time()
... try:
... qk.transpile(qc, basis_gates=basis)
... except Exception:
... pass
... end = time()
... return end-start
...
>>> for b in [['u'], ['u3', 'u2', 'u1'], ['sx', 'p'], ['rx', 'ry']]:
... print(b, t(b))
...
['u'] 17.1777400970459
['u3', 'u2', 'u1'] 16.48400378227234
['sx', 'p'] 14.011835813522339
['rx', 'ry'] 12.08644723892212
This is a best case example, but for e.g. a Toffoli where decompositions will contain single qubit gates (and so its possible to make some progress):
>>> qc = qk.QuantumCircuit(3)
>>> qc.ccx(0,1,2)
>>> for b in [['u'], ['u3', 'u2', 'u1'], ['sx', 'p'], ['rx', 'ry']]:
... print(b, t(b))
...
['u'] 69.04226517677307
['u3', 'u2', 'u1'] 67.77550601959229
['sx', 'p'] 65.70645785331726
['rx', 'ry'] 59.11228585243225
In general, determining whether or not a given basis transformation is possible will probably be as hard as finding it, but it may be possible to identify e.g. non-universal basis sets and raise a warning in these cases.