# CAREER: The computational complexity of many-body entanglement

> **NSF 01003031DB NSF RESEARCH & RELATED ACTIVIT** · University of Washington (WA) · $867,115

## Abstract

Many-body quantum systems exhibit entanglement patterns that make tasks such as predicting outcomes, certifying device behavior, or succinctly describing the ground state/space computationally prohibitive. This project will develop a theory of computational complexity that explains when physically motivated quantum states (especially ground and low-energy states of local Hamiltonians) admit efficient description and verification, and when they provably do not. These insights are particularly timely due to the growing capabilities of near-term quantum devices, whose behavior increasingly probes regimes of entanglement that are classically intractable. This project will also strengthen quantum-information training by developing graduate-level curriculum in quantum complexity theory and by creating mentored research pathways for undergraduate and graduate students, with the goal of broadening participation in theoretical quantum computing.

Technically, this project formulates and proves lower bounds on the description complexity of many-body states arising from local Hamiltonians, focusing on the resources required to (i) represent these states succinctly, (ii) verify or test their properties from local measurements or interactive procedures, and (iii) perform state transformations such as cloning. The particular focus on the description complexity of ground states of local Hamiltonians yields a lens that connects the peculiar nature of entanglement with established tools from theoretical computer science, such as query complexity lower-bounds, classical and quantum error-correction, and boolean function analysis. Expected outcomes include improving our understanding of core quantum complexity classes (e.g., QMA vs QCMA), bettering our understanding of quantum query complexity and state transformations, and making progress towards the quantum PCP conjecture, the major open problem in quantum complexity theory. In addition, these contributions are expected to influen

## Key facts

- **NSF award ID:** 2541127
- **Awardee organization:** University of Washington (WA)
- **SAM.gov UEI:** HD1WMN6945W6
- **PI:** Chinmay Nirkhe
- **Primary program:** 01003031DB NSF RESEARCH & RELATED ACTIVIT
- **All programs:** CAREER-Faculty Erly Career Dev, QUANTUM COMPUTING
- **Estimated total:** $867,115
- **Funds obligated:** $559,520
- **Transaction type:** Continuing Grant
- **Period:** 09/15/2026 → 08/31/2031

## Primary source

NSF Award Search: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2541127

## Citation

> US National Science Foundation, Award 2541127, CAREER: The computational complexity of many-body entanglement. Retrieved via AI Analytics 2026-06-30 from https://api.ai-analytics.org/grant/nsf/2541127. Licensed CC0.

---

*[NSF Awards dataset](/datasets/nsf-awards) · CC0 1.0*