Develops the theoretical foundations used to compare quantum and classical computation, including quantum complexity theory and analyses of the difficulty of sampling quantum circuits.
UC Berkeley EECSarXivVazirani helps establish what a claimed quantum advantage means mathematically. Quantum complexity theory supplies a framework for comparing computational models, and his later work examines the difficulty of reproducing the output of randomly chosen quantum circuits. These contributions matter because experimental performance alone does not explain whether a task is classically difficult. His profile emphasizes the theoretical evidence and its assumptions, keeping complexity results separate from the engineering performance or commercial usefulness of a device.
UC Berkeley EECSarXivDefining contributions
Work, in context- 1993
Quantum complexity theory
With Ethan Bernstein, Vazirani developed quantum complexity theory, formalizing questions about the computational power of quantum machines relative to classical models. The work appeared at STOC in 1993 and in an expanded journal treatment.
Co-author of Quantum Complexity Theory with Ethan Bernstein.
Source-supported recordUC Berkeley EECS - 2018
The complexity of random circuit sampling
Vazirani co-authored an analysis of random circuit sampling that studied hardness and verification. It connected typical output probabilities to worst-case computational difficulty and examined anti-concentration, strengthening the theoretical basis for sampling experiments.
Co-author with Adam Bouland, Bill Fefferman and Chinmay Nirkhe.
Source-supported recordarXiv
Keep in perspective
The sampling contribution is a theoretical analysis, not a claim of a physical quantum-advantage demonstration.
Follow the evidence
2 sourcesPrimary papers, institutional records and attributed announcements. Each source supports the claims linked above.
- UC Berkeley EECSInstitutional profile
Umesh Vazirani
Named professorship, research identity and bibliography identifying Quantum Complexity Theory with Ethan Bernstein at STOC 1993.
Checked 2026-09-19 - arXivPrimary research
Quantum Supremacy and the Complexity of Random Circuit Sampling
Co-authorship, average-case hardness and anti-concentration analysis for random circuit sampling.
Published 2018-03-12 · Checked 2026-09-19