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:

And they shouldn't be:

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:


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.

  • $\begingroup$ Does this answer your question? Grover algorithm for more than one element $\endgroup$ May 4, 2021 at 1:04
  • $\begingroup$ Here's the thing, wouldn't that mean I can solve 3sat in polynomial time with a quantum computer? All I need to do is start off with a set of qubits representing the variables and remove the every combination that does not satisfy each clause. I will update the question to make it more clear. $\endgroup$ May 4, 2021 at 13:07
  • $\begingroup$ Not at all. Grover's search only gives you a square root speed-up. So while it might take you time $O(2^n)$ to run on a classical computer, it only takes you time $O(2^{n/2})$ to run on a quantum computer. No exponential speedup, but very useful. This is indeed exactly the sort of situation that you want to use Grover's Search. $\endgroup$
    – DaftWullie
    May 4, 2021 at 13:46
  • $\begingroup$ I understand that is the case if I apply each computation to all of the qbits at the same time. What I'm wondering is: can I apply each computation on 3 qbits at a time (which might overlap). $\endgroup$ May 4, 2021 at 13:51
  • 1
    $\begingroup$ I see what you're getting at now! I think the issue is that you're going to have a global search state, you cannot break the underlying state down into little pieces. Moreover, each of the later Grovers that you run, you need an oracle that produces the correct input (which is no longer the uniform superposition, because you've removed some terms), which means that it has to repeat all of the earlier runs of Grover each time. $\endgroup$
    – DaftWullie
    May 4, 2021 at 14:06

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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