0
$\begingroup$

Nilsen states that one can define a function for the oracle in the Grover algorithm, which is constructed as follows. So there is a number $m$ that consists of $p$ and $q$ (both primes) $m = pq$. Now define a function that says $f (x) \equiv 1 $ if $x$ divides $m$, 0 otherwise.

Then the function $f(x)$ for $x \in \{1,7,11,77\}$ would be 1. That means in the algorithm then the amplitudes of these states would be negated and increased by the diffusion operator. If I measure the register then say I could measure states $1, 7, 11, 77$. But 1 and 77 do not bring me much as prime factors?

So that I actually measure 7 and 11 as correct prime factors, would it be enough to simply rerun the algorithm?

Improve this question
$\endgroup$
3
  • $\begingroup$ Step back - what are you asking? Why do you think that $77 \bmod 7 = 1$? Why do you think that $77\bmod 1=1$? The way you've defined $f(x)$ is perfectly fine, and $f(x)$ would be $1$ for $x\in\{1,7,11,77\}$. $\endgroup$
    – Mark Spinelli
    May 1, 2019 at 2:50
  • $\begingroup$ That's what I was about. 1,7,11 and 77 are correct. Only one would like to measure the prime factors 7 and 11 as best as possible. But the algorithm would then probably make the phase shift for 1,7,11 and 77, so I measure one of these states at the end, with 1 and 77 not giving me much as prime factors. Is it enough to simply repeat the algorithm? $\endgroup$
    – user4961
    May 1, 2019 at 8:26
  • $\begingroup$ Edit: Oh, that was also a mistake of mine, of course, 77 mod 1 = 0 as well as 77 mod 7 = 0 (typo). $\endgroup$
    – user4961
    May 1, 2019 at 8:33

1 Answer 1

Reset to default
2
$\begingroup$

If you implement an oracle for Grover's algorithm that sometimes gives unhelpful answers, you can, as you suggest, rerun and remeasure. In your example, there are only two incorrect answers $x=0$ and $x=m$. With the way you defined $f(x)$, these would indeed be negated and diffused. Because there are only two bad answers, the impact may be small.

However the oracle in Grover's Algorithm can be anything that you can define. So you can explicitly define $f(x)$ to be $1$ iff $x$ divides $m$ and $x\not\in \{0,m\}$. This has the effect of making $f$ a little more complicated of course, increasing the gate count, but depending on the situation it may be more efficient than having to rerun/remeasure.

Is there a reason you wish to run Grover's algorithm to factor a number? Are you trying to understand something in N&C?

Improve this answer
$\endgroup$
1
  • $\begingroup$ The background is this: I read this in Nielsen and then found that there are also values that are not so pleasant then. To stay in the example 1 and 77, that would not help me as a prime factor. That is why the question came up to me, how to prevent it. I thought I'd run the algorithm again. But the most interesting part is the "real" implementation if you will. Because in the end that has to be implemented with a circuit. Immediately I would not know how to realize this as a circuit. As you say, you can define the function like this. But then is the question, how to implement this (circuit) $\endgroup$
    – user4961
    May 1, 2019 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.