A Quantum Algorithm for a Problem of Statistical Distance

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

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

Abstract

In the Statistical Distance to Uniform Distribution (SDU) problem, the aim is to compare a probability distribution over all n-bit strings with the uniform distribution. In this paper, we deal with the restriction of SDU in which the probabilities of the 2^n/2 first strings (under the usual lexicographic ordering) are never smaller than the 2^n/2 last strings. We prove that this restriction admits a polynomial-time quantum algorithm.

Keywords: Statistical Distance to Uniform Distribution, quantum algorithm, BQP

References

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.