2
$\begingroup$

From the literature it seems that grover's algorithm works if $N$ is not a power of $2$. For instance, https://en.wikipedia.org/wiki/Grover%27s_algorithm and https://arxiv.org/abs/quant-ph/0005055

I can definitely see that how this algorithm is represented by using unitary matrices. But, when discussing the circuit, all textbooks I found assume $N=2^n$.

May I ask that how the circuit is designed if $N$ is not a power of $2$? Any reference is appreciated!

$\endgroup$
4
$\begingroup$

One relatively straightforward strategy is to embed the calculation as a search over $M$ qubits where $M=2^n$ and $$ 2^{n-1}<N\leq 2^n. $$ Your oracle then just has to return a non-match for the extra basis states.

$\endgroup$
3
$\begingroup$

The oracle for $N\neq 2^n$ will be exactly the same, and the only difference is the diffusion operator. And in fact, all we need to change in the diffusion operator is the layer of Hadamard gates. Instead, we need a reversible circuit to perform:

$$ \vert 0\rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\vert k\rangle$$

(we actually don't care what it does on other basis states since the diffusion operator is just supposed to add a phase to everything that isn't a uniform superposition; as an exercise, you can show that any valid unitary with the action on $\vert 0\rangle$ shown above will suffice.)

Unfortunately, while this circuit is provably fairly easy to construct, explicit circuits are hard to come by. I asked a similar question here and the only answers involved arbitrary rotation gates or measurement (measurement won't work in Grover's algorithm because we need the adjoint).

If you have access to arbitrary controlled rotations, then we can build it up in a rather complicated way. The basic idea is recursive: We can certainly construct arbitrary superpositions for $N$ if it is a 2-bit number (if $N=1$ we just output $\vert 0\rangle$, and if $N=2$ we just apply a single Hadamard). If $N$ is an $n$-bit number then the superposition over $N$ can be written as

$$ \frac{1}{\sqrt{N}}\sum_{k=0}^{2^{n-1}-1}\vert k\rangle + \frac{1}{\sqrt{N}}\sum_{k=2^{n-1}}^{N-1}\vert k\rangle$$

But first we can re-write the normalizing coefficients, defining $p$ as $p=2^{n-1}/N$, and then $N=2^{n-1}/p$, and $N = (N-2^{n-1})/(1-p)$, we can rewrite the state as

$$ \sqrt{p}\frac{1}{\sqrt{2^{n-1}}}\sum_{k=0}^{2^{n-1}-1}\vert k\rangle + \sqrt{1-p}\frac{1}{\sqrt{N-2^{n-1}}}\sum_{k=2^n}^{N-1}\vert k\rangle$$

Then notice: The sum on the left has $0$ as the first qubit, and the sum on the right has $1$ on the first qubit, so we can move those out and re-parameterize the sum:

$$ \sqrt{p}\vert 0 \rangle\underbrace{\frac{1}{\sqrt{2^{n-1}}}\sum_{k=0}^{2^{n-1}-1}\vert k\rangle}_{A} + \sqrt{1-p}\vert 1\rangle\underbrace{\frac{1}{\sqrt{N-2^{n-1}}}\sum_{k=0}^{N-2^{n-1}-1}\vert k\rangle}_{B}$$

Then: (A) is a uniform superposition over $n-1$ qubits; we can form that with a bunch of Hadamard gates. (B) is a uniform superposition up to $N-2^{n-1}-1$; we can construct that recursively with our circuit for $n-1$ bit numbers

Thus, all we do is start with a rotation to map the first qubit from $\vert 0\rangle$ to $\sqrt{p}\vert 0\rangle + \sqrt{1-p}\vert 1\rangle$. Then we use that qubit to control the application of either all $H$ gates, or our circuit for a superposition of arbitrary $n-1$ bit numbers.

$\endgroup$
2
  • $\begingroup$ Thanks! As a newbie, may I ask why the oracle is exactly the same? Could I say, because the states beyond N-1 simply has 0 amplitude, so it wouldn't matter what outcomes they obtained when calling the oracle? $\endgroup$
    – Victor
    Sep 24 at 21:09
  • 1
    $\begingroup$ Yes, that's a good point. It depends how the oracle is implemented. Ultimately, it has to act on $n$ qubits, so it has to do something on states $| b\rangle$ where $b\geq N$. You're right that it could do anything on those states because they won't be present in any superposition during the algorithm. $\endgroup$
    – Sam Jaques
    Sep 24 at 21:33

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.