Updated on 2025/04/10

写真a

 
LE GALL Francois Pierre Marcel
 
Organization
Graduate School of Mathematics Division of Mathematics Computational Mathematics Professor
Graduate School
Graduate School of Mathematics
Undergraduate School
School of Science Department of Mathematics
Title
Professor
Contact information
メールアドレス
External link

Degree 1

  1. Phd (Computer Science) ( 2006.3   The University of Tokyo ) 

Research Interests 4

  1. Quantum computing

  2. Computational complexity

  3. Distributed computing

  4. Algorithms

Research Areas 1

  1. Informatics / Theory of informatics

Current Research Project and SDGs 4

  1. Distributed Computing

  2. Quantum computing

  3. Computational Complexity

  4. Algorithms

Research History 5

  1. Nagoya University   Graduate School of Mathematics   Professor

    2022.4

  2. Nagoya University   Graduate School of Mathematics   Associate professor

    2019.10 - 2022.3

  3. Kyoto University   Graduate School of Informatics   Designated associate professor

    2016.4 - 2019.9

  4. The University of Tokyo   Graduate School of Information Science and Technology   Designated associate professor

    2012.4 - 2016.3

  5. The University of Tokyo   Graduate School of Information Science and Technology   Designated lecturer

    2009.4 - 2012.3

Professional Memberships 5

  1. INFORMATION PROCESSING SOCIETY OF JAPAN

  2. EATCS

  3. ACM SIGACT

  4. ACM

  5. 日本数学会

Committee Memberships 19

  1. Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)   Steering committee chair  

    2024.10 - 2025.9   

      More details

    Committee type:Academic society

  2.   Editorial board member  

    2023.1   

  3. Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)   Steering committee member  

    2022.10   

  4. 26th Conference on Quantum Information Processing (QIP 2023)   Program committee chair  

    2022.5 - 2023.2   

  5. ACM Transactions on Quantum Computing   Editorial board member  

    2019.6   

  6. Computational Complexity   Editorial board member  

    2016.6   

      More details

    Committee type:Academic society

  7. ACM-SIAM Symposium on Discrete Algorithms (SODA24)   Program Committee member  

    2024.2 - 2024.7   

      More details

    Committee type:Academic society

  8. 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)   Program Committee member  

    2024.2 - 2024.7   

      More details

    Committee type:Academic society

  9. 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)   Program Committee member  

    2024.2 - 2024.7   

      More details

    Committee type:Academic society

  10. ACM-SIAM Symposium on Discrete Algorithms (SODA24)   Program Committee member  

    2023.7 - 2024.1   

      More details

    Committee type:Academic society

  11.   組織委員  

    2023.4 - 2026.3   

      More details

    Committee type:Academic society

  12. 2023 Computational Complexity Conference (CCC 2023)   Program Committee member  

    2023.2 - 2023.7   

      More details

    Committee type:Academic society

  13. 2023 Computational Complexity Conference (CCC 2023)   Program Committee member  

    2023.2 - 2023.7   

  14. The International Symposium on Quantum Science, Technology and Innovation (Quantum Innovation)   組織委員  

    2023   

      More details

    Committee type:Government

  15. Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)   Steering committee member  

    2022.10   

  16. 26th Conference on Quantum Information Processing (QIP 2023)   Program committee chair  

    2022.5 - 2023.2   

  17. 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)   Program committee chair  

    2021.10 - 2022.7   

  18. 電子情報通信学会   コンピュテーション研究会専門委員  

    2016.6 - 2022.5   

      More details

    Committee type:Academic society

  19. 51st EATCS International Colloquium on Automata, Languages and Programming   Program Committee member  

       

      More details

    Committee type:Academic society

▼display all

Awards 2

  1. NISTEP Award 2017

    2017.11   MEXT  

    Francois Le Gall

  2. ISSAC 2014 Distinguished Paper Award

    2014.7   ACM-SIGAL  

 

Papers 51

  1. 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

     More details

    Publishing type:Part of collection (book)   Publisher:Society for Industrial and Applied Mathematics  

    DOI: 10.1137/1.9781611977912.133

  2. No Distributed Quantum Advantage for Approximate Graph Coloring. Reviewed

    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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1145/3618260.3649679

    Other Link: https://dblp.uni-trier.de/db/conf/stoc/stoc2024.html#Coiteux-RoyDGKG24

  3. Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture. Reviewed

    Sevag Gharibian, François Le Gall

    Proceedings of the 54th ACM Symposium on Theory of Computing (STOC 2022)     page: 19 - 32   2022

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1145/3519935.3519991

    Other Link: https://dblp.uni-trier.de/db/conf/stoc/stoc2022.html#GharibianG22

  4. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.ITCS.2021.28

    Other Link: https://dblp.uni-trier.de/db/conf/innovations/innovations2021.html#FraigniaudGNP21

  5. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1137/1.9781611976465.171

    Other Link: https://dblp.uni-trier.de/db/conf/soda/soda2021.html#Censor-HillelCG21

  6. 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.1

     More details

    Authorship:Corresponding author  

    DOI: 10.1007/s00037-025-00264-9

    Open Access

  7. 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

     More details

    Authorship:Lead author, Corresponding author  

    DOI: 10.1007/s00037-024-00262-3

    Open Access

  8. 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

     More details

    Authorship:Corresponding author  

  9. Prior entanglement exponentially improves one-server quantum private information retrieval for quantum messages Reviewed

    Seunghoan Song, François Le Gall, Masahito Hayashi

    EPJ Quantum Technology   Vol. 11 ( 1 )   2024.9

     More details

    Publishing type:Research paper (scientific journal)   Publisher:Springer Science and Business Media LLC  

    DOI: 10.1140/epjqt/s40507-024-00266-6

    Other Link: https://link.springer.com/article/10.1140/epjqt/s40507-024-00266-6/fulltext.html

  10. Quantum state synthesis: relation with decision complexity classes and impossibility of error reduction. Reviewed

    Hugo Delavenne, François Le Gall

    Quantum Information and Computation   Vol. 24 ( 9&10 ) page: 754 - 765   2024.9

     More details

    Publishing type:Research paper (scientific journal)  

    DOI: 10.26421/QIC24.9-10-3

  11. Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. Reviewed

    Sevag Gharibian, François Le Gall

    SIAM Journal on Computing   Vol. 52 ( 4 ) page: 1009 - 1038   2023.8

     More details

    Publishing type:Research paper (scientific journal)  

    DOI: 10.1137/22m1513721

    Other Link: https://dblp.uni-trier.de/db/journals/siamcomp/siamcomp52.html#GharibianG23

  12. Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. Reviewed

    François Le Gall, Saeed Seddighin

    Algorithmica   Vol. 85 ( 5 ) page: 1251 - 1286   2023.5

     More details

    Publishing type:Research paper (scientific journal)  

    DOI: 10.1007/s00453-022-01066-z

  13. 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

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.STACS.2023.42

    Other Link: https://dblp.uni-trier.de/db/conf/stacs/stacs2023.html#GallMN23

  14. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.MFCS.2023.63

    Other Link: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2023.html#GallMN23

  15. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.ICALP.2023.32

    Other Link: https://dblp.uni-trier.de/db/conf/icalp/icalp2023.html#CadeFGHGMW23

  16. Quantum Distributed Computing: Potential and Limitations (Invited Talk).

    François Le Gall

    OPODIS     page: 2 - 1   2023

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.OPODIS.2023.2

    Other Link: https://dblp.uni-trier.de/db/conf/opodis/opodis2023.html#Gall23

  17. 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

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.ITCS.2022.35

    Other Link: https://dblp.uni-trier.de/db/conf/innovations/innovations2022.html#Censor-HillelFG22

  18. Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. Reviewed

    François Le Gall, Saeed Seddighin

    Proceedings of the 13th Innovations in Theoretical Computer Science conference (ITCS 2022)     page: 97 - 23   2022

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.ITCS.2022.97

    Other Link: https://dblp.uni-trier.de/db/conf/innovations/innovations2022.html#GallS22

  19. Quantum approximate counting for Markov chains and collision counting. Reviewed

    Francois Le Gall, Iu-Iong Ng

    Quantum Information & Computation   Vol. 22 ( 15&16 ) page: 1261 - 1279   2022

     More details

    Publishing type:Research paper (scientific journal)  

    DOI: 10.26421/QIC22.15-16-1

  20. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.ISAAC.2022.6

    Other Link: https://dblp.uni-trier.de/db/conf/isaac/isaac2022.html#HasegawaG22

  21. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1007/978-3-031-20624-5_39

    Other Link: https://dblp.uni-trier.de/db/conf/latin/latin2022.html#GallS22

  22. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.DISC.2022.48

    Other Link: https://dblp.uni-trier.de/db/conf/wdag/disc2022.html#GallMN22

  23. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.MFCS.2021.59

    Other Link: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2021.html#HiraharaG21

  24. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.TQC.2021.10

    Other Link: https://dblp.uni-trier.de/db/conf/tqc/tqc2021.html#GallNY21

  25. 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

     More details

    Language:English   Publishing type:Research paper (scientific journal)  

    DOI: 10.26421/QIC21.15-16-1

  26. 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

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.ISAAC.2021.74

    Other Link: https://dblp.uni-trier.de/db/conf/isaac/isaac2021.html#HasegawaG21

  27. 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

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.ISAAC.2021.58

    Other Link: https://dblp.uni-trier.de/db/conf/isaac/isaac2021.html#GallM21

  28. 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

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.STACS.2020.23

    Web of Science

    Other Link: https://dblp.uni-trier.de/db/conf/stacs/stacs2020.html#IzumiGM20

  29. Barriers for Rectangular Matrix Multiplication.

    Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

    Electron. Colloquium Comput. Complex.   Vol. 27   page: 30 - 30   2020

     More details

    Publishing type:Research paper (scientific journal)  

    Other Link: https://dblp.uni-trier.de/db/journals/eccc/eccc27.html#ChristandlGLZ20

  30. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.MFCS.2020.53

    Other Link: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2020.html#JethwaniGS20

  31. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1007/978-3-030-58150-3_19

    Other Link: https://dblp.uni-trier.de/db/conf/cocoon/cocoon2020.html#MiyamotoIKG20

  32. On Distributed Listing of Cliques. Reviewed

    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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.1145/3382734.3405742

    Other Link: https://dblp.uni-trier.de/db/conf/podc/podc2020.html#Censor-HillelGL20

  33. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.DISC.2020.33

    Other Link: https://dblp.uni-trier.de/db/conf/wdag/disc2020.html#Censor-HillelFG20

  34. 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

     More details

    Publishing type:Research paper (international conference proceedings)  

    DOI: 10.4230/LIPIcs.DISC.2020.43

    Other Link: https://dblp.uni-trier.de/db/conf/wdag/disc2020.html#FraigniaudGNP20

  35. Finding Small and Large $k$-Clique Instances on a Quantum Computer Reviewed

    Sara Ayman Metwalli, Francois Le Gall, Rodney Van Meter

    IEEE Transactions on Quantum Engineering   Vol. 1   page: 1 - 11   2020

     More details

    Publishing type:Research paper (scientific journal)   Publisher:Institute of Electrical and Electronics Engineers (IEEE)  

    DOI: 10.1109/tqe.2020.3045692

  36. 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

     More details

    Publisher:Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik  

  37. 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

  38. Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model. Reviewed

    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

     More details

    Publisher:ACM  

    DOI: 10.1145/3293611.3331628

  39. 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

     More details

    Publisher:Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik  

  40. 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

     More details

  41. Generalized Quantum Arthur-Merlin Games. Reviewed

    Hirotada Kobayashi, François Le Gall, Harumichi Nishimura

    SIAM J. Comput.   Vol. 48 ( 3 ) page: 865 - 902   2019

  42. 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

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Association for Computing Machinery  

    In the past few years, successive improvements of the asymptotic complexity of square matrix multiplication have been obtained by developing novel methods to analyze the powers of the Coppersmith-Winograd tensor, a basic construction introduced thirty years ago. In this paper we show how to generalize this approach to make progress on the complexity of rectangular matrix multiplication as well, by developing a framework to analyze powers of tensors in an asymmetric way. By applying this methodology to the fourth power of the Coppersmith-Winograd tensor, we succeed in improving the complexity of rectangular matrix multiplication. Let denote the maximum value such that the product of an n n matrix by an n n matrix can be computed with O(n2+) arithmetic operations for any &gt
    0. By analyzing the fourth power of the Coppersmith-Winograd tensor using our methods, we obtain the new lower bound &gt
    0:31389, which improves the previous lower bound &gt
    0:30298 obtained by Le Gall (FOCS'12) from the analysis of the second power of the Coppersmith-Winograd tensor. More generally, we give faster algorithms computing the product of an n nk matrix by an nk n matrix for any value k 6= 1. (In the case k = 1, we recover the bounds recently obtained for square matrix multiplication). These improvements immediately lead to improvements in the complexity of a multitude of fundamental problems for which the bottleneck is rectangular matrix multiplication, such as computing the all-pair shortest paths in directed graphs with bounded weights.

    DOI: 10.1137/1.9781611975031.67

    Scopus

  43. Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. Reviewed

    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

     More details

  44. 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

     More details

    Publisher:Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik  

    DOI: 10.4230/LIPIcs.MFCS.2018.26

  45. Quantum Algorithm for Triangle Finding in Sparse Graphs Reviewed

    Francois Le Gall, Shogo Nakajima

    ALGORITHMICA   Vol. 79 ( 3 ) page: 941 - 959   2017.11

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:SPRINGER  

    This paper presents a quantum algorithm for triangle finding over sparse graphs that improves over the previous best quantum algorithm for this task by Buhrman et al. (SIAM J Comput 34(6):1324-1330, 2005). Our algorithm is based on the recent (O) over tilde (n(5/4))-query algorithm given by Le Gall (Proceedings of the 55th IEEE annual symposium on foundations of computer science, pp 216-225, 2014) for triangle finding over dense graphs (here n denotes the number of vertices in the graph). We show in particular that triangle finding can be solved with O(n(5/4-epsilon)) queries for some constant epsilon > 0 whenever the graph has at most O(n(2-c))edges for some constant c > 0.

    DOI: 10.1007/s00453-016-0267-z

    Web of Science

  46. 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

     More details

    Language:English   Publishing type:Research paper (scientific journal)   Publisher:RINTON PRESS, INC  

    It is known that the group non-membership problem is in QMA relative to any group oracle and in SPPnBQP for solvable groups. We consider a modified version of the group non-membership problem where the order of the group is also given as an additional input. We show that the problem is in (the promise version of) AWPP relative to any group oracle. To show the result, we use the idea of postselected quantum computing.

    Web of Science

    Other Link: http://dblp.uni-trier.de/db/journals/qic/qic17.html#journals/qic/MorimaeNG17

  47. 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

     More details

    Publisher:Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik  

    DOI: 10.4230/LIPIcs.TQC.2017.6

  48. Triangle Finding and Listing in CONGEST Networks. Reviewed

    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

     More details

  49. 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

     More details

    Language:English   Publishing type:Research paper (international conference proceedings)   Publisher:Springer Verlag  

    Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: given a black box implementing a quantum the promise that the black box implements either the unitary operator U:1 or the unitary operator U:2, the goal is to decide whether U=U:1 or U=U:2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded-error probability using (formula presented) \\right\\rceil queries to the black-box, where \\theta _\\mathrm{cover} represents the “closeness” between U:1 and U:2 (this parameter is determined by the eigenvalues of the matrix (formula presented). We also show that this upper bound is essentially tight: we prove that there exist operators U:1 and U:2 such that any quantum algorithm solving this problem with bounded-error probability requires at least (formula presented) queries.

    DOI: 10.1007/978-3-319-62389-4_26

    Scopus

  50. Quantum Algorithms for Matrix Products over Semirings. Reviewed

    François Le Gall, Harumichi Nishimura

    Chicago J. Theor. Comput. Sci.   Vol. 2017   2017

  51. 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

     More details

    Publisher:Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik  

    DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.41

▼display all

Presentations 21

  1. 量子アルゴリズムの現状と展望 Invited

    ムーンショット目標6 公開シンポジウム  2025.3.4 

     More details

    Event date: 2025.3

    Presentation type:Oral presentation (invited, special)  

  2. 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) 

     More details

    Event date: 2025.2

    Presentation type:Oral presentation (general)  

  3. Space-bounded quantum interactive proof systems International conference

    François Le Gall, Yupan Liu, Harumichi Nishimura and Qisheng Wang

     More details

    Event date: 2025.2

    Presentation type:Oral presentation (general)  

  4. Quantum Distributed Computing Invited International conference

    Francois Le Gall

    IHP Workshop: Quantum technologies for cryptography  2024.12.3 

     More details

    Event date: 2024.12

    Presentation type:Oral presentation (invited, special)  

  5. 量子アルゴリズム Invited

    ルガル フランソワ

    ムーンショット目標6 ミニシンポジウム2024 量子コンピュータは、未来をどう変えうるか ~FTQCとそこに至る過程で期待されるアプリケーション~  2024.10.1 

     More details

    Event date: 2024.10

  6. Online Locality Meets Distributed Quantum Computing Invited

    Francois Le Gall

    2024.9.26 

     More details

    Event date: 2024.9

  7. 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 

     More details

    Event date: 2024.9

  8. Theoretical Foundations of Quantum Advantage in Quantum Algorithms Invited

    Francois Le Gall

    Q2B 2024 Tokyo  2024.7.25 

     More details

    Event date: 2024.7

  9. Quantum distributed computing: potential and limitations Invited

    Le Gall Francois

    2023 CONFERENCE ON PRINCIPLES OF DISTRIBUTED SYSTEMS (OPODIS 2023)  2023.12.7 

     More details

    Event date: 2023.12

    Presentation type:Oral presentation (invited, special)  

  10. 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 

     More details

    Event date: 2023.11

    Language:English   Presentation type:Oral presentation (invited, special)  

  11. Theoretical Foundations of Quantum Advantage in Quantum Computing Invited

    Francois Le Gall

    京都大学基礎物理学研究所 創立70周年記念シンポジウム  2023.11.22 

     More details

    Event date: 2023.11

    Presentation type:Oral presentation (invited, special)  

  12. 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 

     More details

    Event date: 2023.9

    Presentation type:Oral presentation (invited, special)  

  13. 多人数の量子通信複雑性における新しい手法

    第47回量子情報技術研究会  2022.12.8 

     More details

    Event date: 2022.12

  14. Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

    第47回量子情報技術研究会  2022.12.8 

     More details

    Event date: 2022.12

  15. ガイド付きローカルハミルトニアン問題の計算複雑性の進展

    第47回量子情報技術研究会  2022.12.8 

     More details

    Event date: 2022.12

  16. Quantum Distributed Computing Invited

    Workshop on Advances in Distributed Graph Algorithms (ADGA 2022)  2022.10.24 

     More details

    Event date: 2022.10

  17. Theoretical Foundations of Quantum Advantage Invited

    Q2B 2022 Tokyo  2022.7.14 

     More details

    Event date: 2022.7

  18. 分散量子対話型証明

    第6回量子ソフトウェア研究会  2022.7.8 

     More details

    Event date: 2022.7

  19. Bounds on oblivious multiparty quantum communication complexity

    第6回量子ソフトウェア研究会  2022.7.8 

     More details

    Event date: 2022.7

  20. 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 

     More details

    Event date: 2021.12

    Language:English   Presentation type:Oral presentation (invited, special)  

  21. Tight Distributed Listing of Cliques Invited

    2021.3.8 

     More details

    Event date: 2021.3

▼display all

KAKENHI (Grants-in-Aid for Scientific Research) 9

  1. 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)

      More details

    Authorship:Principal investigator 

    Grant amount:\203450000 ( Direct Cost: \156500000 、 Indirect Cost:\46950000 )

  2. 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

      More details

    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.

  3. 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

      More details

    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.

  4. 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)

      More details

    Authorship:Coinvestigator(s)  Grant type:Competitive

  5. 量子アルゴリズムの理論と実装を接続する革新的基盤の創出

    Grant number:20H05966  2020.11 - 2025.3

    科学研究費助成事業  学術変革領域研究(A)

    山下 茂, 山本 直樹, ルガル フランソワ, 森 立平, 谷 誠一郎, 西村 治道

      More details

    Authorship:Coinvestigator(s) 

    量子計算各種モデルにおける計算能力の解析を行う理論的なアプローチと、実際に量子計算機を利用する実践的なアプローチの両面から以下の4項目の研究を行う。
    (A) 既存の量子計算モデルの結果を量子・古典協調の観点から、あるいは「弱い」量子計算モデルの観点から再検討・再構築する。
    (B) 量子計算に起こりうる現実的なエラーを考慮に入れた計算モデルの検討を進める。
    (C) 量子計算の方式に応じて異なる量子回路のモデルを量子・古典協調利用の枠組みの中で検討・評価する。
    (D) 量子計算と古典計算を協調して利用する計算アルゴリズムの能力を解析するための計算モデルを検討・評価する。

  6. 量子アルゴリズム・計算量・浅層回路と量子コンピュータ実機実験による量子優位性研究 International coauthorship

    Grant number:20H00579  2020.4 - 2025.3

    日本学術振興会  科学研究費助成事業  基盤研究(A)

    今井 浩, 山下 茂, ルガル フランソワ, Avis David

      More details

    Authorship:Coinvestigator(s)  Grant type:Competitive

    量子コンピュータの得意な問題を用いて量子計算優越性を達成したとGoogleの研究者らが主張したところである。しかし、その問題は実応用とは無縁であり、IT社会に多大なインパクトを与えるの量子素因数分解計算などの実機実装の研究が重要となっている。本研究では、量子計算が本研究グループの量子浅層回路の計算量理論・実機に対応する量子回路の設計理論・量子非局所性とその組み合わせ構造に着目することにより、理論的に真に高速と示すことができる量子優位性を有する問題の最先端を研究し、量子コンピュータ実機で実証する。このような取り組みで、量子優位性が直接的に実社会に影響を与える新たな問題群を見出す成果を目指す。
    3年度目の本研究では、量子優位性を示すことを、研究代表者のところで(1) 分散量子計算を量子機械学習においてスケールアップした実験を実施し、(2) 量子ランダムアクセス符号を拡張した量子緩和を用いた量子近似最適化法に関する研究を理論と実機での実験によって目指した。IBM Quantumの量子コンピュータでの計算も行うことによって、近未来の量子コンピュータの実用性を示す成果をあげることができた。これらの成果はIEEE Quantum Computing and Engineering (QCE) 2023に論文が採択され、(1)の量子機械学習に関する論文の方は、応用面が評価されて応用分野の最優秀論文賞を受賞した。予備的に400超量子ビットのマシンでの結果も得ている。(1)の分散量子計算に関する理論的な研究成果が、分担者のLe Gallによって量子分散対話証明の独自の枠組みの中で得られている。また、研究代表者のところの研究協力者との研究でも、量子ハイブリッドスキームの優位性についても量子計算量理論の観点から示されている。また、(2)の量子最適化での量子緩和の考えは、分担者のDavid Avisによる量子情報の多面体アプローチによる解析を行って得られた成果と、半定値緩和の適用可能性の面で関係している。量子回路設計では分担者の山下の方で、MPMCTゲートを用いた量子回路の最適化、さらに相対位相Toffoliゲートの量子回路設計において導入された相対位相をキャンセルする新方法を提案するなどの成果を上げることができた。
    分散量子機械学習の研究で、その応用面が評価されて、IEEE Quantum Comptuing and Engineeringの国際会議で応用分野での最優秀論文に選ばれている。応用面での量子優位性を示す研究の推進という観点からのもので、このように当初計画より先に進んでいる。
    2024年度には、1000量子ビットスケールの量子コンピュータ実機の利用も目指すとともに、量子分散計算がハードウェアの制約からモジュールを接続してスケールアップする方向での実験の研究にも取り組む予定である。理論面の成果とともに、量子優位性を応用・理論両面で示すことを目指す。

  7. Theoretical Research on Quantum Supremacy

    Grant number:19F19079  2019.7 - 2021.3

      More details

    Authorship:Other 

  8. 対話型証明の新展開-古典から量子まで

    Grant number:19H04066  2019.4 - 2023.3

    科学研究費助成事業  基盤研究(B)

    西村 治道, ルガル フランソワ, 森前 智行, Buscemi F.

      More details

    Authorship:Coinvestigator(s) 

    今日の量子計算量理論において,対話型証明の概念は非常に大きな存在となっている.一方で,近年その実装へ向けて社会的注目を集める量子コンピュータはまだ小規模であり,量子メモリや量子通信は依然として高コストである.この状況を鑑みて,本研究では量子計算や量子通信が制限された量子対話型証明や量子計算に動機づけられた古典対話型証明,さらにはその中間的な対話型証明モデルに着目し,それらの対話型証明モデルについての計算量理論を展開する.これにより量子コンピュータの検証問題に対する新しい解決法を提案し,既存の量子対話型証明モデルや量子多項式階層理論を俯瞰的に捉えることができるような包括的成果を得ることを目指す.

  9. 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

      More details

    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.

▼display all