The role of randomness in quantum state certification with unentangled measurements

Yuhan Liu, Jayadev Acharya
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:3523-3555, 2024.

Abstract

Given $n$ copies of an unknown quantum state $\rho\in\mathbb{C}^{d\times d}$, quantum state certification is the task of determining whether $\rho=\rho_0$ or $\|\rho-\rho_0\|_1>\varepsilon$, where $\rho_0$ is a known reference state. We study quantum state certification using unentangled quantum measurements, namely measurements which operate only on one copy of $\rho$ at a time. When there is a common source of randomness available and the unentangled measurements are chosen based on this randomness, prior work has shown that $\Theta(d^{3/2}/\varepsilon^2)$ copies are necessary and sufficient. This holds even when the measurements are allowed to be chosen adaptively. We consider deterministic measurement schemes (as opposed to randomized) and demonstrate that ${\Theta}(d^2/\varepsilon^2)$ copies are necessary and sufficient for state certification. This shows a separation between algorithms with and without randomness. We develop a lower bound framework for both fixed and randomized measurements that relates the hardness of testing to the well-established Lüders rule. More precisely, we obtain lower bounds for randomized and fixed schemes as a function of the eigenvalues of the Lüders channel which characterizes one possible post-measurement state transformation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-liu24a, title = {The role of randomness in quantum state certification with unentangled measurements}, author = {Liu, Yuhan and Acharya, Jayadev}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {3523--3555}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/liu24a/liu24a.pdf}, url = {https://proceedings.mlr.press/v247/liu24a.html}, abstract = {Given $n$ copies of an unknown quantum state $\rho\in\mathbb{C}^{d\times d}$, quantum state certification is the task of determining whether $\rho=\rho_0$ or $\|\rho-\rho_0\|_1>\varepsilon$, where $\rho_0$ is a known reference state. We study quantum state certification using unentangled quantum measurements, namely measurements which operate only on one copy of $\rho$ at a time. When there is a common source of randomness available and the unentangled measurements are chosen based on this randomness, prior work has shown that $\Theta(d^{3/2}/\varepsilon^2)$ copies are necessary and sufficient. This holds even when the measurements are allowed to be chosen adaptively. We consider deterministic measurement schemes (as opposed to randomized) and demonstrate that ${\Theta}(d^2/\varepsilon^2)$ copies are necessary and sufficient for state certification. This shows a separation between algorithms with and without randomness. We develop a lower bound framework for both fixed and randomized measurements that relates the hardness of testing to the well-established Lüders rule. More precisely, we obtain lower bounds for randomized and fixed schemes as a function of the eigenvalues of the Lüders channel which characterizes one possible post-measurement state transformation.} }
Endnote
%0 Conference Paper %T The role of randomness in quantum state certification with unentangled measurements %A Yuhan Liu %A Jayadev Acharya %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-liu24a %I PMLR %P 3523--3555 %U https://proceedings.mlr.press/v247/liu24a.html %V 247 %X Given $n$ copies of an unknown quantum state $\rho\in\mathbb{C}^{d\times d}$, quantum state certification is the task of determining whether $\rho=\rho_0$ or $\|\rho-\rho_0\|_1>\varepsilon$, where $\rho_0$ is a known reference state. We study quantum state certification using unentangled quantum measurements, namely measurements which operate only on one copy of $\rho$ at a time. When there is a common source of randomness available and the unentangled measurements are chosen based on this randomness, prior work has shown that $\Theta(d^{3/2}/\varepsilon^2)$ copies are necessary and sufficient. This holds even when the measurements are allowed to be chosen adaptively. We consider deterministic measurement schemes (as opposed to randomized) and demonstrate that ${\Theta}(d^2/\varepsilon^2)$ copies are necessary and sufficient for state certification. This shows a separation between algorithms with and without randomness. We develop a lower bound framework for both fixed and randomized measurements that relates the hardness of testing to the well-established Lüders rule. More precisely, we obtain lower bounds for randomized and fixed schemes as a function of the eigenvalues of the Lüders channel which characterizes one possible post-measurement state transformation.
APA
Liu, Y. & Acharya, J.. (2024). The role of randomness in quantum state certification with unentangled measurements. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:3523-3555 Available from https://proceedings.mlr.press/v247/liu24a.html.

Related Material