Speaker
Description
We present a protocol for learning an unknown $n$-qubit Hamiltonian
supported on Pauli strings of weight at most $k$, with what is, to our
knowledge, the first instance-optimal $\ell_2/\ell_2$ recovery guarantee
that is simultaneously efficient in total evolution time, measurement
count, and classical decoding time, all scaling sublinearly in the
$O(n^k)$-dimensional ambient space. The protocol requires only time
evolution interleaved with single-qubit Pauli operations, together with
GHZ-type probe states for Heisenberg-limited phase estimation, and it
assumes no prior knowledge of the interaction terms.
The structural observation at its heart is that the quantum experiment
natively implements the measurements of sublinear-time sparse recovery:
within a commuting Pauli sector, a Walsh--Hadamard transform of estimated
eigenvalue differences yields signed hash buckets in the sense of
CountSketch, and sign shifts imprint the coordinates of a binary linear
code onto isolated coefficients. Identification decodes this robust
sparse-label code in time $\mathrm{poly}(k, \log n)$, and estimation takes
candidate-isolated medians on a fresh sketch. The analysis is carried out
in a deterministic residual model in which arbitrary, possibly biased and
correlated, measurement and modeling errors are charged only by their
total energy. Random basis selection lifts the sector result to full
$k$-body Hamiltonians. For an $M$-term Hamiltonian and target error
$\epsilon_H$, the protocol uses $\widetilde{O}(M \log n)$ measurements,
evolution time $\widetilde{O}(M \log n / \epsilon_H)$ at the Heisenberg
limit, and $\widetilde{O}(M\,\mathrm{polylog}(n))$ decoding time, with the
exponential-in-$k$ but $n$-independent overheads quantified explicitly.
| Topic | Theoretical foundations of quantum learning |
|---|---|
| Additional Topic | Hybrid quantum-classical approaches for learning and optimization |