Why this contribution matters
Vazirani 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 EECSarXivThe work behind the recognition
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.
For the assumptions behind claims of quantum advantage, read our guide to quantum benchmarks.
The evidence map
Both views link each contribution to its sources. Choose a contribution on the map or read them all in the list.
Quantum complexity theory
Umesh Vazirani
Supports: Named professorship, research identity and bibliography identifying Quantum Complexity Theory with Ethan Bernstein at STOC 1993.
Checked 19 Sept 2026Credit & limits: Co-author of Quantum Complexity Theory with Ethan Bernstein.
Read the full contribution| Contribution | Evidence & what it supports | Credit & limits |
|---|---|---|
| Quantum complexity theory1993 | Institutional recordUmesh Vazirani Named professorship, research identity and bibliography identifying Quantum Complexity Theory with Ethan Bernstein at STOC 1993. Checked 19 Sept 2026 | Co-author of Quantum Complexity Theory with Ethan Bernstein. |
| The complexity of random circuit sampling2018 | Primary paperQuantum Supremacy and the Complexity of Random Circuit Sampling Co-authorship, average-case hardness and anti-concentration analysis for random circuit sampling. Published 12 Mar 2018 · Checked 19 Sept 2026 | Co-author with Adam Bouland, Bill Fefferman and Chinmay Nirkhe. |
Follow the evidence
3 sourcesPrimary papers, institutional records and attributed announcements. Each source supports the claims linked above.
- UC Berkeley EECSInstitutional record
Umesh Vazirani
Named professorship, research identity and bibliography identifying Quantum Complexity Theory with Ethan Bernstein at STOC 1993.
Checked 19 Sept 2026 - arXivPrimary paper
Quantum Supremacy and the Complexity of Random Circuit Sampling
Co-authorship, average-case hardness and anti-concentration analysis for random circuit sampling.
Published 12 Mar 2018 · Checked 19 Sept 2026 - UC Berkeley EECSInstitutional record
Umesh Vazirani — current Berkeley faculty profile
Current named professorship and co-directorship of the Berkeley Quantum Computation Center; research in quantum computing, algorithms and complexity theory.
Checked 20 Oct 2026