As in the title, I have a doubt regarding the implementation of a boolean formula used as an oracle for a quantum algorithm. The problem is that so far I could reproduce the formula as a quantum circuit relatively easily and then solve the related SAT using Grover search. However, if for instance I have 8 variables, I would need more or less twice the number of qubits to reproduce the formula (8 for introducing the variables, the others as workspace to perform the logic operations). Even though Grover search allows a quadratic speed up, I feel that implementing the oracle in this classical way is still a big hindrance in terms of qubits needed, given the fact that they are limited to small amounts.
I am trying to see if it is possible to encapsulate the 8 variables in 3 qubits so that using a Walsh-Hadamard transform I would have a superposition with $2^3=8$ possible states. 2 problems arise:
1) How could i perform the logical operations needed to represent the boolean formula?
2) Given a single qubit, I can look at it as a variable and assign true and false values to the states $\left|1\right>$ and $\left|0\right>$ respectively; however, if I use multiple qubits and put all of them in a superposition, when assigning each state to a specific variable I can no longer see if they are true or false by looking at the output states! How could I decide a true/false output in this case?
Do you guys think this is something feasible? I feel I am missing a key point in the process.
For instance $\left(x_1\cdot x_2\right)+\left(x_3\cdot x_1\cdot x_4\right)+\left(x_5\cdot x_6\right)$, where every variable $x_i \in \left\lbrace 0,1\right\rbrace$ and " $\cdot$ " stands for the logic AND operation and "$+$" for the logic OR.