On Testing and Learning Quantum Junta Channels

Zongbo Bao, Penghui Yao
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1064-1094, 2023.

Abstract

We consider the problems of testing and learning quantum k-junta channels, which are n-qubit to n-qubit quantum channels acting non-trivially on at most k out of n qubits and leaving the rest of qubits unchanged. We show the following.1. An \tilde{O}(k)-query algorithm to distinguish whether the given channel is k-junta channel or is far from any k-junta channels, and a lower bound \Omega(\sqrt{k}) on the number of queries;2. An \tilde{O}(4^k)-query algorithm to learn a k-junta channel, and a lower bound \Omega(4^k/k) on the number of queries.This gives the first junta channel testing and learning results, and partially answers an open problem raised by Chen et al. (2023). In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in Montanaro and Osborne (2010).

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-bao23b, title = {On Testing and Learning Quantum Junta Channels}, author = {Bao, Zongbo and Yao, Penghui}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {1064--1094}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/bao23b/bao23b.pdf}, url = {https://proceedings.mlr.press/v195/bao23b.html}, abstract = {We consider the problems of testing and learning quantum k-junta channels, which are n-qubit to n-qubit quantum channels acting non-trivially on at most k out of n qubits and leaving the rest of qubits unchanged. We show the following.1. An \tilde{O}(k)-query algorithm to distinguish whether the given channel is k-junta channel or is far from any k-junta channels, and a lower bound \Omega(\sqrt{k}) on the number of queries;2. An \tilde{O}(4^k)-query algorithm to learn a k-junta channel, and a lower bound \Omega(4^k/k) on the number of queries.This gives the first junta channel testing and learning results, and partially answers an open problem raised by Chen et al. (2023). In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in Montanaro and Osborne (2010).} }
Endnote
%0 Conference Paper %T On Testing and Learning Quantum Junta Channels %A Zongbo Bao %A Penghui Yao %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-bao23b %I PMLR %P 1064--1094 %U https://proceedings.mlr.press/v195/bao23b.html %V 195 %X We consider the problems of testing and learning quantum k-junta channels, which are n-qubit to n-qubit quantum channels acting non-trivially on at most k out of n qubits and leaving the rest of qubits unchanged. We show the following.1. An \tilde{O}(k)-query algorithm to distinguish whether the given channel is k-junta channel or is far from any k-junta channels, and a lower bound \Omega(\sqrt{k}) on the number of queries;2. An \tilde{O}(4^k)-query algorithm to learn a k-junta channel, and a lower bound \Omega(4^k/k) on the number of queries.This gives the first junta channel testing and learning results, and partially answers an open problem raised by Chen et al. (2023). In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in Montanaro and Osborne (2010).
APA
Bao, Z. & Yao, P.. (2023). On Testing and Learning Quantum Junta Channels. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:1064-1094 Available from https://proceedings.mlr.press/v195/bao23b.html.

Related Material