5
$\begingroup$

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?

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ Mar 9 '14 at 0:24
7
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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}$ $\endgroup$
    – user6973
    Mar 9 '14 at 1:24
  • $\begingroup$ @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. $\endgroup$ Mar 9 '14 at 2:13
  • 4
    $\begingroup$ 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. $\;\;\;$ $\endgroup$
    – user6973
    Mar 9 '14 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.