No edit summary |
Twinkle1990 (talk | contribs) Undid revision 1220743272 by Twinkle1990 (talk) Tag: Undo |
||
(13 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Computing and quantum scientific}} |
|||
{{User sandbox}} |
|||
{{Draft topics|biography|physics}} |
|||
<!-- EDIT BELOW THIS LINE --> |
|||
{{AfC topic|blp}} |
|||
{{AfC submission|||ts=20240409134504|u=IRIF|ns=2}} |
|||
'''Miklos Santha''' (born in 1955) is a French-Hungarian computer scientist known for his contributions to complexity theory, randomized algorithms, and quantum computing. As a Senior Researcher Emeritus at the [[Centre national de la recherche scientifique]] (CNRS), Research Professor and Principal Investigator at the [[Centre for Quantum Technologies|Center for Quantum Technologies (CQT)]] at the [[National University of Singapore]], Santha also played a role in fostering research groups in quantum computing in both France and Singapore. |
|||
== Biography == |
== Biography == |
||
Miklos Santha received his diploma in mathematics in 1979 from [[Eötvös Loránd University]] in Budapest, and his Ph.D. in mathematics in 1983 from the [[Université Paris 7]]. His advisor was [[Jacques Stern (cryptologue)|Jacques Stern]]. Since 1988 he has been a CNRS researcher, currently at the [[Institut de recherche en informatique fondamentale]] (IRIF) at [[Université Paris-Cité]]. |
Miklos Santha received his diploma in mathematics in 1979 from [[Eötvös Loránd University]] in Budapest, and his Ph.D. in mathematics in 1983 from the [[Université Paris 7]]<ref>{{cite thesis |last=Santha |first=Miklos |date=1983 |title=Contribution à l'étude de la hiérarchie polynomiale relativisée |url=https://www.sudoc.fr/132401355 |degree=Thèse de doctorat |publisher=Université Paris Diderot - Paris 7 (1970-2019)}}</ref> His advisor was [[Jacques Stern (cryptologue)|Jacques Stern]]. Since 1988 he has been a CNRS researcher, currently at the [[Institut de recherche en informatique fondamentale]] (IRIF) at [[Université Paris-Cité]]. |
||
In the 90’, he created one of the earliest and internationally recognized groups on quantum computing in the world<ref>[https://www.irif.fr/en/equipes/algocomp/index Algorithms and complexity] research group now at [[Institut de recherche en informatique fondamentale|IRIF]] |
In the 90’, he created one of the earliest and internationally recognized groups on quantum computing in the world, Algorithms and Complexity group<ref>[https://www.irif.fr/en/equipes/algocomp/index Algorithms and complexity] research group now at [[Institut de recherche en informatique fondamentale|IRIF]]</ref><ref>Algorithms and Complexity research group report, 2004, https://www.lri.fr/~mbl/RA2004/B2-Algo.pdf</ref>, and the first one in France. Starting from 2008, in Singapore, Santha was appointed by [[Artur Ekert]] to establish another quantum computing research group at the [[Centre for Quantum Technologies|CQT]]<ref>[https://cs.quantumlah.org/ Computer Science Group] at the [[Centre for Quantum Technologies|CQT]]</ref><ref>CNRS News, ''Reinventing computer science for quantum computing'' by Martin Koppe, 03.16.2021, https://news.cnrs.fr/articles/reinventing-computer-science-for-quantum-computing </ref>. |
||
== Research == |
== Research == |
||
In the field of algorithms, he initiated the study of weak random sources and the extraction of random bits<ref>{{Citation | vauthors=((Santha, M.)), ((Vazirani, U. V.)) | year=1986 | title=Generating quasi-random sequences from semi-random sources | publisher=Elsevier BV | url=http://dx.doi.org/10.1016/0022-0000(86)90044-9}}</ref> from such sources with [[Umesh Vazirani]], a theory that is still explored by physicists in the context of [[Bell inequalities]]. |
In the field of algorithms, he initiated the study of weak random sources and the extraction of random bits<ref>{{Citation | vauthors=((Santha, M.)), ((Vazirani, U. V.)) | year=1986 | title=Generating quasi-random sequences from semi-random sources | journal=Journal of Computer and System Sciences | volume=33 | pages=75–87 | publisher=Elsevier BV | doi=10.1016/0022-0000(86)90044-9 | url=http://dx.doi.org/10.1016/0022-0000(86)90044-9}}</ref> from such sources with [[Umesh Vazirani]], a theory that is still explored by physicists in the context of [[Bell inequalities]]. |
||
Santha had several contributions in the conception of quantum algorithms with exponential speed-ups for group and algebraic problems, such as hidden subgroup problems<ref>{{Citation | vauthors=((Friedl, K.)), ((Ivanyos, G.)), ((Magniez, F.)), ((Santha, M.)), ((Sen, P.)) | year=2003 | |
Santha had several contributions in the conception of quantum algorithms with exponential speed-ups for group and algebraic problems, such as hidden subgroup problems<ref>{{Citation | vauthors=((Friedl, K.)), ((Ivanyos, G.)), ((Magniez, F.)), ((Santha, M.)), ((Sen, P.)) | title=Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | year=2003 | chapter=Hidden translation and orbit coset in quantum computing | pages=1–9 | publisher=ACM | doi=10.1145/780542.780544 | isbn=1-58113-674-9 | chapter-url=http://dx.doi.org/10.1145/780542.780544}}</ref>, generalizing [[Shor's algorithm]]. He also co-designed a framework for quantum search using quantum walks<ref>{{Citation | vauthors=((Magniez, F.)), ((Nayak, A.)), ((Roland, J.)), ((Santha, M.)) | year=2011 | title=Search via Quantum Walk | journal=SIAM Journal on Computing | volume=40 | pages=142–164 | publisher=Society for Industrial & Applied Mathematics (SIAM) | doi=10.1137/090745854 | arxiv=quant-ph/0608026 | url=http://dx.doi.org/10.1137/090745854}}</ref>, that generalizes Grover’s algorithm for any graph structure. |
||
== Selected publication == |
== Selected publication == |
||
# {{Citation | vauthors=((Santha, M.)), ((Vazirani, U. V.)) | year=1986 | title=Generating quasi-random sequences from semi-random sources | publisher=Elsevier BV | url=http://dx.doi.org/10.1016/0022-0000(86)90044-9}} |
# {{Citation | vauthors=((Santha, M.)), ((Vazirani, U. V.)) | year=1986 | title=Generating quasi-random sequences from semi-random sources | journal=Journal of Computer and System Sciences | volume=33 | pages=75–87 | publisher=Elsevier BV | doi=10.1016/0022-0000(86)90044-9 | url=http://dx.doi.org/10.1016/0022-0000(86)90044-9}} |
||
# {{Citation | vauthors=((Magniez, F.)), ((Nayak, A.)), ((Roland, J.)), ((Santha, M.)) | year=2011 | title=Search via Quantum Walk | publisher=Society for Industrial & Applied Mathematics (SIAM) | url=http://dx.doi.org/10.1137/090745854}} |
# {{Citation | vauthors=((Magniez, F.)), ((Nayak, A.)), ((Roland, J.)), ((Santha, M.)) | year=2011 | title=Search via Quantum Walk | journal=SIAM Journal on Computing | volume=40 | pages=142–164 | publisher=Society for Industrial & Applied Mathematics (SIAM) | doi=10.1137/090745854 | arxiv=quant-ph/0608026 | url=http://dx.doi.org/10.1137/090745854}} |
||
# {{Citation | vauthors=((Friedl, K.)), ((Ivanyos, G.)), ((Magniez, F.)), ((Santha, M.)), ((Sen, P.)) | year=2003 | |
# {{Citation | vauthors=((Friedl, K.)), ((Ivanyos, G.)), ((Magniez, F.)), ((Santha, M.)), ((Sen, P.)) | title=Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | year=2003 | chapter=Hidden translation and orbit coset in quantum computing | pages=1–9 | publisher=ACM | doi=10.1145/780542.780544 | isbn=1-58113-674-9 | chapter-url=http://dx.doi.org/10.1145/780542.780544}} |
||
# {{Citation | vauthors=((Ambainis, A.)), ((Balodis, K.)), ((Belovs, A.)), ((Lee, T.)), ((Santha, M.)), ((Smotrovs, J.)) | year=2017 | title=Separations in Query Complexity Based on Pointer Functions | publisher=Association for Computing Machinery (ACM) | url=http://dx.doi.org/10.1145/3106234}} |
# {{Citation | vauthors=((Ambainis, A.)), ((Balodis, K.)), ((Belovs, A.)), ((Lee, T.)), ((Santha, M.)), ((Smotrovs, J.)) | year=2017 | title=Separations in Query Complexity Based on Pointer Functions | journal=Journal of the ACM | volume=64 | issue=5 | pages=1–24 | publisher=Association for Computing Machinery (ACM) | doi=10.1145/3106234 | arxiv=1506.04719 | url=http://dx.doi.org/10.1145/3106234}} |
||
==References== |
==References== |
Latest revision as of 17:11, 25 April 2024
Miklos Santha (born in 1955) is a French-Hungarian computer scientist known for his contributions to complexity theory, randomized algorithms, and quantum computing. As a Senior Researcher Emeritus at the Centre national de la recherche scientifique (CNRS), Research Professor and Principal Investigator at the Center for Quantum Technologies (CQT) at the National University of Singapore, Santha also played a role in fostering research groups in quantum computing in both France and Singapore.
Biography
Miklos Santha received his diploma in mathematics in 1979 from Eötvös Loránd University in Budapest, and his Ph.D. in mathematics in 1983 from the Université Paris 7[1] His advisor was Jacques Stern. Since 1988 he has been a CNRS researcher, currently at the Institut de recherche en informatique fondamentale (IRIF) at Université Paris-Cité.
In the 90’, he created one of the earliest and internationally recognized groups on quantum computing in the world, Algorithms and Complexity group[2][3], and the first one in France. Starting from 2008, in Singapore, Santha was appointed by Artur Ekert to establish another quantum computing research group at the CQT[4][5].
Research
In the field of algorithms, he initiated the study of weak random sources and the extraction of random bits[6] from such sources with Umesh Vazirani, a theory that is still explored by physicists in the context of Bell inequalities.
Santha had several contributions in the conception of quantum algorithms with exponential speed-ups for group and algebraic problems, such as hidden subgroup problems[7], generalizing Shor's algorithm. He also co-designed a framework for quantum search using quantum walks[8], that generalizes Grover’s algorithm for any graph structure.
Selected publication
- Santha, M., Vazirani, U. V. (1986), "Generating quasi-random sequences from semi-random sources", Journal of Computer and System Sciences, 33, Elsevier BV: 75–87, doi:10.1016/0022-0000(86)90044-9
- Magniez, F., Nayak, A., Roland, J., Santha, M. (2011), "Search via Quantum Walk", SIAM Journal on Computing, 40, Society for Industrial & Applied Mathematics (SIAM): 142–164, arXiv:quant-ph/0608026, doi:10.1137/090745854
- Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P. (2003), "Hidden translation and orbit coset in quantum computing", Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM, pp. 1–9, doi:10.1145/780542.780544, ISBN 1-58113-674-9
- Ambainis, A., Balodis, K., Belovs, A., Lee, T., Santha, M., Smotrovs, J. (2017), "Separations in Query Complexity Based on Pointer Functions", Journal of the ACM, 64 (5), Association for Computing Machinery (ACM): 1–24, arXiv:1506.04719, doi:10.1145/3106234
References
- ^ Santha, Miklos (1983). Contribution à l'étude de la hiérarchie polynomiale relativisée (Thèse de doctorat thesis). Université Paris Diderot - Paris 7 (1970-2019).
- ^ Algorithms and complexity research group now at IRIF
- ^ Algorithms and Complexity research group report, 2004, https://www.lri.fr/~mbl/RA2004/B2-Algo.pdf
- ^ Computer Science Group at the CQT
- ^ CNRS News, Reinventing computer science for quantum computing by Martin Koppe, 03.16.2021, https://news.cnrs.fr/articles/reinventing-computer-science-for-quantum-computing
- ^ Santha, M., Vazirani, U. V. (1986), "Generating quasi-random sequences from semi-random sources", Journal of Computer and System Sciences, 33, Elsevier BV: 75–87, doi:10.1016/0022-0000(86)90044-9
- ^ Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P. (2003), "Hidden translation and orbit coset in quantum computing", Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM, pp. 1–9, doi:10.1145/780542.780544, ISBN 1-58113-674-9
- ^ Magniez, F., Nayak, A., Roland, J., Santha, M. (2011), "Search via Quantum Walk", SIAM Journal on Computing, 40, Society for Industrial & Applied Mathematics (SIAM): 142–164, arXiv:quant-ph/0608026, doi:10.1137/090745854