位数発見問題（いすうはっけんもんだい、）は、数学の問題。

ある整数 について、を満たす最小の正の整数を位数という。

を表現するビット数をとすると、 の時間計算量で位数を発見することのできる古典アルゴリズムは存在しない。一方量子アルゴリズムを用いるとの時間計算量で求めることができる。

また、冪剰余は位数発見問題のうちの一つであり、暗号理論の分野で広く使用されている。

ショアのアルゴリズムのサブルーチンには、位数発見の操作を要する。

脚注

外部リンク

An exact quantum order finding algorithm and its applications -