How to prepare a superposed states of odd integers from $1$ to $\sqrt{N}$?

Question

$\newcommand{\q}[2]{\langle #1 | #2 \rangle} \newcommand{\qr}[1]{|#1\rangle} \newcommand{\ql}[1]{\langle #1|} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\round}[1]{\left\lfloor #1 \right\rceil} \DeclareMathOperator{\div}{div} \DeclareMathOperator{\modulo}{mod} $I present all the detailed reasoning in my strategy and show it has a problem. My question is how to overcome this flaw. An example here will be best. In what follows, "bit" means "q-bit".

Let $N = 77$ and let $n$ be the number of bits of $N$. How many bits do I need to superpose all odd integers from 1 to $\sqrt{77}$? I believe that's approximately $n/2$. (It is $n/2$ exactly if $n$ were even. Since it is not, I need $\floor{n/2} + 1$.) For $N = 77$, $7$ bits is enough.

Let $B$ be a register big enough to hold the superposed states of all all odd integers from 1 to $\sqrt{77}$. Let $A$ be a register big enough to hold $77$, but also big enough to hold the division of $77$ by the superposed state held in $B$. For clarity, assume my division operator is given by

$$U_{\div} \qr{b}_x \qr{a}_y = \qr{b}_x (\qr{a \div b} \qr{a \modulo b})_y$$

and assume that $y = n + (n/2)$ and $x = n/2$. So, in our example, since $N=77$, it follows $n = 8$ and then the size of $B$ is $4$ bits, while the size of $A$ is $8 + 4 = 12$.

But since I want in $B$ only the odd integers, I take $B$'s lowest bit and force it to be $1$. So my preparation of $B$ is to start with it completely zeroed out, flip its lowest bit and finally use the Hadamard gate on all of B's bits except the lowest. I get

$$H^{\otimes 3} \qr{000}\otimes\qr1 = \qr{+}\qr{+}\qr{+} \otimes \qr{1}.$$

Now I get the states $\qr{1}, \qr3, \qr5, \qr7, \qr9, \qr{11}, \qr{13}, \qr{15}$. I wish I had stopped at $\qr{7}$.

This means I need less than $n/2$ bits in register $B$. By inspection, I see in this example that the size of $B$ should be $3$ bits, not $4$ because this way I end up with the superposition terms $\qr1, \qr3, \qr5, \qr7$, but all I'm sure of here is just this example.

So the question is what size in general should $B$ have so that it is able to hold all superposition terms of only odd integers from $1$ to $\sqrt{N}$?

Answer 1

You would only need $\log_2(N)$ bits to represent a number $N$ and also all the numbers from $0$ to $N$. Similarly, you would need $$\log_2(\sqrt{N}) = \log_2(N^{\frac{1}{2}}) = \frac{1}{2} \times \log_2(N) $$ bits to represent numbers from $0$ to $\sqrt{N}$. So I would say you would need half of $\log_2(N)$ qubits in your B register. The power of quantum computing comes from the fact that in the classical computer, you could only represent a specific number in the range of $1$ to $\sqrt{N}$ with $\log_2(\sqrt{N})$ qubits, here you would get the benefit of superposition that would hold all of them.