Frédéric Magniez

CNRS Research Director



 

In short

I have been a CNRS researcher since 2000, holding the position of Research Director since 2009 (equivalent to a full professor in research and PhD supervision, but without formal teaching duties). My research focuses on the design of algorithms, whether randomized or quantum, as well as the study of their limitations.

I was also professor at the École Polytechnique from 2003 to 2015, deputy director of the Fondation des Sciences Mathématiques de Paris from 2015 to 2018, professor at the Collège de France from 2020 to 2021 to teach quantum algorithms, and director of the Institut de Recherche en Informatique Fondamentale from 2018 to 2022. Since 2025, I have led the consortium for Quantum Technologies at Paris Cité and Sorbonne Paris Nord.

Former student of the Ecole Normale Supérieure de Cachan, Frédéric Magniez is graduated both in mathematics (agrégation) and computer science (PhD). His PhD thesis was awarded by the Association Française d’Informatique Théorique in 2000. He then became a CNRS researcher and worked at the Université Paris Sud, before joining the Institut de Recherche en Informatique Fondamentale (IRIF) at the Université Paris Cité in 2010. His research focuses on the design and analysis of randomized algorithms for processing large data sets, as well as the development of quantum computing, particularly algorithms, cryptography and its interactions with physics.

Professor at the École Polytechnique from 2003 to 2015, Frédéric Magniez co-initiated the first course dedicated to quantum computing of the institution. In 2006, he founded and led the national working group for quantum computing, that currently brings together 20 research groups. From 2013 to 2017, he ran the Algorithms and Complexity group, whose research in algorithmics and quantum computing is recognized worldwide. In 2015, he became Deputy Director of the Fondation des Sciences Mathématiques de Paris, before taking over as Director of IRIF in 2018 until 2022. Professor at the Collège de France from 2020 to 2021, holder of the Annual Chair in Informatics and Digital Sciences, he taught quantum algorithms. Since 2025, he has led the consortium for Quantum Technologies at Paris Cité and Sorbonne Paris Nord.

Main research

Topics Groups

Current academic services

Teaching Research projects Responsibilities Committees

Publications

External sources

Books and book chapters

[B3]

F. Magniez. Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing. Leçons inaugurales du Collège de France 303. 80 pages. Collège de France / Fayard, Nov. 2021. isbn: 978-2-213-72130-9.

[B2]

I. Kerenidis, F. Magniez, and D. Xiao. Complexité de communication. In: Informatique Mathématique - Une photographie en 2014. Presses Universitaires de Perpignan, 2014. isbn: 978-2-35412-228-7.

[B1]

M. Kiwi, F. Magniez, and M. Santha. Exact and approximate testing/correcting of algebraic functions: A survey. In: Proceedings of 1st Summer School on Theoretical Aspects of Computer Science. Also ECCC Report TR01-014. 2000, pp. 30–83. doi: 10.1007/3-540-45878-6_2.

Journals

[J28]

Y. Hamoudi and F. Magniez. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. In: ACM Transactions on Computation Theory 15.1-2 (2023). doi: 10.1145/3589986.

[J27]

F. Magniez and A. Nayak. Quantum Distributed Complexity of Set Disjointness on a Line. In: ACM Transactions on Computation Theory 14.1 (2022), pp. 1–22. doi: 10.1145/3512751.

[J26]

T. Carette, M. Laurière, and F. Magniez. Extended Learning Graphs for Triangle Finding. In: Algorithmica 82 (2020), pp. 980–1005. doi: 10.1007/s00453-019-00627-z.

[J25]

L. Boczkowski, I. Kerenidis, and F. Magniez. Streaming Communication Protocols. In: ACM Transactions on Computation Theory 10.4 (2018), 19:1–19:21. doi: 10.1145/3276748.

[J24]

S. Jeffery, F. Magniez, and R. de Wolf. Optimal parallel quantum query algorithms. In: Algorithmica 79.2 (2017), pp. 509–529. doi: 10.1007/s00453-016-0206-z.

[J23]

T. Lee, F. Magniez, and M. Santha. Improved quantum query algorithms for triangle finding and associativity testing. In: Algorithmica 77.2 (2017), pp. 459–486. doi: 10.1007/s00453-015-0084-9.

[J22]

S. Jeffery, R. Kothari, F. Le Gall, and F. Magniez. Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. In: Algorithmica 76.1 (2016), pp. 1–16. doi: 10.1007/s00453-015-9985-x.

[J21]

H. Krovi, F. Magniez, M. Ozols, and J. Roland. Quantum walks can find a marked element on any graph. In: Algorithmica 74.2 (2016), pp. 851–907. doi: 10.1007/s00453-015-9979-8.

[J20]

F. Magniez, A. Nayak, M. Santha, J. Sherman, G. Tardos, and D. Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. In: Random Structures & Algorithms 48.3 (2016), pp. 612–638. doi: 10.1002/rsa.20598.

[J19]

K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen. Hidden translation and orbit coset in quantum computing. In: SIAM Journal on Computing 43.1 (2014), pp. 1–24. doi: 10.1137/130907203.

[J18]

F. Magniez, C. Mathieu, and A. Nayak. Recognizing well-parenthesized expressions in the streaming model. In: SIAM Journal on Computing 43 (6 2014), pp. 1880–1905. doi: 10.1137/130926122.

[J17]

C. Konrad and F. Magniez. Validating XML documents in the streaming model with external memory. In: ACM Transactions on Database Systems 38.4 (2013). Special issue of ICDT’12, p. 27. doi: 10.1145/2504590.

[J16]

T. Lee, F. Magniez, and M. Santha. A learning graph based quantum query algorithm for finding constant-size subgraphs. In: Chicago Journal of Theoretical Computer Science 10 (2012). doi: 10.4086/cjtcs.2012.010.

[J15]

F. Magniez, A. Nayak, P. Richter, and M. Santha. On the hitting times of quantum versus random walks. In: Algorithmica 63.1 (2012), pp. 91–116. doi: 10.1007/s00453-011-9521-6.

[J14]

F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. In: SIAM Journal on Computing 40.1 (2011), pp. 142–164. doi: 10.1137/090745854.

[J13]

E. Fischer, F. Magniez, and M. de Rougemont. Approximate satisfiability and equivalence. In: SIAM Journal on Computing 39.6 (2010), pp. 2251–2281. doi: 10.1137/070703776.

[J12]

L. Magnin, F. Magniez, A. Leverrier, and N. Cerf. Strong no-go theorem for gaussian quantum bit commitment. In: Physical Review A 81.1 (2010), 010302(R). doi: 10.1103/PhysRevA.81.010302.

[J11]

K. Friedl, F. Magniez, M. Santha, and P. Sen. Quantum testers for hidden group properties. In: Fundamenta Matematicae 91.2 (2009). Special issue on Machines on Computations and Universality, pp. 325–340. doi: 10.3233/FI-2009-0046.

[J10]

S. Laplante and F. Magniez. Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In: SIAM Journal on Computing 38.1 (2008), pp. 46–62. doi: 10.1137/050639090.

[J9]

W. van Dam, F. Magniez, M. Mosca, and M. Santha. Self-testing of universal and fault-tolerant sets of quantum gates. In: SIAM Journal on Computing 37.2 (2007), pp. 611–629. doi: 10.1137/S0097539702404377.

[J8]

S. Laplante, R. Lassaigne, F. Magniez, S. Peyronnet, and M. de Rougemont. Probabilistic abstraction for model checking: An approach based on property testing. In: ACM Transactions on Computational Logic 8.4 (2007), p. 20. doi: 10.1145/1276920.1276922.

[J7]

F. Magniez and A. Nayak. Quantum complexity of testing group commutativity. In: Algorithmica 48.3 (2007), pp. 221–232. doi: 10.1007/s00453-007-0057-8.

[J6]

F. Magniez and M. de Rougemont. Property testing of regular tree languages. In: Algorithmica 49.2 (2007), pp. 127–146. doi: 10.1007/s00453-007-9028-3.

[J5]

F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. In: SIAM Journal on Computing 37.2 (2007), pp. 413–424. doi: 10.1137/050643684.

[J4]

H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and R. de Wolf. Quantum algorithms for element distinctness. In: SIAM Journal on Computing 34.6 (2005), pp. 1324–1330. doi: 10.1137/S0097539702402780.

[J3]

F. Magniez. Multi-linearity self-testing with relative error. In: Theory of Computing Systems 38.5 (2005), pp. 573–591. doi: 10.1007/s00224-004-1125-y.

[J2]

G. Ivanyos, F. Magniez, and M. Santha. Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem. In: International Journal of Foundations of Computer Science 14.5 (2003), pp. 723–740. doi: 10.1142/S0129054103001996.

[J1]

M. Kiwi, F. Magniez, and M. Santha. Approximate testing with error relative to input size. In: Journal of Computer and System Sciences 66.2 (2003), pp. 371–392. doi: 10.1016/S0022-0000(03)00004-7.

Proceedings

[P40]

F. Dufoulon, F. Magniez, and G. Pandurangan. Quantum Communication Advantage for Leader Election and Agreement. In: Proceedings of 44th ACM Symposium on Principles of Distributed Computing. To appear. 2025.

[P39]

P. Fraigniaud, M. Luce, F. Magniez, and I. Todinca. Deterministic Even-Cycle Detection in Broadcast CONGEST. In: Proceedings of 52nd International Colloquium on Automata, Languages and Programming. To appear. 2025.

[P38]

P. Fraigniaud, M. Luce, F. Magniez, and I. Todinca. Even-Cycle Detection in the Randomized and Quantum CONGEST Model. In: Proceedings of 43rd ACM Symposium on Principles of Distributed Computing. 2024, pp. 209–219. doi: 10.1145/3662158.3662767.

[P37]

Y. Hamoudi and F. Magniez. Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs. In: Proceedings of 16th Conference on the Theory of Quantum Computation, Communication and Cryptography. TQC Outstanding Paper Prize. 2021, 1:1–1:21. doi: 10.4230/LIPIcs.TQC.2021.1.

[P36]

T. Izumi, F. Le Gall, and F. Magniez. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In: Proceedings of 37th International Symposium on Theoretical Aspects of Computer Science. Also presented at TQC’20. 2020, 23:1–23:13. doi: 10.4230/LIPIcs.STACS.2020.23.

[P35]

F. Magniez and A. Nayak. Quantum Distributed Complexity of Set Disjointness on a Line. In: Proceedings of 47th International Colloquium on Automata, Languages and Programming. 2020, 82:1–82:18. doi: 10.4230/LIPIcs.ICALP.2020.82.

[P34]

Y. Hamoudi and F. Magniez. Quantum Chebyshev’s Inequality and Applications. In: Proceedings of 46th International Colloquium on Automata, Languages and Programming. 2019, 69:1–69:16. doi: 10.4230/LIPIcs.ICALP.2019.69.

[P33]

E. Fischer, F. Magniez, and T. Starikovskaya. Improved bounds for testing Dyck languages. In: Proceedings of 29th ACM-SIAM Symposium on Discrete Algorithms. 2018, pp. 1529–1544. doi: 10.1137/1.9781611975031.100.

[P32]

F. Le Gall and F. Magniez. Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks. In: Proceedings of 37th ACM Symposium on Principles of Distributed Computing. Also presented at QIP’19 as a contributed talk. 2018, pp. 337–346. doi: 10.1145/3212734.3212744.

[P31]

L. Boczkowski, I. Kerenidis, and F. Magniez. Streaming Communication Protocols. In: Proceedings of 44th International Colloquium on Automata, Languages, and Programming. 2017, 130:1–130:14. doi: 10.4230/LIPIcs.ICALP.2017.130.

[P30]

T. Carette, M. Laurière, and F. Magniez. Extended Learning Graphs for Triangle Finding. In: Proceedings of 34th International Symposium on Theoretical Aspects of Computer Science. 2017, 20:1–20:14. doi: 10.4230/LIPIcs.STACS.2017.20.

[P29]

N. François, F. Magniez, M. de Rougemont, and O. Serre. Streaming Property Testing of Visibly Pushdown Languages. In: Proceedings of 24rd European Symposium on Algorithms. 2016, 43:1–43:17. doi: 10.4230/LIPIcs.ESA.2016.43.

[P28]

V. Kanade, N. Leonardos, and F. Magniez. Stable Matching with Evolving Preferences. In: Proceedings of 20th International Workshop on Randomization and Computation. 2016, 36:1–36:13. doi: 10.4230/LIPIcs.APPROX-RANDOM.2016.36.

[P27]

N. François, R. Jain, and F. Magniez. Unidirectional Input/Output Streaming Complexity of Reversal and Sorting. In: Proceedings of 18th International Workshop on Randomization and Computation. 2014, pp. 654–668. doi: 10.4230/LIPIcs.APPROX-RANDOM.2014.654.

[P26]

S. Jeffery, F. Magniez, and R. de Wolf. Optimal parallel quantum query algorithms. In: Proceedings of 22nd European Symposium on Algorithms. 2014, pp. 592–604. doi: 10.1007/978-3-662-44777-2_49.

[P25]

A. Belovs, A. Childs, S. Jeffery, R. Kothari, and F. Magniez. Time-Efficient Quantum Walks for 3-Distinctness. In: Proceedings of 40th International Colloquium on Automata, Languages and Programming. Also presented at QIP’14 as a contributed talk. 2013, pp. 105–122. doi: 10.1007/978-3-642-39206-1_10.

[P24]

N. François and F. Magniez. Streaming complexity of checking priority queues. In: Proceedings of 30th Symposium on Theoretical Aspects of Computer Science. 2013, pp. 454–465. doi: 10.4230/LIPIcs.STACS.2013.454.

[P23]

S. Jeffery, R. Kothari, and F. Magniez. Nested quantum walks with quantum data structures. In: Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms. Also presented at QIP’14 as a contributed talk. 2013, pp. 1474–1485. doi: 10.1137/1.9781611973105.106.

[P22]

T. Lee, F. Magniez, and M. Santha. Improved quantum query algorithms for triangle finding and associativity testing. In: Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms. Also presented at QIP’13 as a contributed talk. 2013, pp. 1486–1502. doi: 10.1137/1.9781611973105.107.

[P21]

S. Jeffery, R. Kothari, and F. Magniez. Improving quantum query complexity of boolean matrix multiplication using graph collision. In: Proceedings of 39th International Colloquium on Automata, Languages and Programming. 2012, pp. 522–532. doi: 10.1007/978-3-642-31594-7_44.

[P20]

C. Konrad and F. Magniez. Validating XML documents in the streaming model with external memory. In: Proceedings of 15th International Conference on Database Theory. Best Newcomer Paper. 2012, pp. 34–45. doi: 10.1145/2274576.2274581.

[P19]

C. Konrad, F. Magniez, and C. Mathieu. Maximum matching in semi-streaming with few passes. In: Proceedings of 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Full version on arXiv. 2012, pp. 231–242. doi: 10.1007/978-3-642-32512-0_20. arXiv: 1112.0184.

[P18]

F. Magniez, A. Nayak, M. Santha, and D. Xiao. Improved bounds for the randomized decision tree complexity of recursive majority. In: Proceedings of 38th International Colloquium on Automata, Languages and Programming. 2011, pp. 317–329. doi: 10.1007/978-3-642-22006-7_27.

[P17]

F. Magniez, M. de Rougemont, M. Santha, and X. Zeitoun. The complexity of approximate Nash equilibrium in congestion games with negative delays. In: Proceedings of 7th Workshop on Internet & Network Economics. 2011, pp. 266–277. doi: 10.1007/978-3-642-25510-6_23.

[P16]

H. Krovi, F. Magniez, M. Ozols, and J. Roland. Finding is as easy as detecting for quantum walks. In: Proceedings of 37th International Colloquium on Automata, Languages and Programming. Also presented at QIP’11 as a featured talk. 2010, pp. 540–551. doi: 10.1007/978-3-642-14165-2_46.

[P15]

F. Magniez, C. Mathieu, and A. Nayak. Recognizing well-parenthesized expressions in the streaming model. In: Proceedings of 42nd ACM Symposium on Theory of Computing. 2010, pp. 261–270. doi: 10.1145/1806689.1806727.

[P14]

F. Magniez, A. Nayak, P. Richter, and M. Santha. On the hitting times of quantum versus random walks. In: Proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms. 2009, pp. 86–95. doi: 10.1137/1.9781611973068.10.

[P13]

F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. In: Proceedings of 39th ACM Symposium on Theory of Computing. Also presented at QIP’07 as a contributed talk. 2007, pp. 575–584. doi: 10.1145/1250790.1250874.

[P12]

E. Fischer, F. Magniez, and M. de Rougemont. Approximate satisfiability and equivalence. In: Proceedings of 21st IEEE Symposium on Logic in Computer Science. 2006, pp. 421–430. doi: 10.1109/LICS.2006.12.

[P11]

F. Magniez, D. Mayers, M. Mosca, and H. Ollivier. Self-testing of quantum circuits. In: Proceedings of 33rd International Colloquium on Automata, Languages and Programming. Also presented at QIP’06 as a contributed talk. 2006, pp. 72–83. doi: 10.1007/11786986_8.

[P10]

F. Magniez and A. Nayak. Quantum complexity of testing group commutativity. In: Proceedings of 32nd International Colloquium on Automata, Languages and Programming. 2005, pp. 1312–1324. doi: 10.1007/11523468_106.

[P9]

F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. In: Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms. Also presented at QIP’04 as an invited talk. 2005, pp. 1109–1117.

[P8]

S. Laplante and F. Magniez. Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In: Proceedings of 19th IEEE Conference on Computational Complexity. 2004, pp. 214–304. doi: 10.1109/CCC.2004.1313852.

[P7]

F. Magniez and M. de Rougemont. Property testing of regular tree languages. In: Proceedings of 31st International Colloquium on Automata, Languages and Programming. 2004, pp. 932–944. doi: 10.1109/LICS.2006.12.

[P6]

K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen. Hidden translation and orbit coset in quantum computing. In: Proceedings of 35th ACM Symposium on Theory of Computing. Also presented at QIP’03 as an invited talk. 2003, pp. 1–9. doi: 10.1145/780542.780544.

[P5]

K. Friedl, F. Magniez, M. Santha, and P. Sen. Quantum testers for hidden group properties. In: Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science. 2003, pp. 419–428. doi: 10.1007/978-3-540-45138-9_36.

[P4]

S. Laplante, R. Lassaigne, F. Magniez, S. Peyronnet, and M. de Rougemont. Probabilistic abstraction for model checking: An approach based on property testing. In: Proceedings of 17th IEEE Symposium on Logic in Computer Science. 2002, pp. 30–39. doi: 10.1109/LICS.2002.1029815.

[P3]

H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and R. de Wolf. Quantum algorithms for element distinctness. In: Proceedings of 15th IEEE Conference on Computational Complexity. 2001, pp. 131–137. doi: 10.1109/CCC.2001.933880.

[P2]

G. Ivanyos, F. Magniez, and M. Santha. Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem. In: Proceedings of 13th ACM Symposium on Parallelism in Algorithms and Architectures. 2001, pp. 263–270. doi: 10.1145/378580.378679.

[P1]

W. van Dam, F. Magniez, M. Mosca, and M. Santha. Self-testing of universal and fault-tolerant sets of quantum gates. In: Proceedings of 32nd ACM Symposium on Theory of Computing. 2000, pp. 688–696. doi: 10.1145/335305.335402.

[P0]

F. Magniez. Multi-linearity self-testing with relative error. In: Proceedings of 17th Symposium on Theoretical Aspects of Computer Science. 2000, pp. 302–313. doi: 10.1007/3-540-46541-3_25.

[P-1]

M. Kiwi, F. Magniez, and M. Santha. Approximate testing with relative error. In: Proceedings of 31st ACM Symposium on Theory of Computing. 1999, pp. 51–60. doi: 10.1145/301250.301269.

Others

[O10]

S. Apers, F. Magniez, S. Sen, and D. Szabó. Quantum property testing in sparse directed graphs. Tech. rep. 2024. arXiv: 2410.05001.

[O9]

F. Magniez and A. Bredariol Grilo, eds. 19th Conference on the Theory of Quantum Computation, Communication and Cryptography. Vol. 310. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Sept. 2024. isbn: 978-3-95977-328-7.

[O8]

I. Kerenidis and F. Magniez. La physique quantique réinvente les algorithmes. July 2015.

[O7]

M.C. Gaudel, R. Lassaigne, M. de Rougemont, and F. Magniez. Some approximations in Model Checking and Testing. Tech. rep. Survey. 2013. arXiv: 1304.5199.

[O6]

F. Magniez and A. Nayak, eds. Special issue in Quantum Computation, Algorithmica 55(3). Vol. 55. 3. Springer, 2009.

[O5]

F. Magniez. Vérification approchée - Calcul quantique. Record number 1018. Habilitation. Université Paris-Sud, France. 2007.

[O4]

J. Kempe, S. Laplante, and F. Magniez. Comment calculer quantique. June 2006.

[O3]

F. Magniez. Auto-test pour les calculs approché et quantique. Record number 6076. PhD thesis. Université Paris-Sud, France, 2000.

Teaching

Collège de France

Quantum algorithms (Annual Chair 2020-21, in French) Related but independent event
Master courses Research schools

Supervision

Offers

Postdoc and PhD Master Thesis
PhD Theses Master Theses Internships (Licence 3 / Master 1)

Management

Responsibilities

University committees Steering committees Editorial committee Program committees

Contact