量子コンピュータ のバックアップ(No.10)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• 量子コンピュータ へ行く。
  • 1 (2023-02-12 (日) 03:06:03)
  • 2 (2023-02-12 (日) 03:58:30)
  • 3 (2023-02-12 (日) 15:11:41)
  • 4 (2023-12-28 (木) 08:44:27)
  • 5 (2023-12-28 (木) 12:45:28)
  • 6 (2023-12-29 (金) 10:12:16)
  • 7 (2023-12-29 (金) 17:09:04)
  • 8 (2023-12-29 (金) 17:17:43)
  • 9 (2023-12-30 (土) 03:57:55)
  • 10 (2023-12-30 (土) 14:33:42)
  • 11 (2024-01-04 (木) 15:05:01)

概要 †

• ゲート型とアニーラ型がある
  • アニーラは実用に近いとはいえ汎用性がなくてコンピュータ科学的には面白くなさそう…
• ある種の問題では古典コンピュータよりも早そうであると言われている
• 専門家ではないので僕が理解したと信じている範囲でのおきもち
  • 結局 qiskit で表示したり、テンソル積を手を動かしたりして、きちんと理解しないと意味がなさそう

参考 †

• https://sakumatcho.hatenablog.com/

アニーラ型 †

• バイナリ変数\( s_i \)を最適化する。設計した \( H_i, G_{ij} \) と (V, E) のグラフを考え、イジングモデル \( \sum_V H_i s_i + \sum_E G_{ij} s_i s_j \)を最小化する \( s_i \) を求めることができる（近似解）
  • 数の分割問題、グラフの分割問題、クリーク判定問題、整数計画問題、精密被覆問題、集合パッキング問題（最大独立集合問題、MIS）、頂点被覆問題、充足可能性問題（SAT）、最小極大マッチング問題、整数重みナップサック問題、グラフ彩色問題、クリークカバー問題、整数長ジョブスケジューリング問題、ハミルトン閉路問題、巡回セールスマン問題、シュタイナー木問題、次数制約付き最小全域木問題、有向帰還頂点集合問題、無向帰還頂点集合問題、最小帰還辺集合問題、グラフ同型性判定問題などがこのイジングモデルに変換できる（まあ自由度が高いモデルだからそりゃそうという気持ち）
• 数学的にはそうだけど、実はマシンによってはイジング模型のグラフに対する制約もある。イジングマシンはイジングモデルを解くためのものなので別に量子である必要はない（CMOS, GPU, 量子など実装はまちまち）。
  • 例えば、Fixstars Amplify AE, 富士通 Digital Annealer, 東芝 SQBM+ は量子ではなく完全グラフを扱える。D-Wave 2000Q は Chimera グラフ、D-Wave Advantage は Pegasus グラフであり、日立製作所によるイジングマシンの CMOS アニーリングは King's グラフを採用している。グラフ形状への落とし込みが一番の問題点となりそう。
  • D-Wave 2000Q/Advantage は 2000~5000 くらいの変数を扱える。
  • 係数パラメータも、D-Wave だと 5 bits くらいしかない。デジタルのものでも 3~64 までまちまち
  • King's graph で完全グラフを表現するための埋め込みアルゴリズムが知られており、最新の D-Wave 2000Q では、2048 量子ビットを 16×16 のユニットセルで構築しています。そのため完全グラフ換算では 4×16=64 量子ビットに相当します。
• D-Wave が量子的効果を使っているのか、それが他のイジングモデルに比べて早いのか、そのあたりはかなり謎
  • 多分量子的効果を使ってはいそうだが、じゃあ GPU とか CMOS とかで実装したやつより早いの？と言われると超高速って感じじゃない気がする…（小並感）
  • 2022-10 くらいに、Amazon Braket から D-Wave が撤退するらしく、謎 https://blueqat.com/blueqat_official_news_ja/eff276c5-7c46-419e-8adf-7f45454ba2c2

数学的基礎 †

ユニタリ行列 †

• ユニタリ行列は実数での直交行列みたいなもの
  • 直交行列 \( M \in \mathbb{R}^{n \times n} \) は、行ベクトルのセットも列ベクトルのセットも正規直交基底になっており、\( x \) も \( Mx \) もノルムが変わらないようなやつ。回転行列や置換行列を含む。
  • ユニタリ行列 \( U \in \mathbb{C}^{n \times n} \) は直交行列の複素数版。重要な性質として
    • \( U \) の \( n \) 個の固有値のうち一つを \( \lambda \in \mathbb{C} \), その固有値に対応する固有ベクトルを \( x_{\lambda} \in \mathbb{C}^n \) とする（固有値の定義: \( U x_{\lambda} = \lambda x_\lambda \), つまり方向を変えずに \( U \) に伸ばされるベクトルが固有ベクトル、伸ばされる係数が固有値 \( \lambda \)）。この時、\( |\lambda| = 1 \)。複素数平面上の単位円にしか固有値がないということなので、\( \lambda = e^{i \theta}\ (\theta \in \mathbb{R}) \) と表記ができる。

テンソル積 †

• \( \mathbb{R^2} \)のベクトル空間と、\( \mathbb{R} \)のベクトル空間が、別の世界がある状態を考える。
  • これを一緒に扱いたい、自然な形でくっつけるように直和を考えると、\( \mathbb{R^3} \) を考えることができる。これを考えることで、別々の世界に居た住民を足すことができる。
  • \( v \in \mathbb{R^2} \) と \( w \in \mathbb{R} \) はそれぞれ、\( (v, 0) = v, (0, w) = 0 \) のように \( \mathbb{R^3} \) に移すことができる。
  • 直和の用語を使うと、\( v \in \mathbb{R^2} \) と \( w \in \mathbb{R} \) はそれぞれ、\( (v, 0) = v \oplus 0, (0, w) = 0 \oplus w \) のように \( \mathbb{R^2} \oplus \mathbb{R} \) の元として考えられる。
  • 集合 \( \mathbb{R^2}\oplus\mathbb{R} = {v \oplus w | v \in \mathbb{R^2}, w \in \mathbb{R}} \)
  • \( (v \oplus w) + (v' \oplus w') = (v + w) \oplus (v' + w') \)
  • \( r(v \oplus w) = (rv \oplus rw) \) スカラー \( r \) だけは両方の世界で共有される

• \( \mathbb{R} \) 代数のテンソル積
  • \( \mathbb{R}[X] \) を \( X \) を変数に持つ多項式環と、\( \mathbb{R}[Y] \) を \( Y \) を変数に持つ多項式環を考える。この別世界があるものと考える。
  • これを同じ箱の中に入れたい場合、\( \mathbb{R}[X,Y] = \mathbb{R}[X] \otimes_{\mathbb{R}} \mathbb{R}[Y] \) と考えると自然
  • 元の \( f(X) \in \mathbb{R}[X] \) は \( f(X) \otimes 1 \in \mathbb{R}[X] \otimes_{\mathbb{R}} \mathbb{R}[Y] \)
  • 元の \( g(X) \in \mathbb{R}[Y] \) は \( 1 \otimes g(Y) \in \mathbb{R}[X] \otimes_{\mathbb{R}} \mathbb{R}[Y] \)
  • 両方の世界で計算をしたいので、下記が成り立ってほしい（以下の条件は双線形写像と呼ばれる）
    • \( (f(X) \otimes g(X)) \cdot (f'(X) \otimes g'(Y)) = (f(X) f'(X)) \otimes (g(Y) g(Y)) \)。\( \cdot \) は \( \mathbb{R}[X] \otimes_{\mathbb{R}} \) 同士の積。それぞれの世界での積が適用される。
    • \( (f(X) + f'(X)) \times g(Y) = f(X) \otimes g(Y) + f'(X) \otimes g(Y) \)
    • \( (rf(X)) \times g(Y) = r (f(X) \otimes g(Y)) = f(X) \otimes (r g(Y)) \)
  • 環の直積と \( \mathbb{R} \) のテンソル積では環準同系ではないので異なる
  • \( \mathbb{R}[X] \otimes_{\mathbb{R}} \mathbb{R}(Y) = \lbrace \sum_{i=1}^{N} f_i(X) \otimes g_i(Y) | f_i(X) \in \mathbb{R}[X], g_i(Y) \in \mathbb{R}[Y] \rbrace \)

• ベクトル空間のテンソル積
  • \( V, W \) をベクトル空間、\( V \) の基底が \( \lbrace v_1, \cdots, v_n \rbrace \), \( W \) の基底が \( \lbrace w_1, \cdots, w_m \rbrace \) とする。\( V \otimes_K W \) を \( \lbrace v_i \otimes w_j \rbrace\ (1 \le i \le n, 1 \le j \le m) \) を「形式的に」基底とする \( mn \) 次元ベクトルとする。
  • この時、\( - \otimes -: V \times W \rightarrow V \otimes_K W \) を \( v \otimes w = \sum_1^n \sum_1^m a_i b_j v_i \otimes w_j \) で定義する。
  • この時、\( (V \times W, - \otimes -) \) は \( V, W \) のテンソル積である。
  • ベクトル空間の線形写像のテンソル積
  • 写像 \( f: V \rightarrow V, g: W \rightarrow W \) について、\( f \otimes g \) を \( (f \otimes g)(v \otimes w) = f(v) \otimes g(w) \) で定義する。

ベクトル空間のテンソルの三表記とテンソル積の行列表現 †

• テンソル積の要素には以下の 3 つ（実際よく使うのは 2 つ）を意識することが重要
  • 1. 数学的な意味でのテンソル積。基底の総和として表現されるもの。
  • 2. 工学的な要請から「フラット化」されたテンソル積。多次元のテンソル積を一次元のベクトルに展開したもの。
  • 3. 2 階テンソルを行列のように表したもの（これをイメージしてもあまり意味がないが、これをイメージしても意味がないということを納得することは大切）

• 数学的な意味でのテンソル積
  • \( V \) を \( R^2 \)、\( W \) を \( R^3 \) とする。ここで、基底 \( e_{V0}, e_{V1} \in V, e_{W0}, e_{W1}, e_{W2} \in W \) とする。テンソル積 \( (V \times W, \otimes) \) の基底は \( e_{V0} \otimes e_{W0}, e_{V0} \otimes e_{W1}, e_{V0} \otimes e_{W2}, e_{V1} \otimes e_{W0}, e_{V1} \otimes e_{W1}, e_{V1} \otimes e_{W2} \) である。
  • ここで数学的な意味でのテンソル積は、\( a \otimes b = \sum_{ij} a_i b_j e_{Vi} \otimes e_{Wj} \) である。
  • 具体: \( a = \begin{pmatrix} -1 \\ 2 \\ \end{pmatrix} \in V, b = \begin{pmatrix} 3 \\ 4 \\ 5 \\ \end{pmatrix} \in W \)、\( V \) の基底を \( e_{V0} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ \end{pmatrix}, e_{V1} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ \end{pmatrix}, e_{V2} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ \end{pmatrix} \)、\( W \) の基底を \( e_{W0} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ \end{pmatrix}, e_{V1} = \begin{pmatrix} 0 \\ 1 \\ 0 \\ \end{pmatrix} \) とする。この時、\( a \otimes b = -3 e_{V0} \otimes e_{W0} -4 e_{V0} \otimes e_{W1} -5 e_{V0} \otimes e_{W2} + 6 e_{V1} \otimes e_{W0} + 8 e_{V1} \otimes e_{W1} + 10 e_{V1} \otimes e_{W2} \)

• 工学的な要請から「フラット化」されたテンソル積
  • \( V \) を \( R^2 \)、\( W \) を \( R^3 \) とする。
  • ここで「フラット化」されたテンソル積は、\( a \otimes b = \begin{pmatrix} a_0 b_0 \\ a_0 b_1 \\ a_0 b_2 \\ a_1 b_0 \\ a_1 b_1 \\ a_1 b_2 \\ \end{pmatrix} \) である。ベクトルの要素の順序は、[右の添字, 左の添字] のリストの辞書順序が早い方から上から埋めていく。
  • 具体: \( a = \begin{pmatrix} -1 \\ 2 \\ \end{pmatrix} \in V, b = \begin{pmatrix} 3 \\ 4 \\ 5 \\ \end{pmatrix} \in W \) とすると、\( a \otimes b = \begin{pmatrix} -3 \\ -4 \\ -5 \\ 6 \\ 8 \\ 10 \\ \end{pmatrix} \)
    • 「2 階テンソルを行列のように表したもの」では、フラット化をせず、\( a \otimes b = \begin{pmatrix} -3 & -4 & -5 \\ 6 & 8 & 10 \\ \end{pmatrix} \) のような表記をすることも可能といえば可能だが、このような表記に対して線形写像を考えて行列演算の形式に落とし込むのは厳しいし、何より多次元拡張性がないので、このような表記は考えない。

• 「フラット化」されたテンソル積の行列表現
  • ここで、量子コンピュータは工学であるので、フラット化された演算を考えることとする。
  • \( V = R^2 \) とその基底 \( e_{V0}, e_{V1} \)、\( W = R^3 \) とその基底 \( e_{V0}, e_{V1}, e_{V2} \) を考える。
  • テンソル積 \( V \otimes W \) もまたベクトル空間となり、テンソル積の空間に閉じた線形写像 \( f: V \otimes W \rightarrow V \otimes W \) を考える。線形写像は一般に、それぞれの基底 \( i, j \) について、\( f(e_{Vi} \otimes e_{Wj}) = \sum_{k, l} T_{ij, kl} e_{Vk} \otimes e_{Wl} \) における \( T_{ij, kl} \) で必要十分に特徴づけることができる。
  • ここで、\( a \in V, b \in W \) について、\( f(a \otimes b) = \begin{pmatrix} T_{00,00} & T_{00,01} & T_{00,10} & T_{00,11} \\ T_{01,00} & T_{01,01} & T_{01,10} & T_{01,11} \\ T_{10,00} & T_{10,01} & T_{10,10} & T_{10,11} \\ T_{11,00} & T_{11,01} & T_{11,10} & T_{11,11} \end{pmatrix} \) と行列を辞書順に埋めた形になる（参考までに。証明しなくてもよい）
  • 一方、\( f \) の具体例として、\( V, W \) で定義される行列 \( A \in V^2, B \in W^2 \) を考え、\( f: a \otimes b \rightarrow (A a) \otimes (B b) \) となるような \( f \) の行列表現を \( A \otimes B \) と定義する。つまり、\( (A \otimes B)(a \otimes b) = (Aa) \otimes (Bb) \)である。
    • ここで、\( a \otimes b \) が「フラット化された」テンソル積だとすると、\( (A a) \otimes (B b) = M a \otimes b \) となるような \( M \) を具体的に構成することが可能である。これは、\( (A \otimes B)(e_{Ai} \otimes e_{Bj}) = \sum_{k, l} A_{ki} B_{lj} e_{Vi} e_{Wj} \) より（詳しく追わなくていい）、\( A \otimes B = \begin{pmatrix} A_{00} B & A_{01} B \\ A_{10} B & A_{11} B \\ \end{pmatrix} \) と表記可能である（重要！）

• 計算演習
  • \( \begin{align*} A &= \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \\ a &= \begin{pmatrix} -1 \\ 2 \end{pmatrix}, \quad b = \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} \end{align*} \)
  • これに対して、\( (A \otimes B)(a \otimes b) \) を 2 つの方法で計算する。
  • 先に \( (A \otimes B)(a \otimes b) = (A a) \otimes (B b) \) を計算したパターン
    • \( \begin{align*} Aa &= \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} -1 \\ 2 \end{pmatrix} \\ &= \begin{pmatrix} 1(-1) + 2(2) \\ 3(-1) + 4(2) \end{pmatrix} \\ &= \begin{pmatrix} 3 \\ 5 \end{pmatrix} \\ Bb &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} \\ &= \begin{pmatrix} 3 \\ 8 \\ 5 \end{pmatrix} \end{align*} \)
    • \( (A \otimes B)(a \otimes b) = (A a) \otimes (B b) = \begin{pmatrix} 3 \\ 5 \end{pmatrix} \otimes \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} = \begin{pmatrix} 9 \\ 24 \\ 15 \\ 15 \\ 40 \\ 25 \end{pmatrix} \)

• 先に \( A \otimes B \) を計算したパターン（フラット化されたテンソル積の表記での線形変換の合成）
  • \( \begin{align*} A \otimes B &= \begin{pmatrix} 1 \cdot B & 2 \cdot B \\ 3 \cdot B & 4 \cdot B \end{pmatrix} \\ &= \begin{pmatrix} 1 \cdot \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} & 2 \cdot \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \\ 3 \cdot \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} & 4 \cdot \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{pmatrix} \\ &= \begin{pmatrix} 1 & 0 & 0 & 2 & 0 & 0 \\ 0 & 2 & 0 & 0 & 4 & 0 \\ 0 & 0 & 1 & 0 & 0 & 2 \\ 3 & 0 & 0 & 4 & 0 & 0 \\ 0 & 6 & 0 & 0 & 8 & 0 \\ 0 & 0 & 3 & 0 & 0 & 4 \end{pmatrix} \end{align*} \)
  • \( \begin{align*} a \otimes b &= \begin{pmatrix} -1 \cdot \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} \\ 2 \cdot \begin{pmatrix} 3 \\ 4 \\ 5 \end{pmatrix} \end{pmatrix} \\ &= \begin{pmatrix} -3 \\ -4 \\ -5 \\ 6 \\ 8 \\ 10 \end{pmatrix} \end{align*} \)
  • \( (A \otimes B)(a \otimes b) = \begin{pmatrix} 9 \\ 24 \\ 15 \\ 15 \\ 40 \\ 25 \end{pmatrix} \)

ゲート型 †

• 2^n の論理符号を並列で扱うような説明をされがちだが、ほとんどの有用そうなアルゴリズムはどちらかというとアナログな計算をしている
  • なので、計算誤差の蓄積で死にがち
• qubits の冪集合は実数値である位相を保持するメモリである。観測すると、|sin θ| の確率で 1, 1-|sin θ| の確率で 0 が出る
  • 量子もつれによって、qubit 同士に拘束条件を加えることで、qubits の冪集合の確率分布を操作する
  • 例: 00: 0度、01: 30度, 10: 0度, 11: 30度 ならば、観測すると 01, 11 だけが 50% ずつの確率で出現する
• メンタルモデルとしては https://www.youtube.com/watch?v=_b_yEgZh3BE&ab_channel=QuantumTokyo を見ておくと良さそう（グローバーのアルゴリズムの説明としては不適切なので、そこを期待して見てはいけない）

基本 †

定義 †

• \( \ket{i} \) は \( i \) 要素目だけ 1 でほかが 0 の縦ベクトル
  • \( \ket{0} = \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix} \) (|0>)
  • \( \ket{0} = \begin{pmatrix} 0 \\ 1 \\ \end{pmatrix} \) (|1>)
  • \( \ket{10_2} = \ket{2_{10}} = (0, 0, 1, 0) \) (下付きの文字は基数。|14_10> = |1110_2>、自明な場合は省略される)
• \( \bra{i} = \ket{i}^* \)、ket の共役転置
  • なので、\( \bra{i} \ket{j} \) は i 行 j 列の要素だけ 1 でほかが 0 の行列
  • なので、\( \ket{i} \bra{j} \) は i = j なら 1, そうでなければ 0
• \( \ket{10_2} = \ket{1_2} \otimes \ket{0_2} \) のように分解できる。教科書によっては \( \ket{\psi} \) 間の直積を全部 \( \otimes \) でつなぐのが面倒になって、\( \otimes \) を省略するようなものもよく見られる。心の目で \( \otimes \) が見えるようになるまでは明示して勉強したほうがいい。

単一量子ビット・量子ゲート †

• 量子ビット \( \ket{\psi} = \alpha \ket{0} + \beta \ket{1} \) where \( |\alpha|^2 + |\beta|^2 = 1, \alpha, \beta \in \mathbb{C} \)。
  • 量子ビットを「観測」すると、壊れて \( |\alpha|^2 \) の確率で 0 が、\( |\beta|^2 \) の確率で 1 が出力される。
• 演算子
  • 例えば演算子 \( \bra{0}\ket{1} \) は量子ビット \( \ket{\psi} \) に作用し、\( \ket{\psi} = \alpha \ket{0} + \beta \ket{1} \) の \( \ket{1} \) の係数 \( \beta \) を使って \( \beta \ket{0} \) を出力する。つまり、\( \bra{0}\ket{1} \ket{\psi} = \beta \ket{0} \)
• 量子ゲートは、演算子であって、対応する量子ビットへの操作が物理的に実現可能なもの
  • 逆操作が存在し、量子ビットから量子ビットへ移すようなものが量子ゲートであるという定義
  • 具体的には、ユニタリ行列であれば量子ゲート（有名なゲートとして X, Y, Z, H などがある）
  • 逆操作はエルミート共役
  • 演算子には、\( \bra{0}\ket{0}, \bra{0}\ket{1}, \bra{1}\ket{0}, \bra{1}\ket{1} \) があったが、これは重ね合わせられる。単一量子ビットに作用する量子ゲートは、一般に \( Z = \begin{bmatrix} \bra{0}\ket{0} & \bra{0}\ket{1} \\ \bra{1}\ket{0} & \bra{1}\ket{1} \\ \end{bmatrix} \) と表記され、状態ベクトル表記された \( \ket{\psi} \) を与えて、\( Z \ket{\psi} \) としてゲートの作用先を計算することができる。

複数量子ビット・量子ゲート †

• \( n \) 個の量子ビットを並べた場合、複数量子ビットは \( 2^n \) 個の複素数 \( c_i\ (\sum_i^{2^n - 1} |c_i|^2 = 1) \) で特徴づけられる。
  • 例えば \( n=3 \) では、\( \ket{\psi} = \sum_{i, j, k \in 2^3} C_{ijk} \ket{ijk} = (c_0, c_1, c_2, c_3, c_4, c_5, c_6, c_7)^T \) と表現され、縦の状態ベクトルとして表記される。
• 定義
  • ket 表記は結合的: \( \ket{011_2} = \ket{01_2} \otimes \ket{1_2} = \ket{0_2} \otimes \ket{1_2} \otimes \ket{1_2}= \ket{3_{10}} \)
  • \( a \otimes b \in \mathbb{C} \otimes \mathbb{C} \) はテンソル積。\( a \otimes b = \begin{pmatrix} a_0 b \\ a_1 b \\ \end{pmatrix} \)
  • \( A \otimes B: \mathbb{C} \otimes \mathbb{C} \rightarrow \mathbb{C} \otimes \mathbb{C} \) はテンソル積の線形変換の行列表記。\( (A \otimes B) a \otimes b = (A a) \otimes (B b) \) で定義される。\( a \otimes b \) をフラットなベクトル表記した場合、\( A \otimes B = \begin{pmatrix} a_{00} B & a_{01} B \\ a_{10} B & a_{11} B \\ \end{pmatrix} \) と書き下すことができる（重要公式）
  • \( (U_0 \otimes U_1)\ket{a b} = (U_0 \otimes U_1)(\ket{a} \otimes \ket{b}) = (U_0 \ket{a}) \otimes (U_1 \ket{b}) \) (テンソル積の双線型性の定義より)
• 量子ビットは右から \( 0 \) 番目、\( 1 \) 番目と読む
• 「右から \( i \) 番目の量子ビットに作用させる量子ゲート」を \( Z_i \in \mathbb{C}^{2 \times 2} \) のように表記する。
  • 2 量子ビットの \( \ket{\psi} = \ket{01} = \ket{0} \otimes \ket{1} \) に右から \( 0 \) 番目の量子ビットに作用する量子ゲート \( Z_i \) を適用すると、作用後は \( \ket{0} \otimes (Z_0 \ket{1}) \) のように、該当する演算部分にのみ作用する。
  • 重要: \( Z_0 \) は \( \ket{01} \) 全体にかけるための行列ではなく、あくまで 0 ビット目の \( \ket{1} \) に局所的にかかるものである。
    • \( Z_0 \) を 0 ビット目に作用させる演算を \( \ket{0} \otimes (Z_0 \ket{1}) \) と同値な、\( \ket{01} \) 全体にかけるユニタリ行列を \( U_{Z_0} \) を考える。つまり、\( U_{Z_0} = \ket{0} \otimes (Z_0 \ket{1}) \) となるような \( U_{Z_0} \in \mathbb{C}^{2^2 \times 2^2} \) を考える。
    • これは、\( U_{Z_0} = I \otimes Z_0 \) で与えられ (ただし \( I \in \mathbb{C}^{2 \times 2} \) は単位行列)、具体的な表記はフラット化されたテンソル積の表記の行列の合成にしたがう。なぜかと言うと \( (I \otimes Z_0) (\ket{0} \otimes \ket{1}) = (I \ket{0}) \otimes (Z_0 \ket{1}) \) (テンソルの計算規則より) \( = \ket{0} \otimes (Z_0 \ket{1}) \)
    • 一般に、\( Z_i \) を \( n \) 量子ビットの状態ベクトル全体にかかるような行列表記することが一般にできる。これは \( I \otimes \cdots \otimes Z_i \otimes I \otimes \cdots \otimes I \) という線形変換を、テンソル積のフラット化された表記の行列の合成にしたがい構成することがすることで、長さ \( 2^n \) の縦ベクトルにフラット化された量子ベクトルに対する \( \mathbb{C}^{2^n \times 2^n} \) 行列が得られる。

• 「右から \( i \) 番目の量子ビットを観測」する場合、そこだけをくくりだした状態にして、その量子ビットがどちらの状態になるかを判定し、その後そうでなかった項を削除して状態ベクトルの二乗和が 1 になるように定数倍を調整する。
  • 例: \( \sqrt{2}/4 \ket{00} + \sqrt{3}/4 \ket{01} + \sqrt{5}/4 \ket{10} + \sqrt{6}/4 \ket{11} \) の \( 0 \) ビット目を観測
    • \( (\sqrt{2}/4 \ket{0} + \sqrt{5}/4 \ket{1}) \otimes \ket{0} + (\sqrt{3}/4 \ket{0} + \sqrt{6}/4 \ket{1}) \otimes \ket{1} \) なので、\( 0 \) は \( (\sqrt{2}/4)^2 + (\sqrt{5}/4)^2 \), \( 1 \) は \( ( \sqrt{3} / 4)^2 + (\sqrt{6}/4) ^ 2 \) の確率で出力される。
    • \( 0 \) が出力された場合、\( \ket{1} = 0 \) を代入した後に量子条件を満たすように変更する。\( (\sqrt{2}/4 \ket{0} + \sqrt{5}/4 \ket{1}) \otimes \ket{0} \) と \( 0 \) ビット目が \( 0 \) のものだけを取り出したが、これでは係数が合わず量子ビットとして成立していないので、\( 4/\sqrt{7} \) をかけて補正する。すると、\( 4\sqrt{7}(\sqrt{2}/4 \ket{0} + \sqrt{5}/4 \ket{1}) \otimes \ket{0} = \sqrt{2}/\sqrt{7} \ket{00} + \sqrt{5}/\sqrt{7} \ket{10} \) となり、正しい量子ビットになる。また、0 ビット目の量子ビットが 0 で確定していることがわかる。
• 量子もつれ
  • \( 1/\sqrt{2} \ket{0} \otimes \ket{0} + 1/\sqrt{2} \ket{1} \otimes \ket{1} \) を考えると、0 ビット目が 0 と観測されれば 1 ビット目は必ず 0 だし、0 ビット目が 1 と観測されれば 1 ビット目は必ず 1 になるということがわかる。これを量子もつれといい、量子テレポーテーションを実現できる。

頻出ゲート †

Hadamard (アダマール) ゲート †

• H で表される 1 量子ゲート
• 対象の量子ビットに対して行列 \( H = 1/\sqrt{2} \begin{pmatrix} 1&1\\1&-1\\ \end{pmatrix} \) をかける。

• 計算練習の意味も兼ねて、式変形は非常に説明的にしています。
• 例1　(アダマールテストの第一段階)
  • \( \ket{0} \otimes \ket{\psi} \) の右から 1 ビット目 (0-indexed, 要するに \( \ket{0} \)）にかける
  • \( \begin{align*} (H \otimes I) (\ket{0} \otimes \ket{\psi}) \\ &= \left(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}\right) \otimes \ket{\psi} \\ &= \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} \otimes \ket{\psi} \\ &= \left(\frac{1}{\sqrt{2}} \ket{0} + \frac{1}{\sqrt{2}} \ket{1}\right) \otimes \ket{\psi} \\ &= \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} + \frac{1}{\sqrt{2}} \ket{1} \otimes \ket{\psi} \\ &= \frac{1}{\sqrt{2}} \left(\ket{0} \otimes \ket{\psi} + \ket{1} \otimes \ket{\psi}\right) \end{align*} \)
• 例2　(アダマールテストの第三段階)
  • \( \frac{1}{\sqrt{2}} (\ket{0} \otimes \ket{\psi} + \ket{1} \otimes (U\ket{\psi})) \) の右から 1 ビット目 (0-indexed) にかける
  • この時、全てのテンソル積の項（つまり、\( \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} \) と \( \frac{1}{\sqrt{2}} \ket{1} \otimes (U\ket{\psi})) \) の両方）の右から 1 ビット目 (0-indexed) に H をかけることになることに注意
  • \( \begin{align*} &(H \otimes I) \left(\frac{1}{\sqrt{2}} (\ket{0} \otimes \ket{\psi} + \ket{1} \otimes (U\ket{\psi}))\right) \\ &= (H \otimes I) \left(\frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi}\right) + (H \otimes I)\left(\frac{1}{\sqrt{2}} \ket{1} \otimes (U\ket{\psi})\right) \\ &= \left(H \frac{1}{\sqrt{2}} \ket{0}\right) \otimes \ket{\psi} + \left(H \frac{1}{\sqrt{2}} \ket{1}\right) \otimes (U\ket{\psi}) \\ &= \left(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \frac{1}{\sqrt{2}} \begin{pmatrix}1 \\ 0 \end{pmatrix}\right) \otimes \ket{\psi} + \left(\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \frac{1}{\sqrt{2}} \begin{pmatrix}0 \\ 1 \end{pmatrix}\right) \otimes (U\ket{\psi}) \\ &= \left(\frac{1}{2} \begin{pmatrix} 1 \\ 1 \end{pmatrix}\right) \otimes \ket{\psi} + \left(\frac{1}{2} \begin{pmatrix} 1 \\ -1 \end{pmatrix}\right) \otimes (U\ket{\psi}) \\ &= \frac{1}{2} (\ket{0} + \ket{1}) \otimes \ket{\psi} + \frac{1}{2} (\ket{0} - \ket{1}) \otimes (U\ket{\psi}) \\ &= \frac{1}{2} \ket{0} \otimes \ket{\psi} + \frac{1}{2} \ket{1} \otimes \ket{\psi} + \frac{1}{2} \ket{0} \otimes (U\ket{\psi}) - \frac{1}{2} \ket{1} \otimes (U\ket{\psi}) \\ &= \frac{1}{2} \ket{0} \otimes (I \ket{\psi}) + \frac{1}{2} \ket{1} \otimes (I \ket{\psi}) + \frac{1}{2} \ket{0} \otimes (U\ket{\psi}) - \frac{1}{2} \ket{1} \otimes (U\ket{\psi}) \\ &= \frac{1}{2} \ket{0} \otimes (I + U) \ket{\psi} + \frac{1}{2} \ket{1} \otimes (I - U) \ket{\psi} \end{align*} \)

制御ユニタリゲート †

• 2 入力 2 出力の量子ゲートで、制御ビットと標的ビットというものがある。「制御ビットが \( \ket{0} \) ならば標的ビットに変更なし、\( \ket{1} \) ならば標的ビットにユニタリ行列 \( U \) をかける」を行うもの（当然制御ビットも重ね合わせなので、変更のない世界線と行列がかけられた世界線は重なり合う）
  • ここですごいのは、「従来のコンピュータでは条件分岐は同時に実行することができないが、量子コンピュータでは状態の重ね合わせを利用して、条件分岐を同時並列的に実行することができる。」ところ！
  • 標的ビットは複数でもよい。
• 例1 (アダマールテストの第二段階)
  • \( \frac{1}{\sqrt{2}} \left(\ket{0} \otimes \ket{\psi} + \ket{1} \otimes \ket{\psi}\right) \) の右から 1 ビット目を制御ビットとして、右から 0 ビット目を標的ビットにする。
  • \( \frac{1}{\sqrt{2}} \left(\ket{0} \otimes \ket{\psi} + \ket{1} \otimes \ket{\psi}\right) \\ = \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} + \frac{1}{\sqrt{2}} \ket{1} \otimes \ket{\psi} \) において、1 項目 \( \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} \) の 1 ビット目は \( \ket{0} \) なので、0 ビット目に対しては何もしない。2 項目 \( \frac{1}{\sqrt{2}} \ket{1} \otimes \ket{\psi} \) の 1 ビット目は \( \ket{1} \) なので、0 ビット目に対して \( U \) をかける。
  • その結果、制御ユニタリゲートを通したあとの量子状態は \( \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{\psi} + \frac{1}{\sqrt{2}} \ket{1} \otimes (U \ket{\psi}) \\ = \frac{1}{\sqrt{2}} \left(\ket{0} \otimes \ket{\psi} + \ket{1} \otimes (U \ket{\psi}) \right) \) となる。

具体的なアルゴリズムに入っていく前に †

• 1 入力 1 出力などで少ない入出力変数のアルゴリズムを考え、裏側で量子アルゴリズムを使うというほうが現実的な使い方
  • 競技プログラミングのように「長さ \( 2^n \) の配列 \( a \) が与えられる」みたいなことをすると旨味が減ってしまう（入力の時点で指数オーダーになるので）
  • 少数の入力と少数の出力を扱うアルゴリズムを高速化するのに、裏側で \( n \) 量子ビットで \( 2^n \) 変数を扱える量子アルゴリズムを使うのが現実的。Shorのアルゴリズムなど、量子フーリエ変換を他のアルゴリズムの一部として用いるほうが実用的。
• 量子フーリエ変換を行うために必要なゲート操作の回数は、\( O(n^2) \) 回で、一方、古典コンピュータでフーリエ変換を行う高速フーリエ変換は、同じ計算を行うのに高速フーリエ変換で \( O(n 2^n) \) の計算量を必要とする。この意味で、量子フーリエ変換は、古典コンピュータで行う高速フーリエ変換に比べて「高速」と言える。
  • これは一見喜ばしいことに見えるが、落とし穴がある。フーリエ変換した結果は量子フーリエ変換後の状態の確率振幅として埋め込まれているが、この振幅を素直に読み出そうとすると、結局は \( O(2^n) \) 回の観測を繰り返さなくてはならない。さらに、そもそも入力を用意する方法も簡単ではない（素直にやると、それぞれの \( O(2^n) \) 個のビットを初期化しないといけないので、やはり指数関数的な時間がかかってしまう）。
  • 量子コンピュータから計算結果を取り出すには、計算、測定、計算、測定、、、と何度も繰り返し行う必要があります。このことを考慮すると、結局指数時間かかってしまうと考えられており、あまりフーリエ変換自体を量子コンピュータで行う意味はない。裏側で使うくらいがよい。

疑似乱数生成 †

• 回路図
  • H はアダマールゲート
  • M は観測

|0>   ---H---*---M---

• 入力: なし
• 出力: 0 もしくは 1 の真正乱数

• 前提: 古典の現状
  • 線形合同法、xorshift、メルセンヌツイスタのようなアルゴリズムが代表的であるが、基本的に初期値がバレると列が予想できるので、攻撃の対象になることがある
  • CPU 熱ノイズなどのハードウェア乱数生成があるが、理論的に「真正」な乱数ではない（遠くにいる攻撃者が予測できないという意味では、十分実用的には真正だけど…）

• これを理解するのはすごく簡単
  • \( \ket{0} \rightarrow H \ket{0} = 1/\sqrt{2} \begin{pmatrix} 1&1\\1&-1 \end{pmatrix} \begin{pmatrix} 1\\0 \end{pmatrix} = 1/\sqrt{2} \begin{pmatrix} 1\\1 \end{pmatrix} = 1/\sqrt{2}\ket{0} + 1/\sqrt{2}\ket{1} \) になるので、観測すると同確率で 0, 1 がでる。

• 量子乱数は、古典の物理系の持つ予測の難しさではなく、初期状態を攻撃者が把握していても現実的に未来に生成される乱数が、量子力学的理論的に、真正に、不可能
• リスク
  • それ本当に量子ですか？量子ハードウェアベンダーは信用できますか？
    • デバイスが内部で線形合同法を使っていることをどうやって見抜けますか？←これはベル不等式でなんとかして検証することはできそうではある
  • H ゲートの質が悪くて回転しすぎたりしませんか？

アダマールテスト †

• 回路図
  • H はアダマールゲート
  • U は 0 番目の量子ビットを制御ビットにして \( U \) をかけたりかけなかったりする制御ユニタリゲート
  • M は観測
  • |psi> は複数量子ビット (/ でそれを表している)

|0>   ---H---*---H---M---
|psi> -/-----U-----------

• できること1
  • 入力: ユニタリ行列 \( U \in \mathbb{C}^{2^n \times 2^n} \)（これを頑張って量子回路として表現できるものとする）
  • 出力: ユニタリ行列の固有ベクトルのうちどれか一つ
    • 固有ベクトルを「固有状態」ともいう。
    • 任意の初期ベクトルに対して、アダマールテストの出力をアダマールテストを何回も入力することを繰り返すと、ある一つの固有ベクトルへと収束する
    • 固有ベクトルは \( 2^n \) 個あるはずだけど一個だけ取得して何かうれしいのかはあまり納得できていない。古典では例えば二分法・逆反復法や MR^3 法によって、一部の固有ベクトルを計算するルーチンが DSTEBAZ + DSTEIN, DSTEGR で実装されているため、実際そういうことを工学的にしたい場面はあるんだろうけど、あまりピンと来ていない。
    • TODO 未証明。理由を理解していない
    • TODO 収束速度についての理論的な保証がわからない
    • TODO 固有ベクトルが量子回路上に埋め込まれるのはいいとして、それをどうやって具体的に取得してくるんだ？

• できること2
  • 入力: ユニタリ行列 \( U \in \mathbb{C}^{2^n \times 2^n} \)（これを頑張って量子回路として表現できるものとする）と、その固有ベクトルのうち 1 本 \( \psi \in \mathbb{C}^{2^n \times 2^n} \)（これをどこかで頑張って探してきたものとする）
    • 「固有ベクトルのうち 1 本」は上の反復計算で構成可能
  • 出力: 固有ベクトルの固有値
    • TODO 収束速度についての理論的な保証を納得していない
  • \( \ket{\psi} \) を制御 \( U \) 演算に通すと、制御ビットの \( \ket{1} \) 側の位相が回転して、その回転量に固有値の情報が乗る（量子回路上に埋め込まれた情報を確率として得るために、もう一回 \( H \) 演算を通す）
  • 古典だと例えば MR^3 法で \( O(2^n) \)、量子では新しい反復アルゴリズムが与えられている

• できること3
  • 入力: ユニタリ行列 \( U \in \mathbb{C}^{2^n \times 2^n} \)（これを頑張って量子回路として表現できるものとする）と、量子ビットとして表現可能な複素ベクトル 1 本 \( \psi \in \mathbb{C}^{2^n \times 2^n} \)（任意に設定可能）
  • 出力: \( \rm{Re} (\bra{\psi} U \ket{\psi}) = \rm{Re} (\begin{pmatrix} \psi_0 & \cdots & \psi_{2^n-1} \end{pmatrix} \begin{pmatrix} U_{0, 0} & \cdots & U_{0, 2^n-1} \\ \vdots & \cdots & \vdots \\ U_{2^n-1, 0} & \cdots & U_{2^n-1, 2^n-1} \end{pmatrix} \begin{pmatrix} \psi_0 \\ \cdots \\ \psi_{2^n-1} \end{pmatrix}) \in \mathbb{R} \)
    • 元のアダマールテストでは \( \rm{Re} (\bra{\psi} U \ket{\psi}) \) しか取れないが、第一段階の \( H \) と第二段階の \( U \) の間に、制御量子ビットにかかる \( 1 \) 量子ゲート \( S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix} \) を挟むと \( \rm{Im} (\bra{\psi} U \ket{\psi}) \in \mathbb{R} \) も推定できるので、実質 \( \bra{\psi} U \ket{\psi} \in \mathbb{C} \) が計算できる。

      |0>   ---H--S-----*---H---M---
      |psi> -/----------U-----------

    • 古典だと普通に行列演算をすることで \( O(4^n) \) かかる

• 前提: 古典での現状
  • \( n \times n \) の対称密行列 \( A \) の固有値・固有ベクトルを計算する場合、まず行列 \( A \) を直交行列 \( Q \) により対称三重対角行列 \( T =Q^t A Q \) に変換し、\( T \) の固有値・固有ベクトルを求めるのが普通。なので、三重対角行列の固有値・固有ベクトルを求める方法が重要
  • ちなみに、固有値計算パートが高速になりすぎて、現状の律速はそこではないらしい。
    • Pentium（2.4 GHz）クラスターを用いて密行列の固有値問題を解く場合、MR^3 アルゴリズムを使用して三重対角行列の固有値と固有ベクトルを計算するのには 406 秒しかかからない。しかし、三重対角行列への変換には 9638 秒、逆変換には 2846 秒の時間が必要であることが報告されている。(P. Bientinesi, I. S. Dhillon, and R. A. van de Geijn. "A parallel eigensolver for dense symmetric matrices based on multiple relatively robust representations." SIAM Journal on Scientific Computing)

• 古典と比べて何がうれしいか？
  • \( 2^n \times 2^n \) のサイズの固有ベクトル・固有値を 1 つ見つける（正確には量子回路に埋め込む）のは、古典では MR^3 法などで \( O(2^n) \) 程度かかりそうだが、反復計算でもとまる
    • 固有値はまあわかるが、固有ベクトルについては収束速度やそもそもどうやって量子回路に埋め込まれたものを抜き出してくるのかは不明だけど。。
  • \( \bra{\psi} U \ket{\psi} \) が反復計算で求まる。収束速度はあまり納得できていないけど、古典の \( O(4^n) \) よりは圧倒的にマシそう。

CNOT ゲート †

• 制御ユニタリゲートの一種で、「制御ビットが \( \ket{0} \) ならば標的ビットに変更なし、\( \ket{1} \) ならば標的ビットの係数を入れ替える」。実はこれと 1 量子ビットに対するユニタリゲートを合わせると任意の制御ユニタリゲートを実現できる。Controlled-NOT ゲート。
  • 例: 制御ビットが \( \ket{0} \) (0 確定)、標的ビットが \( 1/\sqrt{5} \ket{0} + 2/\sqrt{5} \ket{1} \) → \( \ket{0}\otimes(1/\sqrt{5} \ket{0} + 2/\sqrt{5} \ket{1}) \)
• 例: 制御ビットが \( \ket{1} \) (1 確定)、標的ビットが \( 1/\sqrt{5} \ket{0} + 2/\sqrt{5} \ket{1} \) → \( \ket{0}\otimes(2/\sqrt{5} \ket{0} + 1/\sqrt{5} \ket{1}) \)
• 面白い例: 制御ビットが \( 1 / \sqrt{2} (\ket{0} + \ket{1}) \)、標的ビットが \( \ket{0}) \) (0 確定) → \( \ket{00} + \ket{11} \) でもつれる（理由: 制御ビットが 0 だった世界線では標的ビットは 0 になり、制御ビットが 1 だった世界線では標的ビットが反転して 1 になるから）
• CNOT \( \ket{00} \) = \( \ket{00} \), CNOT \( \ket{01} \) = \( \ket{01} \), CNOT \( \ket{10} \) = \( \ket{11} \), CNOT \( \ket{11} \) = \( \ket{10} \) より、CNOT = \( \begin{pmatrix} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&0&1 \\ 0&0&1&0 \\ \end{pmatrix} \)

グローバーのアルゴリズム †

• 「f: 2^n -> bool を入力し、f(x) = true となるような x を量子状態として全列挙する。ただし量子状態なので全列挙内容は見れず、一回の観測ではその一例しか得られない」
• イメージとしては 3-SAT ソルバの論理式を設計する部分がオラクル設計と同じという理解。だから概ね 3-SAT と相性が良さそうな問題は解けそう（例: グラフ、スケジューリング、数独）に見えるが、実際には論理式を表現すると誤差で死ぬらしい (2023)
• 勝手に量子ゲートで作れることが AND の OR だけだと考えてしまいそうだが、実はもっと自由度があるはずであることには注意
• ということを理解していると巷で言われているデータベース検索が容易というのもかなり語弊があって、データベースのフルスキャン後に量子回路の構造を決定しないといけない気がしていて、フルスキャンの時点で計算量が O(n) になるんですがそれは…という気持ちに

ショアのアルゴリズム †

• 素因数分解ならし O(n^3 log n), 高速乗算を使うともうちょっと早くなる
  • 2014 bit RSA だと、2000 万個 qubits があれば 7.44 時間くらいで解けそう、くらいの感じらしい https://zenn.dev/hk_ilohas/articles/shor_algorithm#fnref-131d-2

• 手順
  • N=15 を素因数分解したい
  • Nと互いに素な整数aをいい加減に見つける。これは簡単に見つかる（簡単に見つかるなら素因数分解が進むので）。今回はa=7とする。
  • ショアのアルゴリズムは、a^r=7^r=1 (mod 15) なる r を、観測された量子ビットの位相からランダムより高い確率で一例出力することができる（証明略、またランダムなので失敗することもあり何回も試行する必要があることに注意）。
  • 正しくない r ならば再試行
  • 奇数の r ならば再試行
  • 偶数の r を見つけることができれば a^r-1 mod N = (a^{r/2}-1)(a^{r/2}+1) = 0 mod N となる。
  • 例: r=4が出力された場合、7^4=1 mod 15 なので、(7^2+1)(7^2-1)=0 mod 15, 50 * 48 = 0 (mod 15)
  • ここで現れた 50, 48 は何か素因数分解っぽくもあるが実際には素因数分解ではない。ここで、gcd(50, 15), gcd(48, 15) が N の素因数分解である可能性が高いことを示すことができる（証明略、どれくらいの確率？量子と関係ある？）
  • 今回、3, 5 が出力されていたので幸せだった。

• メモ
  • なお、rはショアのアルゴリズムを実行した結果として得られる量子ビットを観測した時の位相θが、数学的には有理数 p/q (q<15) として表される。量子の性質上、観測ごとに異なる実数が出力される可能性があることに注意。観測したθを有理数としてp/q (q<15) と表したときの q がショアのアルゴリズムの出力 (の一例) r である。
  • 位相は実数値だけど有理数は有理数だから、N がでかくなると量子計算の位相推定誤差で有理数を推定することが難しくなりませんか？
  • 既約分数であるという制約はありますか？なくて p/q (q<N/2) だった場合、一回の観測で r は複数出ませんか？

• 感想
  • N がデカいと誤差で実数から有理数の変換が大変そうで r を見つけるのが難しそう