Doctoral Thesis Proposal - William He

July 23, 2026  12:00PM—1:30PM

Location:
4405 - Gates and Hillman Centers

Speaker:
WILLIAM HE, Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://wrhe.github.io/

Efficient Quantum Statistical Algorithms

This thesis proposal is about designing efficient algorithms for quantum statistical problems. I will discuss two previous works of mine on testing/learning quantum states with realistic measurements and other efficiency constraints.

  1. In a paper with Meghal Gupta and Ryan O'Donnell, I gave the first polynomial-in-n sample complexity algorithm for certifying any pure n-qubit quantum state using only single-qubit measurements. Our algorithm, which uses only O(n/ε) copies of the input state for ε soundness in fidelity, answered an open question of Huang, Preskill, and Soleimanifar, who had shown that a Haar-random state could with high probability be certified with a comparable number of copies and single-qubit measurements.
  2. In a paper with Sabee Grewal, Meghal Gupta, Aniruddha Sen, and Mihir Singhal, I gave the first algorithm that for learning an n-qubit pure state to fidelity at least 1-ε using near-optimal runtime Õ(2^n/ε) (and sample complexity) while also using only Pauli measurements. Previous algorithms with optimal sample complexity required both time Õ(8^n/ε) and entangled measurements.

I will also propose some directions for improvements on these two works.

  1. Improve the tolerance parameter of the result from [GHO25] from O(1/n) to Ω(1).
  2. Give an algorithm with similar efficiency guarantees as [GGHSS26] that learn 2η-close (in fidelity) hypotheses for states that are η-close to pure with runtime Õ(2^n/η).
  3. Give a time-optimal algorithm for mixed state tomography by combining the pure state reduction from Pelecanos, Spilecki, Tang, and Wright with the pure state tomography algorithm from [GGHSS26].

Thesis Commitee:

Ryan O'Donnell (Chair)
Aayush Jain
Jason Li
Hsin-Yuan Huang (Caltech, Oratomic)

Thesis Proposal

Contact
Matt Stewart

Add event to Google
Add event to iCal