Uppskattning av Shannon och Rényi entropies av okända diskreta fördelningar är ett grundläggande problem i statistiska egenskapstester och ett aktivt forskningsämne i både teoretisk datavetenskap och informationsteori. Täta gränser för antalet prover för att uppskatta dessa entropier har fastställts i den klassiska miljön, medan föga är känt om deras kvant motsvarigheter. I den här artikeln ger vi de första kvantalgoritmerna för att uppskatta α-Rényi entropies (Shannon entropy är 1-Renyi entropy). I synnerhet visar vi en quadratic quantum speedup för Shannon entropy uppskattning och en generisk quantum speedup för α-Rényi entropy uppskattning för alla α ≥ 0, inklusive en snäv gräns för kollisionen-entropy (2-Rényi entropy). Vi tillhandahåller också kvant övre gränser för extrema fall som Hartley entropy (dvs. logaritmen för stödstorleken för en distribution, motsvarande α = 0) och minentropy fall (dvs. α = +∞), samt Kullback-Leibler skillnaden mellan två fördelningar. Dessutom kompletterar vi våra resultat med kvant nedre gränser på α-Rényi entropy uppskattning för alla α ≥ 0. Vårt tillvägagångssätt är inspirerat av Bravyis, Harrows och Hassidims (BHH) banbrytande arbete [13] om kvantalgoritmer för fördelning av egendom, dock med många nya tekniska ingredienser. För Shannon entropy och 0-Rényi entropy uppskattning, förbättrar vi prestandan för BHH ramverket, särskilt dess felberoende, med Montanaros metod för att uppskatta den förväntade utdatavärdet för en kvant subrutin med begränsad varians [41] och ger en finjusterad felanalys. För allmän α-Rényi entropy estimering utvecklar vi vidare ett förfarande som rekursivt approximerar α-Rényi entropy för en sekvens av αs, som i anden liknar ett kylschema i simulerad glödgning. För specialfall som heltal α ≥ 2 och α = +∞ (d.v.s. min-entropi), minskar vi problemet med entropiuppskattning till α-särskiljbarheten respektive log n-särskildhetsproblemen. Vi utnyttjar olika tekniker för att få våra lägre gränser för olika områden av α, inklusive minskningar till (varianter av) befintliga lägre gränser i kvantförfrågan komplexitet samt polynom metod inspirerad av den berömda kvant lägre gränsen för kollisionsproblem.
Nyligen Li och Wu REF studerade kvantförfrågan komplexiteten i att uppskatta entropi av diskreta distributioner.
Quantum query complexity of entropy estimation
{'venue': 'IEEE Transactions on Information Theory 65 (2019), no. 5, 2899-2921', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}