<p>You don't need to keep track of all $3$ colours for your colouring, because we know how to two colour quickly. </p>

<p>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.</p>

CC BY-SA 3.0
2014-03-09T02:13:31.867Z
@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
CC BY-SA 3.0
2014-03-09T00:24:05.157Z
2014-03-09T00:24:05.157Z
Artem Kaznatcheev
<p>According to <a href="http://www.cs.princeton.edu/theory/complexity/ab_quantumchap.pdf" rel="noreferrer">Arora &amp; Barak (pdf)</a>, 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).</p>

<p>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?</p>

<p>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})$.</p>

<p>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?</p>

CC BY-SA 3.0
2014-03-09T00:24:59.580Z
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
<cc.complexity-theory><graph-algorithms><quantum-computing>
Grover's search algorithm for 3 coloring
matthon
# Grover's search algorithm for 3 coloring

(Asked by: username_0 on 2014-03-08)

According to [Arora & Barak (pdf)](http://www.cs.princeton.edu/theory/complexity/ab_quantumchap.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?

**Tags:** cc.complexity-theory, graph-algorithms, quantum-computing

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2014-03-09. Score: 8

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.

> **Comments:**
> **username_1**: @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.  

---

