代数幾何と量子計算で素数分解
- 具体的な課題として、素数p,qの積がMになるかどうかの判定問題を扱っている
- 自然数p,qを二進法で表すことで、{0,1}の二値制約のある変数のセットによって、満足すべき式を書き下している
- その変数セットを
とすると、それらに対して、新たに
という制約がある、と考えることで、
をイデアルの生成元とする
- また、制約多項式に登場する、
なる単項式については、
の組み合わせ的に取り扱うことにしている
- 制約式に現れる単項式の中に登場するすべてのペア
を
という制約として入れ込む
- このyとxとからなる制約式はいずれも、二項の式で、単項の差になっている。ここから求まるラジカル・イデアルも同様で、トーリックイデアルの特徴をもっている
- これに対して、グレブナー基底を計算してやることで、求める解が「理論的」には得られる
- グレブナー基底では、変数順序を入れて、掃き出し法を適用することにより、
の混合生成元のうち、
のみでできた「部分グレブナー基底（とそれに対応するイデアル）を求めることができるから
- しかしながら、この方式だと、追加変数 x の個数がどんどん増えてしまうので、このままやるのは得策ではない
- ちなみに、変数 x の個数に応じて量子計算機のビット数が増えてしまうのが、その理由
- どうするか。。。
- 制約多項式を「最適化問題的には同じ」だが、字数が低い多項式に変形する作戦を取る。これをNormal formを取る、という。Normal formを取るにあたり、適当な基底多項式を用いるが、このときグレブナー基底を用いることができる
- また、Normal formを取って、制約式が簡素になっても、変数 x の数が多ければ、量子ビット数負荷は変わらないが、グレブナー基底を参照することで、xの取り換えを行って、現れる x の個数を減らすことができる。特に、トーリックイデアルになっており、この取り換えが容易に進む
- 結局、トーリックイデアルの都合よさ、グレブナー基底の都合よさを用いて、制約を二次の項の差の式のセットに落とせて、しかも、追加した変数 x を含まない y のみの制約も判明し、最適化問題の解にたどり着く
- 実際には、問題設定をこのようにした後、量子回路埋め込み問題でさらに工夫をする必要がある模様だが、その点は、現在の興味の対象外
