Now that we have computed the final result of each clause, to compute the final result for the function as a whole, we will need to combine each of these temporary results with a multi-qubit quantum AND. We will do so two results at a time, using the quantumand_2 function, until we get to the final result. This takes advantage of the fact that t, u, v, w, x, y, and z are all the results of the seven individual clauses t ∧ u ∧ v ∧ w ∧ x ∧ y ∧ z = ((((((t ∧ u) ∧ v) ∧ w) ∧ x) ∧ y) ∧ z), and we can in general regroup an AND function over many variables into sub-functions over two variables at a time with the help of temporary variables to store the result. In fact, we can do the grouping however we like, and use the quantumand_2 function, so long as it is two at a time. Here, I chose to group the results two at a time, t ∧ u ∧ v ∧ w ∧ x ∧ y ∧ z = ((t ∧ u) ∧ (v ∧ w)) ∧ ((x ∧ y) ∧ z), for clarity of the code (each of which corresponds to our quantum circuit requiring an additional qubit).
Each time we call quantumand_2, we will need to specify the indices of the quantum registers containing the input qubits over which to compute the quantum AND, as well as the index of a temporary quantum register in which to store the result. Thus, our computation will require six more temporary registers, the sixth of which is actually not temporary (index 22) as it will (finally!) contain the final result of the computation. For convenience, the quantumand_2 function returns the index of the temporary register in which the result is stored.
Thus, in our choice of variables corresponding to the results of each of the seven clauses, the quantum register at index intermediate_and_pair1 (index 17) contains the result of (t ∧ u), the quantum register at index intermediate_and_pair2 (index 18) contains the result of (v ∧ w), and the quantum register at index intermediate_and_pair3 (index 19) contains the result of (x ∧ y). Then, the quantum register at index intermediate_and_pair_12 (index 20) contains the result of ((t ∧ u) ∧ (v ∧ w)), the quantum register at index intermediate_and_pair_34 (index 21) contains the result of ((x ∧ y) ∧ z), and the quantum register at index final_result_and_pair_1234 (index 22) contains the final result:
This corresponds to the result of the entire 3sat_mystery(a,b,c) function evaluated on a given input.
The code to do the quantum AND combination of the individual clauses is then as follows:
# Let's whittle down
intermediate_and_pair1=quantumand_2(qr,qc,first_clause,second_clause,17)
intermediate_and_pair2=quantumand_2(qr,qc,third_clause,fourth_clause,18)
intermediate_and_pair3=quantumand_2(qr,qc,fifth_clause,sixth_clause,19)
# Now whittling down further
intermediate_and_pair_12=quantumand_2(qr,qc,intermediate_and_pair1,intermediate_and_pair2,20)
intermediate_and_pair_34=quantumand_2(qr,qc,intermediate_and_pair3,seventh_clause,21)
# Now whittling down to 1 result
final_result_and_pair_1234=quantumand_2(qr,qc,intermediate_and_pair_12,intermediate_and_pair_34,22)