Grover search

Let $n\geq1$ be an integer, $N=2^n$, $x$ be a nonzero $N$-bit string, and $t=|\{j:x_j=1\}|$. Given access to an $n$-qubit oracle $U_x$ such that $U_x\ket{j}=(-1)^{x_j}\ket{j}$, for every integer $k\geq0$, there exists a quantum algorithm that returns an index $j$ satisfying $x_j=1$ with probability $\sin^2((2k+1)\arcsin\sqrt{t/N})$, using at most $n+1$ logical qubits, $k$ queries to $U_x$, and the following gate counts: $$ \begin{array}{c|ccc} n & \text{Toffoli gates} & \text{CNOT gates} & \text{Single-qubit gates} \\ \hline 1 & 0 & 0 & 1+3k \\ 2 & 0 & k & 2+8k \\ 3 & k & 0 & 3+15k \\ 4 & 4k & 0 & 4+19k \\ 5 & 10k & 0 & 5+23k \\ n\geq6 & 8(n-4)k & 0 & n+(4n+3)k \end{array} $$