Robust quantum state certification and uncertainty principles for total influence

Abstract

We show that nonadaptive single-qubit Pauli measurements suffice to test whether an unknown $n$-qubit state $\ddot{I}$ is $\epsilon$-close to or $O(\epsilon )$-far from an ideal target state $|\ddot{I}ˆ⟩$, for all but a $2^{-\hat{I}\text{c◯}(n)}$ fraction of target states. The test uses $O({\epsilon }^{-2}\log (1/\hat{I}´))$ copies of $\ddot{I}$ to achieve confidence $1-\hat{I}´$, which is information-theoretically optimal even among protocols with arbitrary joint measurements. The main technical innovation is an uncertainty principle for weighted generalizations of the total influence of Boolean functions. As a simple example, the unweighted variant states that $\mathbf{Inf}[f]+\mathbf{Inf}[\hat{f}]=\hat{I}\text{c◯}(n)$, which is a natural hypercube analogue of the Heisenberg uncertainty principle (here $\hat{\cdot }$ denotes the $2^{-n/2}$-normalized Fourier transform). The weighted case generalizes $\mathbf{Inf}[\cdot ]$ and $\mathbf{Inf}[\hat{\cdot }]$ to Dirichlet energies associated with Glauber dynamics for certain dual measures on the cube.

73 + 3 pages, 1 figure

Topics & keywords