所属
大学院多元数理科学研究科 多元数理科学専攻 数理解析 教授
大学院担当
大学院多元数理科学研究科
学部担当
理学部 数理学科
職名
教授
連絡先
外部リンク
ルガル フランソワ ピエール マルセル
LE GALL Francois Pierre Marcel
LE GALL Francois Pierre Marcel
学位 1
-
博士（情報理工学） （ 2006年3月 東京大学 ）
研究キーワード 4
-
量子計算
-
計算量理論
-
分散計算
-
アルゴリズム
研究分野 1
-
情報通信 / 情報学基礎論
現在の研究課題とSDGs 4
-
分散計算
-
量子計算
-
計算量理論
-
アルゴリズム
経歴 5
-
名古屋大学 多元数理科学研究科 教授
2022年4月 - 現在
-
名古屋大学 多元数理科学研究科 准教授
2019年10月 - 現在
-
京都大学 情報学研究科 特任准教授
2016年4月 - 2019年9月
-
東京大学 情報理工学系研究科 特任准教授
2012年4月 - 2016年3月
-
東京大学 情報理工学系研究科 特任講師
2009年4月 - 2012年3月
所属学協会 5
-
情報処理学会
-
EATCS
-
ACM SIGACT
-
ACM
-
日本数学会
委員歴 8
-
Editorial board member
2023年1月 - 現在
-
Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) Steering committee member
2022年10月 - 現在
-
26th Conference on Quantum Information Processing (QIP 2023) Program committee chair
2022年5月 - 2023年2月
-
ACM Transactions on Quantum Computing Editorial board member
2019年6月 - 現在
-
Computational Complexity Editorial board member
2016年6月 - 現在
団体区分：学協会
-
Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) Steering committee member
2022年10月 - 現在
-
ACM Transactions on Quantum Computing Editorial board member
2019年6月 - 現在
団体区分：学協会
-
電子情報通信学会 コンピュテーション研究会専門委員
2016年6月 - 現在
団体区分：学協会
受賞 2
-
NISTEP Award 2017
2017年11月 文部科学省 科学技術・学術政策研究所
LE GALL, Francois Pierre Marcel
-
ISSAC 2014 Distinguished Paper Award
2014年7月 ACM-SIGAL
論文 40
-
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems.
François Le Gall, Saeed Seddighin
Proceedings of the 13th Innovations in Theoretical Computer Science conference (ITCS 2022) 頁： 97 - 23 2022年
-
Sevag Gharibian, François Le Gall
Proceedings of the 54th ACM Symposium on Theory of Computing (STOC 2022) 頁： 19 - 32 2022年
-
Distributed Quantum Proofs for Replicated Data. 査読有り
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
Proceedings of the 12th Innovations in Theoretical Computer Science conference (ITCS 2021) 頁： 28 - 20 2021年
-
Tight Distributed Listing of Cliques. 査読有り
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf
Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) 頁： 2878 - 2891 2021年
-
Distributed Quantum Interactive Proofs 査読有り
Francois Le Gall, Masayuki Miyamoto and Harumichi Nishimura
Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 頁： 42:1 - 42:21 2023年3月
-
Improved Hardness Results for the Guided Local Hamiltonian Problem. 査読有り
Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans
Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023) 頁： 32:1 - 32:19 2023年
-
Quantum Distributed Algorithms for Detection of Cliques.
Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman
Proceedings of the 13th Innovations in Theoretical Computer Science conference (ITCS 2022) 頁： 35 - 25 2022年
-
Quantum approximate counting for Markov chains and collision counting. 査読有り
Francois Le Gall, Iu-Iong Ng
Quantum Information & Computation 22 巻 ( 15&16 ) 頁： 1261 - 1279 2022年
-
An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes. 査読有り
Atsuya Hasegawa, François Le Gall
Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022) 頁： 6 - 14 2022年
-
Bounds on Oblivious Multiparty Quantum Communication Complexity. 査読有り
François Le Gall, Daiki Suruga
Proceedings of the 15th Latin American Theoretical Informatics Symposium (LATIN 2022) 頁： 641 - 657 2022年
-
Brief Announcement: Distributed Quantum Interactive Proofs. 査読有り
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Proceedings of the 36th International Symposium on Distributed Computing (DISC 2022) 頁： 48 - 3 2022年
-
Quantum Logarithmic Space and Post-Selection. 査読有り
François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz
Proceedings of the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) 頁： 10 - 17 2021年
-
Test of Quantumness with Small-Depth Quantum Circuits. 査読有り
Shuichi Hirahara, François Le Gall
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) 頁： 59 - 15 2021年
-
Quantum communication complexity of distribution testing.
Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov
Quantum Information & Computation 21 巻 ( 15&16 ) 頁： 1261 - 1273 2021年
-
Quantum Advantage with Shallow Circuits Under Arbitrary Corruption.
Atsuya Hasegawa, François Le Gall
Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021) 頁： 74 - 16 2021年
-
Lower Bounds for Induced Cycle Detection in Distributed Computing.
François Le Gall, Masayuki Miyamoto
Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021) 頁： 58 - 19 2021年
-
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model 査読有り
Izumi Taisuke, Le Gall Francois, Magniez Frederic
37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020) 154 巻 頁： 23 - 13 2020年
-
Barriers for Rectangular Matrix Multiplication.
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
Electron. Colloquium Comput. Complex. 27 巻 頁： 30 - 30 2020年
-
Quantum-Inspired Classical Algorithms for Singular Value Transformation. 査読有り
Dhawal Jethwani, François Le Gall, Sanjay K. Singh
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 頁： 53 - 14 2020年
-
Quantum Speedup for the Minimum Steiner Tree Problem. 査読有り
Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise, François Le Gall
Proceedings of the 26th International Computing and Combinatorics Conference (COCOON 2020) 頁： 234 - 245 2020年
-
On Distributed Listing of Cliques. 査読有り
Keren Censor-Hillel, François Le Gall, Dean Leitersdorf
Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC 2020) 頁： 474 - 482 2020年
-
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. 査読有り
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman
Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020) 頁： 33 - 17 2020年
-
Brief Announcement: Distributed Quantum Proofs for Replicated Data. 査読有り
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
Proceedings of the International Symposium on Distributed Computing (DISC 2020) 頁： 43 - 3 2020年
-
Finding Small and Large $k$-Clique Instances on a Quantum Computer 査読有り
Sara Ayman Metwalli, Francois Le Gall, Rodney Van Meter
IEEE Transactions on Quantum Engineering 1 巻 頁： 1 - 11 2020年
-
Average-Case Quantum Advantage with Shallow Circuits. 査読有り
François Le Gall
34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA. 頁： 21:1-21:20 2019年
-
Quantum Query Complexity of Unitary Operator Discrimination. 査読有り
Akinori Kawachi, Kenichi Kawano, Francois Le Gall, Suguru Tamaki
IEICE Transactions 102-D 巻 ( 3 ) 頁： 483 - 491 2019年
-
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model. 査読有り
Taisuke Izumi, François Le Gall
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. 頁： 84 - 93 2019年
-
Quantum Advantage for the LOCAL Model in Distributed Computing. 査読有り
François Le Gall, Ansis Rosmanis, Harumichi Nishimura
36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany 頁： 49:1-49:14 2019年
-
Quantum Advantage for the LOCAL Model in Distributed Computing
Le Gall Francois, Nishimura Harumichi, Rosmanis Ansis
36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019) 2019年
-
GENERALIZED QUANTUM ARTHUR-MERLIN GAMES 査読有り
Kobayashi Hirotada, Le Gall Francois, Nishimura Harumichi
SIAM JOURNAL ON COMPUTING 48 巻 ( 3 ) 頁： 865 - 902 2019年
-
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. 査読有り
François Le Gall, Frédéric Magniez
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018 頁： 337 - 346 2018年
-
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups. 査読有り
François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi
43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK 頁： 26:1-26:13 2018年
-
Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor 査読有り
François Le Gall, Florent Urrutia
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 頁： 1029 - 1046 2018年
-
Quantum Algorithm for Triangle Finding in Sparse Graphs 査読有り
Francois Le Gall, Shogo Nakajima
ALGORITHMICA 79 巻 ( 3 ) 頁： 941 - 959 2017年11月
-
MODIFIED GROUP NON-MEMBERSHIP IS IN PROMISE-AWPP RELATIVE TO GROUP ORACLES 査読有り
Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall
QUANTUM INFORMATION & COMPUTATION 17 巻 ( 3-4 ) 頁： 242 - 250 2017年3月
-
Triangle Finding and Listing in CONGEST Networks. 査読有り
Taisuke Izumi, François Le Gall
Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017 頁： 381 - 389 2017年
-
Quantum query complexity of unitary operator discrimination 査読有り
Akinori Kawachi, Kenichi Kawano, François Le Gall, Suguru Tamaki
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10392 巻 頁： 309 - 320 2017年
-
Quantum Algorithms for Matrix Products over Semirings. 査読有り
François Le Gall, Harumichi Nishimura
Chicago J. Theor. Comput. Sci. 2017 巻 2017年
-
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. 査読有り
Dean Doron, François Le Gall, Amnon Ta-Shma
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA 頁： 41:1-41:20 2017年
-
Multiparty Quantum Communication Complexity of Triangle Finding. 査読有り
François Le Gall, Shogo Nakajima
12th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2017, June 14-16, 2017, Paris, France 頁： 6:1-6:11 2017年
講演・口頭発表等 9
-
多人数の量子通信複雑性における新しい手法
第47回量子情報技術研究会 2022年12月8日
-
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
第47回量子情報技術研究会 2022年12月8日
-
ガイド付きローカルハミルトニアン問題の計算複雑性の進展
第47回量子情報技術研究会 2022年12月8日
-
Theoretical Foundations of Quantum Advantage 招待有り
Q2B 2022 Tokyo 2022年7月14日
-
分散量子対話型証明
第６回量子ソフトウェア研究会 2022年7月8日
-
Bounds on oblivious multiparty quantum communication complexity
第６回量子ソフトウェア研究会 2022年7月8日
-
Quantum algorithms for large-scale problems 招待有り 国際会議
François Le Gall
Quantum Innovation 2021, the International Symposium on Quantum Science, Technology and Innovation 2021年12月9日
-
Tight Distributed Listing of Cliques 招待有り
2021年3月8日
-
Quantum Distributed Computing 招待有り
Workshop on Advances in Distributed Graph Algorithms (ADGA 2022) 2022年10月24日
科研費 8
-
研究課題/研究課題番号：21H04879 2021年4月 - 2026年3月
科学研究費助成事業 基盤研究(A)
小柴 健史, 河内 亮周, 田中 圭介, 安永 憲司, ルガル フランソワ, 西村 治道
担当区分：研究分担者
量子コンピュータ開発が段階的に発展することを想定し，黎明期（現在の状況に対応し，量子計算能力をクラウドサービスとして利用できる計算環境）および成長期（上記に加えて，量子状態を生成できる量子デバイスあるいは量子通信装置など実現が容易な量子ハードウェアも利用できる計算環境）に適合した量子アルゴリズム・量子プロトコルの理論と設計方法の構築を目的とする。現在の情報化社会から量子情報化社会へ移行する際の準備として，計算基盤を段階的にシフトさせ，現在の情報セキュリティ技術に対する量子アルゴリズムの脅威による急激な変革を緩和させる技術を提供する。黎明期・成長期ごとに必要と思われる技術を設定し研究を遂行する。
-
研究課題/研究課題番号：20H05966 2020年11月 - 2025年3月
科学研究費助成事業 学術変革領域研究(A)
山下 茂, 山本 直樹, ルガル フランソワ, 森 立平, 谷 誠一郎, 西村 治道
担当区分：研究分担者
量子計算各種モデルにおける計算能力の解析を行う理論的なアプローチと、実際に量子計算機を利用する実践的なアプローチの両面から以下の4項目の研究を行う。
(A) 既存の量子計算モデルの結果を量子・古典協調の観点から、あるいは「弱い」量子計算モデルの観点から再検討・再構築する。
(B) 量子計算に起こりうる現実的なエラーを考慮に入れた計算モデルの検討を進める。
(C) 量子計算の方式に応じて異なる量子回路のモデルを量子・古典協調利用の枠組みの中で検討・評価する。
(D) 量子計算と古典計算を協調して利用する計算アルゴリズムの能力を解析するための計算モデルを検討・評価する。 -
量子アルゴリズム・計算量・浅層回路と量子コンピュータ実機実験による量子優位性研究
研究課題/研究課題番号：20H00579 2020年4月 - 2025年3月
科学研究費助成事業 基盤研究(A)
今井 浩, 山下 茂, ルガル フランソワ, Avis David
担当区分：研究分担者
量子コンピュータの得意な問題を用いて量子計算優越性を達成したとGoogleの研究者らが主張したところである。しかし、その問題は実応用とは無縁であり、IT社会に多大なインパクトを与えるの量子素因数分解計算などの実機実装の研究が重要となっている。本研究では、量子計算が本研究グループの量子浅層回路の計算量理論・実機に対応する量子回路の設計理論・量子非局所性とその組み合わせ構造に着目することにより、理論的に真に高速と示すことができる量子優位性を有する問題の最先端を研究し、量子コンピュータ実機で実証する。このような取り組みで、量子優位性が直接的に実社会に影響を与える新たな問題群を見出す成果を目指す。
-
Quantum Algorithms for Large-Scale Quantum Computers: New Horizons and Applications
研究課題/研究課題番号：20H04139 2020年4月 - 2024年3月
科学研究費助成事業 基盤研究(B)
ルガル フランソワ, 泉 泰介, 平原 秀一
担当区分：研究代表者
配分額：17290000円 （ 直接経費：13300000円 、 間接経費：3990000円 ）
将来に実現が期待される大規模な量子コンピュータの有力な応用を見いだすことは、量子計算の研究において最優先課題の一つである。本研究では、理論的な側面からこの課題に取り組む。研究期間中には、大規模な量子コンピュータ向けの新しい量子アルゴリズムの開発とともに、量子コンピュータの計算能力が発揮できる新分野の開拓を目指す。
-
研究課題/研究課題番号：19H04066 2019年4月 - 2023年3月
科学研究費助成事業 基盤研究(B)
西村 治道, ルガル フランソワ, 森前 智行, Buscemi F.
担当区分：研究分担者
今日の量子計算量理論において，対話型証明の概念は非常に大きな存在となっている．一方で，近年その実装へ向けて社会的注目を集める量子コンピュータはまだ小規模であり，量子メモリや量子通信は依然として高コストである．この状況を鑑みて，本研究では量子計算や量子通信が制限された量子対話型証明や量子計算に動機づけられた古典対話型証明，さらにはその中間的な対話型証明モデルに着目し，それらの対話型証明モデルについての計算量理論を展開する．これにより量子コンピュータの検証問題に対する新しい解決法を提案し，既存の量子対話型証明モデルや量子多項式階層理論を俯瞰的に捉えることができるような包括的成果を得ることを目指す．
-
量子スプレマシーの理論研究
研究課題/研究課題番号：19F19079 2019年7月 - 2021年3月
担当区分：その他
様々な側面から効率の良い量子アルゴリズムの構築に取り組み、量子コンピュータの新しい応用分野の開拓を目指す。理論的にも応用的にも重要な計算問題において、量子計算の古典計算に対する優位性（量子スプレマシー）を確立することを最終目標とする。
<BR>
第1世代の大規模量子コンピュータは分散型システムとして実現される見込みがあるため、本研究課題では特に量子分散計算に着目する予定である。量子分散アルゴリズムの計算時間の新しい解析手法を開発することによって、分散計算の枠組みにおいての量子スプレマシーの確立を目指す。
In the past year, my main research achievements concern the precise characterization of the resources necessary for quantum computers to solve certain computational tasks. In particular, these tasks are the quantum approximate counting and the quantum coupon collection. The two papers that my collaborators and I wrote on these tasks were accepted and presented at the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020).
In the approximate counting problem, there is a finite set with a subset of its elements marked, and one is asked to estimate the number of marked elements. In the quantum version of this problem, one can determine which elements are marked through various quantum computational resources. The study of how much of each resource is required to solve this task was started by Aaronson et al., but their characterization of resource requirements was incomplete. We managed to prove a complete characterization and, in doing so, to generalize one of the main methods for placing limitations on the power of quantum algorithms.
In the quantum coupon collection, similarly, there is a set with some of its elements marked, but, for this problem, one is asked to find all the marked elements, only given specific quantum states that encode which of the elements are marked. We proved that, under certain conditions, this task can be solved faster by quantum computers than an analogue task by classical computers. In addition, we proved that our quantum algorithm is optimal, meaning that no further improvements of it are possible.
I believe my research is going well. In addition to research problems that we have already solved, there are others on which we have substantial progress.
In the area of quantum query algorithms, one of the best-known open problems is that of precisely characterizing the quantum query complexity of finding 3-collisions in the input. We are currently working on adapting some of the recently introduced techniques for analyzing a closely-related task in the cryptographic setting, where random inputs are addressed. We have already obtained a partial adaptation for a slightly simpler task, that of finding 2-collisions, and I believe that this approach can be further generalized.
In the area of distributed quantum computing, we are investigating how many rounds of communication are required for solving locally checkable problems, that is, problems for which the correctness of the output can be quickly checked. In the case when the topology of the network corresponds to the cycle graph, we have already shown that quantum communication cannot significantly speed-up computation of problems that are global in their nature. Also, for the cycle graph, no non-trivial limitations on the power of quantum networks were known for problems that are local in their nature. One such fundamental problem is the graph 3-coloring. We have produced and executed computer tests that show that there are certain non-trivial limitations on the power of quantum distributed algorithms for 3-coloring, and we are currently in the process of proving and strengthening these results analytically.
We will continue research on quantum query complexity, trying to establish tight query lower bounds for the 3-collision problem. Some of the techniques that we plan to use have been recently used for analyzing quantum time-space tradeoffs. We plan to see if this might help to precisely characterize time-space tradeoffs for the 2-collision problem.
Also, recently researchers have started to study quantum query algorithms that can access the input in multiple diverse ways. Within the last year we have better understood how to analyze capabilities of such algorithms, but multiple questions remain open. One of them is to understand the power of these algorithms when their probability of success is not required to be large.
In the area of distributed quantum computing, we will continue to investigate the round complexity of locally checkable problems, namely, how many rounds of communication are required to solve them. For classical networks, the round complexity classifies all locally checkable problems in few and very distinct classes. We would like to see if a similar classification can be established in the quantum setting.
Quantum computation is performed by logical quantum circuits. There are significant similarities between studying quantum circuits and quantum networks, as in both scenarios one has to study how quickly and widely information can spread within the system. We plan to investigate what is the minimum depth of quantum circuits for constructing certain entangled quantum states, in particular, states that are codewords in quantum error correcting codes. -
量子プロトコル理論の線的展開
研究課題/研究課題番号：16H01705 2016年4月 - 2021年3月
小柴 健史
担当区分：研究分担者
量子プロトコルに関しての基礎的研究として，量子計算機を持つと主張するサーバに対する量子計算機を持つかのクライアントによる古典的検証可能性に，報酬の概念を導入するモデルを提案し，ゲーム理論的な形での同課題の解決という新しい方向性を見出した。またクライアントがサーバに計算の内容を秘匿して量子計算をさせるブラインド量子計算の基本的な設定での不可能性を示し，さらに弱い量子計算モデルによるサンプリングの不可能性も示した。
量子分散プロトコルの優位性の確立に向けては，大きな進展を得ることができた。具体的には，分散計算の中核的な問題である「全対最短経路問題」に対して，最良の古典分散プロトコルより高速な量子分散プロトコルの開発に成功した。帯域幅の限られているモデルにおいて，三角形発見問題を高速に解く量子分散プロトコルを構築できた。
量子プロトコル理論へ基礎を与えるための古典暗号プロトコル研究でも貢献した。セキュアメッセージ伝達プロトコルについて，複数の独立した敵対者が存在するモデルでは，すべての通信路が支配されたとしてもゲーム理論的な安全性を達成できることを示した。これは，敵対者がすべての資源を支配した場合に自明に安全性が成り立たない古典的な安全性では実現できない結果である。さらに，並列計算が容易な効率の良いコミットメント方式を提案し，その耐量子安全性を評価した。情報理論的な安全性を持つ秘密計算の一種である条件付き秘密開示方式などの通信効率および使用乱数長の限界を評価した。
量子コンピュータの初期の利用形態であるサーバによる代理計算に関して，幾つかの限界があることを示した。また，サーバが本当に量子コンピュータであるのかを古典的に検証を行うという基本的問題に対してゲーム理論的な概念を導入することで解決を見るなど，量子プロトコル理論に新機軸を見出すことに成功している。
量子プロトコル理論を展開することが本研究課題の目標であるが，代表的な課題である量子分散計算研究において幾つかの基本モデルにおいて効率的なプロトコルを得ることに成功しており，量子プロトコル理論を強化することにつながっている。量子分散計算の研究成果は独創的な位置受けにあり，権威ある国際会議での発表に至っている。
新しい枠組みからの研究として，昨年度から取り組んでいるゲーム理論的なアプローチを導入したプロトコルの可能性・限界についても発展的成果を得ることが出来ている。
順調に研究成果を得ることができており，幾つかの研究成果は対外的にも高い評価を得ることができている。本研究課題は，複数のアプローチを組み合わせることを研究方法の中心的な方策と考えているが，アプローチ間の融合的なテーマ設定を検討し議論を行う機会を設けるなど研究複数のアプローチ間の連携を強化することより，一層の成果を創出することを目指す。例えば，古典暗号理論におけるゲーム理論的な概念の導入を量子プロトコル理論においても検討するなどが考えられる。
また，国内外の研究者と連携して研究を進めていくことも検討する。特に国際共同研究への発展可能性を意識し，量子プロトコル理論において世界的な拠点を形成すべく，本研究課題と関連したトピックで研究集会や国際ワークショップ等を昨年度に引き続き主催することも検討する。 -
Algebraic Complexity Theory: New Approaches and Algorithmic Applications
研究課題/研究課題番号：16H05853 2016年4月 - 2020年3月
ルガル フランソワ
担当区分：研究代表者
配分額：12480000円 （ 直接経費：9600000円 、 間接経費：2880000円 ）
本研究課題では、代数的計算量理論に基づき、理論計算機科学の諸問題を解くための新しい手法を開発した。研究期間内に得た主な成果は次のように大別できる。
まず、代数的問題を解く新しいアプローチを開発し、長方形行列積アルゴリズムの高速化に成功した。次、代数的手法を新たな理論計算機科学の問題に応用することができた。特に分散計算においては、様々な問題に対して、高速な分散アルゴリズムを構築した。最後に、グラフ問題に対して、従来のアルゴリズムより高速な量子アルゴリズムの開発にも成功した。
行列積は情報処理の普遍的な計算である。本研究で開発した行列積アルゴリズムは世界最高速であり、すでに理論計算機科学に広く使われており、今後もアルゴリズムの設計の重要なツールになると期待できる。分散計算における新アプローチは、汎用性が高く、分散計算の基幹技術になる可能性が高い。開発した量子アルゴリズムも、重要なグラフ問題を解くものであり、量子計算の優位性の確立に向けて大きな役割を果たすと期待できる。