We study efficient quantum certification algorithms for unitary quantum process using no ancilla. Previous study showed that one can distinguish whether an unknown unitary $U$ is equal to or $\varepsilon$-far from a known or unknown unitary $V$ in fixed dimension with $O(\varepsilon^{-2})$ uses of the unitary, in which the Choi state is used and thus a high dimensional ancilla system is always needed. We give an algorithm that distinguishes the two cases with $O(\varepsilon^{-1})$ uses of the unitary, using fewer or no ancilla, outperforming previous relevant results.
We study efficient quantum certification algorithms for unitary quantum process using no ancilla. Previous study showed that one can distinguish whether an unknown unitary U is equal to or ε-far from a known or unknown unitary V in fixed dimension with O(ε−2) uses of the unitary, in which the Choi state is used and thus a high dimensional ancilla system is always needed. We give an algorithm that distinguishes the two cases with O(ε−1) uses of the unitary, using fewer or no ancilla, outperforming previous relevant results.
We study efficient quantum certification algorithms for quantum state set and unitary quantum channel. We present an algorithm that uses O(ε−4ln∣P∣) copies of an unknown state to distinguish whether the unknown state is contained in or ε-far from a finite set P of known states with respect to the trace distance. This algorithm is more sample-efficient in some settings. Previous study showed that one can distinguish whether an unknown unitary U is equal to or ε-far from a known or unknown unitary V in fixed dimension with O(ε−2) uses of the unitary, in which the Choi state is used and thus an ancilla system is needed. We give an algorithm that distinguishes the two cases with O(ε−1) uses of the unitary, using much fewer or no ancilla compared with previous results.
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.
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.
Estimating the unitarity of an unknown quantum channelEprovides information on how much it is unitary, which is a basic and important problem in quantum device certification and benchmarking. Unitarity estimation can be performed with either coherent or incoherent access, where the former in general leads to better query complexity while the latter allows more practical implementations. In this paper, we provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms that useO(ϵ−2)andO(d⋅ϵ−2)calls toEwith coherent and incoherent accesses, respectively, wheredis the dimension of the system thatEacts on and$\epsilon istherequiredprecision.Wefurthershowthatboththed−dependenceand\epsilon −dependenceofouralgorithmsareoptimal.Aspartofourresults,wesettlethequerycomplexityofthedistinguishingproblemfordepolarizingandunitarychannelswithincoherentaccessbygivingamatchinglowerbound\Omega (\sqrt {d}),improvingthepriorbestlowerbound\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).
In the quantum state distinguishing problem, an algorithm is given copies of a state ∣ψ⟩ or ∣φ⟩ separated by trace distance ε, and tasked with deciding which is the case. It is a standard result that Θ(ε−2) copies are required, while having access to a unitary state preparation oracle and its inverse improves this to Θ(ε−1) queries. We study the intermediate case with forward-only access, capturing scenarios where the oracle is a physical process that cannot be reversed. Tang and Wright recently showed that distinguishing a known state from an \emph{unknown} close state requires Ω(ε−2) forward queries in high dimension; we strengthen this result by proving the same bound even when both states are known, as in the state distinguishing setting. Moreover, our lower bound uses a direct hybrid argument, avoiding advanced compressed oracle techniques used in the prior work. In contrast, we give a dimension-independent algorithm solving a continuous-time variant of state distinguishing with only O(ε−1) total forward evolution time. The algorithm uses quantum Zeno dynamics to confine evolution to a known two-dimensional subspace. Thus, a quadratic advantage survives without inverse access for a natural continuous-time analogue of state distinguishing.
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 Ω(d/ε) and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of Θ(d/ε) . 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 O(1/ε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.