Double CNOTs in the CX block generated by the annealer

[Aerylia]

Occasionally, the annealer finds CX blocks where two of the same CNOTs are added together. This is inefficient.

This is because the line of code that checks whether the CNOTs are preceding or not only checks the surrounding layers. So suppose I have 5 layers in the CX block with only CNOT(1,2) in the first layer, then the third layer might also obtain CNOT(1,2).

In OptimizedCircuit.random_flip_cx() :

if layer_idx < len(self._cx_block)-1 and self._cx_block[layer_idx+1].has_cx(ctrl, trgt):
    # Try again if CX gate already present in layer above (to avoid redundancy)
    continue
if layer_idx > 0 and self._cx_block[layer_idx-1].has_cx(ctrl, trgt):
    # Try again if CX gate already present in layer below (to avoid redundancy)

[sg495]

That's a good point. Something like the code below would do the trick:

  def _check_cx_at_layer(self, ctrl: int, trgt: int, layer_idx: int) -> Tuple[bool, bool]:
      block_l = self._cx_block[layer_idx]
      # 1. Check whether the layer has the desired CX:
      if block_l.has_cx(ctrl, trgt):
          return True, True
      # cx found ^^^^  ^^^^ break search
      # 2. Check whether there is a blocking CX on the control side:
      ctrl_gate = block_l.incident(ctrl)
      if ctrl_gate and ctrl_gate[1] == ctrl:
          return False, True
      #    no cx ^^^^^  ^^^^ break search
      # 3. Check whether there is a blocking CX on the target side:
      trgt_gate = block_l.incident(trgt)
      if trgt_gate and trgt_gate[0] == trgt:
          return False, True
      #    no cx ^^^^^  ^^^^ break search
      return False, False
      #no cx ^^^^^  ^^^^^ continue search

  def random_flip_cx(self) -> Tuple[int, Tuple[int, int]]:
      while True:
          layer_idx = int(self._rng.integers(len(self._cx_block)))
          ctrl, trgt = self._cx_block[layer_idx].random_flip_cx(self._rng)
          cx_present = False
          for l in range(layer_idx+1, len(self._cx_block)):
              cx_present, break_here = self._check_cx_at_layer(ctrl, trgt, l)
              if break_here:
                  break
          for l in range(layer_idx-1, -1, -1):
              cx_present, break_here = self._check_cx_at_layer(ctrl, trgt, l)
              if break_here:
                  break
          if cx_present:
              continue
          self._flip_cx(layer_idx, ctrl, trgt)
          return layer_idx, (ctrl, trgt)

That said, it has a big impact in terms of performance, because CX flips are a very common operation, so unless the quality drop in solutions is significant I'm wary of making this change.

[Aerylia]

Considering that most of the performance metrics that we are using are gate count/depth, this would make the algorithm seem worse than it needs to be. It could also be resolved by removing these obvious inefficiencies at a final pass.

[sg495]

Yeah, that's probably better. More generally, the blocks could be simplified at the end as CX circuits.