# Techniques: On Estimating the Quantum Tsallis Relative Entropy

## What the paper contributes (one paragraph)

The paper gives a complete computational-complexity picture for estimating the quantum alpha-Tsallis relative entropy between two unknown quantum states for any constant alpha in (0, 1). It provides an efficient quantum estimator with query and sample complexity polynomial in the rank r of the states, built by block-encoding the operator rho^(alpha-1) sigma^(1-alpha) via quantum singular value transformation and reading off the trace with a Hadamard test, then converting the query algorithm to a sample-based one with a samplizer. As an application, this yields the first efficient quantum tester for tolerant quantum state certification in the Hellinger distance, with sample complexity O-tilde(r^3.5) that exponentially beats tomography when r is polynomial in the qubit count. It also proves matching lower bounds and that the associated distinguishability problems are QSZK-complete in general and BQP-complete in the low-rank case.

## Techniques offered

- **quantum Tsallis relative entropy estimation (block-encoding plus Hadamard test via quantum singular value transformation)** - An efficient quantum estimator that returns the alpha-Tsallis relative entropy (and, at alpha = 1/2, the Hellinger distance) of two unknown states to additive error eps with rank-polynomial query and sample complexity, supplying a reusable distinguishability-measure subroutine for any pipeline that holds two state-preparation circuits or copies.
  - guarantee: statistical bound: additive-error eps estimate with explicit query complexity O-tilde(r^1.5) and sample complexity O-tilde(r^3.5) at alpha = 1/2, with matching lower bounds up to polynomial factors.
  - quote: "Our first result is an efficient quantum algorithm for estimating the quantum Tsallis relative entropy."

- **tolerant quantum state certification in Hellinger distance (tolerant property tester)** - A quantum tester that distinguishes states close in Hellinger distance from states far in Hellinger distance, supplying a tolerant closeness-testing primitive that exponentially outperforms the tomography-based folklore approach in the low-rank regime.
  - guarantee: property test: distinguishes the Hellinger-distance-at-most-eps_1 case from the at-least-eps_2 case using O-tilde(r^3.5) samples (or O-tilde(r^1.5) queries) of the two states.
  - quote: "As an application, this gives a quantum tester for the tolerant closeness testing between quantum states with respect to the quantum Hellinger distance (see \cref{thm:tolerant-state-certification-Hellinger-distance})."

- **samplizer / quantum multi-samplizer** - An algorithmic tool that converts a query-based quantum algorithm into one driven only by samples (copies) of the input quantum states, supplying a generic query-to-sample reduction usable to make other state-property estimators work from copies alone.
  - guarantee: statistical bound: simulates the query algorithm to diamond-norm error delta using density matrix exponentiation, turning the query complexity into a corresponding sample complexity.
  - quote: "To obtain the sample complexity, we adopt the algorithmic tool called samplizer \cite{WZ25,WZ24b} that enables us to simulate the aforementioned query-based approach by samples of quantum states $\rho$ and $\sigma$, which is a convenient use of the density matrix exponentiation \cite{LMR14,KLL+17,GKP+24} to simulate quantum query algorithms."

## Where it could apply

- Target primitive(s): state-property estimation and quantum hypothesis testing / state distinguishability and certification; sampling and state-preparation-circuit access models. Not VQE/QAOA/QPE/Trotter specific.
- Target application group(s): platforms_tooling (benchmarking, characterisation, verification of prepared states); quantum_ml (objective-function and gradient estimation for quantum Boltzmann machines).
- Code family / hardware assumptions: none (hardware-agnostic; assumes access to copies of the states or to their state-preparation circuits, plus QSVT/block-encoding capability).

## Caveats

The core results also include QSZK-completeness and BQP-completeness classifications, but these are computational-hardness statements rather than capabilities suppliable to an external result, so they are not listed as techniques. The estimator and tester are theoretical, asymptotic algorithms with rank-polynomial costs and high inverse-eps exponents, with no implementation or empirical benchmark; suppliability assumes low-rank states and access to either many copies or trusted state-preparation circuits.