The Bernstein Vazirani can solve s for f(x) = s(dot product) x mod 2. My question is if its possible to modify this to work for mod 3,4 etc. Is this even possible? Edit: Whats the probability of the modified algorithms success?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ arxiv.org/pdf/1609.03185.pdf I haven't checked the paper but it seems to be dealing with precisely this topic. Since the Bernstein-Vazirani algorithm is essentially looking at the inner product oracle in the Fourier basis (Hadamard transform is the quantum Fourier transform for the group $Z_2^n$), generalizing this to quantum Fourier transform for, say, $Z_k^n$ seems to be a natural direction, at least. $\endgroup$– AYunApr 25, 2022 at 14:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In the case where the modulus you want to take is even, you can return to standard Benstein-Vazirani: If you're doing $f(x)=s\cdot x\text{ mod }2p$, then this has a $k$-bit output and the least significant bit of this is just $s\cdot x\text{ mod }2$. You can use the standard Bernstein-Vazirani algorithm. You just have to be careful that the extra $k-1$ bits don't prevent the interference. I believe the trick is that on the $k$-qubit register, you input the state $|-\rangle$ on the least significant bit, and $|+\rangle$ on all the others. This means that you only get the phase kick-back from the one bit you're interested in.
answered Apr 25, 2022 at 6:48