位数発見問題
位数発見問題（いすうはっけんもんだい、英: Order finding problem ,Order finding problem）は、数学の問題[1][2]。
ある整数 x,N ∈ ℤ (x < N)について、xr ≡ 1 (mod N)を満たす最小の正の整数rを位数という。
Nを表現するビット数をL=logNとすると、 poly(L)の時間計算量で位数を発見することのできる古典アルゴリズムは存在しない。一方量子アルゴリズムを用いるとO(L3)の時間計算量で求めることができる。
また、冪剰余は位数発見問題のうちの一つであり、暗号理論の分野で広く使用されている[3]。
ショアのアルゴリズムのサブルーチンには、位数発見の操作を要する[4]。
脚注
[編集]- ^ 西村治道『基礎から学ぶ 量子計算: アルゴリズムと計算量理論』株式会社 オーム社、2022年11月18日、134頁。ISBN 978-4-274-22969-5。
- ^ 若山 正人. “光とゼータ関数の特殊値”. 東京理科大学理学部. 2024年10月5日閲覧。
- ^ 嶋田義皓『量子コンピューティング ―基本アルゴリズムから量子機械学習まで―』株式会社 オーム社、2020年11月9日、80頁。ISBN 978-4-274-22621-2。
- ^ 高橋康博. “https://www.rd.ntt/cs/event/openhouse/2008/quantum/doc/shor.pdf”. 日本電信通話 NTTコミュニケーション化学基礎研究所. 2024年10月5日閲覧。
外部リンク
[編集]- An exact quantum order finding algorithm and its applications - arXiv:2205.04240
- “Lecture 10: Order finding”. John Watrous, University of Calgary. 2024年10月5日閲覧。
- “Practical Quantum Algorithms for Order-Finding Problem”. MInf Project (Part 1) ,Report Master of Informatics, School of Informatics ,University of Edinburgh. 2024年10月5日閲覧。
 | この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。 |