Chapter 13 Quantum algorithms for graph problems
In this chapter we are going to discuss quantum algorithms for graph theoretical problems. Initial focus of this chapter revolves around the work of (Dürr et al. 2006), which investigated the query complexity of problems like MINIMUM SPANNING TREE, CONNECTIVITY, STRONG CONNECTIVITY, and SINGLE SOURCE SHORTEST PATH. Classically, these problems can be solved efficiently i.e. in polynomial number of queries to the graph. In this chapter, we will see how to decrease the query complexity of the quantum algorithm further, by applying in a shrewd way amplitude amplification and related algorithms. More specifically, in the work of (Dürr et al. 2006), they used three different versions of the Grover’s algorithm. In particular, we state a slightly improved version here, with a quadratic improvement also in the runtime dependence on the probability of failure.
Theorem 13.1 (Grover's search algorithm, version of (Buhrman et al. 1999)) Let \(N=2^n\) for \(n>0\). Given quantum oracle access \(O_x: |i\rangle\mapsto|i\rangle|x_i\rangle\) to a vector \(x \in [k]^{N}\) (for a fixed \(k\)) and access to an oracle \(O_f |x\rangle = (-1)^{f(x)}|x\rangle\) for a function \(f:[k] \mapsto \{0,1\}\), If \(m\) is the number of elements of the vector \(x\) that are evaluated to \(1\) (called marked elements), there is a quantum algorithm that succeed with probability greater than \(1-\delta\) and finds an index of a marked element using \(O_x\) only \(O(\sqrt{N/m \log(1/\delta)})\) times.
In fact, note that the “standard” version of bounding the probability of failure of a quantum or classical randomized algorithm consist in repeating the algorithm a certain number of time, and use the “powering lemma” C.1. This will result in an increase of the runtime that is logarithmic in \(\delta\). This version of Grover’s algorithm achieves a quadratic speedup in the failure probability.
Further discussions of some of the quantum algorithms for graphs can also be found in (Dürr et al. 2006) and also in (Dörn 2008).
As usual, we assume two different access to the graph: the “adjacecny matrix model” and the “adjacency array” (or list) model.
- In the adjacecy matrix model we assume to have query access to the entries of an adjacecny matrix of a graph, as in definition 3.12.
- In the adjacency list model we assume to have query access to the an oracle that tells us the number of adjacent nodes, and an oracle that gives us the index of the adjacent nodes, as in 3.13. Note that sometimes this goes under the name “adjacency array”, as in the quantum case we don’t have to go through the whole list of adjacent nodes, but we can index them as an array.
13.1 Connectivity
The problem of connectivity, as stated below can be seen as a special case of them minimum spanning tree problem, where all edges of \(G\) carries equal weight.
Definition 13.1 (GRAPH CONNECTIVITY problem) Given an undirected graph \(G=(V,E)\), decide if \(G\) is connected.
The following algorithm has first been proposed in (Dürr et al. 2006), and reelaborated in (Dörn 2008).
Figure 13.1: Algorithm for graph connectivity of undirected graph in the adjacecy model
Theorem 13.2 (Quantum algorithm for graph conectivity (adjacency matrix model)) Assume that \(U_A\) is a unitary that gives you query access to the adjacency matrix \(M\) of an undirected graph \(G=(V,E)\). Then, deciding if a graph is connected has an expected number of queries to \(U_{A}\) of \(\widetilde{O}(n^{3/2})\). In particular, if the graph is connected, algorithm in figure 13.1 returns a spanning tree for \(G\) with probability greater than \(2/3\).
Proof. The whole algorithm tries to build a spanning tree for the graph. If we succeed, then the graph is connected. The algorithm start by creating a data structure that holds \(n\) different connected components, one for each vertex. Then, we construct a spanning tree by finding an edge that connects any two of the connected components.
Initialize the algorithm with an empty edge set \(A\) for the spanning tree \(T=(V,A)\). We use theorem 13.1 on the operator \(U_A\) and the oracle \(U_{f_T}\). As usual, \(U_A\) is defined as \(U_A : |i,j,c\rangle \mapsto |i,j,c\oplus A_{ij}\rangle\). We ecapsulate into the oracle \(U_{f_T}\) the data structure that stores the connected components, so we can have a unitary implementing the function \(f_T : E \mapsto \{0,1\}\):
\[f_T(e) \begin{cases} 1 & \text{if } c(T \cup e) < c(T) \\ 0 & \text{otherwise} \end{cases}\] Where \(c(G)\) is the number of connected components of the graph \(G\). It is basically a unitary that checks if a given edge has endpoints of 2 different connected component. Note that \(U_{f_T}\) needs to compare a given edge with a whole list of edges that are currently in the list of connected components. Note that in order to work, this oracle should compare a given edge with the list of edges that are part of the spanning tree \(T\). The spanning tree can grow up to size \(O(n)\), so the depth of the oracle is at worst \(O(n)\) (up to a polylogarithmic factors).
The runtime analysis is concluded by noting that we need to repeat the search procedure of theorem 13.1 up to \(n\) times (because when we obtain \(n\) nodes in the MST we stop the algorithm). Suppose that the graph is connected. The main loop of the algorithm is repeated exactly \(n-1\) times, and each search withint the loop can be done in \(O(\sqrt{n^2/k})\), where \(k\) is the number of valid solutions to the search problem. These solutions correspond to the edges \(e\) of \(G\) that are linking any two connected components. It is simple to observe that at the first iteration we have at least \(k=n-1\) solutions (i.e. any edge is a good solution), and the number of solutions decreases at each iteration. The number of queries to the oracle is:
\[\sum_{k=2}^n \sqrt{\frac{n^2}{(k-1)}} = n\sum_{k=2}^n \frac{1}{\sqrt{k-1}}\] With Cauchy-Schwartz we can see that:
\[\sum_{k=2}^n \frac{1}{\sqrt{k-1}} = \sum_{k=1}^{n-1} \frac{1}{\sqrt{k}} \leq \sqrt{n-1}\left(\sum_{k=1}^{n-1}\frac{1}{k} \right)^{1/2} = \sqrt{n-1}\left(\gamma + \log(n-1) + \frac{1}{2(n-1)} \right)^{1/2}\]
where \(\gamma\) is the Bonferroni constant, and we just interpret the second norm as a truncated Harmonic series approximated by Taylor expansion. Thus, overall we get \[\sum_{k=2}^n \sqrt{\frac{n^2}{k-1}} \leq n \sqrt{n-1} \left(\gamma + \log(n-1) + \frac{1}{2(n-1)} \right)^{1/2} = O(n^{1.5}\log(n))\]
If the graph is not connected, at some point we will not be able to find any new edges, and the procedure of theorem 13.1 will fail (we can repeat this procedure a certain number of times to be sure that there are indeed no more valid edges, leveraging the powering lemma, i.e. lemma C.1).
We need to set the failure probability of each run of theorem 13.1. It is simple to check that if we want the probability of failure to be bounded by \(2/3\) we need to se the probability of failure for a single run of the algorithm as \(\delta \geq \frac{1}{3n}\). This is relatively simple to obatin from the union bound (see exercise C.2).
Exercise 13.1 (Improve bound of number of queries) Can you show that \(\sum_{k=2}^n \sqrt{\frac{n^2}{(k-1)}}=O(n^{3/2})\), i.e. without the polylogarithmic factor \(\log(n)\). Or can you prove that it is not possible to remove it? Hint.
For the array model, we report the theorem of (Dürr et al. 2006).
Theorem 13.3 (Quantum algorithm for graph conectivity (array model)) Assume that \(U_A\) is a unitary that gives you query access to the array model of an undirected graph \(G=(V,E)\). Then, deciding if a graph is connected has an expected number of queries to \(U_{M}\) of \(O(n)\). In particular, algorithm \(\ref{fig:quantum-algo-connectivity}\) returns a spanning tree for \(G\) if \(G\) is connected, otherwise runs forever.
13.2 Summary of results
A summary of the query complexities is stated below.
| Problem | Adj. Matrix | Array |
|---|---|---|
| Minimum Spanning Tree | \(O(n^{3/2})\) | \(O(\sqrt{nm})\) |
| Connectivity | \(O(n^{3/2})\) | \(O(n)\) |
| Strong Connectivity | \(O(n^{3/2})\) | \(\Omega(\sqrt{nm})\), \(O(\sqrt{nmlog(n)})\) |
| Single Sourced Shortest Path | \(\Omega(n^{3/2})\), \(O(n^{3/2}log^{2}(n))\) | \(\Omega(\sqrt{nm}log^{2}(n))\), \(O(\sqrt{nm})\) |