Marcussen and Gong: Quality Control for Pattern Counting, Adaptivity in Quantum Learning
Harvard SEAS Computer Science Colloquium Series, 22 October 2026
Table of Contents
Event
| Field | Value |
|---|---|
| Series | Computer Science Colloquium Series, Harvard SEAS |
| Date | EDT; end time not given (popcorn and coffee outside the room from 14:15) |
| Venue | Science and Engineering Complex (SEC) LL2.224, 150 Western Avenue, Allston MA 02134 |
| Format | Two graduate-student talks, open to the public |
| Speakers | Cassandra Marcussen; Weiyuan Gong |
| Talk | Speaker | Advisor |
|---|---|---|
| Quality Control Algorithms for Pattern Counting | Cassandra Marcussen | Madhu Sudan |
| The Power of Adaptivity in Quantum Learning | Weiyuan Gong | Sitan Chen |
Quality control algorithms for pattern counting
The question: when can an algorithm that works well on random inputs be trusted on real data? A quality control algorithm accepts inputs drawn from the assumed random model and, with high probability, rejects any input on which the model's prediction is substantially wrong. It does not have to say what the right answer is, only whether the cheap answer can be used.
The case in the talk is permutation patterns, the relative order of entries in a sequence, with predictions from an i.i.d. model. Estimating how often a length-k pattern occurs in an arbitrary input takes exponentially many queries in k. Checking whether the i.i.d. prediction can be trusted takes only polynomially many. Joint work with Ronitt Rubinfeld and Madhu Sudan.
The paper is Marcussen, Rubinfeld and Sudan (2026) (Marcussen, Rubinfeld, and Sudan 2026). It follows their random-graphs paper (Marcussen, Rubinfeld, and Sudan 2025), which defines the problem. Given a distribution D and a quality function ρ with ρ ≈ 1 on a typical draw, accept most inputs drawn from D and reject every input, adversarial ones included, whose ρ is far from 1. For k-clique counts in G(n,p), worst-case approximate counting needs p-Ω(k²) queries, while quality control needs p-O(k).
Not property testing, not quite testable learning
Property testing is worst-case on both sides: accept everything with the property, reject everything far from it. Quality control is lopsided. Soundness is worst-case, so no bad input gets through. Completeness only has to hold for typical random inputs, so an odd input that happens to have the right count may be rejected. That asymmetry is where the savings come from.
The nearest relative is testing the distributional assumptions of a learner (Rubinfeld and Vasilyan 2022). There a tester and learner are paired so that, if the data passes, the learner's output can be trusted. Testable learning under distribution shift (Klivans, Stavropoulos, and Vasilyan 2023) extends that to a different test distribution. Quality control has the same shape, but it certifies a statistic of one input rather than a learner.
Why exponential becomes polynomial
For an i.i.d. real sequence, each of the k! relative orders of k entries is equally likely, so the prediction for a length-k pattern is about C(n,k)/k! occurrences. Counting small patterns exactly or approximately is its own literature (Even-Zohar and Leng 2019). On arbitrary input, approximate counting can need exponentially many queries in k. Quality control gets by with poly(k), and the paper also proves a superlinear lower bound in k.
A plausible reading of the abstract, not checked against the paper's body: a worst-case sequence can hide its pattern occurrences where random samples rarely look. A quality-control algorithm never has to find them. It only has to notice that the sequence doesn't look i.i.d. at a scale that matters.
Adaptivity in quantum learning
In classical active learning, adaptivity is the whole point: binary search finds a threshold with exponentially fewer labels than random sampling. In quantum learning every measurement disturbs the state it probes, and for many basic tasks adaptive strategies have been proven to give little or no advantage over fixed ones.
The talk's claim is that adaptivity still pays, sometimes dramatically, with savings in the number of copies of the state ranging from quadratic to doubly exponential:
| Setting | Non-adaptive | Adaptive | Paper |
|---|---|---|---|
| Stabilizer states, single-copy measurements | Ω(n²) copies | Θ(n), matching two-copy Bell sampling | (Bittel et al. 2026) |
| Shadow tomography (many properties), two-copy measurements | baseline | exponentially fewer copies | (Chen, Gong, and Zhang 2024) |
| Gaussian states of light, Gaussian measurements | Ω(E/ε²), linear in energy E | log log E, a floor for any Gaussian strategy | (Chen et al. 2026) |
The middle row compares like with like: adaptive and non-adaptive protocols on the same two-copy budget. The abstract's "comparable strategies" means that, not single-copy measurement.
Why adaptivity is hard to use here
A quantum state can't be read like a variable. Measuring it gives one random outcome and destroys the state, so learning costs copies: freshly prepared instances of the state, which play the role that queries play in learning theory. A single-copy measurement touches one copy at a time. A two-copy measurement can entangle a pair, as Bell sampling does, and that is strictly more powerful.
Adaptivity means choosing the next measurement from earlier outcomes, as binary search does. With noisy, destructive, low-information probes the usual theorem is that a well-chosen fixed random design does about as well. Full tomography with single-copy measurements is the standard example: adaptive and non-adaptive strategies both need Ω(d³/ε²) copies in trace distance (Chen et al. 2022; Haah et al. 2015). Classical shadows (Huang, Kueng, and Preskill 2020) are non-adaptive and already close to optimal for many prediction tasks. Where the big separations were found, they came from quantum memory, not from adaptivity (Chen et al. 2021).
These papers find the structures where adaptivity does pay. For stabilizer states and shadow tomography, a few cheap probes reveal a basis or subspace that later probes can aim at. For Gaussian states, each round narrows the energy scale. With T rounds the cost goes as E1/(2^T−1), so each extra round takes another square root, a coarse-to-fine search on a scale parameter (Chen et al. 2026). The stabilizer upper bound matches what two-copy Bell sampling achieves (Montanaro 2017; Grewal et al. 2023).
Speakers
Cassandra Marcussen is a fifth-year PhD student in computer science at Harvard, advised by Madhu Sudan. She works on sublinear and local algorithms, average-case complexity and quasirandomness, and on how computation stays reliable when only limited information about the input is available. She holds an NDSEG Fellowship.
Weiyuan Gong is a PhD student at Harvard SEAS, advised by Sitan Chen. He works on quantum learning theory, quantum algorithms and quantum complexity theory.
Both biographies are from the announcement.
Questions to bring
For Marcussen:
- Completeness holds only on average under i.i.d. If a real input is i.i.d. under a slightly different marginal, say with ties or a discretized value range, is it rejected? Is there a version that tolerates inputs close to D, as the distribution-shift work does for learners?
- Clique counting cost depended on k² against k, and pattern counting on exponential against polynomial. Is there one structural parameter of the statistic that predicts when quality control beats worst-case estimation?
- Could these testers serve as practical randomness checks, for PRNG test suites, A/B assignment shuffles or generated test inputs? What constants hide in the poly(k)?
For Gong:
- Is there one structural property, such as a small hidden subspace or a scale parameter, that predicts when adaptivity helps, or is it decided case by case?
- How robust are the Θ(n) stabilizer and log log E protocols to noise between rounds, given that each round adds classical feed-forward latency on real hardware?
- Do the T-round tradeoffs carry beyond Gaussian states? How many rounds are actually needed?
Notes
Notes pending.