Estimation of Nonlinear Physical Quantities By Measuring Ancillas Nhat A. Nghiem, Tzu-Chieh Wei Abstract In this article, we present quantum algorithms for estimating von Neumann entropy and Renyi entropy, which are crucial physical and information-theoretical properties of a given quantum state ρ \rho . Although there have been existing works that achieved the same goal, some prior developments assume the unitary that prepares the purification to the target state ρ \rho . Here, we consider an alternative setting where only copies of ρ \rho are given and construct a quantum algorithm that estimates the desired entropy. Our framework can complete the given task by measuring a small number of ancilla qubits without directly measuring the system, and that it achieves significant improvement over prior relevant developments. For example, for the Renyi entropy of the order of non-integral α \alpha , our method achieves almost power-of-two improvement in sample complexity with respect to the rank of the given state and almost a power-of-two improvement in error tolerance compared with the work by Wang et al. [Phys. Rev. Applied 19, 044041 (2023)]. I Introduction Quantum computation has emerged as new computational frontier [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 ] . Early proposals have suggested that, by utilizing the intrinsic features of quantum mechanics, information could be stored and processed in a peculiar manner, potentially having the capability to overcome computational hurdles in classical computation. At the core of quantum computation is the quantum algorithm, where a procedure is executed in a programmable manner, utilizing quantum resources that output the solution to any given problem. Beginning with the Deutsh algorithm [ 2 ] , followed by the breakthroughs of Shor’s factorization algorithm [ 5 ] and Grover’s search algorithm [ 6 ] , countless quantum algorithms have been invented to tackle a wide array of problems, stemming from a diverse domain of computation. Notable examples of these subsequent developments include quantum linear solver [ 18 , 19 ] , quantum data fitting [ 20 ] , quantum walks [ 21 , 22 ] , quantum simulation algorithm [ 7 , 8 , 9 , 10 , 22 , 13 , 14 ] , etc. Recently, it has been realized that [ 23 ] there is a common structure underlying many of them. More specifically, a unified and possibly simplified description of all quantum algorithms exists, namely, the quantum singular value transformation framework (QSVT). The fact that the quantum singular value transformation framework allows the unification of quantum algorithms has opened up a new and exciting exploration revenue for subsequent potential development. A meaningful question emerged: In addition to providing a common ground for quantum algorithms, can quantum singular value transformation allow the power of a quantum computer to be more exploitable? In other words, it is of great interest to examine whether or not QSVT allows any stronger quantum algorithm and also constitutes a quantum algorithm that could solve any open challenges thus far. In Ref. [ 24 ] the authors proposed a quantum algorithm to find the largest eigenvalue, based on the classical power method, with quadratic speed-up compared to the classical algorithm. In subsequent constructions, [ 25 , 26 ] , they showed that QSVT could dramatically accelerate the execution of the quantum power method in [ 24 ] , and hence improve from quadratic to superpolynomial speedup. Additionally, in [ 25 ] , the authors also showed that using tools from QSVT, such as block encoding operators and related arithmetic operations (linear combination, multiplication), the quantum gradient descent algorithm first proposed in [ 27 ] could also be substantially sped up. In the work [ 28 ] , the authors showed that the QSVT technique could be used to implement the Petz recovery channel, which is a vital tool in quantum information science. In this work, inspired by the aforementioned examples, we continue the exploration of the power quantum singular value transformation. Here, we aim to leverage the techniques from quantum singular value transformation to construct a quantum algorithm that takes copies of given density matrix \rho , and output an estimation to its Renyi entropy and Von Neumann entropy. These quantities are non-linear functionals of \rho , which are more challenging to estimate compared to the linear functionals, such as the combination of some Pauli product observables. Meanwhile, measuring on copies of \rho alone would not be sufficient to reveal any higher order of its function. In fact, both of these entropic quantities have been considered, and methods of measuring them have been worked out in various contexts [ 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 ] . For example, the works in [ 32 , 33 , 34 , 37 , 36 ] assume unitary access to the purification of state \rho , instead of direct copies of \rho . On the other hand, the works in [ 35 , 37 ] rely on variational strategies, which is heuristic. The two most relevant works to us here are Refs. [ 29 ] and [ 31 ] , where the authors also aimed to estimate the Renyi and Von Neumann entropies using copies of \rho . The difference between our strategy and [ 29 , 31 ] is the approach we use from the transformation of singular quantum values, allowing us to construct the so-called block encoding (see 1 for the definition) of \rho and directly manipulate the arbitrary power of \rho , which is useful for estimating desired entropies. We shall show that, by adding further ancillas of small size, we can perform a unitary on the joint system, and measure the ancillas; we can use such measurement outcomes to estimate the desired quantities. More importantly, the number of copies of a given state required in our protocol is significantly less than that of [ 29 ] , and under a particular condition, that is, when the rank of given state does not scale as the dimension of the system, the sample complexity is also much less than that of the direct measurement approach provided in [ 31 ] . Thus, our contribution makes a substantial improvement towards the application of the quantum algorithmic framework to physical problems of estimating entropies. Our work is organized as follows. To improve readability, we provide an overview of our framework in the following section II , involving an introduction to the necessary recipes, related techniques, and illustrative insights behind our method. We then proceed to the full treatment towards Renyi entropy and von Neumann entropy estimation in subsequent sections. First, in section III , we devote the construction for Renyi entropy of arbitrary non-negative order \alpha . We divide it into three parts: the first part III.1 aims at \alpha being integers; the second part III.2 aims at \alpha being a fraction and greater than 1 ; and the last part III.3 discussed the case where \alpha being fractional and less than 1 . The reason for these divisions, as we shall see below, is mainly technical, as for different \alpha , the best tool required that produces the most efficient resource turns out to be different. Section IV is devoted to the von Neuman entropy. We will provide two alternative ways, one based on direct manipulation of the density operator (section IV.1 ), and the other based on polynomial approximation (to Von Neumann entropy, section IV.2 ), to estimate the desired quantity. We conclude and discuss outlook in section V , meanwhile, we have many central definitions and tools, stated as lemmas, in the appendix A . II Overview of Techniques and Related Recipes This section aim s to provide a more technical overview as well as key recipes underlying our main construction, which will be provided in Sections III and IV . We first define two main entropic quantities of interest: \displaystyle\text{$\alpha$-order Renyi entropy }S_{\alpha}=\frac{1}{1-\alpha}\log\Tr(\rho^{\alpha}), (1) \displaystyle\text{von Neumann entropy }S_{v}=-\Tr(\rho\log\rho). (2) We remark that the latter, the von Neumann entropy, is actually the limit of the former S_{v}=\lim_{\alpha=1}S_{\alpha} . To achieve the goal of their estimation, we first need to construct a block encoding of operator \rho . We refer to Appendix A for a concrete definition of block encoding, as well as key arithmetic operations involving block-encoded operators. We recall the following recipe that was first proposed in [ 38 ] and further improved in the seminal QSVT work [ 23 , 28 ] : Lemma 1 Given multiple copies of \rho , then it is possible to construct a \Delta -approximated block encoding of \pi\rho/4 using \mathcal{O}\Big(\frac{1}{\Delta}\log\frac{1}{\Delta}\Big) copies of \rho . The factor \pi/4 in the above seems unconventional at first, however, as we shall see, it results from a tool in [ 23 ] , in particular, its Lemma 70, the polynomial approximation of 2\sin^{-1}(x)/\pi and its Corollary 71. Next, using the density matrix exponentiation method in [ 39 ] , one can simulate the unitary operator \exp(-i\rho t) . Then we also have the following lemma from [ 23 ] : Lemma 2 (Logarithmic of Unitary, Corollary 71 in [ 23 ] ) Suppose that U=\exp(-iH) , where H is a Hamiltonian of norm at most 1/2 . Let \epsilon\in(0,1/2] , then we can implement an \epsilon -approximated block encoding of \pi H/2 (see further definition 1 ) with \mathcal{O}(\log\frac{1}{\epsilon}) uses of controlled-U and its inverse, using \mathcal{O}(\log\frac{1}{\epsilon}) two-qubit gates and using a single ancilla qubit. As \rho/2 ’s norm is at most 1/2, we first construct the operator \exp(-i\rho/2) using the density matrix exponentiation technique proposed in [ 39 ] . Then, applying the above lemma, one can carry out the transformation: \displaystyle\begin{pmatrix}\exp(-i\rho/2)&\cdot\\ \cdot&\cdot\end{pmatrix}\longrightarrow\begin{pmatrix}\frac{\pi\rho}{4}&\cdot\\ \cdot&\cdot\end{pmatrix}. (3) Then, we obtain the block encoding of \pi\rho/4 . Rényi entropy . Given the above block encoding, we use Lemma 7 in Appendix A to construct the block encoding of any non-negative integer power of \pi\rho/4 , i.e., for k\in\mathbb{Z}_{+} we can achieve the transformation: \displaystyle\begin{pmatrix}\frac{\pi\rho}{4}&\cdot\\ \cdot&\cdot\end{pmatrix}\longrightarrow\begin{pmatrix}(\frac{\pi\rho}{4})^{k}&\cdot\\ \cdot&\cdot\end{pmatrix}. (4) For k\notin\mathbb{Z}_{+} , for example, for 02 , then we need to choose \delta=|1-\alpha|\epsilon/(2r_{\rho}^{\alpha-1}) . Therefore, in order to estimate \alpha -th order Renyi entropy (for \alpha being an integer >1 of a given density matrix \rho up to an additive accuracy \delta , the number of \rho required in this method is \mathcal{O}\Big(\alpha\frac{r_{\rho}^{2\alpha-2}}{\epsilon^{2}}\Big), which suggests intuitively that it is efficient when \rho has a low rank. We remark that we have dropped the factor |1-\alpha| in the above estimation as it is greater than 1 in the regime \alpha\in(2,\infty) . III.2 Non-integer \alpha>1 For any \alpha , we can always break it as \alpha=\gamma+c , where \gamma=(2k+1) ( k\in\mathbb{Z}_{+} ) is an odd number and -1