We study the power of local test for bipartite quantum states. Our central result is that, for properties of bipartite pure states, unitary invariance on one part implies anoptimal(over all global testers) local tester acting only on the other part. As an application, we demonstrate • Purified samples offer no advantage in property testing of mixed states. • A matching lower bound Ω(r2/ε2) for testing the Schmidt rank of bipartite states with perfect completeness, settling an open question raised in the survey of Montanaro and de Wolf (ToC 2016). • A lower bound Ω(( √n+ √r)· √r/ε2) for testing whether ann-partite state is a matrix product state of bond dimensionror ε-far, improving the prior lower bounds Ω( √n/ε2) by Soleimanifar and Wright (SODA 2022) and Ω( √r) by Aaronson et al. (ITCS 2024). • A matching lower bound Ω(d/ε2) for testing whether ad-dimensional bipartite state is maximally entangled or ε-far, showing that the algorithm of O’Donnell and Wright (STOC 2015) is optimal for this task. • A query lower bound Ω(d/ √ Δ) for thed-dimensional entanglement entropy problem with gap Δ, improving the prior lower bounds Ω(4√d) by She and Yuen (ITCS 2023) and Ω(1/ √ Δ) by Wang and Zhang (SICOMP 2025) and Weggemans (Quantum 2025). Moreover, we extend our central result to a robust version where the tested states are subject to noise and are not guaranteed to be pure: in this case, one-way LOCC is sufficient to realize the optimal tester.
We study the power of local test for bipartite quantum states. Our central result is that, for properties of bipartite pure states, unitary invariance on one part implies anoptimal(over all global testers) local tester acting only on the other part. As an application, we demonstrate • Purified samples offer no advantage in property testing of mixed states. • A matching lower bound Ω(r2/ε2) for testing the Schmidt rank of bipartite states with perfect completeness, settling an open question raised in the survey of Montanaro and de Wolf (ToC 2016). • A lower bound Ω(( √n+ √r)· √r/ε2) for testing whether ann-partite state is a matrix product state of bond dimensionror ε-far, improving the prior lower bounds Ω( √n/ε2) by Soleimanifar and Wright (SODA 2022) and Ω( √r) by Aaronson et al. (ITCS 2024). • A matching lower bound Ω(d/ε2) for testing whether ad-dimensional bipartite state is maximally entangled or ε-far, showing that the algorithm of O’Donnell and Wright (STOC 2015) is optimal for this task. • A query lower bound Ω(d/ √ Δ) for thed-dimensional entanglement entropy problem with gap Δ, improving the prior lower bounds Ω(4√d) by She and Yuen (ITCS 2023) and Ω(1/ √ Δ) by Wang and Zhang (SICOMP 2025) and Weggemans (Quantum 2025). Moreover, we extend our central result to a robust version where the tested states are subject to noise and are not guaranteed to be pure: in this case, one-way LOCC is sufficient to realize the optimal tester.
Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including:
1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity tr(ρ2) and the inner product tr(ρσ).
2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals tr(ρk).
3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal.
4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state.
5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states.
6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal.
To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.
Product testing, i.e., deciding whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition, serves as a bridge between quantum property testing, unentangled quantum proof systems, and tensor optimization. Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined. In this work, we determine this curve exactly. Let ω be the maximum squared overlap of the input with a product state, and let PTn(ω) be the largest possible acceptance probability of the product test over all n-partite pure states with product overlap ω, allowing arbitrary finite local dimensions. We prove that, for every $n\ge 2 $ and every $ω\in(0,1] $, PTn(ω)=21(1+mω2+(1−mω)2), where $m=\lfloor1/ω\rfloor $. The formula recovers the previously known tight section of the curve for $ω\ge 1/2 $, resolves all low-overlap regimes $ω<1/2 $, and implies $\mathrm{PT}_n(ω)\to 1/2 $ as ω→0 answering an open problem in [Soleimanifar and Wright, SODA 2022]. As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from QMA(k) to QMA(2). Our techniques, built upon those of Soleimanifar and Wright, allow us to resolve these open questions while remaining surprisingly elementary.
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 unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary and has to decide whether it satisfies some property. We propose a new technique for proving lower bounds on the quantum query complexity of unitary property testing and related problems, which utilises its connection to unitary channel discrimination. The main advantage of this technique is that all obtained lower bounds hold for any C -tester with C⊆QMA(2)/qpoly , showing that even having access to both (unentangled) quantum proofs and advice does not help for many unitary property testing problems. We apply our technique to prove lower bounds for problems like quantum phase estimation, the entanglement entropy problem, quantum Gibbs sampling and more, removing all logarithmic factors in the lower bounds obtained by the sample-to-query lifting theorem of Wang and Zhang (2023). As a direct corollary, we show that there exist quantum oracles relative to which QMA(2)⊅SBQP and QMA/qpoly⊅SBQP . The former shows that, at least in a black-box way, having unentangled quantum proofs does not help in solving problems that require high precision.
Quantum channel discrimination is a fundamental task in quantum information processing. In the one-shot regime, discrimination between two candidate channels is characterized by the diamond norm. Beyond this basic setting, however, many scenarios in distributed quantum information processing remain unresolved, motivating notions of distinguishability that capture the power of the available resources. In this work, we formulate a theory of testers for bipartite channel discrimination, leading to the concept of the entanglement cost of bipartite channel discrimination: the minimum Schmidt rank k of a shared maximally entangled state required for local protocols to achieve the globally optimal success probability. We introduce k-injectable testers as a tester-based description of entanglement-assisted local discrimination and, in particular, study the class of k-injectable positive-partial-transpose (PPT) testers, which constitutes a numerically tractable relaxation of the practically relevant class of LOCC testers.
For every k, we derive a semidefinite program (SDP) for the optimal success probability, which in turn yields an efficiently computable one-shot PPT entanglement cost. To render these optimization problems numerically feasible, we prove a symmetry-reduction principle for covariant channel pairs, thereby reducing the effective dimension of the associated SDPs. Finally, by dualizing the SDP, we derive bounds on the composite channel-discrimination problem and illustrate our framework with proof-of-principle examples based on the depolarizing channel, the depolarized SWAP channel, and the Werner--Holevo channels.
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that Θ(N) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where N denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform O(N1/3) queries, showing a polynomial speedup. They also proved that Ω(N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight Ω(N1/3) quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.