In this paper, the following feature map is used:
$$x \to \vert\phi(x)\rangle = \frac{1}{\sqrt{2^k}}\sum_{i=0}^{2^k-1}\vert x\cdot g^i\rangle$$
But no circuit is provided. A theoretical description of the circuit is provided in the supplementary information on page 17 (the image is provided below).
The steps require:
- Modular multiplication and exponentiation: $$C_{y,k}\vert i \rangle \vert 0^n \rangle= \vert i \rangle \vert (y\cdot g^i) \% p \rangle$$ But they don't describe how to create this.
- Discrete log: $$U_y \vert (y\cdot g^i) \% p \rangle \vert0\rangle = \vert i \rangle\vert (y\cdot g^i) \% p \rangle$$
The overall process is described as: $$\vert0^n\rangle \overset{H^{\otimes k}}{\to}\frac{1}{\sqrt{2^k}}\sum_{i \in\{0,1\}^k}\vert i\rangle \overset{C_{y,k}}{\to}\frac{1}{\sqrt{2^k}}\sum_{i \in\{0,1\}^k}\vert i\rangle \vert (y\cdot g^i) \% p \rangle \overset{U_y^\dagger}{\to}\frac{1}{\sqrt{2^k}}\sum_{i \in\{0,1\}^k}\vert (y\cdot g^i) \% p \rangle$$
How to create this feature map?
