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

Daiki Suruga · 2025

Read Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group by Daiki Suruga (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-05710.txt.

Introduction

Learning a chosen property of an unknown quantum operation, without learning all of it, is given exact cost limits by Daiki Suruga in a solo 2025 quantum information paper. Fully mapping a unitary needs samples growing with its size, which explodes with the number of qubits.

Suruga frames estimation of any square-integrable function of the unitary, given controlled access to it, in one scheme. The optimal sample count is pinned down tightly when error is averaged over all unitaries. An algorithm then achieves the optimum under a learning criterion for several function classes. Uses include matrix elements, trace, determinant, and polynomial functions, via a generalised Hadamard test.

Catalog record

CREATORDaiki Suruga
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-05710

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group Daiki Suruga Abstract 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 : 𝖴 ⁡ ( d ) → ℂ f:{\mathsf{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 𝖴 ⁡ ( d ) {\mathsf{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 𝖴 ⁡ ( d ) {\mathsf{U}(d)} . Our technique generalize the Hadamard test and leverage tools from representation theory, yielding both lower and upper bound on sample complexity. 1 Introduction In quantum mechanics, any time evolution of a closed system is described by a unitary operator. As a result, many tasks in quantum information science involve estimating characteristics of a given, yet unknown unitary process. Examples of such tasks include the validation and certification of quantum circuits, error mitigation and correction in quantum processes, and the identification of hidden or unknown dynamics in black-box quantum systems. For such tasks, one needs to accurately estimate some characteristics of the unitaries, such as deviation from the ideal process (i.e., noise), eigenvalues and eigenvectors, or even the complete description of the unitary operator. With the rapid theoretical and experimental advancement of quantum information technologies, developing efficient methods for estimating the properties of unknown unitary operations has become increasingly essential, and has therefore received much attention. A standard approach to estimating the characteristics of a given unitary operator is to reconstruct the entire unitary process—that is, to estimate all matrix elements of the unitary operator (sometimes up to a global phase). As a full characterization of a given unitary process is a fundamental task in quantum information science, numerous studies have addressed the full unitary tomography problem. See, e.g., [ AJV01 , CDS05 , Hay06 , YRC20 , HKOT23 ] , as well as a simple method described in Nielsen and Chuang [ NC10 , Section 8.4.2] . In particular, Ref. [ HKOT23 ] recently showed that estimating a d -dimensional black-box unitary with high probability (when accuracy is measured by the diamond norm) requires \Theta(d^{2}) samples. This implies that the number of required samples scales exponentially with the number of qubits. On the other hand, many other studies focus on estimating a specific characteristic of a black-box unitary U ; here the characteristic is formally defined as the value f(U) of a function f:{\mathsf{U}(d)}\to\mathbb{C} (where {\mathsf{U}(d)} denotes the unitary group of dimension d ). For example, the (normalized) trace \frac{1}{d}\Tr U of a unitary U may be estimated by a simple application of the Hadamard test (see, e.g., [ Chi , Section 16.1] ) with only a constant number of queries to the controlled U operation, no matter how many qubits the unitary U acts on. This application of the Hadamard test provides an exponentially more sample-efficient method (with respect to the number of qubits) than a simple application of the full unitary tomography where the given unitary U is directly estimated by the full tomography first, and then \frac{1}{d}\Tr U is computed by classical computation. As in this example, it is often the case that one provably reduces the number of samples significantly compared to the full unitary tomography, when focusing on a specific characteristic. Because of its provable efficiency, there are many works that focus on estimating a specific characteristic, including the determinant \det U [ ZBQ+25 , AS25 ] , the eigenvalues [ Kit95 , DJSW07 , SHF13 , KLY15 , MdW23 ] , and other quantities [ LSS+20 , SY23 , FEK25 ] . While there is a rich literature on estimating specific functions f(U) , only a few such functions, such as the trace and the determinant, have been systematically studied. For general functions f:{\mathsf{U}(d)}\to\mathbb{C} , no efficient estimation scheme is currently known. It is therefore desirable to develop a unified, sample-efficient estimation framework that applies to a broad class of such functions. 1.1 Our contributions The main purpose of this paper is to provide a unified estimation framework that allows for the construction of sample-efficient algorithms for estimating f(U) for any choice of the function f(U) . Our results are twofold: (i) In our first result, we tightly characterize the sample complexity required to estimate a function f accurately, when the accuracy is measured by the averaged bias over the Haar measure on {\mathsf{U}(d)} . This works for any function f that is square-integrable, i.e., f\in L^{2}({\mathsf{U}(d)}) . (ii) In our second result, we provide an estimation algorithm based on the one designed for the first result. This algorithm become sample-optimal for estimating several kinds of functions even in the PAC (Probably Approximately Correct) learning framework, one of the most standard frameworks for tomography/estimation. In sections 1.1.1 and 1.1.2 , each of the two results is explained in detail respectively. 1.1.1 First result To state our first result formally, we define the averaged bias \mathbf{Bias}_{G}(\mathcal{A},f) of an estimation algorithm \mathcal{A} for a function f as follows: Definition . Let f:{\mathsf{U}(d)}\to\mathbb{C} . We say a query algorithm \mathcal{A} estimates the function f correctly with the averaged bias over the group G={\mathsf{U}(d)} less than \varepsilon if and only if \mathbf{Bias}_{G}(\mathcal{A},f):=\mathbf{E}_{G}\left[\mathbf{Bias}_{g}(\mathcal{A},f)\right]<\varepsilon where \mathbf{Bias}_{g}(\mathcal{A},f) is the bias of the algorithm \mathcal{A} at g\in{\mathsf{U}(d)} , and the expectation \mathbf{E}_{G} is taken over the normalized Haar measure over the group {\mathsf{U}(d)} . One first result is 1 , that shows the number of optimal query access for estimating f under the condition \mathbf{Bias}_{G}(\mathcal{A},f)<\varepsilon is characterized by the quantity \mathsf{Rep}_{\varepsilon}(f) . The formal definition of the quantity \mathsf{Rep}_{\varepsilon}(f) is defined later in 6 . Theorem 1 . Let f\in L^{2}({\mathsf{U}(d)}) , and \mathsf{Rep}_{\varepsilon}(f) be as in 6 . • For any query algorithm \mathcal{A} that queries to controlled-g estimates f with \mathbf{Bias}_{G}(\mathcal{A},f)<\varepsilon , then the algorithm \mathcal{A} requires \Omega(\mathsf{Rep}_{\varepsilon}(f)) query access. • There is an estimation algorithm \mathcal{A} with O(\mathsf{Rep}_{\varepsilon}(f)) query access that satisfies \mathbf{Bias}_{G}(\mathcal{A},f)<\varepsilon . Together, these bounds imply that the optimal query complexity for estimation f with accuracy \varepsilon is \Theta(\mathsf{Rep}_{\varepsilon}(f)). Remarks on 1 . We now give several remarks regarding 1 . • First, we remark that the measure of accuracy \mathbf{Bias}_{G} is not the standard choice considered in the literature. The most commonly used measure is arguably the one defined in the PAC learning framework, which is in the scope of our second result. Compared to the PAC-based criterion, our measure imposes in some sense a weaker requirement; the number of query access for accurately estimating f(U) with respect to the measure \mathbf{Bias}_{G} is always smaller than with respect to the PAC learning measure (under a

Read the complete text