烏梅什·瓦茲拉尼

烏梅什·維爾庫馬爾·瓦茲拉尼（英語：Umesh Virkumar Vazirani）是一位印度裔美國數學家和計算機科學家，是加利福尼亞大學柏克萊分校電機工程與計算機科學的羅傑·A·斯特勞赫教授，也是柏克萊量子計算中心的主任。他的研究興趣主要在於量子計算方面。他也是一本關於算法的教科書的共同作者^[1]。

烏梅什·瓦茲拉尼 Umesh Vazirani
國籍	美國
母校	麻省理工學院 加利福尼亞大學柏克萊分校
知名於	伯恩斯坦-瓦茲拉尼算法（英語：Bernstein–Vazirani algorithm）
獎項	富爾克森獎（2012）
網站	www.cs.berkeley.edu/~vazirani/
科學生涯
研究領域	量子計算、計算複雜性
機構	加利福尼亞大學柏克萊分校
論文	Randomness, Adversaries and Computation（1986年）
博士導師	曼紐爾·布盧姆
博士生	斯科特·亞倫森（英語：Scott Aaronson） 安德里斯·安貝尼斯（英語：Andris Ambainis） 桑吉夫·阿羅拉（英語：Sanjeev Arora） 烏爾米拉·馬哈德夫（英語：Urmila Mahadev） 邁度·蘇丹（英語：Madhu Sudan） 大衛·祖克曼（英語：David Zuckerman (computer scientist)）

生平

瓦茲拉尼於1981年在麻省理工學院獲得學士學位^[2]，1986年在加利福尼亞大學柏克萊分校獲得博士學位，師從曼紐爾·布盧姆^[3]。

他和加利福尼亞大學爾灣分校教授維傑·瓦茲拉尼（英語：Vijay Vazirani）是兄弟。

研究工作

瓦茲拉尼是量子計算領域的創始人之一。他在1993年和他的學生伊森·伯恩斯坦（Ethan Bernstein）一起發表關於量子複雜性理論的論文^[4]，定義出一個量子圖靈機的模型，該模型適合於基於複雜性的分析。這篇論文還給出一個量子傅立葉變換的算法，之後被彼得·秀爾在一年內用於他著名的整數因子的量子算法。

他與查爾斯·H·本尼特（英語：Charles H. Bennett (physicist)）、伊森·伯恩斯坦和吉勒斯·布拉薩德（英語：Gilles Brassard）合作，表明量子計算機解決黑盒搜索問題的速度不能超過待搜索元素數量的 ${\displaystyle O({\sqrt {N}})}$ 。這一結果表明格羅弗算法是最優的，並表明量子計算機不能在多項式時間內僅使用證明人解決NP完全的問題^[5][6]。

獲獎和榮譽

2005年，瓦茲拉尼和他的兄弟維傑·瓦茲拉尼（英語：Vijay Vazirani）獲選為計算機協會會士，烏梅什因其對理論計算機科學和量子計算的貢獻^[7]，維傑則因其在近似算法方面的成就而獲選為會士^[8]。2012年，瓦茲拉尼因其在改善圖分離器和相關問題的逼近率方面的成就，與薩蒂什·拉奧（英語：Satish Rao）和桑吉夫·阿羅拉（英語：Sanjeev Arora）共同獲得富爾克森獎。 2018年，他獲選為美國國家科學院院士。