# From the Order of a Group to the Power of a Square Matrix

## 目標

定義出一個 $H$，使得 $H^k$ 與 $x^k\pmod{N}$ 產生對應關係。

因為我們希望當 $x^r=1\pmod{N}$ 時，$H^r=I$。
其中 $r$ 是 $\mathbb{Z}_N$ 的 order of group。

但是我們不知道$r$是多少。

----

## 定義 $H$

直接定義 $H^k = \left|x^k\pmod{N}\right>$

但是$H^k$是 square matrix，$\left|x^k\pmod{N}\right>$ 是 column vecter。
不行這樣定義。

改成定義
$$
H^k\left|?\right> = \left|x^k\pmod{N}\right> \tag{1}
$$

---

## $\left|?\right>=$ ?

$\left|?\right>$該等於多少?

令 $k=0$

$$
\begin{align*}
&& H^0\left|?\right> &= \left|x^0\pmod{N}\right> \\
\Rightarrow && I\left|?\right> &= \left|1 \pmod{N}\right> \\
\Rightarrow && \left|?\right> &= \left|1 \right>
\end{align*}
$$

所以我們可以得到$\left|?\right>=\left|1\right>$，因此
$$
H^k\left|1\right> = \left|x^k\pmod{N}\right> \tag{2}
$$

---

## $H\left|y\right> =$ ?

對任意$\left|y\right>$，$H\left|y\right>$該等於多少?

---

令 $k=k_1+k_2$

$$
\begin{align*}
&& H^{k_1+k_2}\left|1\right> &= \left|x^{k_1+k_2}\pmod{N}\right> \\
\Rightarrow && H^{k_1}H^{k_2}\left|1\right> &= \left|x^{k_1}x^{k_2}\pmod{N}\right> \\
\Rightarrow && H^{k_1}\left|x^{k_2}\pmod{N}\right> &= \left|x^{k_1}x^{k_2}\pmod{N}\right>
\end{align*}
$$

令 $k_1=1$ 且 $k_2=\log_x y$ ，代入上式，得到:

$$
H\left|y\pmod{N}\right> = \left|x y\pmod{N}\right> \tag{3}
$$

---

## 最後

剩下幾個問題。

$H\left|y \right>
=H\left|xy \pmod{N}\right>$ 是否成立?
有必要去證明嗎?

$H$裡面的每個element是什麼?
有算的必要嗎?