メーリングリストの皆様、
群馬大の森前と申します。
非ユニバーサル量子計算に関する研究会のご案内をさせていただきます。
会場のキャパシティの都合上、参加される場合は
morimae[at]gmail.comまでご連絡いただけますと助かります。
宜しくお願いいたします。
日時：３月３０日（月）10:40-
場所：CELC（http://www.al.ics.saitama-u.ac.jp/elc/celc/） セミナー室
内容：量子計算の究極のゴールはユニバーサル量子計算機、つまり任意の量子アルゴリズム
が実行できるような汎用量子計算機、を作ることである。しかしながら、まだまだそのゴールは遠い。そこで、近年、ユニバーサル量子計算機ではないが、何かしら古典計算機よりも速い計算を
デモンストレートできるような「非ユニバーサル量子計算機」の研究が注目を浴びている。
非ユニバーサル量子計算機はユニバーサル量子計算機よりも実験的実現に対する技術的要請が少ないし、古典計算と量子計算の境界がどこにあるのかを理論的に探る上でも重要なクラスである。例えば、交換する量子ゲートのみからなる量子計算機や、相互作用無しのボソンを
用いた量子計算機、非常にサーマルな量子状態を用いた量子計算機などは明らかにユニ
バーサル量子計算機ではない。それどころか、古典計算機でシミレートできてしまいそうである。
ところが驚くことに、これらのモデルが古典計算機で効率的にシミレートできたら、
多項式階層が崩壊することが証明された[1,2,4]。多項式階層とはP,NPを一般化したものであり、P=NPだと信じられていないのと同様に、多項式階層は崩壊しないだろうと計算機科学では強く信じられている。したがって、これらの結果は、上記の非ユニバーサル量子計算モデルが古典計算機ではシミレートできないことを示している。また、交換するゲートのみからなる非ユニバーサル量子計算は古典イジング分配関数と面白い関係を持つことが知られているため、古典イジングの計算困難性と量子計算の計算能力が繋がる[3]。本研究会では、この非ユニバーサル量子計算の基礎と最近の話題についての講演が行われる。フリーディスカッションの時間も設けられている。
スケジュール：
座長：西村治道（名古屋大）
時間：10:40-11:40
話題提供者：森前智行（群馬大）
話題：one clean qubit 量子計算モデルの古典シミレート不可能性
参考文献：
[1] On the hardness of classically simulating the one clean qubit model
Tomoyuki Morimae, Keisuke Fujii, Joseph F. Fitzsimons
Physical Review Letters 112, 130502 (2014)
時間：12:45-13:45
話題提供者：藤井啓祐（京都大）
話題：Instantaneous quantum polynomial time modelとイジング分配関数
参考文献：
[2] Classical simulation of commuting quantum computations implies
collapse of the polynomial hierarchy
Michael J. Bremner, Richard Jozsa, Dan J. Shepherd
Proceedings of Royal Society A 467: 459–472 (2011)
[3] Quantum Commuting Circuits and Complexity of Ising Partition Functions
Keisuke Fujii, Tomoyuki Morimae
arXiv:1311.2128
時間：14:00-15:00
話題提供者：玉手修平（NII）
話題：相互作用なしのボソン粒子を用いた量子計算機モデルの古典シミレート不 可能性
参考文献：
[4] The computational complexity of linear optics
Scott Aaronson and Alex Arkhipov,
Proc. 43th ACM Symposium on Theory of Computing (STOC11), pp. 333-342 (2011);
Journal version appeared in Theory of Computing 9: 143-252 (2013)
時間：15:15-
フリーディスカッション