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

AIP conference proceedings

Estimating Polynomial Functions of a Quantum State

Todd A. Brun

Published Jan 1, 2004• 0 citations
Publisher

Abstract

In this presentation I show that any mth‐degree polynomial function of the elements of the density matrix ρ can be estimated by finding the expectation value of two observables on m copies of ρ, without performing state tomography. Many important quantities in quantum information theory—such as the concurrence, three‐tangle, negativity, purity, and Renyi entropy—are either polynomials or simple functions of polynomials. Since circuits exists which can approximate the measurement of any observable, in principle one can find a circuit which will estimate any such polynomial function by averaging over many runs. Some simple examples are presented and compared to existing approaches, and the efficiency is discussed.

DOI
10.1063/1.1834385

Related papers

Measuring polynomial functions of states

Todd A. Brun

In this paper I show that any $m$th-degree polynomial function of the elements of the density matrix $\rho$ can be determined by finding the expectation value of an observable on $m$ copies of $\rho$, without performing state tomography. Since a circuit exists which can approximate the measurement of any observable, in principle one can find a circuit which will estimate any such polynomial function by averaging over many runs. I construct some simple examples and compare these results to existing procedures.

arXiv:quant-ph/0401067•Quantum Information and Computation•Sep 1, 2004•98 citations

Sample-efficient estimation of nonlinear quantum state functions

Hongshun Yao, Yingjian Liu, Tengxiang Lin +1 more

Estimating nonlinear functions of quantum states is essential for quantum information processing tasks such as entropy quantification, fidelity estimation, and entanglement spectroscopy. Existing approaches based on quantum state tomography incur exponential resource overhead, while methods relying on purified query access impose significant practical constraints. Here, we introduce the quantum state function framework, which extends the swap test via a linear combination of unitaries and parameterized quantum circuits. The framework estimates any normalized degree-n polynomial function of a quantum state with precision ε using $${{{\mathcal{O}}}}(n/{\varepsilon }^{2})$$ copies, operating directly on identical copies without block-encoding or purified queries. Applied to von Neumann entropy, quantum relative entropy, and state fidelity, it achieves sample complexity $$\widetilde{{{{\mathcal{O}}}}}({\gamma }^{2}/({\varepsilon }^{2}\kappa ))$$, where κ is the minimal nonzero eigenvalue and γ a normalization factor. This framework establishes a unified paradigm for nonlinear quantum state processing, broadening the toolkit for practical quantum data analysis. Estimating nonlinear functions of quantum states is essential for quantum information processing but often computationally expensive. The quantum state function framework estimates a degree-n polynomial of a quantum state with $${{{\mathcal{O}}}}(n/{\varepsilon }^{2})$$ copies without purified query access, enabling practical entropy, fidelity, and eigenvalue estimation.

arXiv:2412.01696•Communications Physics•Jun 6, 2026•7 citations

Measuring Less to Learn More: Quadratic Speedup in Learning Nonlinear Properties of Quantum States

Yukun Zhang, Yusen Wu, You Zhou +1 more

A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as Tr(ρ^{k}O). Intuitively, one expects that computing a kth order quantity generally requires O(k) copies of the state ρ, and we rigorously establish this lower bound under sample access to ρ. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of ρ, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of Θ(sqrt[k]) and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory-specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling and evaluating other multiple nonlinear quantum observables with classical shadows.

arXiv:2509.01571•Physical Review Letters•Jan 20, 2026•10 citations

Simultaneous Estimation of Nonlinear Functionals of a Quantum State

Kean Chen, Qisheng Wang, Yu Zhan +1 more

We consider a fundamental task in quantum information theory, estimating the values of tr(Oρ), tr(Oρ2), . . . , tr(Oρk) for an observableOand a quantum state ρ. We show that Θ(k) samples of ρ are sufficient and necessary to simultaneously estimate all thekvalues. This means that estimating all thekvalues is almost as easy as estimating only one of them, tr(Oρk). As an application, our approach advances the sample complexity of entanglement spectroscopy and the virtual cooling for quantum many-body systems. Moreover, we extend our approach to estimating general functionals by polynomial approximation.

arXiv:2505.16715•IEEE Transactions on Information Theory•Jun 4, 2026•19 citations

Unitary circuit synthesis for tomography of generalized coherent states

Rolando D. Somma

We present a method that outputs a sequence of simple unitary operations to prepare a given quantum state that is a generalized coherent state. Our method takes as inputs the expectation values of some relevant observables. Such expectations can be estimated by performing projective measurements on O(M3⁡log(M/δ)/ε2) copies of the state, where M is the dimension of an associated Lie algebra, ɛ is a precision parameter, and 1 − δ is the required confidence level. The method can be implemented on a classical computer and runs in time O(M4⁡log(M/ε)). It provides O(M⁡log(M/ε)) simple unitaries that form the sequence. The overall complexity is then polynomial in M, being very efficient in cases where M is significantly smaller than the Hilbert space dimension, as for some fermion algebras. When the algebra of relevant observables is given by certain Pauli matrices, each simple unitary may be easily decomposed into two-qubit gates. We discuss applications to efficient quantum state tomography and classical simulations of quantum circuits.

arXiv:1811.08479•Journal of Mathematical Physics•Nov 1, 2019•6 citations

Enhanced Estimation of Quantum Properties with Common Randomized Measurements

Benoît Vermersch, Aniket Rath, Bharathan Sundar +3 more

We present a technique for enhancing the estimation of quantum state properties by incorporating approximate prior knowledge about the quantum state. This consists in performing randomized measurements on a quantum processor and comparing the results with those obtained from a classical computer that stores an approximation of the quantum state. We provide unbiased estimators for expectation values of multicopy observables and present performance guarantees in terms of variance bounds that depend on the prior knowledge accuracy. We demonstrate the effectiveness of our approach through experimental and numerical examples detecting mixed-state entanglement, and estimating polynomial approximations of the von Neumann entropy and state fidelities. Published by the American Physical Society 2024

arXiv:2304.12292•PRX Quantum•Mar 28, 2024•27 citations
In this presentation I show that any mth‐degree polynomial function of the elements of the density matrix ρ can be estimated by finding the expectation value of two observables on m copies of ρ, without performing state tomography. Many important quantities in quantum information theory—such as the concurrence, three‐tangle, negativity, purity, and Renyi entropy—are either polynomials or simple functions of polynomials. Since circuits exists which can approximate the measurement of any observable, in principle one can find a circuit which will estimate any such polynomial function by averaging over many runs. Some simple examples are presented and compared to existing approaches, and the efficiency is discussed.
In this paper I show that any mmmth-degree polynomial function of the elements of the density matrix ρ\rhoρ can be determined by finding the expectation value of an observable on mmm copies of ρ\rhoρ, without performing state tomography. Since a circuit exists which can approximate the measurement of any observable, in principle one can find a circuit which will estimate any such polynomial function by averaging over many runs. I construct some simple examples and compare these results to existing procedures.
Estimating nonlinear functions of quantum states is essential for quantum information processing tasks such as entropy quantification, fidelity estimation, and entanglement spectroscopy. Existing approaches based on quantum state tomography incur exponential resource overhead, while methods relying on purified query access impose significant practical constraints. Here, we introduce the quantum state function framework, which extends the swap test via a linear combination of unitaries and parameterized quantum circuits. The framework estimates any normalized degree-n polynomial function of a quantum state with precision ε using O(n/ε2){{{\mathcal{O}}}}(n/{\varepsilon }^{2})O(n/ε2) copies, operating directly on identical copies without block-encoding or purified queries. Applied to von Neumann entropy, quantum relative entropy, and state fidelity, it achieves sample complexity O~(γ2/(ε2κ))\widetilde{{{{\mathcal{O}}}}}({\gamma }^{2}/({\varepsilon }^{2}\kappa ))O(γ2/(ε2κ)), where κ is the minimal nonzero eigenvalue and γ a normalization factor. This framework establishes a unified paradigm for nonlinear quantum state processing, broadening the toolkit for practical quantum data analysis. Estimating nonlinear functions of quantum states is essential for quantum information processing but often computationally expensive. The quantum state function framework estimates a degree-n polynomial of a quantum state with O(n/ε2){{{\mathcal{O}}}}(n/{\varepsilon }^{2})O(n/ε2) copies without purified query access, enabling practical entropy, fidelity, and eigenvalue estimation.
A fundamental task in quantum information science is to measure nonlinear functionals of quantum states, such as Tr(ρ^{k}O). Intuitively, one expects that computing a kth order quantity generally requires O(k) copies of the state ρ, and we rigorously establish this lower bound under sample access to ρ. Surprisingly, this limitation can be overcome when one has purified access via a unitary that prepares a purification of ρ, a scenario naturally arising in quantum simulation and computation. In this setting, we find a different lower bound of Θ(sqrt[k]) and present a quantum algorithm that achieves this bound, demonstrating a quadratic advantage over sample-based methods. The key technical innovation lies in a designed quantum algorithm and optimal polynomial approximation theory-specifically, Chebyshev polynomial approximations tailored to the boundary behavior of power functions. Our results unveil a fundamental distinction between sample and purified access to quantum states, with broad implications for estimating quantum entropies and quantum Fisher information, realizing quantum virtual distillation and cooling and evaluating other multiple nonlinear quantum observables with classical shadows.
We consider a fundamental task in quantum information theory, estimating the values of tr(Oρ), tr(Oρ2), . . . , tr(Oρk) for an observableOand a quantum state ρ. We show that Θ(k) samples of ρ are sufficient and necessary to simultaneously estimate all thekvalues. This means that estimating all thekvalues is almost as easy as estimating only one of them, tr(Oρk). As an application, our approach advances the sample complexity of entanglement spectroscopy and the virtual cooling for quantum many-body systems. Moreover, we extend our approach to estimating general functionals by polynomial approximation.
We present a method that outputs a sequence of simple unitary operations to prepare a given quantum state that is a generalized coherent state. Our method takes as inputs the expectation values of some relevant observables. Such expectations can be estimated by performing projective measurements on O(M3⁡log(M/δ)/ε2) copies of the state, where M is the dimension of an associated Lie algebra, ɛ is a precision parameter, and 1 − δ is the required confidence level. The method can be implemented on a classical computer and runs in time O(M4⁡log(M/ε)). It provides O(M⁡log(M/ε)) simple unitaries that form the sequence. The overall complexity is then polynomial in M, being very efficient in cases where M is significantly smaller than the Hilbert space dimension, as for some fermion algebras. When the algebra of relevant observables is given by certain Pauli matrices, each simple unitary may be easily decomposed into two-qubit gates. We discuss applications to efficient quantum state tomography and classical simulations of quantum circuits.
We present a technique for enhancing the estimation of quantum state properties by incorporating approximate prior knowledge about the quantum state. This consists in performing randomized measurements on a quantum processor and comparing the results with those obtained from a classical computer that stores an approximation of the quantum state. We provide unbiased estimators for expectation values of multicopy observables and present performance guarantees in terms of variance bounds that depend on the prior knowledge accuracy. We demonstrate the effectiveness of our approach through experimental and numerical examples detecting mixed-state entanglement, and estimating polynomial approximations of the von Neumann entropy and state fidelities. Published by the American Physical Society 2024