Optimal Quantum Junta Testing without Inverse Queries
Abstract
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/(ε2log k)). 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 Õ(k) upper bound and a Ω̃(√k) lower bound at constant ε, establishing the optimal Θ(k/log k) 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/log k) forward queries and Õ(√k) queries with inverse access.
Related
- On State Distinguishing Without Inverse Queries
- Resource Compatibility in Optimal Quantum Symmetry Testing
- Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
- Optimal Stabilizer Testing and Learning with Limited Quantum Memory
- Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas
BibTeX
@misc{bao2026optimal,
title = {{Optimal Quantum Junta Testing without Inverse Queries}},
author = {Jinge Bao and Minbo Gao and Penghui Yao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37926},
eprint = {2609.37926},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37926},
}
RIS
TY - UNPB
TI - Optimal Quantum Junta Testing without Inverse Queries
AU - Jinge Bao
AU - Minbo Gao
AU - Penghui Yao
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37926
UR - https://arxiv.org/abs/2609.37926
AB - 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/(ε^2log k)). 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 Õ(k) upper bound and a Ω̃(√k) lower bound at constant ε, establishing the optimal Θ(k/log k) 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/log k) forward queries and Õ(√k) queries with inverse access.
ER -