代数幾何と量子計算で素数分解

www.nature.com
arxiv.org

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