Thomas Vidick

2024 Israel Award Winner — Faculty

Thomas Vidick

Current Position:
Professor of Computer Science and Applied Mathematics, Weizmann Institute of Science; Professor of Computing and Mathematical Sciences, California Institute of Technology, United States

Institution:
Weizmann Institute of Science

Discipline:
Computer Science

Recognized for: Groundbreaking work exploring how quantum effects affect complexity in computing that resulted in establishing new boundaries on computationally verifiable knowledge. The work of Thomas Vidick, PhD, in quantum complexity and quantum cryptography will shape the development of 21st century quantum networks for secure communication and computation.


Areas of Research Interest and Expertise: 

Quantum computing, complexity theory, quantum cryptography, operator algebras

Previous Positions:

BSc in Computer Science, École Normale Supérieure, Paris, France
MSc in Computer Science, University Paris 7, France (Advisor: Julia Kempe)
PhD in Computer Science, University of California-Berkeley, USA (Advisor: Umesh Vazirani)
Postdoctoral Associate, Massachusetts Institute of Technology, USA (Advisor: Scott Aaronson)

Research Summary: 

The fields of complexity theory and cryptography study the capabilities of classical computers – devices whose functioning is accurately modeled by classical, Newtonian physics – for computation and secure communication. Thomas Vidick, PhD, is pioneering research in quantum complexity and cryptography that explores the capabilities of quantum devices, whose rules of operation are governed by quantum mechanics. Quantum computers may perform certain computational tasks exponentially faster than classical computers and can enable new cryptographic protocols that leverage quantum mechanics to reach new levels of security in communication.

One of Vidick’s most astonishing results is the equality MIP*=RE. This equality formulates an equivalence between two seemingly unrelated computational models. The first model, MIP*, is based on quantum mechanics – specifically quantum entanglement – which allows instantaneous correlation between two particles separated by very large distances. The second model captures the complexity of the famous Halting problem introduced by Alan Turing in the 1930s. The equality MIP*=RE shows the unexpected power of entanglement for proof verification. This result has far-reaching consequences beyond the field of computer science. It represents a significant milestone in our quest to understand the power and limitations of quantum computing, and it opens new avenues for research at the intersection of computer science, mathematics and quantum physics.

Professor Vidick’s wide-ranging work has already been crucial in shaping the field of quantum computational cryptography and is settling major problems in pure mathematics – some of which had been open for over 50 years. This has sparked interest in using quantum techniques to tackle mathematical problems and could revolutionize the field of proof verification.

“In my research, I have been lucky to stumble upon deep questions at the interface of computer science, mathematics and physics. I am grateful to my many collaborators for accompanying me on the journey to resolve some of these questions. Together, our insights and hard work have opened a never-ending maze of wonders that will never cease to fascinate me.”

Key Publications:

  1. Ji, A. Natarajan, T. Vidick, J. Wright, H. Yuen. Quantum Soundness of Testing Tensor Codes. Discrete Analysis, 2022.
  2. Natarajan, T. Vidick. A Quantum Linearity Test for Robustly Verifying Entanglement. STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017.
  3. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, T. Vidick. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. Journal of the ACM, 2021.
  4. Arad, Z. Landau, U. Vazirani, T. Vidick. Rigorous RG Algorithms and Area Laws for Low Energy Eigenstates in 1D. Communications in Mathematical Physics, 2017.

Other Honors: 

2023Held Prize, US National Academy of Sciences
2021Simons Investigator Award, Simons Foundation
2019Presidential Early Career Award for Scientists and Engineers, US National Science Foundation
2019ASCIT Teaching Award, Associated Students of the California Institute of Technology
2017CIFAR Azrieli Global Scholar Award, The Canadian Institute for Advanced Research

 

In the Media: 

ScienceNews A Quantum Strategy Could Verify the Solutions to Unsolvable Problems-In Theory

Nature News-- How ‘Spooky’ is Quantum Physics? The Answer Could be Incalculable

Quanta Magazine Landmark Computer Science Proof Cascades Through Physics and Math

Quanta Magazine How to Turn a Quantum Computer Into the Ultimate Randomness Generator

Website