A STUDY OF GROVER’S SEARCH ALGORITHM VIA
PROJECTIVE GEOMETRY
RAEEZ LORGAT
Abstract. In 2005, Nielsen et al. formulated a continuous analogue of a dis-
crete quantum circuit by introducing a computational metric on the Lie Group
of Unitary transformations, thus allowing the introduction of the calculus of
variations in pursuit of quantum circuit lower bounds. As a parallel to this
approach, we show how Grovers search algorithm on n items corresponds to
a geodesic under the Fubini Study metric on P
n1
, the complex projective
space, and exhibit an explicit family of deformations of the algorithm of which
Grover’s Search algorithm is the optimal limit under a 1-parameter real family.
1. Introduction
Few general techniques are available for constructing efficient quantum circuits
implementing a given unitary operator. To this end, in [1, 2, 3 and 4] Nielsen et al
develop a geometric method for bounding the circuit complexity of a given unitary
operator. The basic observation notes that a quantum circuit may be thought of
as a discrete path in the smooth manifold of invertible unitary operators U(n).
Minimal complexity circuits then could be thought of as discrete paths of shortest
length. However, to make precise the idea of shortest length we require a means
of measuring distances within U (n) such that the distance between two unitary
operators is proportional to the complexity of synthesizing one operator given the
other. Such a metric is termed a computational metric.
In the theory of Riemannian Geometry and Lie Groups, distances are measured
via a Riemannian metric: an assignment of a symmetric bilinear form on the tangent
space to each given point p compatible with the Lie Group structure on U(n)
h, i
p
: T
p
U(n)T
U
(n) R
If the metric is chosen correctly, the circuit complexity of a given unitary operator
U is then proportional to the distance d(I, U ) where I is the identity operator and
d is the distance function on U(n) induced by the metric. In this way we equate
the question of finding a minimal complexity circuit implementing U to finding a
path of minimal length connecting I and U in U (n) under the appropriate metric.
These paths are given modeled by geodesics, and can be expressed naturally as the
solutions (obtained via the calculus of variations) to the so-called geodesic equa-
tions derived in terms of the metric.
We follow this discussion with a geometric proof of the optimality of Grovers
algorithm. While outside of Nielsen et als framework, the proof casts Grovers algo-
rithm as a geodesic of a natural metric on Complex Projective space. As a principle
homogenous space (i.e. a space on which the Unitary group acts transitively), there
1
2 RAEEZ LORGAT
is expected to be a strong link between this and the aforementioned point of view.
We also include a result on a family deformations of Grover’s search algorithm en-
countered in this geometric setting.
The core of this report falls into three distinct sections: section 2 a discussion of
the Riemannian metric correlating discrete quantum circuits to continuous paths
on the Unitary group, section 3 a geometric proof of the optimality of Grovers
search algorithm and section 4 a discussion of a family of deformations of Grover’s
search algorithm.
2. The Computational Metric
For simplicity we restrict our discussion to the 2
2n1
dimensional Lie Group
SU(2
n
) (the results can be extended to U (2
n
) with added technical work). SU (2
n
)
is a smooth manifold with tangent space su(2
n
), i.e. given a point of SU(2
n
) a tan-
gent vector can be thought of as a hamiltonian, i.e. a traceless 2
n
× 2
n
Hermitian
matrix. In this way, a Riemannian metric on SU (2
n
) at a point U in SU(2
n
) is a
positive-definite bilinear form hH, J i
U
mapping traceless Hermitian matrices to R.
If U(t) is a curve in SU (2
n
) generated by a Hamiltonian H(t) by the Schrodinger
equation
dU = iHU,
then the length of the curve is given by
Z
p
hH(t), H(t)idt.
This allows us to define a distance d(U 1, U 2) between two unitary operators in
SU(2
n
) as the minimal length curve connecting them with respect to any given
metric. We build the computational metric as follows: let P be the subspace of
n-qubit Hamiltonians which contain only 1 and 2 body terms, i.e. their expansion
in terms of sums and tensor products of Pauli Operators contains only terms of
weight at most 2, such as
= σ
x
I
n1
, σ
y
I
n3
σ
z
I.
Let Q denote the complementary space of Hamiltonians containing only 3 and
more-body terms, then
su(2
n
) = P + Q
as any hamiltonian can be uniquely decomposed into a sum
H = H
P
+ H
Q
Let P, Q also denote the projections onto these subspaces, then we can define
an inner product on su(2
n
) as
hH, Ji = tr(H · P(J)) + q · tr(Q(J))2n
Nielsen et al call the term q is penalty parameter which when chosen sufficiently
large causes a variation in the length
hH, Ji
viewed as a cost of moving an infinitesimal distance on SU (2
n
) in the direction
specified by the Hamiltonian H(t). A large q thus penalizes a large cost to the
choice of 3 or more qubit gates.
A STUDY OF GROVER’S SEARCH ALGORITHM VIA PROJECTIVE GEOMETRY 3
In [4] Nielsen et al. prove the induced distance d(I, U ) from the identity element to
any given U in SU (2
n
) bounds G(U): the minimal number of 1 and 2 qubit gates
required to synthesize U, thus
d(I, U ) G(U )
.
It follows that the explicit construction and computation of the length of a
geodesic from I to a given unitary operator U will prove a lower bound on the gate
complexity of U .
3. Grovers Algorithm as a geodesic on Projective Space
We now digress to investigate a geometric formulation of the optimality of
Grovers algorithm.
Theorem 3.1. Grovers algorithm acts by evolving its initialized state along a geo-
desic of the Fubini Study metric on complex projective space. As the Fubini-Study
metric is the unique natural unitary-invariant metric on projective space, and evo-
lution of a state via the action of Unitary matrix preserves the metric, Grovers
algorithm is optimal among all quantum algorithms.
Proof. To this end, assume our search function is encoded as a boolean-valued
indicator function f with domain the symbols 1 . . . n. Grovers algorithm initializes
our system with a quantum state that is a uniform super-position over n qubits.
|ai =
1
N
N1
X
x=0
|xi,
Iff(t) = 1, then we can note the inner product
ht||ai =
1
N
= sin
θ
2
allows us to express |ai as
cos
θ
2
|si
sin
θ
2
|ti
Once |ai is initialized, Grovers algorithm calls f in the form of a diffusion operator
I
t
|xi = (1)
f(x)
|xi,
iterated on the state |ai as the operator
U = I
a
I
t
= (12|aiha|)(12|tiht|)
With respect to θ we see U takes the form of a real rotation
cosθ sinθ
sinθ cosθ
Thus k iterations of the diffusion operator yields
|ψ(k)i = U
k
|ai =
cos(k +
1
2
θ|si
sin(k +
1
2
θ)|ti
The notation above makes it clear that the optimal k
π
4
N yielding a running time
complexity of O(
N).
4 RAEEZ LORGAT
Now, if we consider the unitary operators in the above circuit formulation of
Grovers search as linear operators acting on the Hilbert space C
n
, then as non-
trivial quantum states are equivalent to 1-dimensional complex subspaces (non-zero
vectors up to a complex scalar), we may work instead directly in complex projective
space. The polar form of a complex number
z = re
yields natural projections
C
n
\{0} S
2n+1
P
n1
,
where the first projection is a quotient by the dilation z = rz for r R
+
(i.e.
projects via normalization every non-zero vector onto the real unit hypersphere
S
2n+1
when C
n
is considered as a 2n dimensional real vector space), and the sec-
ond projection identifies great circles on S
2n+1
, i.e. equates any two points of S
2n+1
given by a rotation by an angle θ.
The first projection restricts the standard (Euclidean) metric on C
n
(i.e. the
2-norm) to the hypersphere S
2n+1
, while the second projection induces a natural
quotient metric on P
n
called the Fubini-Study metric.
Now projective space has the characteristic property that through any two points
there passes a unique projective line P
1
, and in the complex case this is the Riemann
Sphere. As a Riemannian globally symmetric space of rank 1, the geodesics of P
1
are all closed and all have equal length, hence are great circles of the Riemann
sphere. It follows that for some vectors ψ
1
, ψ
2
of unit norm in C
n
, a geodesic of
P
n1
is of the form
|ψ(u) = cos
u
2
|ψ
1
i + sin
u
2
|ψ
2
i
Returning to Grovers algorithm, recall k iterations of the diffusion operator yields
|ψ(k) = U
k
|a =
cos(k +
1
2
θ|si
sin(k +
1
2
θ)|ti
Let |ψ
1
i = |s, |ψ
2
i = |ti and u = 2(k + 1)θ then we see that Grovers algorithm
evolves the initial state |ai along a geodesic of the Fubini-Study metric:
|ψ(u) = cos
u
2
|ψ
1
+ sin
u
2
|ψ
2
4. Deformations of Grover’s algorithm
Now we investigate a natural generalization suggested by the geometry given
above. Connecting any two points in state space P
n
there is a unique projective
line P
1
and its preimage under the natural projections outlined in section 3 above
produces a unique complex plane
C
2
C
n
.
This inspires us to consider products of pairs of linear combinations of orthogonal
projections. In more detail, we consider unitary operators U
1
,U
2
such that each is a
A STUDY OF GROVER’S SEARCH ALGORITHM VIA PROJECTIVE GEOMETRY 5
linear combination of orthogonal projections, i.e. for orthogonal pairs of projections
(A
i
, B
i
)
i=0,1
each characterized by
A
2
i
= A
i
B
2
i
= B
i
A
i
+ B
i
= 1
then
U
i
= α
i
A
i
+ β
i
B
i
where the α
i
and β
i
are complex numbers. Then the operator we are interested in
is the family of products
(U
2
U
1
)
α
1
1
2
2
parameterizing a family of Unitary Operators, and hence a family of Quantum
Algorithms.
For our first example, for A
1
= |xihx|, B
1
= 1 A
1
and
A
2
=
1
N
1 . . . 1
.
.
. . . .
.
.
.
1 . . . 1
and B
2
= 1 A
1
then since A
2
= |x
2
ihx
2
| with x
2
=
1
N
1
.
.
.
1
then the parameters
α
1
= α
2
= 1 = β
1
= β
2
which means
U
1
= 1 2A
1
U
2
= 1 2A
2
(note that U
2
coincides with the diffusion operator introduced in section 3) repro-
duces the original Grover’s search as iterated applications of
(U
2
U
1
)
1,1,1,1
,
and for all other values of the parameters produces a deformed version of the algo-
rithm.
In order to analyse these deformations we restrict our attention to the C
2
on
which all non-trivial behaviour occurs, i.e. we consider the span of vectors
|x
0
i and
1
N 1
X
x6=x
0
|xi.
On this basis we have
U
1
=
α
1
β
1
and U
2
=
α
2
β
2
+
β
2
α
1
N
1
N 1
N 1 1
.
Now we have four complex parameters, but we can fix two of them by fixing the
choice of phase in each U
i
. We set
α
1
= β
2
= 1
6 RAEEZ LORGAT
then
(U
2
U
1
)
α
2
1
=
1
N
1 + α
2
(1 N ) β
1
(1 + α
2
)
N 1
(1 + α
2
)
N 1 β
1
(1 + α
2
N )
.
Similarly, we fix initial conditions by assuming the input vector is the same as in
our original Grover’s search i.e.
|x
in
i =
1
N
|x
0
i +
r
N 1
N
1
N 1
X
x6=x
0
|xi.
Now we’d like to compute the probability amplitude of finding the desired state as a
function of the parameters, and we do so via spectral decomposition of (U
2
U
1
)
α
2
1
.
If e
i
λ
j
are the associated eigenvalues with eigenvectors |λ
j
i then the spectral the-
orem yields
hx
0
|(U
2
U
1
)
n
α
2
1
|x
in
i = e
inλ
1
(
1
N
+ e
in(λ
2
λ
1
)
hx
0
|λ
2
)ihλ
2
|x
i
ni.
Finally
det(U
2
U
1
)
α
2
1
= β
1
α
2
and tr(U
2
U
1
)
α
2
1
= (β
1
+ α
2
) +
1
N
(1 + β
2
)(1 + α
1
)
so it follows that the eigenvalues
e
j
=
tr(U
2
U
1
)α
2
, α
1
2
r
det(U
2
U
1
)α
2
, α
1
+
tr(U
2
U
1
)α
2
, α
1
2
2
and the eigenspaces |λ
j
i are spanned by
"
(β
1
α
2
)N+(1β
1
)(1+α
2
)
4(det(U
2
U
1
)
α
2
1
N
2
+((β
1
α
2
)N+(1β
1
)(1+α
2
))
2
2(1+α
2
)
N1
1
#
.
Now denote by N
opt
the value of n where the above probability of finding the desired
state is maximized, then we have derived that as n we have the difference in
eigenvalues
λ
2
λ
1
n→∞
4
N
Real
α
2
obtaining for a parametrization
α
1
= e
that
N
opt
n→∞
b
π
4
cos
φ
2
c
N.
So we conclude that this family of deformations can be thought of as a family of
search algorithms with efficiency a function of the real parameter φ. This family has
all elements of order O(
N), and acheives optimality at φ = 0 where the algorithm
deforms into Grover’s search. Note that the worst behaviour occurs when φ π
which coincides with (U
2
U
1
) being the identity operator. Thus, we can view this
family in the framework of Nielsen et al as a smooth path in the unitary group
connecting the trivial algorithm to Grover’s search.
A STUDY OF GROVER’S SEARCH ALGORITHM VIA PROJECTIVE GEOMETRY 7
5. Conclusion
Though the Nielsen et al. approach in principle allows us to introduce the cal-
culus of variations to the task of proving quantum circuit lower bounds, to-date
no new lower bounds proofs have resulted from this approach. The reasons are
many-fold: the geometry of the Lie Groups U (n) and SU (n) is poorly understood
(even for n as low as 3), inhibiting insight into the metrics we place on them, or the
ways in which these metrics and their geodesics may be deformed. Furthermore,
the computational metric as defined is far from a natural construction: there is no
obvious way to derive it from or relate it to the known structure theories of U(n).
Most structurally interesting, however, is a consequence of Razborov Rudich: if
classical pseudorandom generators exist, then there can be no classical algorithm
running in time polynomial in 2
n
which produces an accurate approximation to the
length of a geodesic under the computational metric, as such an algorithm would
allow us to efficiently distinguish between circuits of differing complexity. Since a
circuit at random has high complexity, thus, we would show pseudorandom gener-
ators do not exist.
Still, the approach bears conceptual value: Lie Groups such as U (n) and SU(n)
have rich theories that are ubiquitous across mathematics and physics; any theoret-
ical bridge to computation: classical or quantum would prove fruitful, and Nielsen
et als approach highlights one such bridge: the identification of circuit complex-
ity of a quantum algorithm with the notion of tensor rank of a non-commutative
Hamiltonian. This bridge may provide further progress yet.
Finally, in contrast to the more general approach of finding geodesics on the
space of all unitary operators, we have also shown how Grovers search algorithm
on n items can be viewed as a geodesic of a natural metric on P
n1
. It remains
to be seen whether the two approaches can be unified into a single framework, but
in contrast to the arbitrary nature of the computational metric introduced in the
Nielsen et al. approach, the Fubini-Study metric descends from the standard inner
product on C
n
via a natural projection map; consequently much more is under-
stood about the Fubini-study metric. Given that a deformation of the Fubini study
metric will yield a deformation of Grovers algorithm, an immediate question is to
further investigate the natural families of quantum circuits arising from deforming
Grovers search algorithm.
Department of Electrical Engineering and Computer Science, Massachusetts Insti-
tute of Technology, Cambridge, MA 02139
E-mail address: raeez@mit.edu