Repository: quantumlib/Qualtran

Issue:
Negative Toffoli counts in ECAdd, QROAMCleanAdjoint
If you compute QECGatesCost for `ec_add_small` example of `ECAdd`, you'll get a negative integer for the number of toffoli gates. This isn't correct! I did a skim of the call graph and I think it's coming from `QROAMCleanAdjoint`.

Discussion:
@tanujkhattar: The reason this is happening is because the formula is misbehaving for small sized circuits. 

Uncomputing a qrom read of N elements, each with bitsize b is reduced to a qrom of N / 2 elements, each of bitsize 2. To load N elements with bitsize b using QROAM, we pick a block size (say lambda) and reduce the problem into two parts: 

1) Do a regular QROM of `N / lambda` elements. This costs `(N / lambda) - 2 + num_controls`. However, if `N / lambda` is small (i.e. 0 or 1 or 2), then the formula really is `max(0, (N / lambda) - 2 + num_controls)`. 

2) Do a `SwapWithZero` of lambda elements, each of bitsize `b`. This costs `(lambda - 1) * b` Toffolis. 

Bringing these two together, for uncomputation of a QROAM, the resulting formula should be 
```
((N / 2 * lambda) - 2 + self.num_controls) + (lambda - 1) * 2  
```
Since `lambda` is a parameter we optimize over, we replace `2 * lambda` with just `lambda` and rewrite the formula as

```
N / lambda + lambda - 4 + self.num_controls
```

This is what is implemented in the build_call_graph of QROAMCleanAdjoint: 

https://github.com/quantumlib/Qualtran/blob/ab9d2eac484edbf6b7ddc6724be0648389a702be/qualtran/bloqs/data_loading/qroam_clean.py#L182

However, when `N` or `N / lambda` is small (0 or 1 or 2), we should take a `max(0, <formula>)`. I think we can change the implementation such that we return the same formula when any of the parameters is symbolic, else we return a `max(0, <formula>)` and it should be a correct fix.

Solution patch:
diff --git a/qualtran/bloqs/data_loading/qroam_clean.py b/qualtran/bloqs/data_loading/qroam_clean.py
index 76e65345..ab53dc58 100644
--- a/qualtran/bloqs/data_loading/qroam_clean.py
+++ b/qualtran/bloqs/data_loading/qroam_clean.py
@@ -189,6 +189,8 @@ class QROAMCleanAdjoint(QROMBase, GateWithRegisters):  # type: ignore[misc]
         block_sizes = prod([2**k for k in self.log_block_sizes])
         data_size = prod(self.data_shape)
         n_toffoli = ceil(data_size / block_sizes) + block_sizes - 4 + self.num_controls
+        if not is_symbolic(n_toffoli):
+            n_toffoli = max(0, n_toffoli)
         return {Toffoli(): n_toffoli}
 
     @cached_property
@@ -278,6 +280,8 @@ class QROAMCleanAdjointWrapper(Bloq):
         block_sizes = prod([2**k for k in self.log_block_sizes])
         data_size = prod(self.qroam_clean.data_shape)
         n_toffoli = ceil(data_size / block_sizes) + block_sizes - 4 + self.qroam_clean.num_controls
+        if not is_symbolic(n_toffoli):
+            n_toffoli = max(0, n_toffoli)
         return {Toffoli(): n_toffoli}
 
     def adjoint(self) -> 'QROAMClean':


Test patch:
diff --git a/qualtran/bloqs/cryptography/ecc/ec_add_test.py b/qualtran/bloqs/cryptography/ecc/ec_add_test.py
index c831ab59..83d57772 100644
--- a/qualtran/bloqs/cryptography/ecc/ec_add_test.py
+++ b/qualtran/bloqs/cryptography/ecc/ec_add_test.py
@@ -443,3 +443,8 @@ def test_ec_add_small(bloq_autotester):
 @pytest.mark.notebook
 def test_notebook():
     qlt_testing.execute_notebook('ec_add')
+
+
+def test_ec_add_small_gate_cost():
+    bloq = _ec_add_small.make()
+    assert get_cost_value(bloq, QECGatesCost()).toffoli == 29
diff --git a/qualtran/bloqs/data_loading/qroam_clean_test.py b/qualtran/bloqs/data_loading/qroam_clean_test.py
index 02d6fd78..c4e5ce6d 100644
--- a/qualtran/bloqs/data_loading/qroam_clean_test.py
+++ b/qualtran/bloqs/data_loading/qroam_clean_test.py
@@ -211,3 +211,19 @@ def test_qroam_clean_classical_sim_multi_dataset():
                 target1_=vals[3],
                 junk_target1_=vals[5],
             ) == (x, y)
+
+
+def test_qroam_clean_small_bloq_counts():
+    qroam_clean = QROAMClean(
+        data_or_shape=(np.array([0, 7]),),
+        selection_bitsizes=(1,),
+        target_bitsizes=(6,),
+        target_shapes=((),),
+        num_controls=0,
+        log_block_sizes=(0,),
+    )
+    assert qroam_clean.t_complexity().t == 0
+    qroam_clean_adj_wrapper = QROAMCleanAdjointWrapper(
+        qroam_clean=qroam_clean, log_block_sizes=(0,)
+    )
+    assert qroam_clean_adj_wrapper.t_complexity().t == 0