The exact LCU sampling overhead of collective diagonal unitaries: resonances and a continued-fraction dichotomy
The minimal sampling overhead of the quadratic collective phase $e^{-i\gamma K^2}$ over one layer of single-qubit rotations is decided by the continued fraction of $\gamma/\pi$. Here $K$ is a collective observable with spectrum $\{0,\dots,n\}$, such as the permutation-symmetric Hamming weight. This gate is the cardinal...