2000年度総会特別講演
講演者：上坂吉則氏（理科大）
認識・学習や人工知能などの分野で数理モデルやアルゴリズムを考案するとしばしば計算の爆発に出会うことがある．これを回避するのにアルゴリズムを近似的に改良する努力が払われていることはよく知られている．回避のもう一つの方法は計算機構そのものをチューリングマシンの呪縛から解き放すことである．実際，計算機構の物理的リソースを古典から量子の世界に移すことによって，量子コンピュータはチューリングマシンの計算の複雑さの壁を破ることに理論上成功している．しかしながら，そのハードウェアを現実のものとするには多くの困難が伴うようである．
ここでは量子計算のからくりを生かしながら，古典の物理リソースによって同様のことを実現しようという試みについて紹介する．
はじめに量子計算のエッセンスが線形性にあることを簡単に紹介し，このトリックを線形受動回路に埋め込むと，チューリングマシンと同等の計算能力と量子コンピュータと同等以上の計算速度を持つことができること，さらにこの世界ではNP問題がP問題に落ちることを示す．しかしながら，この結果には周波数爆発と呼ばれる難点があり，これを回避する試みについても二三触れることにする．
この講演では，海のものとも山のものともわからない研究途上の話題をたたき台とするという往年のAVIRGの精神に沿うこととし，一つの試みを紹介して諸賢の明晰・活発な議論に期待することとしたい．
《参考文献》
[1] 須鎗弘樹，上坂吉則 ，組合せ最適化問題の目的関数を計算する量子回路の一構成法，電子情報通信学会論文誌，Vol.J81-A, No.12, pp.1722-1727，1998．
[2] 上坂吉則，量子コンピュータの基礎数理，コロナ社，230pp，2000．
[3] 上坂吉則 ，新しい計算機構の提案ー線形回路による超並列計算ー，情報処理学会，新しい計算パラダイムシンポジウム，pp.43-50，2000．