arXiv:2212.09319 · IEEE Transactions on Information Theory

Unitarity Estimation for Quantum Channels

Kean Chen, Qisheng Wang, Peixun Long, Mingsheng Ying

Published Mar 31, 2023• 12 citations

Abstract

Estimating the unitarity of an unknown quantum channel$\mathcal {E}$provides 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 use$O(\epsilon ^{-2})$and$O(\sqrt {d}\cdot \epsilon ^{-2})$calls to$\mathcal {E}$with coherent and incoherent accesses, respectively, where$d$is the dimension of the system that$\mathcal {E}$acts on and$\epsilon $is the required precision. We further show that both the$d$-dependence and$\epsilon $-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound$\Omega (\sqrt {d})$, improving the prior best lower bound$\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).

DOI: 10.1109/tit.2023.3263645

Related papers

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

quant-pharXiv:2604.26900Leibniz international proceedings in informaticsApr 30, 20260 citations

Optimal Diamond Distance Estimation for Unitary Channels

Jinge Bao, Qisheng Wang

quant-pharXiv:2610.40623Oct 30, 20260 citations

Query-optimal estimation of unitary channels in diamond distance

Jeongwan Haah, Robin Kothari, Ryan O’Donnell +1 more

arXiv:2302.14066Annual Symposium on Foundations of Computer ScienceNov 6, 202323 citations

Unitary Channel Testing Under a Depolarizing Noise Assumption

Hirak Ghosh, Andrew Jackson, Animesh Datta

quant-pharXiv:2606.10730Jun 10, 20260 citations

Query complexities of quantum channel discrimination and estimation: A unified approach

Zixin Huang, Johannes Jakob Meyer, Theshani Nuradha +1 more

quant-pharXiv:2511.10832Nov 17, 20250 citations

On the query complexity of unitary channel certification

Sangwoo Jeon, Changhun Oh

arXiv:2507.17254npj Quantum InformationDec 29, 20250 citations

arXiv:2212.09319 · IEEE Transactions on Information Theory

Unitarity Estimation for Quantum Channels

Kean Chen, Qisheng Wang, Peixun Long, Mingsheng Ying

Published Mar 31, 2023• 12 citations

arXiv HTML PDF

Abstract

Estimating the unitarity of an unknown quantum channel

\mathcal {E}

provides 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 use

O(\epsilon ^{-2})

and

O(\sqrt {d}\cdot \epsilon ^{-2})

calls to

\mathcal {E}

with coherent and incoherent accesses, respectively, where

d

is the dimension of the system that

\mathcal {E}

acts on and

\epsilon

is the required precision. We further show that both the

d

-dependence and

\epsilon

-dependence of our algorithms are optimal. As part of our results, we settle the query complexity of the distinguishing problem for depolarizing and unitary channels with incoherent access by giving a matching lower bound

\Omega (\sqrt {d})

, improving the prior best lower bound

\Omega (\sqrt [{3}]{d})

by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).

DOI: 10.1109/tit.2023.3263645

Related papers

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

We consider the problem of quantum channel certification to unitary, where one is given access to an unknown $d$ -dimensional channel $\mathcal{E}$ , and wants to test whether $\mathcal{E}$ is equal to a target unitary channel or is $\varepsilon$ -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/\varepsilon^2)$ queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii) $Θ(d/\varepsilon)$ queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii) $Θ(\sqrt{d}/\varepsilon)$ 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 consider the problem of quantum channel certification to unitary, where one is given access to an unknown $d$-dimensional channel $\mathcal{E}$, and wants to test whether $\mathcal{E}$ is equal to a target unitary channel or is $\varepsilon$-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/\varepsilon^2)$ queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii) $Θ(d/\varepsilon)$ queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii) $Θ(\sqrt{d}/\varepsilon)$ 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.

quant-pharXiv:2604.26900Leibniz international proceedings in informaticsApr 30, 20260 citations

Optimal Diamond Distance Estimation for Unitary Channels

Jinge Bao, Qisheng Wang

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 $\varepsilon$ , using $O(\sqrt{d}/\varepsilon)$ 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).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 $\varepsilon$, using $O(\sqrt{d}/\varepsilon)$ 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).

quant-pharXiv:2610.40623Oct 30, 20260 citations

Query-optimal estimation of unitary channels in diamond distance

Jeongwan Haah, Robin Kothari, Ryan O’Donnell +1 more

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$ -close to the unknown unitary in diamond norm. We design an algorithm achieving error $\varepsilon$ using $O\left(\mathrm{~d}^{2} / \varepsilon\right)$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)$ [via standard process tomography] or $O\left(\mathrm{~d}^{2.5} / \varepsilon\right)$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce $\varepsilon$ -error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega\left(\mathrm{d}^{2} / \varepsilon\right)$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$-close to the unknown unitary in diamond norm. We design an algorithm achieving error $\varepsilon$ using $O\left(\mathrm{~d}^{2} / \varepsilon\right)$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)$ [via standard process tomography] or $O\left(\mathrm{~d}^{2.5} / \varepsilon\right)$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce $\varepsilon$-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega\left(\mathrm{d}^{2} / \varepsilon\right)$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.

arXiv:2302.14066Annual Symposium on Foundations of Computer ScienceNov 6, 202323 citations

Unitary Channel Testing Under a Depolarizing Noise Assumption

Hirak Ghosh, Andrew Jackson, Animesh Datta

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 $\varepsilon$ -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/\varepsilon).$ The query complexity of the relaxed problem of testing whether the black-box channel is $\varepsilon_1$ -close to a target unitary or $\varepsilon_2$ -far in the diamond distance is $Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).$ In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.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 $\varepsilon$-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/\varepsilon).$ The query complexity of the relaxed problem of testing whether the black-box channel is $\varepsilon_1$-close to a target unitary or $\varepsilon_2$-far in the diamond distance is $Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).$ In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.

quant-pharXiv:2606.10730Jun 10, 20260 citations

Query complexities of quantum channel discrimination and estimation: A unified approach

Zixin Huang, Johannes Jakob Meyer, Theshani Nuradha +1 more

The goal of quantum channel discrimination and estimation is to determine the identity of an unknown channel from a discrete or continuous set, respectively. The query complexity of these tasks is equal to the minimum number of times one must call an unknown channel to identify it within a desired threshold on the error probability. In this paper, we establish lower bounds on the query complexities of channel discrimination and estimation, in both the parallel and adaptive access models. We do so by establishing new or applying known upper bounds on the squared Bures distance and symmetric logarithmic derivative Fisher information of channels. Phrasing our statements and proofs in terms of isometric extensions of quantum channels allows us to give conceptually simple proofs for both novel and known bounds. We also provide alternative proofs for several established results in an effort to present a consistent and unified framework for quantum channel discrimination and estimation, which we believe will be helpful in addressing future questions in the field.The goal of quantum channel discrimination and estimation is to determine the identity of an unknown channel from a discrete or continuous set, respectively. The query complexity of these tasks is equal to the minimum number of times one must call an unknown channel to identify it within a desired threshold on the error probability. In this paper, we establish lower bounds on the query complexities of channel discrimination and estimation, in both the parallel and adaptive access models. We do so by establishing new or applying known upper bounds on the squared Bures distance and symmetric logarithmic derivative Fisher information of channels. Phrasing our statements and proofs in terms of isometric extensions of quantum channels allows us to give conceptually simple proofs for both novel and known bounds. We also provide alternative proofs for several established results in an effort to present a consistent and unified framework for quantum channel discrimination and estimation, which we believe will be helpful in addressing future questions in the field.

quant-pharXiv:2511.10832Nov 17, 20250 citations

On the query complexity of unitary channel certification

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 / ε 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.

arXiv:2507.17254npj Quantum InformationDec 29, 20250 citations

Estimating the unitarity of an unknown quantum channel

\mathcal {E}

O(\epsilon ^{-2})

and

O(\sqrt {d}\cdot \epsilon ^{-2})

calls to

\mathcal {E}

with coherent and incoherent accesses, respectively, where

d

is the dimension of the system that

\mathcal {E}

acts on and

\epsilon

is the required precision. We further show that both the

d

-dependence and

\epsilon

\Omega (\sqrt {d})

, improving the prior best lower bound

\Omega (\sqrt [{3}]{d})

by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).

We consider the problem of quantum channel certification to unitary, where one is given access to an unknown

d

-dimensional channel

\mathcal{E}

, and wants to test whether

\mathcal{E}

is equal to a target unitary channel or is

\varepsilon

-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/\varepsilon^2)

queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii)

Θ(d/\varepsilon)

queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii)

Θ(\sqrt{d}/\varepsilon)

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.

d

-dimensional unitary channels to within additive error

\varepsilon

, using

O(\sqrt{d}/\varepsilon)

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).

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is

\varepsilon

-close to the unknown unitary in diamond norm. We design an algorithm achieving error

\varepsilon

using

O\left(\mathrm{~d}^{2} / \varepsilon\right)

applications of the unknown channel and only one qudit. This improves over prior results, which use

O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)

[via standard process tomography] or

O\left(\mathrm{~d}^{2.5} / \varepsilon\right)

[Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce

\varepsilon

-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires

\Omega\left(\mathrm{d}^{2} / \varepsilon\right)

applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.

\varepsilon

-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/\varepsilon).

The query complexity of the relaxed problem of testing whether the black-box channel is

\varepsilon_1

-close to a target unitary or

\varepsilon_2

-far in the diamond distance is

Θ\bigl(\varepsilon_2/(\varepsilon_2 - \varepsilon_1)^2\bigr).

In both cases, we provide matching lower bounds that hold even for adaptive, ancilla-assisted protocols with multi-outcome incoherent measurements.

\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.