Shorのアルゴリズム、リターンズ

まえにShorのアルゴリズムは

Shorのアルゴリズムって、こういう感じ？
https://blog.goo.ne.jp/xmldtp/e/1f7778c7abb046cdf66f455441ea5782

にかいたけど、よく理解していないので
基礎から応用やトレンドまで学ぶ量子コンピューティング入門セミナー【Shorのアルゴリズム編】
https://liberal-arts-for-tech.connpass.com/event/135613/
を聞いてきた！ので内容メモメモ
（ただし、Shorのアルゴリズムについては、聞き入ってしまい、メモ取れなかった、
　ごめん！）

---

・自己紹介
　IPA採択されたよ！
　OpenQL

・量子アルゴリズム
　Grover
　量子テレポーテーション
　アダマール、位相推定、量子フーリエ変換
　Shor→きょうここ

・量子コンピューターを使う
・SymPy（しむぱい）でやってる
・ライブラリはそろってる

・量子計算の裏側：シュレーディンガー方程式
　→解：波動関数　→答え求められる：波になる→ユニタリ演算子

強味
・量子重ね合わせ状態：並列計算してるような・・・
　→測定してしまうと、一つの答えしか出ない
　→この状態をはじめに作る　N：量子ビットの数
　　　いまは２０　４９～７０くらいでスパコンを抜く
　　フィディリティ（エラー精度）が問題

・エンタングルメント
　２個以上あったとき、密に関連する。
　独立性がないほうが表現力上がる→応用例：量子テレポーテーション

・量子アルゴリズム
　波の性格を使う：確率振幅
　フィデリティ：９９．９％ならうまくいく（今７０％）

・3つの潮流
　（１）高精度の大規模量子コンピューター向け量子アルゴリズム
　（２）NISQ量子ー古典ハイブリッド
　　　VQE
　　　QAOA arXiv:1712.05771
　　　QCL：arXiv:1803.00745
　（３）すぷれましー：優位性
　　　人工的な無意味な問題の場合も

・Grover
　当たり判定：一つの状態を高確率で取り出す
　　マーキング→反転：ぴょんと出てくる

・テレポーテーション

・位相推定
　位相の差を知りたい→そのための回路：アダマールテスト
　　→位相を確率的に推定する
　　　　実部も虚部も出せる

・SWAPテスト
　コントロールユニタリーをコントロールSWAPゲートにすると、内積が出る

【おすすめの本】
量子情報工学
量子情報科学入門
量子コンピューターの基礎数理
量子アルゴリズム


・QPE（位相推定）
　固有値があると想定せよ（位相キックバック）
　固有値なので（スカラーになるので）前に出せる
　kitaevの位相推定：与えられたユニタリUの固有値を指数精度で計算できるアルゴリズム
　→固有ベクトルが入力
　→任意の量子状態にしたい：QPE

で、これが出てくれば、逆フーリエ変換で、元に戻せる
　離散フーリエ変換→量子フーリエ変換

Shorのアルゴリズム
・ユークリッドの互除法
　素因数を発見する→周期性を発見する問題に置き換える
　　位数を調べる（＝周期と同じ）余りが１になれば、周期性が出てくる

量子コンピューターは周期を求めるところだけ
そこは位相推定を使う