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

n−1

, 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 eﬃcient 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 ﬁnding a minimal complexity circuit implementing U to ﬁnding 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-deﬁnite 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 deﬁne 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 deﬁne

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 suﬃciently

large causes a variation in the length

hH, Ji

viewed as a cost of moving an inﬁnitesimal distance on SU (2

n

) in the direction

speciﬁed 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

N−1

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 diﬀusion 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 diﬀusion 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

iθ

yields natural projections

C

n

\{0} → S

2n+1

→ P

n1

,

where the ﬁrst 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 identiﬁes great circles on S

2n+1

, i.e. equates any two points of S

2n+1

given by a rotation by an angle θ.

The ﬁrst 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 diﬀusion 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 ﬁrst 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 diﬀusion 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 ﬁx two of them by ﬁxing 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 ﬁx 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 ﬁnding 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

iλ

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

)

√

N−1

1

#

.

Now denote by N

opt

the value of n where the above probability of ﬁnding the desired

state is maximized, then we have derived that as n → ∞ we have the diﬀerence in

eigenvalues

λ

2

− λ

1

→

n→∞

4

√

N

Real

√

α

2

obtaining for a parametrization

α

1

= e

iφ

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 eﬃciency 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 deﬁned 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 eﬃciently distinguish between circuits of diﬀering 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 identiﬁcation 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 ﬁnding 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

n−1

. It remains

to be seen whether the two approaches can be uniﬁed 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