Quantum query complexity
of some graph problems

C. Dürr	Univ. Paris-Sud

M. Heiligman	National Security Agency

P. Høyer	Univ. of Calgary

M. Mhalla	Institut IMAG, Grenoble

Single Source Shortest Paths

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

Given a directed graph
G(V,E), with non-negative edge weights and a source vertex v0

find the shortest paths to all vertices v

v0

1

1

4

3

12

How many queries of the type ''what is the weight of the edge (u,v)?'' are necessary to solve the problem with bounded error?

Classical	(n2)

Quantum	(n3/2), O(n3/2log3/2n)

Single Source Shortest Paths

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

Given a directed graph
G(V,E), with non-negative edge weights and a source vertex v0

find the shortest paths to all vertices v

v0

1

1

4

3

12

How many queries of the type ''what is the weight of the edge (u,v)?'' are necessary to solve the problem with bounded error?

Classical	(n2)

Quantum	(n3/2), O(n3/2log3/2n)

General algorithm

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

Tree T={v0} covering vertices S={v0}

while |S|<n

add cheapest border edge (u,v)∈E∩Sx(V\S) to A
add v to S

Definition cost of edge (u,v)

=shortest path weight(v0,u) + edge weight(u,v)

v0

P3

Quantum procedure for finding cheapest border edge

Consider the decomposition of |S| into powers of 2

Decompose S into P1∪…∪Pk s.t.

|P1|>…>|Pk|

and each |Pi| is a power of 2

P1

P2

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

P3

Quantum procedure for finding cheapest border edge

Consider the decomposition of |S| into powers of 2

Decompose S into P1∪…∪Pk s.t.

|P1|>…>|Pk|

and each |Pi| is a power of 2

Suppose for every Pi we computed Ai : the |Pi| cheapest border edges of Pi with distinct targets
(for edges with source∈Pi and target∉P1∪…∪Pi)

P1

P2

•

•

•

•

•

•

•

•

•

•

•

•

•

A1

A2

A3

•

•

•

•

•

P3

Observations

Ai∩Sx(V\S) (restricted to targets∉S) is non empty for every i

The cheapest border edge of S (u,v) has its source u∈Pi for some i, and therefore v∈Ai

Thus (A1∪…∪Ak)∩Sx(V\S)
contains the cheapest border edge of S

P1

P2

•

•

•

•

•

•

•

•

•

•

•

•

•

A1

A2

A3

u

v

•

•

•

•

•

Computing Ak using
a minimum search procedure

P3

P1

P2

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

5

•

2

8

9

Input

matrix ℕa×b

Output

a column disjoint minimal entries

Bounded error quantum query complexity

(ab)

8	5	∞	∞
∞	2	9	∞

•

Single source	(n2)	(n3/2), O(n3/2log2n)	(m)	((nm)), O((nm)log2n)

shortest paths
Minimum weight	(n2)	(n3/2)	(m)	((nm))

spanning tree

Connectivity	(n2)	(n3/2)	(m)	(n)

(undirected graph)

Strong Connectivity	(n2)	(n3/2)	(m)	((nm)), O((nmlogn))
(directed graph)

Bounded error
quantum query complexity

Adjacency matrix model

1: 2: 3: 4:

1: 0 1 1 0

2: 1 0 0 0

3: 1 1 0 1

4: 0 0 0 0

Bounded error (classical) quantum query complexity

1

3

2

4

Adjacency array model

1: 2 3

2: 1

3: 1 4 2

4:

2003-12-06T12:08:11