所属
大学院多元数理科学研究科 多元数理科学専攻 数理解析 教授
大学院担当
大学院多元数理科学研究科
学部担当
理学部 数理学科
職名
教授
連絡先
外部リンク
ルガル フランソワ ピエール マルセル
LE GALL Francois Pierre Marcel
LE GALL Francois Pierre Marcel
学位 1
-
博士（情報理工学） （ 2006年3月 東京大学 ）
研究キーワード 4
-
量子計算
-
計算量理論
-
分散計算
-
アルゴリズム
研究分野 1
-
情報通信 / 情報学基礎論
現在の研究課題とSDGs 4
-
分散計算
-
量子計算
-
計算量理論
-
アルゴリズム
経歴 5
-
名古屋大学 多元数理科学研究科 教授
2022年4月 - 現在
-
名古屋大学 大学院多元数理科学研究科 准教授
2019年10月 - 2022年3月
-
京都大学 情報学研究科 特任准教授
2016年4月 - 2019年9月
-
東京大学 情報理工学系研究科 特任准教授
2012年4月 - 2016年3月
-
東京大学 情報理工学系研究科 特任講師
2009年4月 - 2012年3月
所属学協会 5
-
情報処理学会
-
EATCS
-
ACM SIGACT
-
ACM
-
日本数学会
委員歴 17
-
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月 - 現在
団体区分：学協会
-
ACM-SIAM Symposium on Discrete Algorithms (SODA24) Program Committee member
2024年2月 - 2024年7月
団体区分：学協会
-
51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024) Program Committee member
2024年2月 - 2024年7月
団体区分：学協会
-
51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024) Program Committee member
2024年2月 - 2024年7月
団体区分：学協会
-
ACM-SIAM Symposium on Discrete Algorithms (SODA24) Program Committee member
2023年7月 - 2024年1月
団体区分：学協会
-
2023 Computational Complexity Conference (CCC 2023) Program Committee member
2023年2月 - 2023年7月
団体区分：学協会
-
2023 Computational Complexity Conference (CCC 2023) Program Committee member
2023年2月 - 2023年7月
-
The International Symposium on Quantum Science, Technology and Innovation (Quantum Innovation) 組織委員
2023年 - 現在
団体区分：政府
-
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月
-
17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022) Program committee chair
2021年10月 - 2022年7月
-
電子情報通信学会 コンピュテーション研究会専門委員
2016年6月 - 2022年5月
団体区分：学協会
-
51st EATCS International Colloquium on Automata, Languages and Programming Program Committee member
団体区分：学協会
受賞 2
-
NISTEP Award 2017
2017年11月 文部科学省 科学技術・学術政策研究所
LE GALL, Francois Pierre Marcel
-
ISSAC 2014 Distinguished Paper Award
2014年7月 ACM-SIGAL
論文 48
-
Faster Rectangular Matrix Multiplication by Combination Loss Analysis 査読有り
François Le Gall
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 頁： 3765 - 3791 2024年1月
-
No Distributed Quantum Advantage for Approximate Graph Coloring. 査読有り
Xavier Coiteux-Roy, Francesco D'Amore 0001, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela
Proceedings of the 56th ACM Symposium on Theory of Computing (STOC 2024) 頁： 1901 - 1910 2024年
-
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年
-
Seunghoan Song, François Le Gall, Masahito Hayashi
EPJ Quantum Technology 11 巻 ( 1 ) 2024年9月
-
Hugo Delavenne, François Le Gall
Quantum Information and Computation 24 巻 ( 9&10 ) 頁： 754 - 765 2024年9月
-
Sevag Gharibian, François Le Gall
SIAM Journal on Computing 52 巻 ( 4 ) 頁： 1009 - 1038 2023年8月
-
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. 査読有り
François Le Gall, Saeed Seddighin
Algorithmica 85 巻 ( 5 ) 頁： 1251 - 1286 2023年5月
-
Distributed Quantum Interactive Proofs. 査読有り
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 頁： 42:1 - 42:21 2023年
-
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications. 査読有り
Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) 頁： 63 - 15 2023年
-
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 Computing: Potential and Limitations (Invited Talk).
François Le Gall
OPODIS 頁： 2 - 1 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 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年
-
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年
-
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 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年
-
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年
-
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年
-
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年
-
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月
-
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年
-
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年
講演・口頭発表等 17
-
量子アルゴリズム 招待有り
ルガル フランソワ
ムーンショット目標6 ミニシンポジウム2024 量子コンピュータは、未来をどう変えうるか ～FTQCとそこに至る過程で期待されるアプリケーション～ 2024年10月1日
-
Online Locality Meets Distributed Quantum Computing 招待有り
情報・計算・暗号の融合による新しい数理基盤の創出 2024年9月26日
-
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, Jukka Suomela
Theory of Quantum Computation, Communication and Cryptography (TQC 2024) 2024年9月12日
-
Theoretical Foundations of Quantum Advantage in Quantum Algorithms 招待有り
Francois Le Gall
Q2B 2024 Tokyo 2024年7月25日
-
Quantum distributed computing: potential and limitations 招待有り
Le Gall Francois
2023 CONFERENCE ON PRINCIPLES OF DISTRIBUTED SYSTEMS (OPODIS 2023) 2023年12月7日
-
Quantum Algorithms: Applications and Theoretical Foundations 招待有り
Francois Le Gall
The 13 th International Symposium for Sustainability by Engineering at Mie University (Research Area C) 2023年11月22日
-
Theoretical Foundations of Quantum Advantage in Quantum Computing 招待有り
Francois Le Gall
京都大学基礎物理学研究所 創立70周年記念シンポジウム 2023年11月22日
-
Theoretical Foundations of Quantum Advantage for Quantum Algorithms 招待有り
Francois Le Gall
YIPQS long-term workshop Quantum Information, Quantum Matter and Quantum Gravity 2023年9月20日
-
多人数の量子通信複雑性における新しい手法
第47回量子情報技術研究会 2022年12月8日
-
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
第47回量子情報技術研究会 2022年12月8日
-
ガイド付きローカルハミルトニアン問題の計算複雑性の進展
第47回量子情報技術研究会 2022年12月8日
-
Quantum Distributed Computing 招待有り
Workshop on Advances in Distributed Graph Algorithms (ADGA 2022) 2022年10月24日
-
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日
科研費 9
-
中規模量子コンピュータによるセキュアな分散型量子計算の基盤創出
研究課題/研究課題番号：24H00071 2024年4月 - 2029年3月
日本学術振興会 科学研究費助成事業 基盤研究(S)
ルガル フランソワ, 田中 圭介, 西村 治道, 河内 亮周, 安永 憲司, 桑原 知剛
担当区分：研究代表者
配分額：203450000円 （ 直接経費：156500000円 、 間接経費：46950000円 ）
中規模量子コンピュータの潜在的能力を最大限に活かすため、中規模量子コンピュータによる分散型量子計算の基盤を創出する。量子的にセキュアなプロトコルを設計し、量子優位性（すなわち、量子コンピュータがスーパーコンピュータよりも速く問題を解決できること）を厳密に裏付けることにより、中規模量子コンピュータの活用方法を開拓し、10～15年後で利用可能な量子アルゴリズムの開発を先駆する。
-
Quantum Algorithms for Large-Scale Quantum Computers: New Horizons and Applications 国際共著
研究課題/研究課題番号：20H04139 2020年4月 - 2024年3月
日本学術振興会 科学研究費助成事業 基盤研究(B)
ルガル フランソワ, 泉 泰介, 平原 秀一
担当区分：研究代表者 資金種別：競争的資金
配分額：17290000円 （ 直接経費：13300000円 、 間接経費：3990000円 ）
将来に実現が期待される大規模な量子コンピュータの有力な応用を見いだすことは、量子計算の研究において最優先課題の一つである。本研究では、理論的な側面からこの課題に取り組む。研究期間中には、大規模な量子コンピュータ向けの新しい量子アルゴリズムの開発とともに、量子コンピュータの計算能力が発揮できる新分野の開拓を目指す。
2022年度は量子アルゴリズムの開発および量子コンピュータの計算能力の究明について、様々な側面から研究を推進し、数多くの成果を得た。
まず、量子特異値変換（QSVT）という、量子アルゴリズムを記述するための統一されたフレームワークについて研究した。低次数の多項式に関連するQSVTを任意の定数精度で効率的に脱量子化する方法を示し、高速な古典アルゴリズムを構築した。その一方、高次数の多項式に関連するQSVTについては、脱量子化の不可能性を示唆する成果を得た。その成果により、化学計算における量子アルゴリズムの優位性を厳密に証明することができた。
次、計算量理論の側面から量子コンピュータの計算能力の究明に取り組んだ。量子・古典ハイブリッドモデルにおいて、様々な計算に対して必要な計算資源を厳密に解析した結果、量子・古典ハイブリッド回路の深さが計算能力に大きく影響することを明らかにした。また、困難性自己増幅という概念に着目して、Fine-grained Complexityの既存研究で研究された自然な分布問題について、困難性の自己増幅の結果を証明した。
さらに、量子分散アルゴリズムの開発に取り組んだ。2021年度に引き続き、分散検証という枠組みで量子分散アルゴリズムの計算能力を調査した結果、量子分散計算の優位性を証明することに成功した。また、グローバルな問題、つまり帯域幅が制限されていない場合でも直径時間を必要とする問題に対して、新しいテクニックを導入し、様々な高速な分散アルゴリズムを構築した。
量子アルゴリズムや計算量理論について、様々な側面から数多くの成果を得て、その結果を理論計算機科学の重要な国際会議および査読付き国際論文誌で発表することができている。
引き続き、量子特有の効果を生かした量子アルゴリズムの開発および量子コンピュータの計算能力の究明を目指す。2023年度は特に分散計算と計算量理論の知識をもとに、量子コンピュータの新しい応用先を開拓していく予定である．また、本研究課題の最終年度となるため、得られた研究成果の周知に力を注ぐ。 -
Algebraic Complexity Theory: New Approaches and Algorithmic Applications 国際共著
研究課題/研究課題番号：16H05853 2016年4月 - 2020年3月
日本学術振興会 科学研究費助成事業 若手研究(A)
ルガル フランソワ
担当区分：研究代表者 資金種別：競争的資金
配分額：12480000円 （ 直接経費：9600000円 、 間接経費：2880000円 ）
本研究課題では、代数的計算量理論に基づき、理論計算機科学の諸問題を解くための新しい手法を開発した。研究期間内に得た主な成果は次のように大別できる。
まず、代数的問題を解く新しいアプローチを開発し、長方形行列積アルゴリズムの高速化に成功した。次、代数的手法を新たな理論計算機科学の問題に応用することができた。特に分散計算においては、様々な問題に対して、高速な分散アルゴリズムを構築した。最後に、グラフ問題に対して、従来のアルゴリズムより高速な量子アルゴリズムの開発にも成功した。 -
量子情報化社会に向けた量子計算基盤の構築 国際共著
研究課題/研究課題番号：21H04879 2021年4月 - 2026年3月
日本学術振興会 科学研究費助成事業 基盤研究(A)
小柴 健史, 河内 亮周, 田中 圭介, 安永 憲司, ルガル フランソワ, 西村 治道
担当区分：研究分担者 資金種別：競争的資金
量子コンピュータ開発が段階的に発展することを想定し，黎明期（現在の状況に対応し，量子計算能力をクラウドサービスとして利用できる計算環境）および成長期（上記に加えて，量子状態を生成できる量子デバイスあるいは量子通信装置など実現が容易な量子ハードウェアも利用できる計算環境）に適合した量子アルゴリズム・量子プロトコルの理論と設計方法の構築を目的とする。現在の情報化社会から量子情報化社会へ移行する際の準備として，計算基盤を段階的にシフトさせ，現在の情報セキュリティ技術に対する量子アルゴリズムの脅威による急激な変革を緩和させる技術を提供する。黎明期・成長期ごとに必要と思われる技術を設定し研究を遂行する。
量子クラウド計算実現の構成要素として, 参加者の入力を他参加者から秘密にしたまま計算を行う秘密計算の一形態である秘密同時メッセージプロトコルの量子版を初めて導入し, ある問題に対して事前共有量子エンタングルメントを利用することで指数関数的に通信量が改良できることを示した. さらに等価性判定問題を一般化した問題やAND関数についても事前共有エンタングルメントによって通信量を削減できることを示した. 事前乱数共有での量子秘密同時メッセージプロトコルにおいて安全性を保証するためには通信量のオーバーヘッドが不可避であることも証明した. また分散ネットワーク環境において, グラフ理論で重要な問題に対する効率的な量子分散アルゴリズムを構築した. 計算資源限定下の量子計算機, 特に定数深さ量子回路の研究を推進し, 一般のノイズを許したモデルにおける定数深さ量子回路での量子優位性を示唆する結果を得た. さらに, 定数深さ量子回路による量子性検証プロトコルを構築した. 量子計算の暗号への脅威に対応するための技術として, ゲーム理論的な安全性評価において従来研究での確率分布間の全変動距離を用いた識別不能性評価の代わりにHellinger距離による新しい安全性定量化手法を導入し, 必要な距離の程度を緩和できることを示し, より妥当な安全性評価が可能であることを明らかにした. また暗号理論で重要な再利用ハッシュ補題は全変動距離で定式化されるが, Hellinger距離に対しても成立することも証明した. さらに耐量子性を持つ暗号プロトコルとして新しいリング署名の構成法を提案した. ユーザがリングと呼ばれるユーザ集合のメンバーとしてメッセージに署名することを可能にするリング署名では, 署名の偽造不可能性に加え, リング内の誰がメッセージに署名したかを秘匿する匿名性も要求されるが, 本提案は標準的な仮定の状況で耐量子性が保証される情報理論的匿名性を持つ一般的構成を初めて与えている.
令和3年9月までに, 研究動向(特に量子秘密分散)の調査, 研究分担者との研究トピックの調整, 研究トピックの研究動向の再調査, 調整後の量子分散等の研究課題の研究開始を行い, 令和4年3月までに, 新規量子秘密分散と従来技術の差異明確化を行う予定であったが, 研究協力者の制限等で予定通りの実施が困難になり, 一部課題トピックに遅延が生じた. しかしながらそれ以外の点については令和3年度において初期的な研究成果が挙がっており順調に研究が進展している. (a. 1)量子コンピュータに対して安全な暗号プロトコルの理論と設計方法においては, 研究実績の概要で報告した耐量子性を持つリング署名の一般的構成方法や安全性定量化手法, (a. 2)量子コンピュータの古典的検証可能性においては, 定数深さ量子回路による量子性検証プロトコル, (b. 1)低量子計算能力モデルにおける量子秘匿計算の理論と設計方法においては量子秘密同時メッセージプロトコルの設計と解析, (b. 2)低量子計算能力モデルにおける量子分散計算の理論と設計方法においては, グラフ理論の重要な問題に対する量子分散アルゴリズムの構築, (c. 1)パーティが合理的に行動を選択する場合の量子プロトコルの理論と設計方法においてはゲーム理論的安全性評価手法, と令和3年度における目標について具体的な研究成果が挙げられており, また令和4年度では令和3年分の遅延を解消し, 研究目標に沿った研究成果が継続的に挙がっており, 全体として大幅な研究計画の遅延はないと考えられる.
令和4年度では, 研究動向の調査, 研究分担者との研究トピックの調整, 研究トピックの研究動向の再調査, 調整後の量子分散等の研究課題の研究開始を行い, 新規量子秘密分散と従来技術の差異明確化を行い, 計画の遅延解消を図る. それを踏まえた上で令和4年度以降においては申請書での当初計画の通り, (a. 1)ではより高度な耐量子暗号プロトコルの設計と安全性解析, (a. 2)では定数深さ量子回路以外の計算資源制限下の量子性検証プロトコルの可能性, (b. 1)では積計算に対する量子秘匿計算プロトコルの設計, (c. 1)量子情報による優位性が示されている分散計算でのゲーム理論的解析による効率改善や不可能性回避の技法の検討を推進する. -
研究課題/研究課題番号：20H05966 2020年11月 - 2025年3月
科学研究費助成事業 学術変革領域研究(A)
山下 茂, 山本 直樹, ルガル フランソワ, 森 立平, 谷 誠一郎, 西村 治道
担当区分：研究分担者
量子計算各種モデルにおける計算能力の解析を行う理論的なアプローチと、実際に量子計算機を利用する実践的なアプローチの両面から以下の4項目の研究を行う。
(A) 既存の量子計算モデルの結果を量子・古典協調の観点から、あるいは「弱い」量子計算モデルの観点から再検討・再構築する。
(B) 量子計算に起こりうる現実的なエラーを考慮に入れた計算モデルの検討を進める。
(C) 量子計算の方式に応じて異なる量子回路のモデルを量子・古典協調利用の枠組みの中で検討・評価する。
(D) 量子計算と古典計算を協調して利用する計算アルゴリズムの能力を解析するための計算モデルを検討・評価する。 -
量子アルゴリズム・計算量・浅層回路と量子コンピュータ実機実験による量子優位性研究 国際共著
研究課題/研究課題番号：20H00579 2020年4月 - 2025年3月
日本学術振興会 科学研究費助成事業 基盤研究(A)
今井 浩, 山下 茂, ルガル フランソワ, Avis David
担当区分：研究分担者 資金種別：競争的資金
量子コンピュータの得意な問題を用いて量子計算優越性を達成したとGoogleの研究者らが主張したところである。しかし、その問題は実応用とは無縁であり、IT社会に多大なインパクトを与えるの量子素因数分解計算などの実機実装の研究が重要となっている。本研究では、量子計算が本研究グループの量子浅層回路の計算量理論・実機に対応する量子回路の設計理論・量子非局所性とその組み合わせ構造に着目することにより、理論的に真に高速と示すことができる量子優位性を有する問題の最先端を研究し、量子コンピュータ実機で実証する。このような取り組みで、量子優位性が直接的に実社会に影響を与える新たな問題群を見出す成果を目指す。
2年度目の研究では、IBMの65量子ビットの量子コンピュータが研究代表者のところで利用できるようになり、それを用いて量子グラフ状態の一般化Bell不等式の破れの研究を進めることができた。65量子ビットのレベルでは、古典シミュレーションもかなり難しくなるとともに、それまでのエラー緩和手法が量子ビット数の指数時間かかっていた点が大きな問題として顕在化する。それを解決するための研究を進め、新たに100量子ビットレベルでも適用できる測定エラーに対するエラー緩和法を提案した。これは初年度に見出した課題を解決したものである。これを次年度に続けて、論文として公開するに至っている。浅層回路に関する計算量理論からの解析では、定数段から次のステップとして、量子ビット数の対数深さのものを考え、それについて取り組みを始めた。この問題の周辺には、Jozsaの予想という浅層回路を古典計算とハイブリッドで用いた場合の計算量に関する問題と密に関係しており、その回目に向けて明確な一歩を次年度に国際会議で論文を成果発表すること示した。分担者のLe Gallは、量子分散計算に関して自ら構築した枠組みの中で活発な研究を進め、国際会議で発表するとともに、研究コミュニティのリーダとして国際会議のプログラム策定などで貢献もしている。分担者の山下が中心となって研究を進め、実機への応用を目指した回路設計の研究も始めており、Sゲートを用いてTゲート・Toffliゲートの数を改善する量子回路設計法や、SATを用いた設計論を展開した。分担者のAvisがスタートさせた量子重力理論の共形場でのエントロピー錐の研究を凸多面体解析を自ら開発した並列プログラムで解析するなどして、次年度に論文発表することにつながっている。
初年度は研究の中で、新たに量子計算の範囲を拡大する研究課題を設定することができ、2年度でそれらの成果創出に向けて取り組んだ。まだコロナ禍の影響があり、海外研究者の招へいは難しいところであるが、次年度にそれを実現して研究推進する展開も検討した。
<BR>
量子コンピュータ実機利用では、65量子ビットの量子コンピュータがさらに127量子ビットのものも利用が始まり、一般化Bell不等式を用いた浅層回路をベンチマーク的に利用することも可能となった。浅層回路の計算量理論・回路設計論の観点からの研究も進展しており、おおむね順調に研究が進展していると判断している。
2年度目の研究を通して、当初目標を拡張した研究計画に沿って、さらに研究推進していく。その中で、エントロピー錐を量子計算的に理解する研究も進める。浅層回路については対数深さの回路独自に解ける問題とともに、それを古典計算とハイブリッド計算した場合の研究をスタートさせる。量子回路設計理論についても、将来の量子誤り訂正実現の観点からの研究に取り組む。 -
量子スプレマシーの理論研究
研究課題/研究課題番号：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. -
研究課題/研究課題番号：19H04066 2019年4月 - 2023年3月
科学研究費助成事業 基盤研究(B)
西村 治道, ルガル フランソワ, 森前 智行, Buscemi F.
担当区分：研究分担者
今日の量子計算量理論において，対話型証明の概念は非常に大きな存在となっている．一方で，近年その実装へ向けて社会的注目を集める量子コンピュータはまだ小規模であり，量子メモリや量子通信は依然として高コストである．この状況を鑑みて，本研究では量子計算や量子通信が制限された量子対話型証明や量子計算に動機づけられた古典対話型証明，さらにはその中間的な対話型証明モデルに着目し，それらの対話型証明モデルについての計算量理論を展開する．これにより量子コンピュータの検証問題に対する新しい解決法を提案し，既存の量子対話型証明モデルや量子多項式階層理論を俯瞰的に捉えることができるような包括的成果を得ることを目指す．
-
量子プロトコル理論の線的展開 国際共著
研究課題/研究課題番号：16H01705 2016年4月 - 2021年3月
日本学術振興会 科学研究費助成事業 基盤研究(A)
小柴 健史, 西村 治道, ルガル フランソワ, 田中 圭介, 河内 亮周, 安永 憲司, 松本 啓史, 堀山 貴史, 小林 弘忠
担当区分：研究分担者 資金種別：競争的資金
量子状態の初期化が容易でない量子計算を定式化したDQC1モデルなどの計算能力を究明することにより，万能でない量子計算モデルでさえ量子超越性を達成し得ることを示した。量子分散アルゴリズムに関しては，標準的な分散計算モデルにおいて「全対最短経路問題」などの幾つかの基本的問題について，古典プロトコルよりも効率的に動作する量子分散プロトコルを開発した。量子暗号プロトコルである秘匿代理量子計算において，古典クライアントでは，完全秘匿性を達成不可能であることを示した。量子性の古典的検証可能性に，報酬概念を導入することで，ゲーム理論的な形での解決という新しい方向性を見出した。
従来の量子アルゴリズムの研究は，古典的手法に対して量子的手法の優勢性を示すことが中心であった。本研究課題においては，汎用量子コンピュータより早期の実現可能性が高い計算モデルにおける量子超越性を示し，量子分散アルゴリズムという分野を新たに開拓し世界をリードする存在であり，量子計算という研究領域を拡大させている。その意味で学術的に大きく貢献していると考えられる。また，非万能量子計算や量子分散アルゴリズムにおける量子計算は比較的小規模であり，量子計算研究の現実的側面を強調するという意義もある。