Open AccessUm Algoritmo Quântico para um Problema de Distância Estatística
Author(s) -
H. Hepp,
Murilo V. G. da Silva,
Leandro M. Zatesko
Publication year - 2021
Language(s) - Portuguese
Resource type - Conference proceedings
DOI - 10.5753/etc.2021.16366
Subject(s) - mathematics , combinatorics
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.