Certifying the correct functioning of a unitary channel is a critical step toward reliable quantum information processing. In this work, we investigate the query complexity of the unitary channel certification task: testing whether a given d -dimensional unitary channel is identical to or ε -far in diamond distance from a target unitary operation. We show that incoherent algorithms—those without quantum memory—require Ω( d / ε 2 ) queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of \(\Omega (\sqrt{d}/\varepsilon )\) and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of \(\Theta (\sqrt{d}/\varepsilon )\) . On the other hand, notably, we prove that for almost all unitary channels drawn from a natural average-case ensemble, certification can be accomplished with only \({\mathcal{O}}(1/{\varepsilon }^{2})\) queries. This demonstrates an exponential query complexity gap between worst- and average-case scenarios in certification, implying that certification is significantly easier for most unitary channels encountered in practice. Together, our results offer both theoretical insights and practical tools for verifying quantum processes.
Certifying the correct functioning of a unitary channel is a critical step toward reliable quantum information processing. In this work, we investigate the query complexity of the unitary channel certification task: testing whether a given d -dimensional unitary channel is identical to or ε -far in diamond distance from a target unitary operation. We show that incoherent algorithms—those without quantum memory—require Ω( d / ε 2 ) queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of (\Omega (\sqrt{d}/\varepsilon )) and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of (\Theta (\sqrt{d}/\varepsilon )) . On the other hand, notably, we prove that for almost all unitary channels drawn from a natural average-case ensemble, certification can be accomplished with only ({\mathcal{O}}(1/{\varepsilon }^{2})) queries. This demonstrates an exponential query complexity gap between worst- and average-case scenarios in certification, implying that certification is significantly easier for most unitary channels encountered in practice. Together, our results offer both theoretical insights and practical tools for verifying quantum processes.
We consider the problem of quantum channel certification to unitary, where one is given access to an unknown d-dimensional channel E, and wants to test whether E is equal to a target unitary channel or is ε-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that:
(i) Θ(d/ε2) queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023).
(ii) Θ(d/ε) queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008).
(iii) Θ(d/ε) queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).
This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.
We present fast algorithms $\unicode{x2013}$ under the depolarizing noise assumption, often made in fault-tolerant quantum computations $\unicode{x2013}$ to test its strength. Our optimal algorithms answer the following question: is the quantum channel implemented by a given black box identical to a target unitary or ε-far from it in the diamond distance, assuming that the deviation is a depolarizing channel with unknown parameter? Our algorithm has a query complexity of Θ(1/ε). The query complexity of the relaxed problem of testing whether the black-box channel is ε1-close to a target unitary or ε2-far in the diamond distance is Θ(ε2/(ε2−ε1)2). In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.
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 the problem of quantum channel certification, we have black box access to a quantum process and would like to decide if this process matches some predefined specification or is ε-far from this specification. The objective is to achieve this task while minimizing the number of times the black box is used. Here, we focus on optimal incoherent strategies for two relevant extreme cases of channel certification. The first one is when the predefined specification is a unitary channel, e.g., a gate in a quantum circuit. In this case, we show that testing whether the black box is described by a fixed unitary operator in dimension d or ε-far from it in the trace norm requires Θ(d/ε2) uses of the black box. The second setting we consider is when the predefined specification is a completely depolarizing channel with input dimension din and output dimension dout. In this case, we prove that, in the non-adaptive setting, Θ~(din2dout1.5/ε2) uses of the channel are necessary and sufficient to verify whether it is equal to the depolarizing channel or ε-far from it in the diamond norm. Finally, we prove a lower bound of Ω(din2dout/ε2) for this problem in the adaptive setting. Note that the special case din=1 corresponds to the well-studied quantum state certification problem.
The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown d-dimensional unitary channels to within additive error ε, using O(d/ε) queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).
Given oracle access to an unknown unitary U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitH, 0<t<1, when the spectrum is separated from the branch cut by a gap δ. Quantum singular value transformation gives an upper bound of O(δ1logε1) queries for approximation error ε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any N-query circuit to the approximation of eitθ by a trigonometric polynomial with degree bounded by O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ(δ1logε1). Consequently, the optimal query complexity for fractional query problem is Θτ(δ1logε1), showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a Ωτ(logε1) bound uniform to δ.