arXiv:2609.37926
Optimal Quantum Junta Testing without Inverse Queries
Jinge Bao, Minbo Gao, Penghui Yao
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 $\varepsilon$-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to $U$, but not to $U^\dagger$ or controlled-$U$. We give tight bounds for both unitary and channel junta testing. For sufficiently large $k$, $n \ge 2k$, and a broad range of $\varepsilon$, both problems have query complexity $Θ\left(k/(\varepsilon^2\log k)\right)$. 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 $\widetilde{O}(k)$ upper bound and a $\widetildeΩ(\sqrt{k})$ lower bound at constant $\varepsilon$, 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 $\varepsilon$, they also give a separation between $Θ(k/\log k)$ forward queries and $\widetilde{O}(\sqrt{k})$ queries with inverse access.
AI Summary
The paper studies testing whether an unknown $n$-qubit unitary or channel acts nontrivially on at most $k$ qubits, versus being $\varepsilon$-far from every such operation. Unitary access is forward-only: neither the inverse nor controlled-unitary access is supplied. Distances are phase-insensitive normalized Hilbert–Schmidt distance for unitaries and normalized Hilbert–Schmidt distance between Choi matrices for channels. Both problems have query complexity $\Theta(k/(\varepsilon^2\log k))$ for sufficiently large $k$, $n\geq2k$, and $2^{-k/16}\leq\varepsilon\leq1/16$. Upper bounds of $O(k/(\varepsilon^2\log(ek)))$ hold for all $1\leq k\leq n$ and $0<\varepsilon\leq1$, using nonadaptive product inputs and single-qubit measurements without ancillas. The channel result closes a previous near-linear-versus-square-root gap. At constant distance, comparison with the existing inverse-access upper bound $O(\sqrt{k}\log^{3/2}k)$ establishes an access-model separation. The upper bounds use influence sampling to produce random subsets of qubits, then apply a classical tester for whether all samples fit inside a common $k$-element set. Its analysis combines sample unions, residual-set truncation, and a Poissonized polynomial statistic. Lower bounds encode classical support-size testing into phase-masked addressing unitaries. Averaging random phases separates query paths by address histograms, enabling exact simulation of averaged acceptance probabilities with classical samples, even for adaptive quantum testers with ancillas. The matching lower bounds require the stated size and distance restrictions. Classicalization applies to the constructed ensemble after averaging, not arbitrary oracles; inverse queries invalidate the argument. Channel access excludes access to an environment or Stinespring dilation.
OpenAI GPT-6 Astra and GPT-5.6 Sol were used extensively throughout the preparation of this manuscript, including for mathematical exploration, checking proof arguments, drafting, and language polishing.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 57 pages, 1 table, 3 algorithms