Instance-Optimal Quantum State Certification with Entangled Measurements
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 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Tight Bounds for Quantum State Certification with Incoherent Measurements
We consider the problem of quantum state certification, where we are given the description of a mixed state $\sigma \in \mathbb{C}^{d \times d}$, $n$ copies of a mixed state $\rho \in \mathbb{C}^{d \times d}$, and $\vare…
Toward Instance-Optimal State Certification With Incoherent Measurements
We revisit the basic problem of quantum state certification: given copies of unknown mixed state $\rho\in\mathbb{C}^{d\times d}$ and the description of a mixed state $\sigma$, decide whether $\sigma = \rho$ or $\|\sigma …
Sample-optimal learning of quantum states using gentle measurements
Gentle measurements of quantum states do not entirely collapse the initial state. Instead, they provide a post-measurement state at a prescribed trace distance $\alpha$ from the initial state together with a random varia…
LEMMADouble Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivity
In response to subtle adversarial examples flipping classifications of neural network models, recent research has promoted certified robustness as a solution. There, invariance of predictions to all norm-bounded attacks …
Open-Ended Question AnsweringTransforming Bell's Inequalities into State Classifiers with Machine Learning
Quantum information science has profoundly changed the ways we understand, store, and process information. A major challenge in this field is to look for an efficient means for classifying quantum state. For instance, on…
BIG-bench Machine LearningQuantum State Tomography