Updated on 2026/03/31
Phd (Computer Science) （ 2006.3 The University of Tokyo ）
Quantum computing
Computational complexity
Distributed computing
Algorithms
Informatics / Information theory
Distributed Computing
Quantum computing
Computational Complexity
Algorithms
Nagoya University Graduate School of Mathematics Professor
2022.4
Nagoya University Graduate School of Mathematics Associate Professor
2019.10 - 2022.3
Kyoto University Graduate School of Informatics Designated Associate Professor
2016.4 - 2019.9
The University of Tokyo Graduate School of Information Science and Technology Designated Associate Professor
2012.4 - 2016.3
The University of Tokyo Graduate School of Information Science and Technology Designated Lecturer
2009.4 - 2012.3
ACM SIGACT
INFORMATION PROCESSING SOCIETY OF JAPAN
EATCS
ACM
日本数学会
Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) Steering committee chair
2024.10 - 2025.9
Committee type：Academic society
Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) Steering committee chair
2024.10 - 2025.9
Committee type：Academic society
Editorial board member
2023.1
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
Committee type：Academic society
ACM-SIAM Symposium on Discrete Algorithms (SODA24) Program Committee member
2024.2 - 2024.7
Committee type：Academic society
51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024) Program Committee member
2024.2 - 2024.7
Committee type：Academic society
51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024) Program Committee member
2024.2 - 2024.7
Committee type：Academic society
ACM-SIAM Symposium on Discrete Algorithms (SODA24) Program Committee member
2023.7 - 2024.1
Committee type：Academic society
組織委員
2023.4 - 2026.3
Committee type：Academic society
2023 Computational Complexity Conference (CCC 2023) Program Committee member
2023.2 - 2023.7
Committee type：Academic society
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
Committee type：Government
Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) Steering committee member
2022.10
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
Committee type：Academic society
51st EATCS International Colloquium on Automata, Languages and Programming Program Committee member
Committee type：Academic society
NISTEP Award 2017
2017.11 MEXT
Francois Le Gall
ISSAC 2014 Distinguished Paper Award
2014.7 ACM-SIGAL
Distributed Quantum Advantage for Local Problems Reviewed Open Access
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren
Proceedings of the 57th ACM Symposium on Theory of Computing (STOC 2025) page： 451 - 462 2025.6
Faster Rectangular Matrix Multiplication by Combination Loss Analysis Reviewed
François Le Gall
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) page： 3765 - 3791 2024.1
No Distributed Quantum Advantage for Approximate Graph Coloring. Reviewed Open Access
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) page： 1901 - 1910 2024
Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture. Reviewed Open Access
Sevag Gharibian, François Le Gall
Proceedings of the 54th ACM Symposium on Theory of Computing (STOC 2022) page： 19 - 32 2022
Distributed Quantum Proofs for Replicated Data. Reviewed
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
Proceedings of the 12th Innovations in Theoretical Computer Science conference (ITCS 2021) page： 28 - 20 2021
Tight Distributed Listing of Cliques. Reviewed
Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, Dean Leitersdorf
Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) page： 2878 - 2891 2021
A Simpler Approximation Algorithm for MAX-k-SAT Reviewed International coauthorship
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch and Suguru Tamaki
Proceedings of the 9th SIAM Symposium on Simplicity in Algorithms (SOSA 2026) page： 247 - 253 2026.1
Group Order is in QCMA Reviewed
François Le Gall, Harumichi Nishimura and Dhara Thakkar.
Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2025) page： 1128 - 1143 2025.12
Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians Reviewed Open Access
François Le Gall
Proceeding of the 2025 European Symposium on Algorithms (ESA 2025) page： 73:1 - 73:19 2025.9
Space-bounded quantum interactive proof systems Reviewed Open Access
François Le Gall, Yupan Liu, Harumichi Nishimura and Qisheng Wang
Proceedings of the 40th Computational Complexity Conference (CCC 2025) page： 17:1 - 17:18 2025.8
Beating the Natural Grover Bound for Low-Energy Estimation and State Preparation Reviewed International coauthorship Open Access
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
Physical Review Letters Vol. 135 ( 3 ) page： 030601 2025.7
Online Locality Meets Distributed Quantum Computing International coauthorship Open Access
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
Proceedings of the 57th ACM Symposium on Theory of Computing (STOC 2025) page： 1295 - 1306 2025.6
Quantum Merlin-Arthur proof systems for synthesizing quantum states Reviewed International coauthorship Open Access
Hugo Delavenne, François Le Gall, Yupan Liu, Masayuki Miyamoto
Quantum Vol. 9 ( 1688 ) page： 1 - 33 2025.4
Barriers for rectangular matrix multiplication Reviewed International coauthorship Open Access
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
Computational Complexity Vol. 34 ( 1 ) page： 4 - 4 2025.2
Robust Dequantization of the Quantum Singular Value Transformation and Quantum Machine Learning Algorithms Reviewed Open Access
François Le Gall
Computational Complexity, Vol. 34 ( 1 ) page： 2 - 2 2025.1
Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries Reviewed International coauthorship
François Le Gall, Oran Nadler, Harumichi Nishimura, Rotem Oshman
Proceedings of the 28th International Conference on Principles of Distributed Systems (OPODIS 2024) page： 34:1 - 34:20 2024.12
Seunghoan Song, François Le Gall, Masahito Hayashi
EPJ Quantum Technology Vol. 11 ( 1 ) 2024.9
Hugo Delavenne, François Le Gall
Quantum Information and Computation Vol. 24 ( 9&10 ) page： 754 - 765 2024.9
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. Reviewed Open Access
Sevag Gharibian, François Le Gall
SIAM Journal on Computing Vol. 52 ( 4 ) page： 1009 - 1038 2023.8
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. Reviewed Open Access
François Le Gall, Saeed Seddighin
Algorithmica Vol. 85 ( 5 ) page： 1251 - 1286 2023.5
Distributed Quantum Interactive Proofs. Reviewed
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) page： 42:1 - 42:21 2023
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications. Reviewed
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) page： 63 - 15 2023
Improved Hardness Results for the Guided Local Hamiltonian Problem. Reviewed
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) page： 32:1 - 32:19 2023
Quantum Distributed Computing: Potential and Limitations (Invited Talk).
François Le Gall
OPODIS page： 2 - 1 2023
Quantum Distributed Algorithms for Detection of Cliques. Reviewed
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) page： 35 - 25 2022
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. Reviewed Open Access
François Le Gall, Saeed Seddighin
Proceedings of the 13th Innovations in Theoretical Computer Science conference (ITCS 2022) page： 97 - 23 2022
An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes. Reviewed
Atsuya Hasegawa, François Le Gall
Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022) page： 6 - 14 2022
Bounds on Oblivious Multiparty Quantum Communication Complexity. Reviewed
François Le Gall, Daiki Suruga
Proceedings of the 15th Latin American Theoretical Informatics Symposium (LATIN 2022) page： 641 - 657 2022
Brief Announcement: Distributed Quantum Interactive Proofs. Reviewed
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
Proceedings of the 36th International Symposium on Distributed Computing (DISC 2022) page： 48 - 3 2022
Quantum approximate counting for Markov chains and collision counting. Reviewed Open Access
Francois Le Gall, Iu-Iong Ng
Quantum Information & Computation Vol. 22 ( 15&16 ) page： 1261 - 1279 2022
Quantum Logarithmic Space and Post-Selection. Reviewed
François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz
Proceedings of the 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) page： 10 - 17 2021
Test of Quantumness with Small-Depth Quantum Circuits. Reviewed
Shuichi Hirahara, François Le Gall
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) page： 59 - 15 2021
Quantum communication complexity of distribution testing. Reviewed
Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov
Quantum Information & Computation Vol. 21 ( 15&16 ) page： 1261 - 1273 2021
Quantum Advantage with Shallow Circuits Under Arbitrary Corruption. Reviewed
Atsuya Hasegawa, François Le Gall
Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021) page： 74 - 16 2021
Lower Bounds for Induced Cycle Detection in Distributed Computing. Reviewed
François Le Gall, Masayuki Miyamoto
Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2021) page： 58 - 19 2021
Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. Reviewed
Taisuke Izumi, François Le Gall, Frédéric Magniez
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) Vol. 154 page： 23 - 13 2020
Brief Announcement: Distributed Quantum Proofs for Replicated Data. Reviewed
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
Proceedings of the International Symposium on Distributed Computing (DISC 2020) page： 43 - 3 2020
Barriers for Rectangular Matrix Multiplication. Open Access
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam
Electron. Colloquium Comput. Complex. Vol. 27 page： 30 - 30 2020
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. Reviewed
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) page： 33 - 17 2020
Quantum-Inspired Classical Algorithms for Singular Value Transformation. Reviewed
Dhawal Jethwani, François Le Gall, Sanjay K. Singh
Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) page： 53 - 14 2020
Quantum Speedup for the Minimum Steiner Tree Problem. Reviewed
Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise, François Le Gall
Proceedings of the 26th International Computing and Combinatorics Conference (COCOON 2020) page： 234 - 245 2020
On Distributed Listing of Cliques. Reviewed Open Access
Keren Censor-Hillel, François Le Gall, Dean Leitersdorf
Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC 2020) page： 474 - 482 2020
Finding Small and Large $k$-Clique Instances on a Quantum Computer Reviewed Open Access
Sara Ayman Metwalli, Francois Le Gall, Rodney Van Meter
IEEE Transactions on Quantum Engineering Vol. 1 page： 1 - 11 2020
Quantum Advantage for the LOCAL Model in Distributed Computing. Reviewed
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 page： 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. Reviewed Open Access
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
SIAM J. Comput. Vol. 48 ( 3 ) page： 865 - 902 2019
Average-Case Quantum Advantage with Shallow Circuits. Reviewed
François Le Gall
34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA. page： 21:1-21:20 2019
Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model. Reviewed Open Access
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. page： 84 - 93 2019
Quantum Query Complexity of Unitary Operator Discrimination. Reviewed
Akinori Kawachi, Kenichi Kawano, Francois Le Gall, Suguru Tamaki
IEICE Transactions Vol. 102-D ( 3 ) page： 483 - 491 2019
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups. Reviewed
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 page： 26:1-26:13 2018
Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor Reviewed
François Le Gall, Florent Urrutia
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms page： 1029 - 1046 2018
Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. Reviewed Open Access
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 page： 337 - 346 2018
Quantum Algorithm for Triangle Finding in Sparse Graphs Reviewed Open Access
Francois Le Gall, Shogo Nakajima
ALGORITHMICA Vol. 79 ( 3 ) page： 941 - 959 2017.11
MODIFIED GROUP NON-MEMBERSHIP IS IN PROMISE-AWPP RELATIVE TO GROUP ORACLES Reviewed
Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall
QUANTUM INFORMATION & COMPUTATION Vol. 17 ( 3-4 ) page： 242 - 250 2017.3
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. Reviewed
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 page： 41:1-41:20 2017
Multiparty Quantum Communication Complexity of Triangle Finding. Reviewed
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 page： 6:1-6:11 2017
Quantum Algorithms for Matrix Products over Semirings. Reviewed
François Le Gall, Harumichi Nishimura
Chicago J. Theor. Comput. Sci. Vol. 2017 2017
Triangle Finding and Listing in CONGEST Networks. Reviewed Open Access
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 page： 381 - 389 2017
Quantum query complexity of unitary operator discrimination Reviewed
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) Vol. 10392 page： 309 - 320 2017
Dequantization and Hardness of Spectral Sum Estimation International coauthorship International conference
Roman Edenhofer, Atsuya Hasegawa and François Le Gall
29th Annual Quantum Information Processing Conference (QIP 2026) 2026.1.28
Distributed Quantum Advantage for Local Problems International coauthorship International conference
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, Isadora Veeren
29th Annual Quantum Information Processing Conference (QIP 2026) 2026.1.28
Group Order is in QCMA International conference
François Le Gall, Harumichi Nishimura and Dhara Thakkar
Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2025) 2026.1.28
Recent developments in quantum distributed computing Invited International coauthorship International conference
Francois Le Gall
39th International Symposium on Distributed Computing 2025.10.27
量子アルゴリズムの現状と展望 Invited
ムーンショット目標6 公開シンポジウム 2025.3.4
Beating Grover search for low-energy estimation and state preparation International coauthorship International conference
Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch and Suguru Tamaki
28th Quantum Information Processing Conference (QIP2025)
Space-bounded quantum interactive proof systems
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
28th Quantum Information Processing Conference (QIP2025)
Quantum Distributed Computing Invited International conference
Francois Le Gall
IHP Workshop: Quantum technologies for cryptography 2024.12.3
量子アルゴリズム Invited
ルガル フランソワ
ムーンショット目標6 ミニシンポジウム2024 量子コンピュータは、未来をどう変えうるか ～FTQCとそこに至る過程で期待されるアプリケーション～ 2024.10.1
Online Locality Meets Distributed Quantum Computing Invited
Francois Le Gall
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 Invited
Francois Le Gall
Q2B 2024 Tokyo 2024.7.25
Quantum distributed computing: potential and limitations Invited
Le Gall Francois
2023 CONFERENCE ON PRINCIPLES OF DISTRIBUTED SYSTEMS (OPODIS 2023) 2023.12.7
Quantum Algorithms: Applications and Theoretical Foundations Invited
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 Invited
Francois Le Gall
京都大学基礎物理学研究所 創立70周年記念シンポジウム 2023.11.22
Theoretical Foundations of Quantum Advantage for Quantum Algorithms Invited
Francois Le Gall
YIPQS long-term workshop Quantum Information, Quantum Matter and Quantum Gravity 2023.9.20
多人数の量子通信複雑性における新しい手法
第47回量子情報技術研究会 2022.12.8
ガイド付きローカルハミルトニアン問題の計算複雑性の進展
第47回量子情報技術研究会 2022.12.8
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
第47回量子情報技術研究会 2022.12.8
Quantum Distributed Computing Invited
Workshop on Advances in Distributed Graph Algorithms (ADGA 2022) 2022.10.24
Theoretical Foundations of Quantum Advantage Invited
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 Invited International conference
François Le Gall
Quantum Innovation 2021, the International Symposium on Quantum Science, Technology and Innovation 2021.12.9
Tight Distributed Listing of Cliques Invited
2021.3.8
Quantum Distributed Computing Invited
IHP Workshop: Quantum technologies for cryptography 2024.12.3
量子アルゴリズムの現状と展望 Invited
Francois Le Gall
ムーンショット目標6 公開シンポジウム2025 2025.3.4
Foundations of Secure Distributed Quantum Computing on Medium-Scale Quantum Computers
Grant number：24H00071 2024.4 - 2029.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (S)
Authorship：Principal investigator
Grant amount：\203450000 （ Direct Cost: \156500000 、 Indirect Cost：\46950000 ）
Quantum Algorithms for Large-Scale Quantum Computers: New Horizons and Applications International coauthorship
Grant number：20H04139 2020.4 - 2024.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (B)
Le Gall Francois
Authorship：Principal investigator Grant type：Competitive
Grant amount：\17290000 （ Direct Cost: \13300000 、 Indirect Cost：\3990000 ）
We investigated the computational power and the applications of large-scale quantum computers. We first rigorously established a quantum advantage (i.e., showed that quantum computers can be faster than supercomputers) for fundamental problems such as high-precision chemistry calculations. We developed several fast quantum distributed algorithms and proved a quantum advantage for distributed computing as well. We also investigated the potential of shallow (i.e., low depth) quantum circuits and demonstrated that they can be significantly more powerful than classical shallow circuits.
Algebraic Complexity Theory: New Approaches and Algorithmic Applications International coauthorship
Grant number：16H05853 2016.4 - 2020.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Young Scientists (A)
Le Gall Francois
Authorship：Principal investigator Grant type：Competitive
Grant amount：\12480000 （ Direct Cost: \9600000 、 Indirect Cost：\2880000 ）
In this research project we developed new techniques based on algebraic complexity theory to solve problems from theoretical computer science. Our main achievements are as follows.
We first developed new approaches to solve algebraic problems, and constructed faster algorithms for rectangular matrix multiplication. We then showed how to apply in a novel way algebraic techniques to several problems from computer science. In particular, via this approach we designed fast distributed algorithms for various computational problems over networks. Finally, we designed several quantum algorithms for graph problems that are faster than the best known algorithms.
Grant number：25K24465 2025.12 - 2032.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Fund for the Promotion of Joint International Research (International Leading Research )
Authorship：Coinvestigator(s)
Construction of Quantum Computaional Infrastracture towards Quantum Information Society International coauthorship
Grant number：21H04879 2021.4 - 2026.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
Authorship：Coinvestigator(s) Grant type：Competitive
Grant number：20H05966 2020.11 - 2025.3
科学研究費助成事業 学術変革領域研究(A)
山下 茂, 山本 直樹, ルガル フランソワ, 森 立平, 谷 誠一郎, 西村 治道
Authorship：Coinvestigator(s)
量子計算各種モデルにおける計算能力の解析を行う理論的なアプローチと、実際に量子計算機を利用する実践的なアプローチの両面から以下の4項目の研究を行う。
(A) 既存の量子計算モデルの結果を量子・古典協調の観点から、あるいは「弱い」量子計算モデルの観点から再検討・再構築する。
(B) 量子計算に起こりうる現実的なエラーを考慮に入れた計算モデルの検討を進める。
(C) 量子計算の方式に応じて異なる量子回路のモデルを量子・古典協調利用の枠組みの中で検討・評価する。
(D) 量子計算と古典計算を協調して利用する計算アルゴリズムの能力を解析するための計算モデルを検討・評価する。
量子アルゴリズム・計算量・浅層回路と量子コンピュータ実機実験による量子優位性研究 International coauthorship
Grant number：20H00579 2020.4 - 2025.3
日本学術振興会 科学研究費助成事業 基盤研究(A)
今井 浩, 山下 茂, ルガル フランソワ, Avis David
Authorship：Coinvestigator(s) Grant type：Competitive
量子コンピュータの得意な問題を用いて量子計算優越性を達成したとGoogleの研究者らが主張したところである。しかし、その問題は実応用とは無縁であり、IT社会に多大なインパクトを与えるの量子素因数分解計算などの実機実装の研究が重要となっている。本研究では、量子計算が本研究グループの量子浅層回路の計算量理論・実機に対応する量子回路の設計理論・量子非局所性とその組み合わせ構造に着目することにより、理論的に真に高速と示すことができる量子優位性を有する問題の最先端を研究し、量子コンピュータ実機で実証する。このような取り組みで、量子優位性が直接的に実社会に影響を与える新たな問題群を見出す成果を目指す。
今年度の本研究においては、量子コンピュータ実機を用いた研究に関して新たに東京農工大白樫教授と連携をすることによって、従来の実機実験アプローチを引き続き156量子ビットのIBM量子コンピュータの実機を用いて遂行することができている。この量子コンピュータのノイズ低減等の効果もあり、量子変分計算においての新手法の有効性を示すこともでき、また量子近似最適化法を量子アニーリングの古典シミュレーション計算システムとの比較を行って、それぞれの利点を理解することができている。また、それに関係して、比較対象として量子アニーリングに通じるイジングマシンに関する研究も行い、部分グラフ同型問題を用いて量子コンパイラへの応用を行い、その有効性を示した。
研究グループ全体では、引き続き量子回路設計に関して、相対位相Toffoliゲートの利用した量子回路設計の論文を発表することができ、さらにルックアップテーブルを用いた手法でのTゲート数の縮小について成果をあげることもできた。量子分散計算での量子優位性が成り立たないクラスとして、近似グラフ採食の問題があることを明らかにした。量子計算量の観点からも、量子合成を判定計算量とエラー緩和の関係を通して成果をあげている。古典・量子両面からの研究として、量子特異値分解そして量子機械学習に関しての脱量子化を行い、古典計算の応用可能性についても調べる新たな展開をはかることができた。量子ホログラフィック錐に関する多面体理論からの解析についても、まとめた成果の講演を行うことができている。
全体として、量子コンピュータ実機を用いた研究と、量子回路設計・量子計算量理論の両面からの研究を推進することができた。
量子コンピュータ実機を用いた研究については、順調に独自の成果を得られている。量子コンピュータのモジュール化を通して大規模化をはかるアプローチがとられている中、そこに分散量子計算の知見を適用する方向も見えてきている。これらをベースとして、数種類の量子コンピュータが開発されてきた現状に対して、現在利用しているマシンの有効性をさらに調べていく研究も計画している。
さらに量子コンピュータ実機を用いた実験を行い、近い将来に利用可能となるモジュール化を通した分散量子計算において、古典計算に対する優位性を調べ、古典・量子の両方向変換の有効性についての理論からの研究に取り組む。計算量理論を深化させることで、の古典・量子の両面からの解析を行う。
Theoretical Research on Quantum Supremacy
Grant number：19F19079 2019.7 - 2021.3
Authorship：Other
Grant number：19H04066 2019.4 - 2023.3
科学研究費助成事業 基盤研究(B)
西村 治道, ルガル フランソワ, 森前 智行, Buscemi F.
Authorship：Coinvestigator(s)
今日の量子計算量理論において，対話型証明の概念は非常に大きな存在となっている．一方で，近年その実装へ向けて社会的注目を集める量子コンピュータはまだ小規模であり，量子メモリや量子通信は依然として高コストである．この状況を鑑みて，本研究では量子計算や量子通信が制限された量子対話型証明や量子計算に動機づけられた古典対話型証明，さらにはその中間的な対話型証明モデルに着目し，それらの対話型証明モデルについての計算量理論を展開する．これにより量子コンピュータの検証問題に対する新しい解決法を提案し，既存の量子対話型証明モデルや量子多項式階層理論を俯瞰的に捉えることができるような包括的成果を得ることを目指す．
Interpolative Expansion of Quantum Protocol Theory International coauthorship
Grant number：16H01705 2016.4 - 2021.3
Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (A)
Takeshi Koshiba
Authorship：Coinvestigator(s) Grant type：Competitive
The computational power of the DQC1 model, which is a formalization of non-universal quantum computation with initialization-hard quantum states, is shown to be superior to classical computation. Many quantum distributed algorithms are developed. Under the standard model for distributed algorithms, efficient quantum protocols for several fundamental problems such as the shortest path problem. Secure quantum delegated computation cannot achieve the perfect security for classical clients. By introducing the notion of rewards in quantum computations, classical verification of having the quantum power of the server is affirmatively settled. This is a game-theoretic solution and gives a novel method in quantum computation.
