量子論理回路の最適化に関する研究

点击翻译按钮获取中文摘要

量子コンピュータの物理的実現には、多くの困難が存在する。例えば、量子もつれ合いを保つことができる時間が短いことや、複雑な量子操作を行なうことが難しいこと等が挙げられる。これらの問題の解決において、量子回路のサイズは非常に重要である。本研究では、量子回路サイズの新たな評価方法について検討する。特に、C-NOTゲートに着目し、量子回路計算量とC-NOTゲート数の関係について、幾つかの定理を示した。現在、量子コンピュータの物理的実現について盛んに研究が行われているが、その実現には多くの困難が伴う。そのうちの一つとして、量子コンピュータは量子重ね合わせ状態という量子力学的にデリケートな状態を取ることが挙げられる。そのため、サイズの大きな量子コンピュータの複雑な量子重ね合わせ状態を長時間維持することは非常に困難となるそれに加えて、量子コンピュータは扱えるビット数が大きくなるほど実現が困難となる。すなわち、同じアルゴリズムを実行する場合、量子コンピュータにおいては、特に、時間計算量および領域計算量を縮小することが本質的に重要な問題となる。そこで、本研究では、量子回路のゲート数とビット数の関係についても考察した。具体的には、あるアルゴリズムを実行する量子回路に対して、それに補助量子ビットを付加し、回路を再構成することで、ゲートの総数をさらに縮小できるかどうかを検証した。我々は古典コンピュータを用いてアルゴリズムを実行するときに、計算時間の短縮のために、計算の途中で、その計算結果の一部をメモリの別の場所に一時的に保管することをよく行う。量子コンピュータの回路設計においても、補助量子ビットはそのようなワークビットとしてたびたび用いられるが、そこで使われる補助量子ビットは厳密に定義されているわけではない。本研究では、どのような種類の補助量子ビットにゲート数縮小の効果があるのかを検証するために、補助量子ビットの分類と定式化を行った。