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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\Omega (\sqrt{d}/\varepsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ω</mi> <mrow> <mo>(</mo> <mrow> <msqrt> <mrow> <mi>d</mi> </mrow> </msqrt> <mo>/</mo> <mi>ε</mi> </mrow> <mo>)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\Theta (\sqrt{d}/\varepsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mrow> <mo>(</mo> <mrow> <msqrt> <mrow> <mi>d</mi> </mrow> </msqrt> <mo>/</mo> <mi>ε</mi> </mrow> <mo>)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">${\mathcal{O}}(1/{\varepsilon }^{2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi class="MJX-tex-caligraphic" mathvariant="script">O</mi> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>/</mo> <msup> <mrow> <mi>ε</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msup> </mrow> <mo>)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> 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.

On the query complexity of unitary channel certification

期刊论文
出版模式：

开放获取
发表日期：

2025年12月29日

查看全文

Sangwoo Jeon,
Changhun Oh

摘要

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/ε²) queries, matching the known upper bound. In addition, for general quantum algorithms, we prove a lower bound of $\Omega (\sqrt{d}/\varepsilon )$ $Ω (\sqrt{d} / ε)$ and present a matching quantum algorithm based on quantum singular value transformation, establishing a tight query complexity of $\Theta (\sqrt{d}/\varepsilon )$ $Θ (\sqrt{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 ${\mathcal{O}}(1/{\varepsilon }^{2})$ $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.