Technical Summary: On Estimating the Trace of Quantum State Powers

Problem Statement

This paper investigates the computational complexity of estimating the trace of quantum state powers, $\text{tr}(\rho^q)$, for an $n$-qubit mixed quantum state $\rho$ given its state-preparation circuit of size $\text{poly}(n)$. This quantity is intrinsically linked to the quantum $q$-Tsallis entropy, defined as $S_q(\rho) = \frac{1 - \text{tr}(\rho^q)}{q - 1}$. The authors focus on two primary decision problems:

1. Quantum $q$-Tsallis Entropy Difference Problem (TsallisQED$_q$): Given two polynomial-size quantum circuits preparing states $\rho_0$ and $\rho_1$, decide whether $S_q(\rho_0) - S_q(\rho_1) \ge 0.001$ or $S_q(\rho_1) - S_q(\rho_0) \ge 0.001$.
2. Quantum $q$-Tsallis Entropy Approximation Problem (TsallisQEA$_q$): Given a single circuit preparing $\rho$ and a threshold $t(n)$, decide whether $S_q(\rho) - t(n) \ge 0.001$ or $S_q(\rho) - t(n) \le -0.001$.

The study addresses a gap in existing literature where efficient quantum algorithms were previously known only for integer $q \ge 2$ (e.g., Purity estimation via the SWAP test) or resulted in exponential time complexity $\exp(n)$ for non-integer $q > 1$ when the state is provided via a preparation circuit.

Methodology

Efficient Quantum Algorithms (Upper Bounds)

For the regime $q \ge 1 + \Omega(1)$, the authors propose a quantum algorithm that achieves polynomial time complexity, significantly improving upon prior $\exp(n)$ results. The methodology relies on three core components:

1. Uniform Polynomial Approximation: The authors introduce efficiently computable uniform approximations for positive power functions $x^q$ over the interval $[0, 1]$. Unlike previous approaches that used piece-wise approximations (leading to rank-dependent errors), this method utilizes Chebyshev truncations and de La Vallée Poussin partial sums to construct polynomials $P(x)$ such that $\max_{x \in [0,1]} |P(x) - \frac{1}{2}x^q| \le \epsilon$ with degree $O(1/\epsilon^{1/q})$.
2. Quantum Singular Value Transformation (QSVT): Using the constructed polynomial, the algorithm implements a block-encoding of $\rho^{q-1}$ via QSVT.
3. Hadamard Test and Amplitude Estimation: The trace $\text{tr}(\rho^q)$ is estimated by performing a Hadamard test on the block-encoded operator and the state $\rho$, followed by quantum amplitude estimation to achieve the desired additive error $\epsilon$.

This approach yields a query complexity of $O(1/\epsilon^{1 + \frac{1}{q-1}})$ and a time complexity of $\text{poly}(n, 1/\epsilon)$ for $q \ge 1 + \Omega(1)$. A sample-efficient variant is also derived using a "samplizer" technique, resulting in a sample complexity of $\tilde{O}(1/\epsilon^{3 + \frac{2}{q-1}})$.

Hardness Results (Lower Bounds)

To establish computational hardness, the authors perform reductions from known hard problems in quantum state testing to TsallisQED$_q$ and TsallisQEA$_q$.

1. New Inequalities: The proofs rely on establishing new inequalities between the quantum $q$-Jensen–Tsallis divergence ($QJT_q$) and the trace distance $T(\rho_0, \rho_1)$ for $1 \le q \le 2$. Specifically, they prove data-processing inequalities for $QJT_q$ and bounds relating $QJT_q$ to the trace distance, generalizing known results for the von Neumann entropy ($q=1$).
2. Reductions:
   • BQP-Hardness: For $1 \le q \le 2$, the authors reduce the Pure-State Distinguishability problem (PureQSD), which is BQP-hard, to the constant-rank variant of TsallisQED$_q$. This demonstrates that estimating the entropy difference for constant-rank states captures the full power of BQP.
   • QSZK/NIQSZK-Hardness: For the regime $1 < q \le 1 + \frac{1}{n-1}$, reductions are made from the general Quantum State Distinguishability (QSD) and Quantum State Closeness to Maximally Mixed State (QSCMM) problems. These reductions utilize bounds on Tsallis entropy relative to the trace distance, showing that these problems are QSZK-hard and, for specific $q$, NIQSZK-hard.

Key Contributions and Results

1. Sharp Phase Transition in Complexity

The paper identifies a sharp phase transition in the computational complexity of estimating $S_q(\rho)$:

• Easy Regime ($q \ge 1 + \Omega(1)$): The problems TsallisQED$_q$ and TsallisQEA$_q$ are contained in BQP. The authors provide a quantum algorithm with polynomial time complexity, exponentially faster than previous $\exp(n)$ approaches.
• Hard Regime ($1 < q \le 1 + \frac{1}{n-1}$): The problems become QSZK-hard (and NIQSZK-hard for specific $q$). This implies that unless $\text{BQP} \subseteq \text{QSZK}$, no efficient quantum algorithm exists for these regimes.
• Boundary Case ($q=1$): Corresponds to the von Neumann entropy, which is known to be QSZK-complete (for difference) and NIQSZK-complete (for approximation).

2. BQP-Completeness of Purity Estimation

As a direct corollary of the BQP-hardness result for $1 \le q \le 2$, the paper establishes that Purity Estimation (estimating $\text{tr}(\rho^2)$) is BQP-hard. This resolves a long-standing question regarding whether estimating the trace of quantum state powers can fully capture the computational power of quantum computing.

3. New Mathematical Tools

• Efficient Uniform Approximations: The construction of efficiently computable uniform polynomial approximations for $x^q$ suitable for QSVT, avoiding the rank-dependence of previous methods.
• QJT$_q$ Inequalities: New inequalities bounding the quantum $q$-Jensen–Tsallis divergence in terms of the trace distance for $1 \le q \le 2$, including data-processing inequalities derived from joint convexity.
• Tsallis Binary Entropy Bounds: Tighter bounds for the Tsallis binary entropy $H_q(x)$ for $1 \le q \le 2$.

Significance and Claims

The paper claims to resolve the computational complexity landscape for estimating quantum $q$-Tsallis entropy across different regimes of $q$.

• Algorithmic Breakthrough: It provides the first efficient (polynomial-time) quantum estimator for non-integer $q \ge 1 + \Omega(1)$, overcoming the exponential barrier of prior works (e.g., [AISW20, WGL+24, WZL24]).
• Complexity Classification: It precisely delineates the boundary between tractable (BQP) and intractable (QSZK-hard) regimes, revealing that the difficulty of estimating entropy increases as $q$ approaches 1 from above, specifically when $q$ is within $O(1/n)$ of 1.
• Foundational Insight: By proving Purity Estimation is BQP-hard, the work confirms that simple properties of quantum states (like purity) are as hard to estimate as general BQP problems, provided the state is given via a circuit.

The authors note that their results rely on the assumption that $q$ is a constant greater than 1 for the efficient algorithm, and the hardness results for the "hard regime" depend on the rank of the states approaching the dimension $2^n$. They explicitly state that the efficient upper bound for the hard regime remains an open problem, though they provide matching lower bounds.