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

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.
Publicado
18/07/2021
HEPP, Henrique; SILVA, Murilo V. G. da; ZATESKO, Leandro M.. Um Algoritmo Quântico para um Problema de Distância Estatística. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 6. , 2021, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2021 . p. 1-4. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2021.16366.