# Applicability of the Bernstein-Vazirani to different modulus

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?

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

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.