Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.20608

Asymptotically optimal unitary estimation in $\mathrm{SU}(3)$ by the analysis of graph Laplacian

Satoshi Yoshida, Hironobu Yoshida, Mio Murao

Published Sep 24, 2025• 0 citations
arXivHTMLPDF

Abstract

Unitary estimation is the task to estimate an unknown unitary operator $U\in\mathrm{SU}(d)$ with $n$ queries to the corresponding unitary operation, and its accuracy is evaluated by an estimation fidelity. We show that the optimal asymptotic fidelity of $3$-dimensional unitary estimation is given by $F_\mathrm{est}(n,d=3) = 1-\frac{56π^2}{9n^2} + O(n^{-3})$ by the analysis of the graph Laplacian based on the finite element method. We also show the lower bound on the fidelity of $d$-dimensional unitary estimation for an arbitrary $d$ given by $F_\mathrm{est}(n,d) \geq 1- \frac{(d+1)(d-1)(3d-2)(3d-1)}{6n^2} + O(n^{-3})$ achieving the best known lower bound and tight scaling with respect to $n$ and $d$. This lower bound is derived based on the unitary estimation protocol shown in [J. Kahn, Phys. Rev. A 75, 022326, 2007].

DOI
10.48550/arxiv.2509.20608

Related papers

Optimal classical shadow estimation of unitary channels at Heisenberg limit

Entong He, Zihao Li, Noam Scully +2 more

Full tomography of an unknown quantum evolution is resource-intensive and often unnecessary when the goal is only to predict selected properties. This motivates the study of classical shadow estimation of unitary channels (CSEU), a task in which one queries an unknown $d$-dimensional unitary $U$ and stores classical data that can later be used to predict expectation values $\mathrm{tr}[O UρU^\dagger]$ for arbitrary input states $ρ$ and observables $O$. Here we propose a parallel and non-adaptive CSEU protocol that uses $\mathcal{O}(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})$ queries to $U$ when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error $\varepsilon$ and is query-optimal, as we prove a matching lower bound $Ω(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})$ for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.

quant-pharXiv:2606.13638•Jun 12, 2026•0 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.

arXiv:2302.14066•Annual Symposium on Foundations of Computer Science•Nov 6, 2023•23 citations

Asymptotically optimal purification of noisy unitary channels in any dimension

Ryotaro Niwa, Satoshi Yoshida, Mio Murao

We consider the problem of noisy unitary purification. Given access to an unknown $d$-dimensional unitary channel followed by depolarizing noise of strength $p$, we aim to construct a superchannel that universally purifies the noisy unitary back to the original unknown unitary. We optimize over arbitrary adaptive sequential strategies and analytically derive the optimal fidelity to the leading order in the noise strength and number of channel uses, while also providing a concrete $\mathrm{SU}(d)$-covariant parallel strategy that attains the optimum. Our result implies the query complexity $Θ(d^2p/ε)$ for achieving leading-order infidelity $ε$ in the low-noise regime, which scales better than the naive approach combining optimal state purification and storage-and-retrieval of quantum channels. We also consider the dual problem of noisy unitary conjugation, where the goal is to obtain the best approximation of the complex conjugate of the original unknown unitary from access to noisy queries. We show that the optimal fidelity for this task coincides with that of noisy unitary purification to the leading-order in the low-noise and large-query limit.

quant-pharXiv:2608.26061•Aug 27, 2026•0 citations

Fast rate estimation of a unitary operation in SU(d)

Jonas Kahn

We give an explicit procedure based on entangled input states for estimating a $\mathrm{SU}(d)$ operation $U$ with rate of convergence $1∕{N}^{2}$ when sending $N$ particles through the device. We prove that this rate is optimal. We also evaluate the constant $C$ such that the asymptotic risk is $C∕{N}^{2}$. However, other strategies might yield a better constant $C$.

arXiv:quant-ph/0603115•Physical Review A•Feb 23, 2007•48 citations

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group

Daiki Suruga

Estimating properties of unknown unitary operations is a fundamental task in quantum information science. While full unitary tomography requires a number of samples to the unknown unitary scaling linearly with the dimension (implying exponentially with the number of qubits), estimating specific functions of a unitary can be significantly more efficient. In this paper, we present a unified framework for the sample-efficient estimation of arbitrary square integrable functions $f: \mathbf{U}(d) \to \mathbb{C}$, using only access to the controlled-unitary operation. We first provide a tight characterization of the optimal sample complexity when the accuracy is measured by the averaged bias over the unitary $\mathbf{U}(d)$. We then construct a sample-efficient estimation algorithm that becomes optimal under the Probably Approximately Correct (PAC) learning criterion for various classes of functions. Applications include optimal estimation of matrix elements of irreducible representations, the trace, determinant, and general polynomial functions on $\mathbf{U}(d)$. Our technique generalize the Hadamard test and leverage tools from representation theory, yielding both lower and upper bound on sample complexity.

arXiv:2509.05710•Sep 6, 2025•0 citations

Unitarity Estimation for Quantum Channels

Kean Chen, Qisheng Wang, Peixun Long +1 more

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

arXiv:2212.09319•IEEE Transactions on Information Theory•Mar 31, 2023•12 citations
Asymptotically optimal unitary estimation in SU(3)\mathrm{SU}(3)SU(3) by the analysis of graph Laplacian
Unitary estimation is the task to estimate an unknown unitary operator U∈SU(d)U\in\mathrm{SU}(d)U∈SU(d) with nnn queries to the corresponding unitary operation, and its accuracy is evaluated by an estimation fidelity. We show that the optimal asymptotic fidelity of 333-dimensional unitary estimation is given by Fest(n,d=3)=1−56π29n2+O(n−3)F_\mathrm{est}(n,d=3) = 1-\frac{56π^2}{9n^2} + O(n^{-3})Fest​(n,d=3)=1−9n256π2​+O(n−3) by the analysis of the graph Laplacian based on the finite element method. We also show the lower bound on the fidelity of ddd-dimensional unitary estimation for an arbitrary ddd given by Fest(n,d)≥1−(d+1)(d−1)(3d−2)(3d−1)6n2+O(n−3)F_\mathrm{est}(n,d) \geq 1- \frac{(d+1)(d-1)(3d-2)(3d-1)}{6n^2} + O(n^{-3})Fest​(n,d)≥1−6n2(d+1)(d−1)(3d−2)(3d−1)​+O(n−3) achieving the best known lower bound and tight scaling with respect to nnn and ddd. This lower bound is derived based on the unitary estimation protocol shown in [J. Kahn, Phys. Rev. A 75, 022326, 2007].
Full tomography of an unknown quantum evolution is resource-intensive and often unnecessary when the goal is only to predict selected properties. This motivates the study of classical shadow estimation of unitary channels (CSEU), a task in which one queries an unknown ddd-dimensional unitary UUU and stores classical data that can later be used to predict expectation values tr[OUρU†]\mathrm{tr}[O UρU^\dagger]tr[OUρU†] for arbitrary input states ρρρ and observables OOO. Here we propose a parallel and non-adaptive CSEU protocol that uses O(min⁡{dε−2,d3/2ε−1})\mathcal{O}(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})O(min{dε−2,d3/2ε−1}) queries to UUU when the observables have constant effective size. This achieves Heisenberg scaling with respect to the additive error ε\varepsilonε and is query-optimal, as we prove a matching lower bound Ω(min⁡{dε−2,d3/2ε−1})Ω(\min\{d\varepsilon^{-2},d^{3/2}\varepsilon^{-1}\})Ω(min{dε−2,d3/2ε−1}) for the query complexity, which remains valid even when stronger access to the unknown unitary is available. Our CSEU protocol is a versatile primitive with applications to several quantum learning tasks. In particular, it yields a near-optimal algorithm for learning an arbitrary Hamiltonian from its real-time evolution in the high-precision regime and recovers the best-known bounds for several tasks in a unified way.
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( d2/ε)O\left(\mathrm{~d}^{2} / \varepsilon\right)O( d2/ε) applications of the unknown channel and only one qudit. This improves over prior results, which use O( d3/ε2)O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)O( d3/ε2) [via standard process tomography] or O( d2.5/ε)O\left(\mathrm{~d}^{2.5} / \varepsilon\right)O( d2.5/ε) [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 Ω(d2/ε)\Omega\left(\mathrm{d}^{2} / \varepsilon\right)Ω(d2/ε) 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 the problem of noisy unitary purification. Given access to an unknown ddd-dimensional unitary channel followed by depolarizing noise of strength ppp, we aim to construct a superchannel that universally purifies the noisy unitary back to the original unknown unitary. We optimize over arbitrary adaptive sequential strategies and analytically derive the optimal fidelity to the leading order in the noise strength and number of channel uses, while also providing a concrete SU(d)\mathrm{SU}(d)SU(d)-covariant parallel strategy that attains the optimum. Our result implies the query complexity Θ(d2p/ε)Θ(d^2p/ε)Θ(d2p/ε) for achieving leading-order infidelity εεε in the low-noise regime, which scales better than the naive approach combining optimal state purification and storage-and-retrieval of quantum channels. We also consider the dual problem of noisy unitary conjugation, where the goal is to obtain the best approximation of the complex conjugate of the original unknown unitary from access to noisy queries. We show that the optimal fidelity for this task coincides with that of noisy unitary purification to the leading-order in the low-noise and large-query limit.
We give an explicit procedure based on entangled input states for estimating a SU(d)\mathrm{SU}(d)SU(d) operation UUU with rate of convergence 1∕N21∕{N}^{2}1∕N2 when sending NNN particles through the device. We prove that this rate is optimal. We also evaluate the constant CCC such that the asymptotic risk is C∕N2C∕{N}^{2}C∕N2. However, other strategies might yield a better constant CCC.
Estimating properties of unknown unitary operations is a fundamental task in quantum information science. While full unitary tomography requires a number of samples to the unknown unitary scaling linearly with the dimension (implying exponentially with the number of qubits), estimating specific functions of a unitary can be significantly more efficient. In this paper, we present a unified framework for the sample-efficient estimation of arbitrary square integrable functions f:U(d)→Cf: \mathbf{U}(d) \to \mathbb{C}f:U(d)→C, using only access to the controlled-unitary operation. We first provide a tight characterization of the optimal sample complexity when the accuracy is measured by the averaged bias over the unitary U(d)\mathbf{U}(d)U(d). We then construct a sample-efficient estimation algorithm that becomes optimal under the Probably Approximately Correct (PAC) learning criterion for various classes of functions. Applications include optimal estimation of matrix elements of irreducible representations, the trace, determinant, and general polynomial functions on U(d)\mathbf{U}(d)U(d). Our technique generalize the Hadamard test and leverage tools from representation theory, yielding both lower and upper bound on sample complexity.
Estimating the unitarity of an unknown quantum channelE\mathcal {E}Eprovides 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)O(\epsilon ^{-2})O(ϵ−2)andO(d⋅ϵ−2)O(\sqrt {d}\cdot \epsilon ^{-2})O(d​⋅ϵ−2)calls toE\mathcal {E}Ewith coherent and incoherent accesses, respectively, wheredddis the dimension of the system thatE\mathcal {E}Eacts on and$\epsilon istherequiredprecision.Wefurthershowthatboththeis the required precision. We further show that both theistherequiredprecision.Wefurthershowthatboththed−dependenceand-dependence and−dependenceand\epsilon −dependenceofouralgorithmsareoptimal.Aspartofourresults,wesettlethequerycomplexityofthedistinguishingproblemfordepolarizingandunitarychannelswithincoherentaccessbygivingamatchinglowerbound-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−dependenceofouralgorithmsareoptimal.Aspartofourresults,wesettlethequerycomplexityofthedistinguishingproblemfordepolarizingandunitarychannelswithincoherentaccessbygivingamatchinglowerbound\Omega (\sqrt {d}),improvingthepriorbestlowerbound, improving the prior best lower bound,improvingthepriorbestlowerbound\Omega (\sqrt [{3}]{d})$by (Aharonov et al., 2022) and (Chen et al., FOCS 2021).