2017 旭硝子財団 助成研究発表会 要旨集

145/223

さらに効率的なシミュレーションが可能になると考えられる．そこで，正則グラフ上の量子ウォークに用途を限定したハードウェアシミュレータを開発した．FPGA 上に実装することで与えられたグラフに応じてハードウェア構成を変更することができる．これを利用して省面積化を目指した．具体的には，与えられたグラフに応じてウォーカーの遷移先を布線論理で実装することで，メモリを大幅に削減できた．また，実験により再構成を用いないハードウェアと比較して効率性を確認した． (2) 量子計算モデルの能力の解析，および量子アルゴリズムの開発 シミュレータ開発の研究に加え，量子アルゴリズムの開発，および量子計算モデルの解析も行った．まず初めに，メモリとしてカウンタを備えた量子計算モデルである量子カウンタオートマトンについて，決定性計算のもとでの能力の解析を行った．具体的には，ある種のプロミス付き問題に対して，量子カウンタオートマトンでは誤りなく解くことができるが，古典決定性カウンタオートマトンでは解くことができないことを示した．この結果は，量子カウンタオートマトンと古典カウンタオートマトンの間に能力の差があることを示すものである．さらに，量子アルゴリズムの設計手法を逆に古典アルゴリズムに応用することで，古典オートマトンに関する新しい結果を得た．具体的には，確率ブラインドカウンタオートマトンおよび決定性（非ブラインド）カウンタオートマトンで認識できるが，決定性ブラインドカウンタオートマトンでは認識できない言語が存在することを示した．この目的のために言語EQ*を確率ブラインドカウンタオートマトンで認識するためのアルゴリズムを開発した．先行研究では，そのようなアルゴリズムは存在しないと予測されていたものであり[6]，この予測を覆したという意味でも興味深い結果と言える． 次に，量子計算モデルに非常に近い性質を持つアフィンオートマトンについて，その能力の解析を行った．アフィンオートマトンは量子オートマトンに比べて解析しやすいモデルであると同時に，量子オートマトンのよい特徴付けを行えることが知られている[2]．このため，アフィンオートマトンを解析することで量子オートマトンの持つ性質を解明できることが期待される．本研究ではアフィン有限オートマトンにカウンタを付加したアフィンカウンタオートマトンについて，決定性計算のもとでの能力を解析し，アフィンカウンタオートマトンが優れていることを証明した． 3. 今後の展開 量子アルゴリズムシミュレータの高速化については一通りの目標を達成したため，今後はそれを応用した新しい量子アルゴリズムの開発へと研究をつなげる予定である．NP完全問題のような困難な問題に対しては，量子コンピュータを用いても効率的な解法は存在しないと予想されている．そのような問題に対しては，発見的手法を用いたアプローチが取られることが多いが，量子アルゴリズムでも同様に発見的手法を用いたアプローチをとることにより，状況によっては高速に問題を解くことができる可能性がある．しかしながら，量子発見的アルゴリズムの開発にはアルゴリズムのシミュレーションが不可欠であり，本研究で開発した高速なシミュレータを有効活用できると考えている． 参考文献 [1] M. Aminian, M. Saeedi, M. Zamani, and M. Sedighi, "FPGA-based circuit model emulation of quantum algorithms," IEEE Computer Society Annual Symposium on VLSI, ISVLSI'08, pp.399-404, April 2008. [2] A. Diaz-Caro and Abuzer Yakaryilmaz, "Affine Computation and Affine Automaton," Proceedings of 11th International Computer Science Symposium in Russia (CSR 2016), LNCS 9691, Springer, pp. 146-160, 2016. [3] M. Fujishima, "Fpga-based high-speed emulator of quantum computing," Proceedings of IEEE International Conference on Field-Programmable Technology, FPT 2003, pp.21-26, December 2003. [4] A. Khalid, Z. Zilic, and K. Radecka, "FPGA emulation of quantum circuits," Proceedings of IEEE International Conference on Computer Design: VLSI in Computers and Processors, ICCD 2004, pp.310-315, October 2004. [5] S. O'uchi, M. Fujishima, and K. Hoh, "An 8-qubit quantum-circuit processor," Proceedings of IEEE International Symposium on Circuits and Systems, ISCAS 2002, pp.209-212, 2002. [6] A. Yakaryilmaz, "Superiority of one-way and realtime quantum machines," RAIRO - Theoretical Informatics and Applications, 46(4), pp.615-641, 2012. 5. 連絡先 住所：〒990-8560 山形市小白川町１－４－１２ 山形大学 地域教育文化学部 電話番号/FAX：023-628-4428 −135−