ミニ研究集会「量子計算」の報告

科学研究費補助金の特定領域研究「新世代の計算限界」 の B03 班は、「量子論理回路の最適化に関する研究」という テーマで、電気通信大学情報通信工学科に所属する私と、 垂井淳先生、太田和夫先生、國廣昇先生をメンバーとして、 共同研究を進めております。

この B03 班では、去る ２００５年３月２６日（土）の１３：００ より、 電気通信大学総合研究棟８階８０７セミナー室で、 量子計算に関するミニ研究集会を開催致しました。 当日は、まず最初に、國廣昇先生 による、「近似を導入した加算剰余演算の成功確率の評価」と題 する講演が行なわれました[Kun]。 そして、その後に、 参加者全員によるフリーディスカッションを行いました。 講演は１６時頃に終了し、その後、１８時頃まで、 ディスカッションを行っておりました。 そもそも、このミニ研究集会を行った動機は、 講演を伺って勉強をしたいということもありましたが、 それに加えて、量子計算の最近の研究動向に関するディスカッションを 行いたいということでした。 その意味では、大変収穫の多い一日だったと思います。

まず、講演では、近似を導入した加算剰余演算の成功確率 について解説されました。Draperが提案した量子加算を構成要素として 加算剰余を構成する場合、その大部分の計算時間は、付加的に 加えられた量子フーリエ変換部であることが知られています。 この問題に対して、近似量子フーリエ変換を導入することにより、 計算時間が削減できると、Draperや、Beauregardにより、主張 されています。しかしながら、彼らは、厳密に評価を行なってい るわけではないそうです。そこで、本発表では、近似精度と加算剰余演算の成功 確率に関して、厳密な評価が提示されました。この評価を用いることにより、 加算剰余演算を構成要素として、Shorのアルゴリズムを構成した場合の、素因数分解の成功確率の評価を行なうことが可能となります。

当日の参加者は、講演者の國廣先生の他、特定領域 B03 班からは、 垂井先生と私が参加し、さらに、電通大大学院の博士課程の学生が１名参加しました。 また、本ミニ研究集会の告知をご覧になった（株）日立製作所システム開発研究所 の２名の研究員の方も参加されました。 年度末ということもあり、この６名でこじんまりと議論を行いましたが、 逆に、このくらいの規模ですと、フランクに質問ができますので、 講演の最中も、盛んに質問が出され、終始、インタラクティブな雰囲気の 研究集会となりました。

講演の本題に入る前には、現在のコンピュータでは、因数分解はどのくらい 高速に行なえるのか？ もし、因数分解を行なう量子コンピュータが実現できるとしても、 そのために莫大な資金が必要だとしたら、その資金を出す機関は 世界の何処にあるのか？ などの、一般的な話題についても、議論がありました。

一方、講演後のフリーデスカッションは、まさに、自由な討論会となりました。 まず、現在、プリンストン高等研究所に在籍する S. Aaronson が、彼の博士 学位論文の中で述べた、Shor のアルゴリズムの物理的実現可能性に関する懐疑論 [Aar1]について議論が行なわれました。 また、その同じ Aaronson が、最近発表した、物理的計算装置 による NP 完全問題の高速解法可能性に対する否定的見解 [Aar2]についても、若干、議論になりました。

そうした話の流れを受けて、さらには、 P = NP ? 問題解決に向けての展望についても、意見が交換されました。 例えば、最新の計算量理論の成果を勉強すると、 P = BPP が信じられるようになってくるとか、 P = NP ? 問題を直接考えるよりは、 NP = coNP ? 問題を考えた方が良いのではないか、 といった意見などが出されました。

そのような議論の影響もあってか、 今年度の B03 班の研究目標は、幾何学的手法を用いて、 量子論理回路のサイズの下界に関する研究を進めることに、 後日決定されました。 実は、今年になって、Neilsen によって、 以下のような定理が証明されています。

定理(Nielsen, 2005 [Nei]) G を SU(2ⁿ) 上の万能量子基底 とし、F を SU(2ⁿ) 上のある条件を満たす計量とするとき、 SU(2ⁿ) に属する任意の U に対して、以下が成り立つ。 d_F(I,U) ≦ m_G(U) ただし、d_F(I,U) は、F を計量とする可微分多様体上における n 量子ビット恒等変換 I と U との距離、 m_G(U) は、ユニタリ変換 U を実現する G を基底とする量子回路の最小サイズとする。

この定理を足がかりとして、 量子回路のサイズに関する強い下界を証明し、 （通常の）計算量理論に対して何らかの貢献を することができれば、 とても素晴らしいことだと考えております。 ただし、上記のような研究を進めるには、まずは、 特定のブール関数に対応する U について、 d_F(I,U) の強い下界を求めることや、 補助量子ビットが、回路計算量に及ぼす影響を 明らかにすることが必要になってきます。

さて、本題のミニ研究会に話を戻しますと、 当日、研究集会全体が終了したのは、結局、１８時過ぎのことでした。 議論は大変長時間に及びましたが、皆さん、非常に楽しい時間を 過ごすことができたとおっしゃっておられました。 その日の議論を通して、 量子計算の理論は、将来、どのような形で量子コンピュータが実現されるにせよ、 されないにせよ、計算量理論の一分野として、大変興味深い話題を提供し 続けてくれる分野であると、私自身、実感することができました。 今後も、適当な頻度で、量子計算に関するこのようなミニ研究集会を 開催して行きたいと考えております。

[Kun]

N. Kunihiro, ``Exact Analyses of Computational Time for Factoring in Quantum Computers'', IEICE Transactions on Fundamentals, Vol.E88-A, No.1, pp.105--111 (2005).

[Aar1]

S. Aaronson, ``Multilinear Formulas and Skepticism of Quantum Computing'', to appear in SIAM Journal of Computing (Also in STOC 2004, pp. 118-127, and quant-ph/0311039).

[Aar2]

S. Aaronson, ``NP-complete Problems and Physical Reality'', quant-ph/0502072, Feb. 2005.

[Nei]

M. A. Nielsen, ``A geometric approach to quantum circuit lower bounds'', quant-ph/0502070, Feb. 2005.

Back to Table of Contents Last modified: Thu Jul 21 08:15:11 JST 2005 modified/maintained by R.Uehara (uehara@jaist.ac.jp)