Thomas Vidick

Thomas Vidick (* 13. Juli 1982) ist ein belgischer Informatiker, der sich mit Komplexitätstheorie, Quantenkryptographie, Quanten-Spieltheorie und allgemein mit Quanteninformatik befasst.

Vidick studierte ab 2002 an der École normale supérieure (Paris) mit dem Bachelor-Abschluss (Magistère) in Informatik und Mathematik. 2007 erhielt er einen Master-Abschluss in Informatik an der Universität Paris-Süd bei Julia Kempe (Master-Arbeit: A study of entanglement in quantum interactive proof systems). 2011 wurde er an der University of California, Berkeley bei Umesh Vazirani promoviert (The complexity of entangled games). Für die Dissertation erhielt er den Bernard Friedman Memorial Prize. Als Post-Doktorand war er bei Scott Aaronson am Massachusetts Institute of Technology. 2014 wurde er Assistant Professor, 2017 Associate Professor und 2018 Professor am Caltech.

Er war unter anderem Gastwissenschaftler am Perimeter Institute und am Zentrum für Quantentechnologie der Nationalen Universität Singapur.

2007 gab er mit Julia Kempe und anderen erste Beweise für NP-Schwere in der Quanten-Spieltheorie.

2014 gab er mit Umesh Vazirani den ersten Geräte-unabhängigen Beweis der Sicherheit von Protokollen für Quantenschlüsselaustausch.

2020 legte er mit Zhengfeng Ji, Anand Natarajan, John Wright und Henry Yuen den Preprint einer Arbeit vor, die falls bestätigt, als Meilenstein in der Komplexitätstheorie gilt. Sie zeigt MIP*=RE, das heißt die Quanteninformatik-Version von Interaktiven Beweissystemen mit mehreren Beweisern (MIP, der Stern in MIP* steht für die Quantencomputerversion) entspricht der mächtigen Komplexitätsklasse der rekursiv aufzählbaren Sprachen (RE), das heißt es umfasst Entscheidungsprobleme für die eine Ja-Antwort durch eine Turingmaschine in endlicher Zeit verifiziert werden kann (Nein-Antworten können dagegen in unendliche Schleifen münden). Dabei teilen im einfachsten Fall von zwei Beweisern diese Quantenverschränkung.

Eine Folgerung des Satzes von Vidick und Kollegen ist, dass es ein Protokoll gibt, in dem zwei quantenverschränkte Beweiser einen Verifizierer mit polynomialer Zeit von der Antwort eines beliebigen berechenbaren Problems überzeugen können, insbesondere auch ob eine bestimmte Turingmaschine hält (Halteproblem).

Die Arbeit widerlegt die Einbettungsvermutung von Alain Connes von 1976, dass jede endliche von Neumann Algebra (solche mit endlicher Spur) gut durch endlich dimensionale Matrizenalgebren approximierbar sind. Der Einbettungssatz von Connes wurde lange als wahr angenommen und eine Reihe von Sätzen beruhen auf ihm (er ist u. a. äquivalent zu Tsirelson's Problem).

2020/21 hatte er einen FSMP Research Chair in Paris und für 2020 bis 2025 hat er einen INRIA International Chair. 2019 erhielt er einen Presidential Early Career Award und 2021 erhielt er einen Simons Investigator Award. 2022 war er eingeladener Sprecher auf dem Internationalen Mathematikerkongress (Connes embedding problem, Tsirelson's problem and MIP*=RE).

Ab 2014 ist er geschäftsführender Herausgeber (Managing Editor) von Theory of Computing.

Schriften (Auswahl)

Außer die in den Fußnoten zitierten Arbeiten.

• From Operator Algebras to Complexity Theory and Back, Notices of the AMS, November 2019
• mit Tina Zhang: Classical proofs of quantum knowledge, Eurocrypt' 21, Arxiv

Weblinks

• Homepage am Caltech, mit CV