In this paper, we systematically study property testing of unitary operators. We first introduce a distance measure that reflects the average difference between unitary operators. Then we show that, with respect to this distance measure, the orthogonal group, quantum juntas (i.e., unitary operators that only nontrivially act on a few qubits of the system), and the Clifford group can be all efficiently tested. In fact, their testing algorithms have query complexities independent of the system's size and have only one-sided error. Then we give an algorithm that tests any finite subset of the unitary group, and demonstrate an application of this algorithm to the permutation group. This algorithm also has one-sided error and polynomial query complexity, but it is unknown whether it can be efficiently implemented in general.
In this paper, we systematically study property testing of unitary operators. We first introduce a distance measure that reflects the average difference between unitary operators. Then we show that, with respect to this distance measure, the orthogonal group, quantum juntas (i.e., unitary operators that only nontrivially act on a few qubits of the system), and the Clifford group can be all efficiently tested. In fact, their testing algorithms have query complexities independent of the system's size and have only one-sided error. Then we give an algorithm that tests any finite subset of the unitary group, and demonstrate an application of this algorithm to the permutation group. This algorithm also has one-sided error and polynomial query complexity, but it is unknown whether it can be efficiently implemented in general.
We study the query complexity of testing quantum juntas. Given an unknown n-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most k qubits or is ε-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to U, but not to U† or controlled-U. We give tight bounds for both unitary and channel junta testing. For sufficiently large k, n≥2k, and a broad range of ε, both problems have query complexity Θ(k/(ε2logk)). Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an O(k) upper bound and a Ω(k) lower bound at constant ε, establishing the optimal Θ(k/logk) query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant ε, they also give a separation between Θ(k/logk) forward queries and O(k) queries with inverse access.
In this paper, we study the following question: given a black box performing some unknown quantum measurement on a multi-qudit system, how do we test whether this measurement has certain property or is far away from having this property. We call this task \textit{property testing} of quantum measurement. We first introduce a metric for quantum measurements, and show that it possesses many nice features. Then we show that, with respect to this metric, the following classes of measurements can be efficiently tested: 1. the stabilizer measurements, which play a crucial role for quantum error correction; 2. the k-local measurements, i.e. measurements whose outcomes depend on a subsystem of at most k qudits; 3. the permutation-invariant measurements, which include those measurements used in quantum data compression, state estimation and entanglement concentration. In fact, all of them can be tested with query complexity independent of the system's dimension. Furthermore, we also present an algorithm that can test any finite set of measurements. Finally, we consider the following natural question: given two black-box measurement devices, how do we estimate their distance? We give an efficient algorithm for this task, and its query complexity is also independent of the system's dimension. As a consequence, we can easily test whether two unknown measurements are identical or very different.
Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is ε1-close to some quantum k-junta or is ε2-far from any quantum k-junta, where an n-qubit unitary U is called a quantum k-junta if it only non-trivially acts on just k of the n qubits. More specifically, we present a tolerant tester with ε1=8ρε, ε2=ε, and ρ∈(0,1), and the query complexity is O(ε2ρ(1−ρ)kklogk), which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to U†, whereas this is usually required in the literature.
In the k-junta testing problem, a tester has to efficiently decide whether a given function f:{0,1}n→{0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ε-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity O~(k/ε) and time complexity O~(nk/ε). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ε).
In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0, 1}n → {0, 1} is a k-junta (i.e., depends on at most k of its input bits) or is ∊-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity and time complexity . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ∊).
In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0,1}n → {0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ∈-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity Ō(√∈) and time complexity Ō(n√∈). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of ω(k1/3) queries for junta-testing (for constant ∈).