#

### 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,

dmeyer@math.ucsd.edu

and

James Pommersheim

Department of Mathematics

Reed College, Portland, OR 97202-8199

jamie@reed.edu

*August 5, 2010*
##### Abstract

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.

- The article:
**PDF** (206,288 bytes)
- Source materials:
**ZIP** (53,474 byes)
- Self citation in
**BIBTeX** (205 bytes)
- Original version (pre-June 2010):
**PDF** (183,737 bytes)

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

Volume 2010, Article 12 (Article 9 in CATS 2009 Special Issue)

Volume 2009
Published articles