Can I use Grover's algorithm on overlapping sets of qubits?

Question

Let's say I have 3 qubits: $q_1,q_2,q_3$.

I want to apply Grover's algorithm on q1,q2, such that q1,q2 $\neq$ 10 and do the same for q2,q3, so that q2,q3 $\neq$ 11. The final possible combinations of the qubits q1,q2,q3 should then be:
000
001
010
110

And they shouldn't be:
011
100
101
111

If this is possible then couldn't I solve 3sat in polynomial time with a quantum computer? Couldn't I just remove the possibility of each clause being unsatisfied from a set of qbits representing the variables in the 3sat problem and then collapse the qbits to see if the final result is satisfiable?

Example of how I think a quantum computer would solve an instance of a 3sat problem in polynomial time:

Note: each computation should be on a set of 3 qbits at a time which should take $2^{3/2}$ time with Grover's algorithm, or O(1) in big O notation)

Variables = ${a,b,c,d,e}$

clauses = ${(\neg a \vee b \vee \neg c),(b \vee c \vee d),(\neg b \vee \neg c \vee d),(c \vee \neg d \vee e),(c \vee \neg d \vee \neg e)}$

We have qubits $q_a, q_b, q_c, q_d, q_e$

for $q_a, q_b, q_c$ we remove the possibility of 101 (since this would not satisfy the 1st clause)

for $q_b, q_c, q_d$ we remove the possibility of 000 and 110 (since those would not satisfy the 2nd and 3rd clause)

for $q_c, q_d, q_e$ we remove the possibility of 010 and 011 (since those would not satisfy the 4th and 5th clause)

Now the possible outputs of the qbits are:

00100
00101
00110
00111
01000
01001
01110
01111
11000
11001
11110
11111

So if I collapse the qbits I should remain with one of these combinations which satisfies the problem. If there is no possible solution, the qbits will just collapse into something meaningless which will not satisfy the problem.

If anyone can show me the flaw in my logic, please let me know, I highly doubt I solved 3sat. I'm just trying to learn.

Answer 1

Grover's algorithm has two components, which alternate and repeat $O(\sqrt{N})$ times: a diffusion operator and an oracle operator. The diffusion operator will cause problems with your idea.

As I understand, what you want to do is start from a uniform superposition

$$\vert \psi_0\rangle =\frac{1}{\sqrt{2^n}}\sum_{b_1,\dots,b_n\in\{0,1\}} \vert b_1\rangle \vert b_2\rangle\dots\vert b_n\rangle$$

and then solve for (e.g.) a clause $C_1$ in $b_1,b_2,b_3$, to get something like:

$$\vert\psi_1\rangle=\frac{1}{\sqrt{N}}\sum_{\substack{b_1,\dots,b_n\in\{0,1\}\\ C_1(b_1,b_2,b_3)=1}} \vert b_1\rangle \vert b_2\rangle\dots\vert b_n\rangle$$

where $N$ is the number of remaining solutions. From this superposition, you want to solve for another clause $C_2$ which involves (e.g.) $b_1, b_4, b_5$ (if no other clause involves $b_1,b_2,b_3$, then it's easy to solve for these 3 variables first and then remove them from the problem).

But now you're searching over the first qubit, $b_1$, but $\vert\psi_1\rangle$, your superposition over $b_1$, is non-trivial. Grover's algorithm requires a way to flip the phase of the starting superposition. Normally, the way to do this is to apply $H$ gates to every qubit and flip the all-zeros state, then apply $H$ again to return to the previous state, but after solving the first clause, the superposition $\vert\psi_1\rangle$ is not just $H^{\otimes n}\vert 0^n\rangle$.

In fact, (as far as I am aware) the only way to construct a diffusion operator for the superposition $\vert\psi_1\rangle$ where $C_1$ is solved is to undo the solution for $C_1$, then apply $H$ gates, then flip over $\vert 0^n\rangle$, then redo those same operations.

If you do that, then you can run Grover's algorithm on a clause-by-clause basis and solve the 3-SAT problem. However, the cost is not polynomial: If there are $m$ clauses, for the last clause, the diffusion operator must solve and unsolve an $m-1$ clause 3-SAT problem. So if the cost of solving this problem is $c_{m-1}$, the total cost will be $\approx\sqrt{2^3}c_{m-1}$. But solving an $m-1$ clause 3-SAT problem will require a diffusion operator that solves an $m-2$ clause 3-SAT problem, so $c_{m-1}\approx \sqrt{2^3}c_{m-2}$ (and so on). You end up multiplying all of the factors of $\sqrt{2^3}$ each time you go through, and the total cost ends up as something like $O(\sqrt{2^{3m}})$ -- which is roughly the exponential cost you would expect from a naive Grover search.