correspondence with triples (x, y, z), with x, y ∈ Z
n
p
and z ∈ Z
p
, where (1, x, z) is the first row of
the matrix and (z, y, 1) is the last column of the matrix. Then G(p, n) is a p-group of order p
2n+1
.
We consider the usual action of G(p, n) on the set X = Z
n+2
p
, considered as column vectors, by
matrix-vector multiplication. The corresponding classical oracle identification problem turns out
to have complexity b(G) = n + 1. To see this note that y and z can be determined by the single
query (0, . . . , 0, 1). Further queries give affine conditions on x, and it requires at least n of these
to determine the value of x.
In contrast to the n + 1 queries needed to solve this question classically, we now show that
a single quantum query suffices to solve the problem with high probability, and that two queries
suffice to solve the problem with certainty.
Theorem 6.1. Let G(p, n) denote the Heisenberg group defined above acting by multiplication on
the set of column vectors X = Z
n+2
p
. Then an optimal single query quantum algorithm solves the
oracle identification problem with probability
P
opt
= 1 −
1
p
+
2
p
n+1
−
1
p
2n+1
.
Furthermore, two queries suffices to solve the oracle identification problem with probability 1.
We will prove this theorem shortly. Before doing so, let us consider a related coset identification
problem. Let H < G(p, n) be the subgroup in which x = y = 0. Then H is a subgroup of order
p, and in fact H is the center of G(p, n). The coset identification problem with respect to this
subgroup H asks us to determine the values of x and y. In the classical case, n + 1 queries are
again required. However this time, a single quantum query solves the coset identification problem
with certainty.
Theorem 6.2. Let G = G(p, n) denote the Heisenberg group acting by multiplication on the set of
column vectors X = Z
n+2
p
. Let H be center of G, the set of all matrices in G for which x = y = 0.
Then the coset identification problem can be solved with a single quantum query with probability 1.
In order to prove these theorems, we must understand the representation theory of G = G(p, n),
which we now describe briefly (for a concise and elegant review, see the letter by M. Isaacs to P.
Diaconis published in the appendix to [Dia]). The group G has p
2n
one-dimensional irreducible
representations and p − 1 irreducible representations of dimension p
n
. The one-dimensional rep-
resentations will be denoted χ
α,β
, indexed by tuples α, β ∈ Z
n
p
. We identify these representations
with their characters which are given by the formula
χ
α,β
(x, y, z) = ω
α·x+β·y
,
with ω denoting a primitive p-th root of unity.
The p
n
dimensional representations denoted ρ
c
, with c ∈ Z
p
, c 6= 0 are described as follows.
Let U be the vector space of all complex-valued functions on (Z
p
)
n
. Fix c ∈ Z
p
with c 6= 0. Then
there is an irreducible representation ρ
c
of G on U given by
[ρ
c
(x, y, z)f](w) = ω
c(y·w+z)
f(w + x).
The character of this representation is given by
θ
c
(x, y, z) =
(
p
n
ω
cz
if x = y = 0,
0 otherwise.
In order to understand the query complexity of the oracle identification problem we must
decompose the representation V = C
X
into irreducible representations. Since this representation
comes from a permutation representation of G, each character value χ
V
(x, y, z) is simply the
number of fixed points of the matrix A = (x, y, z). This number of fixed points is determined
by the rank of the matrix A
0
= A − I. If (x, y, z) = 0, then A
0
has rank 0, and if x and y are
Accepted in Quantum 2021-03-03, click title to verify. Published under CC-BY 4.0. 26