0
$\begingroup$

The textbook Grover search algorithm presented in many lecture notes (eg.) is over bitstrings $x \in \{0,1\}^{n}$. Typically the Grover operator is of the form $G = H U H V$ where $H$ is the Walsh-Hadamard transform for $n$-qubit states, and $U$ and $V$ are some reflections. Is it true with the substitution of $H$ for the Quantum Fourier Transform $\operatorname{QFT}_k$ over the cyclic group $\mathbb{Z}_k$ one can obtain an algorithm that solves the unstructured search problem over $k$-ary strings $x \in [k]^n$? Are there any difficulties that arise, or does this generalization just work? Could you provide some references that describe this more general setup?

$\endgroup$

1 Answer 1

0
$\begingroup$

I think you are right about the direction of the generalization. After a quick search I found these:

https://arxiv.org/abs/0809.0932 - one of the earliest examples I found tracing back citations - maybe the first proposal?

The rest I found are around the same topic with different optimizations and implementation aspects - from which I gather that implementing/decomposing the q-ary Toffoli gate and in general finding a good gateset to implement the algorithm with are the key tricky bits in implementations.

https://arxiv.org/abs/1209.4489

https://arxiv.org/abs/2012.04447

https://arxiv.org/abs/2001.06316

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.