Um Algoritmo Quântico para um Problema de Distância Estatística

No problema Distância Estatística para Distribuição Uniforme (SDU), o objetivo é comparar uma distribuição de probabilidade sobre as strings de n bits com a distribuição uniforme. Neste trabalho, lidamos com a restrição de SDU em que as probabilidades das 2^n/2 primeiras strings (sob a ordenação lexicográfica usual) nunca são menores que as das 2^n/2 últimas. Provamos que esta restrição admite um algoritmo quântico polinomial.