Chicago Journal of Theoretical Computer Science

Volume 2010

Article 13

Published by the Department of Computer Science, The University of Chicago.

Single-Query Learning from Abelian and Non-Abelian Hamming Distance Oracles

David A. Meyer
Project in Geometry and Physics,
Department of Mathematics
University of California San Diego, La Jolla, CA 92093-0112,
James Pommersheim
Department of Mathematics
Reed College, Portland, OR 97202-8199

August 5, 2010

We study the problem of identifying an n-bit string using a single quantum query to an oracle that computes the Hamming distance between the query and hidden strings. The standard action of the oracle on a response register of dimension r is by powers of the cycle (1 ... r), all of which, of course, commute. We introduce a new model for the action of an oracle---by general permutations in S_r---and explore how the success probability depends on r and on the map from Hamming distances to permutations. In particular, we prove that when r = 2, for even n the success probability is 1 with the right choice of the map, while for odd n the success probability cannot be 1 for any choice. Furthermore, for small odd n and r = 3, we demonstrate numerically that the image of the optimal map generates a non-abelian group of permutations.

Submitted November 20, 2009, revised July 5, 2010, published August 5, 2010.

DOI: 10.4086/cjtcs.2010.013

[] Volume 2010, Article 12 (Article 9 in CATS 2009 Special Issue)
[back] Volume 2009 [back] Published articles
[CJCTS home]