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

• Henrique Hepp UFPR
• Murilo V. G. da Silva UFPR
• Leandro M. Zatesko UTFPR

DOI: https://doi.org/10.5753/etc.2021.16366

Resumo

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.

Palavras-chave: Distância Estatística para Distribuição Uniforme, Algoritmo Quântico, BQP

Referências

Goldreich, O., Sahai, A., and Vadhan, S. (1999). Can statistical zero knowledge be made non-interactive? or On the relationship of SZK and NISZK. In Annual International Cryptology Conference, pages 467–484.

Kobayashi, H. (2003). Non-interactive quantum perfect and statistical zero-knowledge. In International Symposium on Algorithms and Computation, pages 178–188.

Montanaro, A. and de Wolf, R. (2016). A survey of quantum property testing. Theory Comput., (7):1–81.

Nielsen, M. A. and Chuang, I. L. (2011). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 10th edition.

Watrous, J. (2002). Limits on the power of quantum statistical zero-knowledge. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 459–468. IEEE.