Given two positive Boolean functions : {0, 1} → {0, 1} and : {0, 1} → {0, 1} expressed in their positive irredundant DNF Boolean formulas, the dualization problem consists in determining if is the dual of , that is if (1, . . . , ) = (1, . . . ) for all (1, . . . ) ∈ {0, 1}. In this paper we present a quantum computing algorithm that solves the dualization problem in polynomial time with respect to the dimensions of the DNF expressions.
It is known [
∈ ∈ = ⋁︁
⋀︁
∈,̸= ∈
where is a family of subsets of {1, 2, . . . , }. For any ∈ the implicant ⋀︀∈ is called
term of the DNF . A positive DNF expression of a boolean function is prime if all its terms are
prime implicants of ; furthermore it is said irredundant if there is no ∈ such that
is another positive DNF representation of . The following theorem characterizes positive DNF
expressions
Theorem 1 ([
By Theorem 1, a positive DNF which contains only and all the implicants of a positive
Boolean function is unique and irredundant. We will call it positive irredundant DNF (PIDNF).
The dualization problem [
In the following the variable is interpreted sometimes as a Boolean (or binary) -dimensional vector and sometimes as the decimal expression of the binary vector. In particular if is the decimal value of the binary vector (1, . . . , ) then the decimal value of the binary vector (1, . . . , ) is = 2 − − 1. We start with the following proposition which will be often used later in the paper.
Proposition 2 ([
By Proposition 2, if is self-dual then every implicant of must intersect every other implicant.
Lemma 3. Suppose is self-dual. Then is balanced, that is, for half of values is 0 and for the other half is 1.
Proof. Let 0 ≤ < 2, then = 2 − − 1. Furthermore since is self-dual we have that () ̸= () for all 0 ≤ < 2. Therefore 2− 1− 1 ∑︁ () + =0 2− 1− 1 ∑︁ () + 2− 1 ∑︁ () = =2− 1 2− 1− 1 ∑︁ (2 − − 1) = =0 =0 2− 1− 1 ∑︁ [ () + ()] = 2− 1 =0 Lemma 4. Let be a positive Boolean function expressed in its PIDNF which satisfies also (2). Then is self-dual if and only if ∑︀2=− 01 () = 2− 1.
Proof. The necessity is given by Lemma 3. As for the suficiency, suppose that ∑︀2=− 01 () = 2− 1 and suppose by contradiction that () = () for some 0 ≤ < 2. Since (2) holds, when () = 1 there exists an implicant such that = 1 for all ∈ . But then () = 0 since intersects all other implicants of . In other words () + () ≤ 1 for all 0 ≤ < 2. Therefore we must have that () = () = 0 for some 0 ≤ < 2. But since 2− 1 2− 1 = ∑︁ () = =0 2− 1− 1 ∑︁ [ () + ()] ≤ 2− 1 =0 we must have, for every 0 ≤ < 2− 1, that () + () = 1, and this is a contradiction.
Now we state he following Remark which will be useful for the rest of the paper (see Theorem
1.11 of reference [
Remark 5. A term = ⋀︀∈ of a positive DNF expression = ⋁︀∈ ⋀︀∈ of a positive Boolean function is absorbed by a term = ⋀︀∈ of if and only if ⊆ .
We define () the Hamming weight of the integer 0 ≤ < 2, as the number of ones in the binary representation of , or, equivalently, if = (1, . . . , ) is a binary vector, then () = ∑︀
=1 .
We said that the complexity of the dualization problem is measured with respect to the
combined size of the PIDNF representation of and , that is, with respect to = | | + ||.
Furthermore as stated in [
Choose > 4 odd and consider the following Boolean function whose positive DNF expression has as a set of implicants, the set of all subsets of {1, . . . , } of cardinality ⌈/2⌉ where ⌈⌉ is the least integer greater or equal than .
Lemma 6. The function expressed by is self-dual. Moreover is the PIDNF representation of , and has a number of terms equal to (︀ ⌈/2⌉)︀ .
Proof. Trivially, by definition, | | = (︀ )︀ . If there exist two implicants and such that ⌈/2⌉ ∩ = ∅ then | ∪ | = || + | | = 2 ⌈/2⌉ > a contradiction to the fact that the number of variables is . So we have that (2) holds for .
For every such that () < ⌈/2⌉ we have that () = 0 since every implicant of has cardinality || = ⌈/2⌉. On the other hand for every such that () ≥ ⌈ /2⌉ then () = 1 since, if we consider as a binary vector, we will always find an implicant such that = 1 for all ∈ . Now it is immediate to check that |{ : 0 ≤ < 2, () ≥ ⌈ /2⌉}| = 2− 1. By Lemma 4, is self-dual. It remains to show that is irredundant. By Theorem 1, is not irredundant if there is some term = ⋀︀∈ of which is absorbed by some other term = ⋀︀∈ of . By Remark 5, this happens if and only if ⊆ and ̸= . But this is impossible because | | = || for all pairs of , ∈ . 2.1. The quantum computing approach In the following we give several quantum computing algorithms for the dual and self-dual problems.
Given two Boolean functions and we build the function ℎ() = () ⊕ () where ⊕ is the sum modulo two.
Note that ℎ can be obtained from and by using a polynomial number of logic gates with respect to the number of terms in their PIDNF expressions. If () = () for all then ℎ() = 0 for all ; that is ℎ is a constant function. We prepare a black box ℎ which performs Deutsch-Jozsa [14] algorithm. We have that the measurements of first qubits will be the transformation |⟩|⟩ → |⟩| ⊕
ℎ()⟩, for 0 ≤ < 2. We use the blackbox ℎ in the and the probability of measuring for |⟩ = |0⟩ is, when ℎ() = 0 for all , equal to 1 since 1 2∑−︁1 2− 1 2
∑︁ (− 1)· +ℎ()|⟩ =0 2 1 2∑−︁1(− 1)ℎ()|0⟩ = |0⟩ so we have the following remark. value |⟩ ̸= |0⟩ then is not the dual of .
Remark 7. Let and be two monotone prime Boolean functions which also satisfy (2) and let ℎ = ⊕ . If we measure at the end of the Deutsch-Jozsa algorithm with blackbox function ℎ, a algorithm, we can conclude that is not self-dual.
In the same way as above we could build a blackbox and apply the Deutsch-Jozsa algorithm to check if is balanced. By Lemma 3, if is self-dual the Deutsch-Jozsa algorithm will output a value |⟩ ̸= |0⟩ with probability one. If we measure a value equal to |0⟩ at the end of the
We note that if is not self-dual then the Deutsch-Jozsa algorithm could output a value a probabilistic algorithm whose running time depend on . equal |⟩ ̸= |0⟩ with probability < 1. So if we repeat the algorithm times and is not self-dual, the probability of observing |⟩ ̸= |0⟩ for times will be . We obtained, in this way,
Another approach to solve the self-dual problem would be to use the quantum counting algorithm [15]. In this approach we build a blackbox . Let be the number of such that () = 1. By Lemma 4, if is self-dual and (2) holds, then = 2− 1. The quantum counting algorithm will estimate the phase of the eigenvalues of the Grover operator which are or (2 − ) where is the angle of rotation of the Grover operator and it satisfies the following equation 2 sin
= 2 √︂ 2 . Thus, if = 2− 1, we have that = . We assume that the register for |2− 1 + 2− 2⟩ the function is not self-dual. measuring the phase is composed by qubits. At the end of the counting algorithm we will measure the phase of the eigenvalue 2 = or 2 = (2 − ) from which we obtain that = 1/4 or
= 3/4. Therefore, if the function is self-dual, at the end of the counting algorithm, we should measure |2− 2⟩ or |2− 1 + 2− 2⟩ with probability one. In other words, if the measurement at the end of the counting algorithm is not equal to |2− 1⟩ and not equal to
We note that the number of iteration of the counting algorithm, and therefore its complexity, depend on the number of qubits we use to approximate the phase .
found then is not self-dual.
such that () = (). If such is From Remark 1, Lemma 3 and Lemma 4 we may summarize the discussion above in the following quantum algorithm for checking if a function is self-dual.
Algorithm Quantum Dual Input: A PIDNF of a Boolean function satisfying (2) and a black box which performs the transformation |⟩|⟩ → |⟩| ⊕ ()⟩, for 0 ≤ < 2.
Procedure: 1. Let ℎ() = () ⊕ (). Use the Deutsch-Jozsa algorithm to check if ℎ is constant. If the output of the Deutsch-Jozsa algorithm is not equal to |0⟩ then output False and exit. 2. Use the Deutsch-Jozsa algorithm to check if is balanced. If the output of the Deutsch
Jozsa algorithm is equal to |0⟩ then output False and exit. 3. Use the Quantum Counting algorithm to count the number of such that () = 1 using = ⌈/2⌉ qubits to measure the phase angle. If the measurement at the end of the algorithm is |⟩ and if ̸= 2− 2 and ̸= 2− 1 + 2− 2 then output False and exit. 4. Use the Grover algorithm to find an such that () = (). If such is found then output False and exit. 5. Output True
The complexity of the algorithm Dual is dominated by the complexity of the quantum counting
and of the Grover algorithms. Recall that is the number of variables of the Boolean formula
and is the dimension of the algorithm’s input. The blackbox used in the algorithms requires
( ) gates. Both algorithms achieve a complexity on the number of quantum iterations which
is (2/2) while the best deterministic classical computing algorithm has time complexity of
( (log )) [
In this paper we shed a new light on the complexity of the dualization problem, with a perspective from a quantum computing approach. We demonstrate that the dualization problem can be solved by using a mixture of several quantum computing algorithms obtaining an exponential speed up if compared to the best classical computing algorithm proposed in literature when the input size of the problem is exponential to the number of variables of the Boolean functions. We think that these ideas, far from being conclusive, could be used to develop faster, either classical or quantum computing, dualization algorithms. 492. URL: https://doi.org/10.1137/15M1027267. doi:10.1137/15M1027267. arXiv:https://doi.org/10.1137/15M1027267. [14] D. Deutsch, R. Jozsa, Rapid solution of problems by quantum computation, Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439 (1992) 553 – 558. URL: https://api.semanticscholar.org/CorpusID:121702767. [15] M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.