$\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}$?

  • $\begingroup$ I'm supposed to go up to the greatest integer not greater than $\sqrt{77}$. $\endgroup$ – R. Chopin Dec 3 '18 at 14:15
  • $\begingroup$ What does the question have to do with superpositions? $\endgroup$ – Norbert Schuch Dec 3 '18 at 15:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Mariia Mykhailova Dec 3 '18 at 17:04
  • 1
    $\begingroup$ 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! $\endgroup$ – R. Chopin Dec 3 '18 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.

  • 1
    $\begingroup$ $\newcommand{\floor}[1]{\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$. $\endgroup$ – R. Chopin Dec 4 '18 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.