Computational hardness of estimating quantum entropies via binary entropy bounds

Titel: Computatiecomplexiteit van het schatten van quantum-entropieën via binary-entropiegrenzen

Auteur: Yupan Liu (EPFL & Nagoya University)
Publicatiedatum: April 2026 (arXiv)

---

1. Probleemstelling

Het artikel onderzoekt de computationele hardheid van het schatten van twee fundamentele generalisaties van de von Neumann-entropie in de quantum-informatietheorie:

1. Quantum $\alpha$-Rényi entropie: $S^R_\alpha(\rho) = \frac{\ln \text{Tr}(\rho^\alpha)}{1-\alpha}$
2. Quantum $q$-Tsallis entropie: $S^T_q(\rho) = \frac{1-\text{Tr}(\rho^q)}{q-1}$

Beide grootheden convergeren naar de von Neumann-entropie ($S(\rho) = -\text{Tr}(\rho \ln \rho)$) wanneer de orde ($\alpha$ of $q$) naar 1 nadert.

Het centrale vraagstuk is de Quantum Entropy Approximation (QEA): een belofteprobleem (promise problem) waarbij gegeven een quantumcircuit dat een toestand $\rho$ bereidt, moet worden bepaald of de entropie boven een drempelwaarde $\tau_Y$ ligt of onder een drempelwaarde $\tau_N$ (waarbij $\tau_Y - \tau_N$ een constante is).

De kernvraag: Hoe moeilijk is het om deze entropieën te schatten voor alle positieve ordes $\alpha$ en $q$? Zijn de problemen, zelfs wanneer beperkt tot toestanden met een lage rang (bijvoorbeeld rang 2), BQP-hard (zo moeilijk als het oplossen van elk probleem dat een universele quantumcomputer efficiënt kan oplossen)?

Eerdere resultaten dekten voornamelijk de von Neumann-entropie (orde 1) en specifieke gevallen van de Tsallis-entropie, maar bestaande methoden waren niet direct uitbreidbaar naar andere ordes.

---

2. Methodologie

De auteur introduceert een nieuwe, systematische aanpak die afwijkt van eerdere methoden die vaak afhankelijk waren van quantum Jensen-divergenties of convexiteitsargumenten die niet voor alle ordes gelden.

De nieuwe aanpak bestaat uit drie pijlers:

1. Mapping naar Binary Entropies:
   De auteur maakt gebruik van een cruciale observatie: voor een toestand met rang 2, specifiek de gemengde toestand $\rho = \frac{1}{2}(|\psi_0\rangle\langle\psi_0| + |\psi_1\rangle\langle\psi_1|)$, kunnen de quantum-entropieën worden uitgedrukt in termen van binary entropies (entropieën van een tweestelsel).

   • Bijvoorbeeld voor $q=2$ (Tsallis): $S^T_2(\rho) = H^T_2\left(\frac{1 - |\langle\psi_0|\psi_1\rangle|^2}{2}\right)$.
   • Hierbij is $1 - |\langle\psi_0|\psi_1\rangle|^2$ de "infidelity" (ontrouw) tussen twee pure toestanden.

2. Hardheid van Infidelity Schatting:
   Het is reeds bewezen dat het schatten van de infidelity $1 - |\langle\psi_0|\psi_1\rangle|^2$ met constante precisie BQP-hard is (gebaseerd op het werk van [RASW23]). Als men kan aantonen dat het schatten van de entropie equivalent is aan het schatten van deze infidelity, volgt de hardheid direct.

3. Nieuwe Ongelijkheden (Bounds):
   De kern van het bewijs ligt in het afleiden van nieuwe, strikte ongelijkheden die de binary entropies van verschillende ordes met elkaar relateren. De auteur toont aan dat de binary entropie van een willekeurige orde $\alpha$ of $q$ begrensd kan worden door de binary entropie van orde 2 (of omgekeerd), met constante factoren.

   • Dit stelt de auteur in staat om een Karp-reductie te construeren: het schatten van de infidelity (BQP-hard) wordt gereduceerd tot het schatten van de $\alpha$-Rényi of $q$-Tsallis entropie.
   • Deze ongelijkheden zijn afhankelijk van de specifieke ranges van $\alpha$ en $q$ (bijv. $0 < \alpha < 2$, $\alpha \ge 2$, etc.) en vereisen ingewikkelde analyse van reeksen en afgeleiden.

---

3. Belangrijkste Resultaten

De paper levert de volgende fundamentele resultaten op:

A. BQP-Hardheid voor Rang-2 Variaties

De auteur bewijst dat de beperkte versies van de problemen, waarbij de quantumtoestand $\rho$ een rang van maximaal 2 heeft (Rank2RényiQEA en Rank2TsallisQEA), BQP-hard zijn voor:

• Alle reële ordes $\alpha > 0$ en $\alpha = \infty$ (min-entropie).
• Alle reële ordes $q > 0$.

Dit betekent dat zelfs voor de kleinste niet-triviale rang (rang 2, aangezien rang 1 pure toestanden zijn met nul entropie), het probleem volledig de rekenkracht van een quantumcomputer vereist.

B. BQP-Completiteit voor Laag-Rang en Algemene Tsallis

Door de nieuwe hardheidresultaten te combineren met bestaande quantum query-algoritmen (bovengrens) uit eerdere literatuur, volgt de BQP-completiteit voor:

1. LowRankRényiQEA$_\alpha$: Voor alle $\alpha > 0$ en $\alpha = \infty$, wanneer de rang van $\rho$ polynomiaal begrensd is.
2. LowRankTsallisQEA$_q$: Voor alle $0 < q \le 1$ (beperkt tot lage rang).
3. TsallisQEA$_q$: Voor alle $q > 1$, zelfs zonder rangbeperking (dit is een uniek resultaat, aangezien Tsallis-entropie voor $q>1$ rang-onafhankelijke schatters toelaat).

C. NQP-Completiteit voor Orde 0

Voor de orde-0 gevallen (die corresponderen met de Hartley-entropie of de rang van de toestand zelf):

• Rank2RényiQEA$_0$ en Rank2TsallisQEA$_0$ zijn NQP-compleet.
• Dit betekent dat het probleem equivalent is aan het tellen van accepterende paden in een niet-deterministische quantumcomputer, wat een andere complexiteitsklasse is dan BQP.

---

4. Technische Bijdragen en Innovaties

• Nieuwe Inequalities: De paper introduceert nieuwe wiskundige grenzen voor $\alpha$-Rényi en $q$-Tsallis binary entropies. Deze relaties (samengevat in Tabel 2 en 3 van de paper) zijn op zichzelf waardevol voor de informatietheorie.
• Overbrugging van Ordes: De methode lost het probleem op dat eerdere benaderingen (gebaseerd op Jensen-divergenties) faalden voor ordes waar de convexiteit niet gegarandeerd was. Door te werken met rang-2 toestanden en binary entropies, omzeilt de auteur deze beperkingen.
• Karp vs. Turing Reducties: In tegenstelling tot eerdere werken die vaak Turing-reducties gebruikten (waarbij een algoritme meerdere keren wordt aangeroepen), bewijst deze paper hardheid via Karp-reducties (een directe transformatie van het probleem), wat een sterkere hardheidsclaim is.
• Analyse van Monotonie: De auteur analyseert zorgvuldig de monotonie van genormaliseerde Tsallis binary entropies, wat leidt tot een interessante observatie over een transitiepunt $q^* \in [2, 3]$ waar de monotonie verandert.

---

5. Betekenis en Impact

1. Volledige Karakterisering: De paper sluit een belangrijke kennislacune in de quantum-complexiteitstheorie. Het biedt nu een volledig beeld van de hardheid van het schatten van Rényi- en Tsallis-entropieën voor alle ordes, niet alleen voor de klassieke von Neumann-entropie.
2. Fundamentele Grenzen: Het resultaat bevestigt dat het schatten van quantum-entropieën inherent moeilijk is, zelfs voor zeer eenvoudige toestanden (rang 2). Dit heeft implicaties voor de haalbaarheid van quantum-algoritmen voor entropie-estimation in praktische toepassingen.
3. Toepassingen: De resultaten zijn relevant voor:
   • Kwantum Cryptografie: Veiligheidsbewijzen voor Quantum Key Distribution (QKD) vertrouwen vaak op entropie-estimatie.
   • Fysica: Het karakteriseren van verstrengeling in fysische systemen.
   • Complexiteitstheorie: Het versterkt het begrip van de relatie tussen klassieke en quantum complexiteitsklassen (BQP, NQP, NIQSZK).
4. Open Problemen: De auteur identificeert dat de huidige methode beperkt is voor het bewijzen van hardheid voor de algemene Rényi-entropie (zonder rangbeperking) voor ordes $\alpha > 1$, vanwege de schaalvergroting van de entropiewaarden ten opzichte van de belofte-gap. Dit blijft een open vraag voor toekomstig onderzoek.

Samenvattend biedt deze paper een doorbraak in het begrijpen van de computationele complexiteit van quantum-entropieën door een elegante combinatie van wiskundige ongelijkheden en reducties vanuit het probleem van het schatten van quantum infidelity.