We give a shadow tomography algorithm that uses $O(\log(m) \log(m/\delta) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $\rho$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_i\rho)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, except with probability at most $\delta$. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on $O(\log(m)/\varepsilon^2)$ copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining $\log(m)$ factor separating the complexity of the quantum problem from its classical counterpart.
We consider a nonlinear model motivated by polychromatic computed tomography (CT). Here, $W$ distinct $d$-dimensional signals $x^*_1, \ldots, x^*_W \in \mathbb{R}^d$ must be recovered from $n$ measurements $(a_i, y_i)_{i = 1}^n$ that obey the nonlinear model $\mathbb{E}[y_i|a_i] = h(\langle a_i, x^*_1 \rangle, \ldots,...
In this work, we consider the fundamental task of estimating the purity of an unknown state to within $\textit{multiplicative}$ error $\varepsilon$. When one can perform general collective measurements, $\Theta\left(\frac{\sqrt{d}}{\varepsilon^2} + \frac{d}{\varepsilon}\right)$ copies are known to be necessary and suff...
We study the problem of sampling from a continuous density $\pi\propto \exp(-V)$ on $\mathbb R^d$, where $V\in C^2(\mathbb R^d)$ has a $\beta$-Lipschitz gradient and $\pi$ satisfies a logarithmic Sobolev inequality with constant $\alpha^{-1}$, and write $\kappa = \beta/\alpha$. We introduce the Gaussian cloud sampler,...
Fan Chen, Sinho Chewi, Jian-Feng Lu et al.· 0 citations
Let $E(X)=\#\{(a,b)\in\Z^2:a^2+b^2\le X\}-\pi X$. We prove that $E(X)=O_\varepsilon(X^{209/670+\varepsilon})$ for every $\varepsilon>0$, uniformly for real $X\ge4$. This breaks the $5/16$ threshold suggested by Huxley as a possible limit of the Bombieri--Iwaniec method at the time. The proof introduces two refinements:...
Xi Cen, Xi-Tao Gao, Cheng Zhang et al.· 0 citations
Optical intensity interferometry (II) can in principle resolve structure on angular scales $\theta\sim \lambda/B$, but it measures only the squared visibility $|{\cal V}|^2$, discarding Fourier phase. We quantify what information can actually be recovered from phase-less $|{\cal V}|^2$ measurements as a function of the...
N. Dalal, B. Dai, Matthew K. Browning· 0 citations
We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincar\'e-dependent bounds (Kothari and Steinhardt, 2017),...
A. Storozhenko· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
