ウメシュ・ヴァジラニ

ウメシュ・ヴィルクマール・ヴァジラニはインド系アメリカ人の学者であり、カリフォルニア大学バークレー校の電気工学およびコンピュータサイエンスのロジャー・A・ストラウチ教授であり、バークレー量子計算センターの所長である。彼の研究対象は主に量子コンピューティングである。彼はアルゴリズムに関する教科書の共著者でもある。^[1]

ヴァジラニは1981年にMITで理学士号を取得し^{[2] 、1986年に}マヌエル・ブルムの指導の下、カリフォルニア大学バークレー校で博士号を取得しました^[3]。

彼はカリフォルニア大学アーバイン校の教授であるビジェイ・ヴァジラニの兄弟です。

ヴァジラニは量子コンピューティング分野の創始者の一人です。1993年に学生のイーサン・バーンスタインと共同で発表した量子複雑性理論に関する論文^{[4]では、複雑性に基づく分析に適した}量子チューリングマシンのモデルを定義しました。この論文では量子フーリエ変換のアルゴリズムも提示されており、その後1年以内にピーター・ショアが整数の因数分解のための有名な量子アルゴリズムで使用しました。

チャールズ・ベネット、イーサン・バーンスタイン、ジル・ブラサードとともに、量子コンピュータはブラックボックス探索問題を探索する要素の数よりも速く解くことができないことを示した。この結果は、グローバー探索アルゴリズムが最適であることを示しています。また、量子コンピュータは証明者のみを使用してNP完全問題を多項式時間で解くことができないことも示しています。^{[5] [6] [疑わしい–議論する]}${\displaystyle O({\sqrt {N}})}$

2005年、ヴァジラニと弟のヴィジェイ・ヴァジラニはともに米国計算機学会フェローに選出された。ウメシュは「理論計算機科学と量子計算への貢献」^{[7]により、ヴィジェイは}近似アルゴリズム^[8]に関する研究により選出された。ヴァジラニはグラフセパレータの近似比の改善と関連問題に関する研究（サティシュ・ラオ、サンジーヴ・アローラと共同）により2012年のフルカーソン賞を受賞した。2018年、彼は米国科学アカデミーに選出された。

• マルムリー、ケタン。ヴァジラニ、ウメッシュ V. Vazirani、Vijay V. (1987)、「マッチングは行列の反転と同じくらい簡単です」、Combinatorica、7 (1): 105–113、CiteSeerX  10.1.1.70.2247、doi :10.1007/BF02579206、MR  0905157、S2CID  47370049この論文の予備版もSTOC '87に掲載されました。
• バーンスタイン、イーサン、ヴァジラニ、ウメッシュ (1993)、「量子複雑性理論」、第 25 回 ACM コンピューティング理論シンポジウム (STOC '93) の議事録、pp. 11–20、CiteSeerX  10.1.1.655.1186、doi :10.1145/167088.167097、ISBN 978-0897915915、S2CID  676378。
• カーンズ、マイケル J.; ヴァジラニ、ウメシュ V. (1994)、計算学習理論入門、MIT プレス、ISBN 9780262111935。
• ベネット、チャールズ H. ; バーンスタイン、イーサン;ブラサード、ジル; ヴァジラニ、ウメッシュ (1997)、「量子コンピューティングの長所と短所」、SIAM Journal on Computing、26 (5): 1510–1523、arXiv : quant-ph/9701001、Bibcode :1997quant.ph..1001B、doi :10.1137/S0097539796300933、MR  1471991、S2CID  13403194。

• カリフォルニア大学バークレー校のウメシュ・ヴァジラニ