Grover's search algorithm for 3 coloring

According to Arora & Barak (pdf), pg. 186, for a polynomial-time computable function $f: \{0,1\}^n \to \{0,1\}$ (represented as a circuit computing $f$), Grover's algorithm finds in $O(\text{poly}(n)2^{n/2})$ time a string $a$ such that $f(a) = 1$ (if such a string exists).

My question is an application of Grover's algorithm to 3 coloring. How can you show, using Grover's algorithm, that 3-coloring can be solved on a quantum computer in time $O(\text{poly}(n)2^{n/2})$, where $n$ is the number of vertices?

This is not a direct application of the algorithm, since although you can easily encode each of the $3^n$ (valid and invalid) colorings of the $n$ vertices using $\log_2(3^n) = n\log_2(3) = O(n)$ bits, this means that Grover's algorithm gives a run time of $O(\text{poly}(n)2^{n\log_2(3)/2}) = O(\text{poly}(n)3^{n/2})$.

So maybe, you would need to show that a coloring (possibly valid) can be encoded using only $n + O(1)$ bits? How would you show that?

• I gave you an answer, but I am not sure if this is a research-level question. In particular, it has nothing to do with quantum computing. – Artem Kaznatcheev Mar 9 '14 at 0:24

You don't need to keep track of all $3$ colours for your colouring, because we know how to two colour quickly.
Let the colours be $\{0,1,2\}$. Have an oracle $f: \{0,1\}^{|V|} \rightarrow \{0,1\}$ that you interpret as selection a subset $C_0 \subseteq V$ that you will pretend is $0$-coloured. Your circuit then (1) in polynomial time checks if $V - C_0$ is two-colourable with $\{1,2\}$, and (2) in polynomial time checks if $C_0$ is an independent set. If both are true then it returns $1$, else $0$. Now you are searching over only $2^n$ database entries for a marked element and so have the runtime you wanted.
• If V is non-empty, then the database entries only need to be the subsets S of V such that $\: 0 < |S| \leq \lfloor |V|/3 \rfloor \;$. $\;\;\;$ (However, I don't know how much improvement that gives.) $\hspace{1.3 in}$ – user6973 Mar 9 '14 at 1:24
• @RickyDemer that factor would disappear in the $\text{poly(n)}$ term. Also, since Grover's algorithm scales as $\sqrt{N/M}$ where $N$ is the size of the search space, and $M$ is the number of matches, it is not inherently obvious that decreasing both by the same factor (as you suggest) would give you a speedup, especially if you have to make your basic oracle more expensive. That is why I did not include such extra 'optimizations' in my answer. – Artem Kaznatcheev Mar 9 '14 at 2:13
• When I plug the |V|-sample binomial distribution with p=1/2 into this theorem and evaluate with wolframalpha, I get that my observation should reduce the size of the search space by a factor of more than 2^((2/25)*n). $\:$ Since there is no reason there needs to be a large number of colorings (consider a complete tripartite graph), that should reduce the upper bound by a factor of more than 2^(n/25), which does not disappear in the poly(n) term. $\;\;\;$ – user6973 Mar 9 '14 at 9:13