Implement table lookups assisted by clean ancillas

[tanujkhattar]

We now have the following QROM implementations to load N classical data items to a b bit register using a log(N) size selection register:

1. QROM: Implemented using Unary Iteration

   • T-complexity: $O(4N − 4)$
   • Qubit count: $O(2 * log(N) + b)$ clean qubits.

2. SelectSwapQROM: Unary iteration based QROM assisted by dirty ancillae. Given a tunable parameter $1 <= \lambda <= N$:

   • T-complexity: $2 * O(\frac{N}{\lambda}) + 4 * O(b\lambda)$ (modulo constant factors)
   • Qubit count: $O(2 * log(N / \lambda) + log(\lambda) + b)$ clean qubits and $O(b * \lambda)$ dirty qubits.
     To compute the T-complexity, notice that we have 2 applications of traditional QROM, each requiring $O(4 * (\frac{N}{\lambda} - 1))$ T-gates and 4 applications of SwapWithZero gate, each requiring $O(4 * (b - 1) * \lambda)$ T-gates.

3. If we have access to clean ancillae instead of dirty ancillae, we can further reduce the T-complexity of data lookups by doing measurement based uncomputation instead of applying the adjoint of QROM and SwapWithZero gates, as done in the second approach above. This approach is described on Page 25 of https://arxiv.org/abs/1902.02134 and (briefly) in https://algassert.com/post/1903

This issue is to track adding a new primitive using appraoch-3.