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$ 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$
    – AYun
    Apr 25, 2022 at 14:21

1 Answer 1


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.


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.