We consider the problem of Clifford testing, which asks whether a black-box n-qubit unitary is a Clifford unitary or at least ε-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability poly(ε). This contrasts with the minimum of 6 copies required for the closely-related task of stabilizer testing. We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting. In doing so, we settle in the positive a conjecture of Bu, Gu and Jaffe, by proving a polynomial inverse theorem for a non-commutative Gowers 3-uniformity norm. We also consider the restricted setting of single-copy access, where we give an O(n)-query Clifford tester that requires no auxiliary memory qubits or adaptivity. We complement this with a lower bound, proving that any such, potentially adaptive, single-copy algorithm needs at least Ω(n1/4) queries. To obtain our results, we leverage the structure of the commutant of the Clifford group, obtaining several technical statements that may be of independent interest.

We prove a conjecture of Arunachalam & Dutt on the existence of a tolerant stabilizer testing algorithm, and achieve an exponential improvement in the parameters of the tester. Key to our argument is a generalized uncertainty relation for sets of Pauli operators, based on the Lovász theta function.

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.

We prove an almost optimal hypercontractive inequality for products of quantum erasure channels, generalizing the hypercontractivity for classical binary erasure channels. To our knowledge, this is the first tensorization-type hypercontractivity bound for quantum channels with no fixed states. The traditional inductive arguments for classical hypercontractivity cannot be generalized to the quantum setting due to the nature of the non-commutativity of matrices. To overcome the difficulty, we establish a novel quantum log-Sobolev inequality for Bernoulli entropy, which includes the classical log-Sobolev inequality and the quantum log-Sobolev inequality as one-partite cases. To our knowledge, its classical counterpart is also unknown prior to this work. We establish a connection between our quantum log-Sobolev inequality and the hypercontractivity bound for quantum erasure channels via a refined quantum Gross’ lemma, extending the analogous connection between the quantum log- Sobolev inequality and the hypercontractivity for qubit unital channels. As an application, we prove an almost tight bound (up to a constant factor) on the classical communication complexity of two-party common randomness generation assisted with erasednoisy EPR states, generalizing the tight bound on the same task assisted with erased-noisy random strings due to Guruswami and Radhakrishnan.

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).