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

$$\newcommand{\q}{\langle #1 | #2 \rangle} \newcommand{\qr}{|#1\rangle} \newcommand{\ql}{\langle #1|} \newcommand{\floor}{\left\lfloor #1 \right\rfloor} \newcommand{\round}{\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}$$?

• I'm supposed to go up to the greatest integer not greater than $\sqrt{77}$. Dec 3, 2018 at 14:15
• What does the question have to do with superpositions? Dec 3, 2018 at 15:24
• In general you might need floor(n/2)+1 bits - it's just that the number 77 is small enough that its square root fits in floor(n/2) bits. Had it been 81, its square root would be 9 and would have required 4 bits instead of 3. You just need to be careful to not prepare a superposition of all numbers written with floor(n/2)+1 bits. Dec 3, 2018 at 17:04
• You make a lot of sense, @MariiaMykhailova. If I restrict my problem to non-perfect powers (which I actually don't care for), then I get the single answer floor(n/2) bits. In my specific example, I'd use 3 bits in register B instead of 4 the result would be as expected. You've answered my question completely. I really appreciate it! Dec 3, 2018 at 23:37

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.
• $\newcommand{\floor}{\left\lfloor #1 \right\rfloor}$You first sentence isn't strictly true. Say $N=129$, then $\log_2(N) \approx 7$. Since we're talking about bits, you must mean $7$. But with only $7$ bits, you get $0, 1, 2, ..., 128$, not $129$. Also, $\floor{\sqrt{129}} = 11$ which needs $4$ bits, while $1/2 \times \floor{\log_2(129)} = 3$. Dec 4, 2018 at 0:02