GateDirection pass goes outside allowed basis gates

[chriseclectic]

Environment

• Qiskit Terra version: 0.25
• Python version: 3.9
• Operating system: MacOS

What is happening?

Trying to run a clifford simulation on a fake backend with ECR basis gates leads to transpilation errors with unsupported basis gates

How can we reproduce the issue?

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
from qiskit.providers.fake_provider import FakeSherbrooke, FakeWashington

# Stabilizer simulator for FakeSherbrooke
clifford_basis_gates = ['ecr', 'sx', 'x', 'id', 'z', 's', 'sdg']
backend = AerSimulator.from_backend(
    FakeSherbrooke(),
    method="stabilizer",
    basis_gates=clifford_basis_gates, 
)

# Circuit
qc = QuantumCircuit(2)
qc.h(0)
qc.cx(0, 1)

# Transpile
transpile(qc, backend)

Raises

TranspilerError: "Unable to translate the operations in the circuit: ['ry', 'h', 'sdg', 'sx', 's', 'ecr', 'x'] to the backend's (or manually specified) target basis: ['break_loop', 'quantum_channel', 's', 'save_expval_var', 'for_loop', 'roerror', 'continue_loop', 'save_probabilities', 'z', 'qerror_loc', 'reset', 'save_clifford', 'snapshot', 'if_else', 'id', 'save_probabilities_dict', 'ecr', 'save_state', 'save_amplitudes_sq', 'sdg', 'save_stabilizer', 'delay', 'while_loop', 'save_expval', 'set_stabilizer', 'sx', 'measure', 'barrier', 'x']. This likely means the target basis is not universal or there are additional equivalence rules needed in the EquivalenceLibrary being used. For more details on this error see: https://qiskit.org/documentation/stubs/qiskit.transpiler.passes.BasisTranslator.html#translation_errors"

What should happen?

Running with a manually specified basis gates works (though the output is not at all optimized in terms of number of 1Q gates):

transpile(qc, basis_gates=["ecr", "x", "sx", "id", "z", "s", "sdg"])

global phase: 3π/2
     ┌───┐┌────┐┌───┐ ┌─────┐     ┌──────┐┌───┐
q_0: ┤ S ├┤ √X ├┤ S ├─┤ Sdg ├─────┤0     ├┤ X ├
     ├───┤├───┬┘├───┴┐└┬───┬┘┌───┐│  Ecr │└───┘
q_1: ┤ S ├┤ S ├─┤ √X ├─┤ S ├─┤ S ├┤1     ├─────
     └───┘└───┘ └────┘ └───┘ └───┘└──────┘     

Any suggestions?

Running transpilation with a callback looks like the issues is due to the GateDirection pass which inserts non-Clifford gates outside the allowed basis gates into the circuit and causes the rest of the transpilation to fail.

def callback(**kwargs):
    print(f"{type(kwargs['pass_']).__name__} output gates: {kwargs['dag'].count_ops()}")

transpile(qc, backend, callback=callback).draw()

ContainsInstruction, gates: {'h': 1, 'cx': 1}
UnitarySynthesis, gates: {'h': 1, 'cx': 1}
HighLevelSynthesis, gates: {'h': 1, 'cx': 1}
Unroll3qOrMore, gates: {'h': 1, 'cx': 1}
SetLayout, gates: {'h': 1, 'cx': 1}
TrivialLayout, gates: {'h': 1, 'cx': 1}
CheckMap, gates: {'h': 1, 'cx': 1}
FullAncillaAllocation, gates: {'h': 1, 'cx': 1}
EnlargeWithAncilla, gates: {'h': 1, 'cx': 1}
ApplyLayout, gates: {'h': 1, 'cx': 1}
CheckMap, gates: {'h': 1, 'cx': 1}
UnitarySynthesis, gates: {'h': 1, 'cx': 1}
HighLevelSynthesis, gates: {'h': 1, 'cx': 1}
UnrollCustomDefinitions, gates: {'h': 1, 'cx': 1}
BasisTranslator, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'ecr': 1, 'x': 1}
CheckGateDirection, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'ecr': 1, 'x': 1}
GateDirection, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}   # NON BASIS RY INSERTED HERE
RemoveResetInZeroState, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
Depth, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
FixedPoint, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
Size, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
FixedPoint, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
Optimize1qGatesDecomposition, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
CXCancellation, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
GatesInBasis, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
UnitarySynthesis, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
HighLevelSynthesis, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
UnrollCustomDefinitions, gates: {'s': 6, 'sx': 2, 'sdg': 1, 'x': 1, 'ry': 2, 'ecr': 1, 'h': 2}
# raises exception here

This pass should only insert gates supported by the backend, and be updated to work with Clifford basis backends to enable simulation testing

[jakelishman]

In general, the transpiler was never designed to support discrete-basis synthesis at the same level of support as for continuous basis gates. While it's GateDirection that happens to fail here, and we can probably tweak the exact replacement it uses to keep things stabiliser-supported for longer into the transpilation pipelines (and potentially even working for you), in principle, this is trying to use transpile in an out-of-spec manner. This is also why transpile is not giving well-optimised results.

If it's sufficient for you, we can potentially change the decomposition of the ECR reversal in GateDirection, though in general it would be a serious additional commitment if the transpiler needed to support optimal discrete-basis synthesis.

[chriseclectic]

I find it a major frustration when trying to do any testing and debugging of primitives at utility scale without real support for Clifford basis in the transpiler, and I think this only becomes more important as we increase the number of qubits and Clifford simulation becomes the only way to do simulator based testing. At the moment I'm not overly concerned about the sub-optimality of the result, just that it can run for testing and debugging.

In the future it would be nice if it could synthesis optimally as well. Now this Clifford support this doesn't need to necessarily be discrete basis gates, it could use backend basis gates (which are Clifford + RZ), and then validate the RZ angles are k*pi/2, and then either have an extra pass to replace these with I, Z, S, Sdg depending on the angle, or update Aer to support clifford-angled RZs for its stabilizer method. But achieving will require making sure synthesis passes respect this by mapping Clifford to valid Clifford angled RZ decompositions in synthesis and optimization routines, which is currently not the case.

[jakelishman]

If you have a particular need for a large-scale feature from Qiskit (which I would argue that optimal discrete-basis synthesis is), please can you be sure to mention it during quarterly planning so it can be worked into our prioritisation, and we can work out who will be responsible?