FIT2026 第25回情報科学技術フォーラム

イベント企画

トップコンファレンス2-3 コンピュテーション/量子ソフトウエア

2026/9/2(水) 13:10-15:10
第6イベント会場

座長：白髪　丈晴（中央大学）

13:10-13:30 講演(1)　非ブール関数に対する困難性の増幅
清水伸高（東京科学大学　工学院経営工学系　助教）
【原発表の書誌情報】Shimizu, N., Yasunaga, K.: Hardness Amplification Beyond Boolean Functions, Proc. ACM Symposium on Theory of Computing (STOC), pp.1278-1289 (2026).
【概要】平均困難性の増幅を有限体上の和へ拡張し、ほぼ最適な予測不能性を示す。応用として、三角形数え上げの誤り耐性付きランダム自己還元も与える。
	【略歴】東京科学大学助教。東京工業大学理学部情報科学科で学士号（2012年）、東京大学大学院情報理工学系研究科で修士号（2018年）・博士号（2021年）を取得。理論計算機科学を専門とし、特に計算量理論を専門にする。
13:30-13:50 講演(2)　計算量理論的万能帰納推論
七島幹人（東京科学大学）
【原発表の書誌情報】S. Hirahara and M. Nanashima, Complexity-Theoretic Universal Inductive Inference, in Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC2026), Pages 377 - 385.
【概要】Solomonoffの万能帰納推論理論の計算量理論的対応として得られた，時間制限付きコルモゴロフ複雑性の効率的近似に基づく多項式時間万能帰納推論アルゴリズムの構成について発表する．
	【略歴】2023年，東京工業大学情報理工学院数理・計算科学コース博士後期課程修了．同年，東京工業大学情報理工学院助教に就任．現在，東京科学大学情報理工学院准教授，ならびに国立情報学研究所特別研究員（Boostクロスアポイント）．専門は，計算量理論，計算論的学習理論，暗号理論など．
13:50-14:10 講演(3)　重み付き編集距離に基づく近似文字列照合
Wellnitz Philip（国立情報学研究所　情報学プリンシプル研究系　助教）
【原発表の書誌情報】Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz: Pattern Matching under Weighted Edit Distance. FOCS 2025. DOI: 10.1109/FOCS63196.2025.00102
【概要】重み付き編集距離に基づく近似文字列照合（PMWED）という計算問題において、長さ $n$ のテキスト文字列 $T$、長さ $m$ のパターン文字列 $P$、編集コストを規定する重み関数へのオラクルアクセス、そして閾値 $k$ に持って、$P$ との重み付き編集距離が $k$ 以下となる $T$ 内の部分文字列（の開始位置）を特定することである。本講演では、PMWEDに対する我々の新しい、かつ概念的に単純な $\tilde{O}(nk)$ 時間アルゴリズムに焦点を当てます。このアルゴリズムは、編集コストが一様である設定のみに使われる古典的なLandauとVishkinのアルゴリズムとは大きく異なるものです。
	【略歴】2024.4~現在: 助教、国立情報学研究所、東京 2021.10~2024.3: ポスドク、MPI-INF、ザールブリュッケン、ドイツ 2018.10~2021.12: PhD (Computer Science)、ザールランド大学/MPI-INF、ザールブリュッケン、ドイツ
14:10-14:30 講演(4)　グループ注文はQCMAにあります
Dhara Thakkar（名古屋大学　Graduate School of Mathematics　Designated Assistant Professor）
【原発表の書誌情報】F. Le Gall, H. Nishimura and D. Thakkar, Group order is in QCMA, in 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), 1128--1143, IEEE Comput. Soc. Press, Los Alamitos, CA.
【概要】In this talk, Dhara will discuss recent progress on the role of classical proofs in quantum complexi ty theory, focusing on group-theoretic problems in the black-box model. We resolve two long-standing open questions in this area. First, we show that the Group Non-Membership problem—known to lie in QMA but not in MA—is in fact in QCMA, settling a 2006 conjecture by Aaronson and Kuperberg. This result follows from a more general result that the Group Order Verification problem lies in QCM A ∩ coQCMA, answering an open question posed by Watrous in 2000. Our techniques also give improved quantum upper bounds on the complexity of many other group-theorets ical problems, such as group isomorphism in black-box group settings.
	【略歴】Dhara Thakkar is a Designated Assistant Professor at the Graduate School of Mathematics, Nagoya University in Japan, where she is working with François Le Gall's research group. Dhara completed her PhD in Theoretical Computer Science at IIT Gandhinagar, India, under the guidance of Bireswar Das. Even before that, she earned her M.Phil. degree (2019) and M.Sc. degree (2018) in (pure) mathematics from Sardar Patel University, India. Dhara’s research interests include Algebraic Computation, Computational Complexity, Group theory, Quantum Computation, Representation theory.
14:30-14:50 講演(5)　スペクトル和推定の脱量子化と困難性
長谷川敦哉（名古屋大学）
【原発表の書誌情報】Roman Edenhofer, Atsuya Hasegawa, François Le Gall. Dequantization and Hardness of Spectral Sum Estimation. Presented as a talk at the 29th Annual Quantum Information Processing Conference (QIP 2026).
【概要】研究では行列のスペクトル和（例えば log-determinant）の推定について、新たな量子インスパイア古典アルゴリズムと計算困難性の結果を示す。既存の量子アルゴリズムでは疎・良条件・正定値行列のlog-determinantを高精度で高速に近似できることが示されているが、本研究は次元に対して多項対数時間に近い計算時間を維持する量子インスパイア古典アルゴリズムを構成する。さらに特定のスペクトル和推定問題が（妥当な複雑性クラスの仮定の下で）古典計算モデルでは同等の時間で解けないことを示す困難性結果も提供する。
	【略歴】2024年9月東京大学大学院情報理工学系研究科コンピュータ科学専攻博士課程修了 2024年10月- 名古屋大学大学院多元数理科学研究科特任助教
14:50-15:10 講演(6)　Quantum Circuit Design for Decoded Quantum Interferometry
Benchasattabuse Naphan（慶應義塾大学　大学院メディアデザイン研究科　特任助教）
【原発表の書誌情報】Natchapol Patamawisut, Naphan Benchasattabuse, Michal Hajdušek, Rodney Van Meter: “Quantum Circuit Design for Decoded Quantum Interferometry,” in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), Albuquerque, NM, USA, Aug. 2025, pp. 291–301.
【概要】Combinatorial optimization problems remain a central challenge in computer science, with Decoded Quantum Interferometry (DQI) recently emerging as a novel algorithmic approach to approximate solutions. DQI operates by reducing instances of linear satisfiability to bounded-distance decoding over quantum superpositions. However, realizing DQI in practice requires overcoming a significant technical hurdle: designing a decoder capable of operating coherently on these superpositions. In this work, we detail the concrete quantum circuit implementation of DQI developed in our recent work. Moving beyond theoretical proposals, the presentation offers a comprehensive technical breakdown of the decoding subroutine, demonstrating the successful integration of a reversible Gauss-Jordan elimination circuit to address the coherency challenge.
	【略歴】Naphan Benchasattabuse is a project assistant professor at the Graduate School of Media Design of Keio University. He received M.Eng. from Chulalongkorn University in 2020 with his thesis on optimizing circuit-based quantum programs for arithmetic circuits, and his PhD from Keio University in 2025. His experience in optimizing quantum circuits got him first place twice in IBM Quantum Challenge for 2019 and Fall 2021. His research interests include protocol design and resource management inside quantum repeater networks, the compilation of quantum programs, and quantum algorithms for optimization problems.