Repository: Qiskit/qiskit-terra (python)

Issue:
VF2Layout transpiler pass inserts extra qubits (more than are in the device)
### Environment

- **Qiskit Terra version**: 0.21.2
- **Python version**: 3.10.5
- **Operating system**: Linux

Here are more qiskit related versions:

qiskit-ibm-runtime==0.6.2
qiskit-ibmq-provider==0.19.2



### What is happening?

When using `ibmq_guadalupe` as a backend (num_qubits == 16), I see that for a circuit with 16 qubits initially that after transpile num_qubits is more than 16.

### How can we reproduce the issue?

The following code produces the problem for me:

```python
qasm_str = """
OPENQASM 2.0;
include "qelib1.inc";
qreg q[16];
creg c[5];
rz(pi/2) q[0];
sx q[0];
sx q[1];
rz(-pi/4) q[1];
sx q[1];
rz(pi/2) q[1];
rz(2.8272143) q[0];
rz(0.43324854) q[1];
sx q[1];
rz(-0.95531662) q[7];
sx q[7];
rz(3*pi/4) q[7];
barrier q[1],q[10],q[4],q[0],q[7];
measure q[1] -> c[0];
measure q[10] -> c[1];
measure q[7] -> c[2];
measure q[4] -> c[3];
measure q[0] -> c[4];
"""

from qiskit import QuantumCircuit, transpile
from qiskit_ibm_runtime import Sampler

from qiskit_ibm_runtime import QiskitRuntimeService


service = QiskitRuntimeService(channel="ibm_quantum")
backend = service.backend("ibmq_guadalupe")

circ = QuantumCircuit.from_qasm_str(qasm_str)

best_circ = transpile(
    circ,
    backend=backend,
    scheduling_method="alap",
    optimization_level=3,
    approximation_degree=0,
)

print(circ.num_qubits)
print(best_circ.num_qubits)
```

This prints 16 and then 20.

Ideally, the next code here would be

```python
with Sampler(circuits=circ_list, service=service, options={"backend": "ibmq_guadalupe"}) as sampler:
    result_c = sampler(circ_list, shots=shots)
```

but that produces an error string which includes `TranspilerError: 'Number of qubits (20) in circuit-78 is greater than maximum (16) in the coupling_map`.

### What should happen?

The transpiled circuit should have a number of qubits consistent with the backend and it should be able to run the circuit on the backend.

### Any suggestions?

The behavior seems similar to https://github.com/Qiskit/qiskit-terra/issues/7677. I tried doing the transpile with both the backend object from qiskit_ibm_runtime (so BackendV2) and from qiskit-ibmq-provider (so BackendV1) but got the same result. I checked that `len(backend.properties().qubits)` was also 16 for the BackendV1 case.

Stepping through in a debugger, I found that the problem occurred in this section:

https://github.com/Qiskit/qiskit-terra/blob/8a3e760ffaf6dcd06c0a0e04f13612fdefd9ab3c/qiskit/transpiler/passes/layout/vf2_layout.py#L193-L195

The chosen_layout had a mapping between 0, 1, 4, 7, 10 (virtual) and 0, 5, 10, 13, 15. 

In these methods:

https://github.com/Qiskit/qiskit-terra/blob/8a3e760ffaf6dcd06c0a0e04f13612fdefd9ab3c/qiskit/transpiler/layout.py#L167-L183

It then looped through and found that it needed to add bits starting from `len(self) == 5`, so skipping 1-4. I am not sure where the breakdown in assumptions occurred but it seems like the layout was assuming physical qubits had been densely mapped with no indices skipped?

If I tweak the example circuit so that it includes a gate on every qubit 0-15, then the transpile produces a circuit with 16 qubits as expected.

Pull request description:
Fix handling of holes in physical bits list in Layout
<!--
⚠️ If you do not respect this template, your pull request will be closed.
⚠️ Your pull request title should be short detailed and understandable for all.
⚠️ Also, please add a release note file using reno if the change needs to be
  documented in the release notes.
⚠️ If your pull request fixes an open issue, please link to the issue.

- [ ] I have added the tests to cover my changes.
- [ ] I have updated the documentation accordingly.
- [ ] I have read the CONTRIBUTING document.
-->

### Summary

Previously the behavior of `Layout.add(virtual)` would attempt to select an available physical bit to pair for the layout. However, the manner in which this selection was done was buggy and it would potentially skip over available physical bits on the device and instead add a new physical bit to the layout. This had unintended consequences for layouts that added bits in higher numbers first. This commit fixes this behavior by first checking that we've exhausted all available physical bits from 0 to max bit in layout. Then if there are no holes in the physical bits in the layout it will add a bit to the top.

### Details and comments

Fixes #8667

Patch:
diff --git a/qiskit/transpiler/layout.py b/qiskit/transpiler/layout.py
index 139b56673..5b00ca10a 100644
--- a/qiskit/transpiler/layout.py
+++ b/qiskit/transpiler/layout.py
@@ -157,18 +157,26 @@ class Layout:
     def add(self, virtual_bit, physical_bit=None):
         """
         Adds a map element between `bit` and `physical_bit`. If `physical_bit` is not
-        defined, `bit` will be mapped to a new physical bit (extending the length of the
-        layout by one.)
+        defined, `bit` will be mapped to a new physical bit.
 
         Args:
             virtual_bit (tuple): A (qu)bit. For example, (QuantumRegister(3, 'qr'), 2).
             physical_bit (int): A physical bit. For example, 3.
         """
         if physical_bit is None:
-            physical_candidate = len(self)
-            while physical_candidate in self._p2v:
-                physical_candidate += 1
-            physical_bit = physical_candidate
+            if len(self._p2v) == 0:
+                physical_bit = 0
+            else:
+                max_physical = max(self._p2v)
+                # Fill any gaps in the existing bits
+                for physical_candidate in range(max_physical):
+                    if physical_candidate not in self._p2v:
+                        physical_bit = physical_candidate
+                        break
+                # If there are no free bits in the allocated physical bits add new ones
+                else:
+                    physical_bit = max_physical + 1
+
         self[virtual_bit] = physical_bit
 
     def add_register(self, reg):
diff --git a/releasenotes/notes/register-add-fix-e29fa2ee47aa6d05.yaml b/releasenotes/notes/register-add-fix-e29fa2ee47aa6d05.yaml
new file mode 100644
index 000000000..41bad77a4
--- /dev/null
+++ b/releasenotes/notes/register-add-fix-e29fa2ee47aa6d05.yaml
@@ -0,0 +1,26 @@
+---
+upgrade:
+  - |
+    The :meth:`.Layout.add` behavior when not specifying a ``physical_bit``
+    has changed from previous releases. In previous releases, a new physical
+    bit would be added based on the length of the :class:`~.Layout` object. For
+    example if you had a :class:`~.Layout` with the physical bits 1 and 3
+    successive calls to :meth:`~.Layout.add` would add physical bits 2, 4, 5, 6,
+    etc. While if the physical bits were 2 and 3 then successive calls would
+    add 4, 5, 6, 7, etc. This has changed so that instead :meth:`.Layout.add`
+    will first add any missing physical bits between 0 and the max physical bit
+    contained in the :class:`~.Layout`. So for the 1 and 3 example it now
+    adds 0, 2, 4, 5 and for the 2 and 3 example it adds 0, 1, 4, 5 to the
+    :class:`~.Layout`. This change was made for both increased predictability
+    of the outcome, and also to fix a class of bugs caused by the unexpected
+    behavior. As physical bits on a backend always are contiguous sequences from
+    0 to :math:`n` adding new bits when there are still unused physical bits
+    could potentially cause the layout to use more bits than available on the
+    backend. If you desire the previous behavior, you can specify the desired
+    physical bit manually when calling :meth:`.Layout.add`.
+fixes:
+  - |
+    Fixed the behavior of :meth:`.Layout.add` which was potentially causing the
+    output of :meth:`~.transpile` to be invalid and contain more Qubits than
+    what was available on the target backend. Fixed:
+    `#8667 <https://github.com/Qiskit/qiskit-terra/issues/8667>`__


Test patch:
diff --git a/test/python/transpiler/test_layout.py b/test/python/transpiler/test_layout.py
index a01c75783..cf034b4d7 100644
--- a/test/python/transpiler/test_layout.py
+++ b/test/python/transpiler/test_layout.py
@@ -217,7 +217,7 @@ class LayoutTest(QiskitTestCase):
         layout.add(self.qr[1], 2)
         layout.add(self.qr[0])
 
-        self.assertDictEqual(layout.get_virtual_bits(), {self.qr[0]: 1, self.qr[1]: 2})
+        self.assertDictEqual(layout.get_virtual_bits(), {self.qr[0]: 0, self.qr[1]: 2})
 
     def test_layout_combine_smaller(self):
         """combine_into_edge_map() method with another_layout is smaller and raises an Error"""
diff --git a/test/python/transpiler/test_vf2_layout.py b/test/python/transpiler/test_vf2_layout.py
index 57eaa09a0..4cb4b4487 100644
--- a/test/python/transpiler/test_vf2_layout.py
+++ b/test/python/transpiler/test_vf2_layout.py
@@ -13,10 +13,12 @@
 """Test the VF2Layout pass"""
 
 import unittest
+from math import pi
+
 import numpy
 import retworkx
 
-from qiskit import QuantumRegister, QuantumCircuit
+from qiskit import QuantumRegister, QuantumCircuit, ClassicalRegister
 from qiskit.transpiler import CouplingMap, Target, TranspilerError
 from qiskit.transpiler.passes.layout.vf2_layout import VF2Layout, VF2LayoutStopReason
 from qiskit.converters import circuit_to_dag
@@ -26,8 +28,11 @@ from qiskit.providers.fake_provider import (
     FakeRueschlikon,
     FakeManhattan,
     FakeYorktown,
+    FakeGuadalupeV2,
 )
 from qiskit.circuit.library import GraphState, CXGate
+from qiskit.transpiler import PassManager
+from qiskit.transpiler.preset_passmanagers.common import generate_embed_passmanager
 
 
 class LayoutTestCase(QiskitTestCase):
@@ -497,7 +502,7 @@ class TestMultipleTrials(QiskitTestCase):
             "DEBUG:qiskit.transpiler.passes.layout.vf2_layout:Trial 159 is >= configured max trials 159",
             cm.output,
         )
-        self.assertEqual(set(property_set["layout"].get_physical_bits()), {49, 40, 58, 3, 4})
+        self.assertEqual(set(property_set["layout"].get_physical_bits()), {49, 40, 58, 0, 1})
 
     def test_no_limits_with_negative(self):
         """Test that we're not enforcing a trial limit if set to negative."""
@@ -518,7 +523,48 @@ class TestMultipleTrials(QiskitTestCase):
             vf2_pass(qc, property_set)
         for output in cm.output:
             self.assertNotIn("is >= configured max trials", output)
-        self.assertEqual(set(property_set["layout"].get_physical_bits()), {3, 1, 2})
+        self.assertEqual(set(property_set["layout"].get_physical_bits()), {3, 1, 0})
+
+    def test_qregs_valid_layout_output(self):
+        """Test that vf2 layout doesn't add extra qubits.
+
+        Reproduce from https://github.com/Qiskit/qiskit-terra/issues/8667
+        """
+        backend = FakeGuadalupeV2()
+        qr = QuantumRegister(16, name="qr")
+        cr = ClassicalRegister(5)
+        qc = QuantumCircuit(qr, cr)
+        qc.rz(pi / 2, qr[0])
+        qc.sx(qr[0])
+        qc.sx(qr[1])
+        qc.rz(-pi / 4, qr[1])
+        qc.sx(qr[1])
+        qc.rz(pi / 2, qr[1])
+        qc.rz(2.8272143, qr[0])
+        qc.rz(0.43324854, qr[1])
+        qc.sx(qr[1])
+        qc.rz(-0.95531662, qr[7])
+        qc.sx(qr[7])
+        qc.rz(3 * pi / 4, qr[7])
+        qc.barrier([qr[1], qr[10], qr[4], qr[0], qr[7]])
+        vf2_pass = VF2Layout(
+            seed=12345,
+            target=backend.target,
+        )
+        vf2_pass(qc)
+        self.assertEqual(len(vf2_pass.property_set["layout"].get_physical_bits()), 16)
+        self.assertEqual(len(vf2_pass.property_set["layout"].get_virtual_bits()), 16)
+        pm = PassManager(
+            [
+                VF2Layout(
+                    seed=12345,
+                    target=backend.target,
+                )
+            ]
+        )
+        pm += generate_embed_passmanager(backend.coupling_map)
+        res = pm.run(qc)
+        self.assertEqual(res.num_qubits, 16)
 
 
 if __name__ == "__main__":