On Testing and Learning Quantum Junta Channels.

Abstract

We consider the problems of testing and learning quantum -junta channels, which are -qubit to -qubit quantum channels acting non-trivially on at most out of qubits and leaving the rest of qubits unchanged. We show the following. 1) An -query algorithm to distinguish whether the given channel is -junta channel or is far from any -junta channels, and a lower bound on the number of queries; 2) An -query algorithm to learn a -junta channel, and a lower bound on the number of queries. This partially answers an open problem raised by [1]. 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 [2]. The distance metric we consider in this paper is obtained by Fourier analysis, which is essentially the L2-distance between Choi representations. Besides, we introduce INFLUENCE-SAMPLE to replace FOURIER-SAMPLE proposed in(Atici and Servedio, 2007). Our INFLUENCE-SAMPLE includes only single-qubit operations and results in only constant-factor decrease in efficiency.