5
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

Boolean variables can be represented by the matrix, $b=\frac{z+1}{2}$, where:
$$ z=\begin{pmatrix}1 & 0 \\ 0 & -1 \end{pmatrix}. $$

Notice that the eigenvalues of $b$ are {0,1}, which is exactly what you want. This is explained on Pg. 1 of this book on quantum mechanics and Boolean functions (see Eq. 3).

Pg. 2 of the same book refers to this paper which explains the connection between Boolean variables and quantum operators in even more detail in Eqs 8-9. In the paper, Eq. 13 is an example of exactly the type of function you have.

So for your example: $x_1x_2+ x_3x_1x_4+x_5x_6$

We have: $\frac{(z_1+1)(z_2+1)}{4} + \frac{(z_3+1)(z_1+1)(z_4+1)}{8} + \frac{(z_5+1)(z_6+1)}{4}$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you for the answer and for the reference, I will read it immediately. At first sight though, in this way I should initialize n qubits, with n the number of boolean variables, and apply to each the quantum operator b, is that right? I mean that, assuming to have these n variables, I would need O(n) qubits anyway to implement the formula. $\endgroup$
    – FSic
    Jul 11, 2018 at 8:53
  • 1
    $\begingroup$ Exactly. N boolean variables = N qubits. $\endgroup$
    – user1271772
    Jul 11, 2018 at 9:21
  • 1
    $\begingroup$ @F.Siciliano: This is an excellent paper where the z-matrix is used to represent a Boolean function. You just have to read pages 1-2: arxiv.org/pdf/1411.6758.pdf $\endgroup$
    – user1271772
    Jul 11, 2018 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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