Learning

Abstract: The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question an important class of states. Namely, for $n$-qubit stabilizer states, we show that the optimal sample complexity of cloning is $\Theta(n)$. Thus, also for this structured class of states, cloning is as hard as learning. To prove these results, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.

Abstract: The optimal quantum measurements for estimating different unknown parameters in a parameterized quantum state are usually incompatible with each other. Traditional approaches to addressing the measurement incompatibility issue, such as the Holevo Cram\'{e}r--Rao bound, suffer from multiple difficulties towards practical applicability, as the optimal measurement strategies are usually state-dependent, difficult to implement and also take complex analyses to determine. Here we study randomized measurements as a new approach for multi-parameter quantum metrology. We show quantum measurements on single copies of quantum states given by $3$-designs perform near-optimally when estimating an arbitrary number of parameters in pure states and more generally, {approximately low-rank well-conditioned states}, whose metrological information is largely concentrated in a low-dimensional subspace. The near-optimality is also shown in estimating the maximal number of parameters for three types of mixed states that are well-conditioned on their supports. Examples of fidelity estimation and Hamiltonian estimation are explicitly provided to demonstrate the power and limitation of randomized measurements in multi-parameter quantum metrology.

Abstract: We consider the task of quantum state certification: given a description of a hypothesis state~$\sigma$ and multiple copies of an unknown state~$\rho$, a tester aims to determine whether the two states are equal or $\epsilon$-far in trace distance. It is known that~$\Theta(d/\epsilon^2)$ copies of~$\rho$ are necessary and sufficient for this task, assuming the tester can make entangled measurements over all copies [CHW07, OW15, BOW19]. However, these bounds are for a worst-case~$\sigma$, and it is not known what the optimal copy complexity is for this problem on an \emph{instance-by-instance} basis. While such instance-optimal bounds have previously been shown for quantum state certification when the tester is limited to measurements unentangled across copies [CLO22, CLHL22], they remained open when testers are unrestricted in the kind of measurements they can perform. We address this open question by proving nearly instance-optimal bounds for quantum state certification when the tester can perform fully entangled measurements. Analogously to the unentangled setting, we show that the optimal copy complexity for certifying~$\sigma$ is given by the worst-case complexity times the fidelity between~$\sigma$ and the maximally mixed state. We prove our lower bounds using a novel quantum analogue of the Ingster--Suslina method, which is likely to be of independent interest. This method also allows us to recover the~$\Omega(d/\epsilon^2)$ lower bound for mixedness testing [OW15], i.e., certification of the maximally mixed state, with a surprisingly simple proof.