Optimizing the Quantum Circuit for Solving Boolean Equations Based on Grover Search Algorithm

Abstract

The solution of nonlinear Boolean equations in a binary field plays a crucial part in cryptanalysis and computational mathematics. To speed up the process of solving Boolean equations is an urgent task that needs to be addressed. In this paper, we propose a method for solving Boolean equations based on the Grover algorithm combined with preprocessing using classical algorithms, optimizing the quantum circuit for solving the equations, and implementing the automatic generation of quantum circuits. The method first converted Boolean equations into Boolean expressions to construct the oracle in the Grover algorithm. The quantum circuit was emulated based on the IBM Qiskit framework and then simulated the Grover algorithm on this basis. Finally, the solution of the Boolean equation was implemented. The experimental results proved the feasibility of using the Grover algorithm to solve nonlinear Boolean equations in a binary field, and the correct answer was successfully found under the conditions that the search space was 2²¹ and three G iterations were used. The method in this paper increases the solving scale and solving speed of Boolean equations and enlarges the application area of the Grover algorithm.

1. Introduction

A large number of scientific problems are often ascribed to the problem of solving Boolean equations. Research on quantum algorithms for solving nonlinear Boolean equations in binary fields is a critical problem in computational mathematics, cryptographic, design, and analysis.

Feynman first proposed the concept of a “quantum computer” in 1981, pointing out that only a quantum computer can effectively simulate a quantum system. In 1985, Deutsch proposed the Quantum Turing Machine for the first time and designed the Deutsch algorithm [1], which laid the basic idea for a quantum algorithm. In 1992, Deutsch and Jozsa jointly proposed the Deutsch–Jozsa algorithm [2], which was the first time exponential acceleration of a classical algorithm was achieved. The Shor algorithm proposed by Shor [3] in 1994 could solve the core large prime factorization problem in an RSA cryptosystem with polynomial time complexity and had better performance at an exponential level compared with classical algorithms. In 1996, Grover proposed the Grover quantum search algorithm, which could search for targets in an unsorted database with a time complexity of $O\left(\sqrt{N}\right)$ [4,5,6,7].

In recent years, more scholars have devoted themselves to quantum algorithm research with the development of scientific theories on quantum computing. They have obtained many valuable findings, such as the problem of solving polynomial systems with noise, integer factorization problems, and knapsack problems. The Grover algorithm can further generalize the problem of solving Boolean equations and expand it to the search problem of finding a target in the solution space of equations. Younes et al. [8] proposed a hybrid quantum search engine. When the number of solutions in the search space exceeded N/3, the algorithm’s time complexity was O(1). Zhou et al. [9] optimized the Grover algorithm by changing the phase rotation angle. When the number of solutions in the search space exceeded N/4, the target solution could be found with a success probability of no less than 98.01% in only one search in the search space. When the number of solutions in the search space equaled N/2, the probability of being found was 1. Zhu et al. [10] developed a robust quantum search algorithm based on the Grover–Long algorithm, with the same time complexity as the Grover algorithm and a high tolerance for M/N uncertainty. In [11], by adaptively changing the search space of different target component proportions, the Grover algorithm achieved overall improvement in the probability of success. Liu et al. [12] proposed a new method of integer factorization based on the Grover search algorithm. Zhang et al. [13] solved the problem of route planning for two manipulators based on the Grover algorithm. Xie et al. [14] proposed an improved quantum search algorithm and applied it to solve the kernel properties of rough sets, which improved the probability of the target component as a whole. Hou et al. [15] proposed an algorithm that leveraged the quadratic speed-up offered by the Grover search to achieve a quantum algorithm for the knapsack problem that showed improvement from classical algorithms. Ju et al. [16] showed how quantum Boolean circuits could be used to implement the oracle and the inversion-about-average function in Grover’s search algorithm and proposed a template of quantum circuits that was capable of searching for the solution of a certain class of one-way functions. Harrow et al. [17] proved that any classical algorithm for solving linear systems of equations generically required exponentially more time than our quantum algorithm. At present, the main problems faced by using the Grover algorithm to solve Boolean equations are still the depth of the quantum circuit and the probability of quantum states.

IBM Qiskit [18,19,20,21,22] is an open-source quantum-computing framework that provides basic qubits, quantum logic gates, and quantum simulators on which quantum circuits and various quantum algorithms can be simulated. In this paper, we use the IBM Qiskit framework to simulate the quantum circuit of a Grover algorithm, solve Boolean equations of different variables, and prove the feasibility of the Grover algorithm in solving the equations. The experimental results show that the solutions of the equations can be found with a high probability when the number of variables is smaller than 21.

Section 2 presents the main steps of the Grover algorithm and the characteristics of nonlinear Boolean equations in a binary field. Section 3 introduces the principle of converting Boolean equations into the quantum circuit and uses the Grover algorithm to solve Boolean equations on this premise. Section 4 optimizes the quantum circuit for solving Boolean equations from three aspects: classical algorithm preprocessing, ancilla bit multiplexing, and the uses of a phase quantum gate. Section 5 introduces the experimental results of solving Boolean equations with different variables, as well as the relationship between the number of variables, the depth of the circuit, and the number of qubits, and analyzes the experimental results. Section 6 concludes this paper and gives an outlook on future work.

2. Grover Algorithm

2.1. The Main Steps of the Grover Algorithm

In 1996, Grover [23] proposed an unstructured quantum search algorithm, a typical quantum-computing algorithm. Its time complexity for searching an unordered database is $O\left(\sqrt{N}\right)$, which is a polynomial speed-up compared to the time complexity of $O(N)$ for the classical search algorithm. The Grover algorithm does not consider the properties of a problem’s internal structure when searching for a solution but only focuses on the characteristics of the search items. Therefore, the algorithm has strong versatility and has a secondary speed-up effect on many classic search problems [3]. The principle of the Grover algorithm is mainly to exploit the powerful parallel ability of quantum to continuously iterate the quantum state, change the probability range to maximize that of the target state, and finally, to obtain it through one measurement. The algorithm mainly includes three parts: the preparation of quantum superposition, the G operator, and measurement. The G operator includes two parts, namely, the oracle and Grover diffusion. The Grover algorithm’s complete quantum circuit framework is shown in Figure 1.

• Prepare the quantum superposition: The Hadamard Transform is applied to the initial state to obtain a uniform superposition state of equal probability amplitude $\left|\varphi \right.〉$, as shown in Equation (1):

  $$\left|\varphi \right.〉=H^{\otimes n}\left|00\cdots 0\right.〉=\frac{1}{\sqrt{N}}{\displaystyle \sum _{x=0}^{N-1}\left|x\right.〉}$$

  (1)

  where $\left|\varphi \right.〉$ is the uniform superposition of the initial state, $N=2^n$, and $N$ is the problem’s solution space.
• Construct the oracle: The oracle marks the target state and reverses its phase, while the phases of other states remain unchanged, that is, $O\left|x\right.〉\to {\left(-1\right)}^{f\left(x\right)}\left|x\right.〉$. If $\left|x\right.〉$ is the target state, then $f\left(x\right)=1$, and the phase of the state is reversed at this time; otherwise, $f\left(x\right)=0$.
• Grover diffusion: By constructing a unitary matrix $U_{\varphi }$, the superposition state is subjected to the averaged inversions of the probability amplitude. The probability amplitude of the target state is flipped, and the other states remain the same, thereby increasing the state’s amplitude. $U_{\varphi }$ is as in Equation (2):

  $$U_{\varphi }=2\left|\varphi \right.〉\left.〈\varphi \right|-I$$

  (2)
• Repeats of the iterations: Repeat steps 2 and 3. In theory, when the number of iterations reaches $⌈\frac{\pi }{4}\sqrt{\frac{N}{M}}⌉$ (N is the number of elements in the search space, and M is the number of targets to be searched), the target state is searched with a probability close to 1 [24].

2.2. Application of the Grover Algorithm in Solving Boolean Equations

The Boolean equations to be solved in this paper had the following characteristics:

• The value range of the variable is the binary field {0, 1}.
• Operations include addition, subtraction, multiplication, and division. This article only focuses on Boolean equations involving addition and multiplication operations, which can represent subtraction and division operations.
• Each term of the equation is a single-variable or two-variable multiplication term.
• The number of variables is the same as the number of equations.

Equation (3) shows three-variable Boolean equations, and its result is in Equation (4):

$$\left\{\begin{array}{l}{x}_1+x_2=0\\ x_1*x_2=1\\ x_1+x_2*x_3=1\end{array}\right.$$

(3)

The result is:

$$\left\{\begin{array}{l}{x}_1=1\\ x_2=1\\ x_3=0\end{array}\right.$$

(4)

We used two-dimensional arrays to store the coefficients of the Boolean equations and one-dimensional arrays to store the values of the Boolean equations. We traversed each equation in the code, added the corresponding quantum logic gate, and drew it to run on the quantum circuit. When the Grover search algorithm was applied to the Boolean equations, first the addition and multiplication operations in the Boolean equations were respectively equivalent to the XOR and AND operations in the Boolean logic relationship, so the equations were converted into a Boolean logic formula [25], and Boolean logic expressions were optimized using classical algorithms to simplify the Boolean equations. Second, we built a quantum circuit for solving Boolean equations and implemented the preparation of a uniform superposition state in the Grover algorithm, the oracle, and the Grover diffusion on the quantum circuit. The oracle and Grover diffusion operations were collectively called the G operator, and the target’s probability was increased by repeatedly iterating the G operator. Finally, the quantum circuit was measured, and the correct result was obtained. The method proposed in this paper solved twenty-one-variable Boolean equations using the Grover algorithm. When the number of iterations of the quantum circuit reached three, the correct answer could be measured, and the probability of finding the answer was the greatest at this time.

3. Simulation of the Grover Algorithm Based on the Qiskit Framework

Qiskit is an open-source quantum-computing framework developed by IBM with essential quantum bits providing various quantum simulators, quantum algorithms, and quantum gates, such as the H gate, Pauli-X gate, CZ gate, CNOT gate, Toffoli gate, and Phase gate, as shown in Figure 2. Qiskit also provides a Python API that can program and simulate quantum algorithms on classical computers.

In this paper, we used Qiskit to simulate the Grover algorithm on the Jupyter Notebook, tried to discover the implementation of the algorithm on Boolean equations, and built a quantum circuit for the Grover algorithm to solve the equations. As shown in Figure 3, when building a quantum circuit, according to the characteristics of Boolean equations, the addition operations of the Boolean equations are equivalent to the XOR operation in the Boolean logic relationship, which can be simulated with two CX quantum gates on the quantum circuit.

As shown in Figure 4, the multiplication operations of the Boolean equations are equivalent to the AND operation in the Boolean logic relationship, which can be simulated with a CCX quantum gate on the quantum circuit.

In this paper, the combination of two CX quantum gates was called the XOR element, and one CCX quantum gate was called the AND element. The oracle part of Boolean equations could be composed of both XOR and AND elements. This way of expressing Boolean equations on quantum circuits provided feasibility for solving the equations. Figure 5 is a quantum circuit diagram of Equation (3).

The quantum circuit first used the XOR and AND elements to construct the oracle in the quantum circuit (the area before the first dashed line in Figure 5) and introduced four ancilla bits to form the quantum circuit of the Boolean equations. Then, the phase of the quantum state was flipped by constructing the $U_{\varphi }$ operator (the region between the first and fourth dashed lines in Figure 5), increasing the probability of the target state. Finally, the quantum state was measured using a measurement gate to obtain the target state. The quantum circuit could search for the correct answer with a probability close to 1 after one iteration of the quantum circuit.

4. Quantum Circuit Optimization

This paper focused on optimizing quantum circuits for solving Boolean equations to increase the solving scale. The main factors affecting the solving scale were the depth of the quantum circuit and the number of qubits. Reducing the depth of quantum circuits could be achieved with classical algorithm preprocessing. The quantum circuit for solving Boolean equations contained two kinds of qubits: the variable bits representing the variables of the equation and the ancilla bits representing the equation. With the increase in the solving scale of Boolean equations, ancilla bits accounted for more than 50% of all qubits, which significantly impacted the program’s execution. When building a quantum circuit, the variable bits could not be reduced, and the ancilla bits could be reduced by multiplexing the bits and using the phase quantum gate to replace the CX/CCX/MCX quantum gate.

The quantum circuit optimization for solving Boolean equations included three steps: classical algorithm preprocessing, multiplexing the ancilla bits, and replacing CX/CCX/MCX quantum gates with phase quantum gates. The framework of the quantum circuit optimization process is shown in Figure 6.

4.1. Preprocessing of Classical Algorithms

When the number of Boolean equation variables is too large, there are many identical terms in different equations in the equation system. According to the operation rules of Boolean equations, these identical terms can be eliminated from each other, thereby reducing the degree of complexity of Boolean equations. Equation (5) is a five-variable Boolean equation:

$$\left\{\begin{array}{l}{x}_1+x_2=1\\ x_2+x_1*x_4=0\\ x_3+x_4+x_5=0\\ x_1+x_3+x_4=1\\ x_1*x_2+x_3+x_4=0\end{array}\right.$$

(5)

From Boolean Equation (5), it can be seen that Equation (3) ($x_3+x_4+x_5=0$) and Equation (4) ($x_1+x_3+x_4=1$) have the same terms, and the addition of these two equations can eliminate the terms to obtain a new equation ($x_1+x_5=1$). The degree of complexity of the new equation is less than those of Equations (3) and (4), so replacing Equation (3) or (4) with the new equation can simplify the Boolean equations without changing the solutions of the equations. This leads to the following general formula:

$$x_a+x_b+x_c+\cdots +x_q=1$$

(6)

$$x_a+x_c+x_d+\cdots +x_p=0$$

(7)

Adding Equation (6) to Equation (7) results in Equation (8):

$$x_b+x_d+\cdots +x_p+x_q=1$$

(8)

Among them, a,b,c,..., z are discrete, increasing, random integers. If the number of terms of Equation (7) is less than the numbers of terms for Equations (5)–(7) can be added to the original Boolean equations to replace Equation (5) or (6) to optimize the degree of complexity of the Boolean equations.

4.2. Multiplexing Ancilla Bits

When the solving scale of Boolean equations reaches 14 variables, the total number of quantum qubits required is 29, of which the number of ancilla bits is 15, accounting for half of all the qubits. In building the quantum circuit for Boolean equation solving, an ancilla bit represents the state of an equation. The Boolean equations are grouped in an arithmetic-sequence-like method, and one ancilla bit can represent the states of multiple equations, which further reduces the number of ancilla bits and increases the solving scale. Formula (9) is used to find the minimum integer value of t:

$$s\le \frac{t\cdot \left(t+1\right)}{2}$$

(9)

In (9), s is the number of equations, and t is the number of equations in the first group. On this basis, Algorithm 1 is used to find the grouping of Boolean equations.

Algorithm 1. Find the grouping of Boolean equations.

Require: g[100], T, i Ensure: g[100] = {0}, T = 0, I = 0 1: while T ≤ s do 2:   g[i] = t 3:   T = T + t 4:   i = i + 1 5:   t = t − 1 6: end while 7: if T ≡ s then 8:   return g[] 9: else T > s then 10:   g[i] = (s + T)/2 11:   return g[100] 12: end if

The value stored in g[100] is the number of equations in each group.

4.3. Using Phase Quantum Gates

According to the characteristics of the oracle in the Grover algorithm, the oracle marks the target state by inverting the phase of the quantum state [6]. In the traditional Grover algorithm, the oracle is usually constructed using CX/CCX/MCX quantum gates, resulting in the need to use an additional ancilla bit. In theory, building an oracle with phase quantum gates can reduce one ancilla bit, as well as the depth of the quantum circuits, compared to CX/CCX/MCX gates, thereby increasing the rate and scale of solving Boolean equations. The replacement of CX/CCX/MCX quantum gates with phase quantum gates is shown in Figure 7. We designed several sets of experiments to compare them and found that using phase quantum gates instead of CX/CCX/MCX gates could effectively improve the speed and scale of solving Boolean equations.

Through these methods, we successfully optimized the quantum circuit. The solution scale and speed of solving Boolean equations were improved. However, these optimization methods were limited to Boolean equations in a binary field. The multiplexing ancilla bit method dramatically reduced the number of qubits but deepened the depth of quantum circuits. Using the phase quantum gate method increased the solution scale to twenty-one variables, but it could not be solved stably for Boolean equations with too much complexity.

5. Experimental Results

In this paper, six experiments were carried out: classical algorithm preprocessing, multiplexing the ancilla bits, using phase quantum gates, etc. The experimental results showed that the maximum solving scale of the Boolean equations based on the Grover search algorithm could reach twenty-one variables.

The experiments were carried out with the Sugon cloud- computing cluster, and the experimental environment is shown in

Table 1. Computing environment.

Device	Setup
OS	X86_64 GNU/Linux
CPU	32-core x86 processor with 2.5 GHz frequency
Network	HDR Infiniband
RAM	128 G
Virtual environment	128 G
Quantum computing framework	Anaconda3-5.2.0
Quantum simulator	qasm_simulator
Programming language	Python 3.6.5

. The dataset in the experiment was in two-dimensional array format, which contained the coefficients and values of the equations, from one variable to twenty-one variables. The code randomly generated the data and optimized to remove unqualified ones.

The first three experiments were classical algorithm preprocessing, multiplexing the ancilla bits, and using phase quantum gates. Figure 8 shows the changes in the number of Boolean equations before and after preprocessing with a classical algorithm (starting with 10 variables). The horizontal axis represented the number of variables in the Boolean equations, and the vertical axis represented the number of terms. As seen from the figure, the classical algorithm preprocessing eliminated the same terms in the equation, which could significantly reduce the degree of complexity of the Boolean equations in a relatively short time, which was helpful for the following solving operations of larger-scale Boolean equations.

Figure 9 shows the difference in the number of qubits before and after multiplexing the ancilla bits, where the horizontal axis represented the number of variables of the Boolean equations, and the vertical axis represented the number of qubits used by the quantum circuit. As seen from the figure, after the Boolean equations were grouped with the arithmetic sequence-like method, when the scale of the equation was small, the effect of multiplexing the ancilla bits was not obvious. However, with the increase in the solving scale of the equations, the number of quantum bits was significantly reduced, and the solving scale reached 19 variables.

Through the analysis of the oracle structure and experimental results, replacing the CX/CCX/MCX quantum gate with the phase quantum gate could achieve the same effect of marking the target state and reducing the number and depth of quantum circuits. As shown in Figure 10, the targets of the quantum circuit in Figure 7 were correctly marked. We compared the experimental results and found that, for a Boolean equation system with nineteen variables, the solution rate using the phase quantum gate was increased, and the solution scale was increased to twenty-one variables.

Next were three Boolean-equation-solving experiments. The first experiment was compared with the second to analyze the results and their probabilities for the two-variable and twenty-one-variable Boolean equations. The second one used two twenty-one-variable Boolean equations for comparison and analyzed the quantum circuit and the change in probability amplitude by iterating for different times. The third set of experiments analyzed the relationship between qubits and quantum circuits using multiple Boolean equations of varying scales.

Figure 11 shows the results of the Grover algorithm for solving two-variable Boolean equations. In this experiment, the answer was searched in a solution space of 2², the average quantum circuit depth was 34, and the shots were 1024. The correct answer could be found through only one G iteration, and the highest probability was obtained in all the cases.

Figure 12 and Figure 13 show the results of the Grover algorithm for solving Boolean equations with twenty-one variables in a solution space of 2²¹ with one and three iterations, respectively. The shots were one million, and the respective average quantum circuit depths were 67,897 and 229,503 (because there was too much data in the solution space, only part of the data was selected for display). It can be seen from the experimental results that the algorithm did not obtain the correct answer when iterated one time and obtained the answer with a higher probability—100101011100000001111—when iterating three times. Through the relationship between the probability amplitude, the number of iterations, and the depth of the quantum circuit, we know that, when the number of iterations increased, the probability of the Grover algorithm successfully finding the target increased. However, the quantum circuit was also deeper, which affected the solving scale and time. In this experiment, the algorithm performed three G iterations to search for the correct answer in the vast solution space with a high probability, and when iterated $⌈\frac{\pi }{4}\sqrt{\frac{N}{M}}⌉$ times, the algorithm searched for the answer with a probability close to 1.

To fully understand the relationship between the number of qubits and quantum circuits, Qiskit was used to solve Boolean equations on different scales many times, and the experimental results were recorded.

Table 2. Number of qubits and circuit depth required for Boolean equations of different scales.

The Scale of Boolean Equations	The Number of Qubits	The Average Depth of the Quantum Circuit
10	16	20,727
11	18	25,613
12	19	36,206
13	20	54,044
14	21	62,507
15	22	80,926
16	24	95,188
17	25	114,292
18	26	141,799
19	27	163,339
20	28	173,713
21	29	223,899

lists the number of qubits and the average quantum circuit depth (three iterations) used for Boolean equations on different scales (starting with ten variables).

It can be seen from Table 2 that, when the scale of the Boolean equations increased, the depth of the quantum circuit became increasingly deeper with the increase in the number of qubits and the number of iterations. When the solving scale reached 22 variables, because the quantum circuit was too deep and the number of qubits was too large, the simulator in Qiskit could not continue to run. Through these three experiments, the situation of the Grover search algorithm for solving large-scale Boolean equations was fully demonstrated.

6. Conclusions

Quantum computing is a rapidly emerging technology that follows the laws of quantum mechanics and uses qubits for computing. Compared with classical computers, quantum computers have obvious advantages in many aspects, such as accuracy and efficiency. Quantum algorithms can perform any computation exponentially more efficiently on quantum computers than on conventional computers.

In this paper, we used the quantum simulator provided by the Qiskit framework to run the Grover algorithm to solve nonlinear Boolean equations in a binary field and prove the feasibility of the Grover algorithm on this problem. By analyzing the structure of Boolean equations and quantum circuits, the quantum circuits were optimized, increasing the solving scale to twenty-one variables. When building a quantum circuit, using classical algorithm preprocessing, multiplexing the ancilla bits, and phase quantum gates to optimize the quantum circuit while increasing the solving scale of Boolean equations, the depth of the quantum circuit was significantly deepened. The experiments showed that the depth of the quantum circuit had a significant influence on the solution of Boolean equations. In theory, if the depth of the quantum circuit could be reduced, the solving scale could continue to grow. When using the Grover algorithm to solve Boolean equations, the main factor affecting the solving scale was the oracle, making the quantum circuit depth rise when distinguishing the target. It was affected by noise when searching for a target, which seriously reduced the probability amplitude of the target.

Our current work mainly was to verify the feasibility of the Grover algorithm in solving Boolean equations and to conduct preliminary experiments to explore the full scale of solving Boolean equations. In future work, we plan to study two aspects: (1) simplifying the terms of Boolean equations using data structures that store the equations efficiently and (2) continuing to optimize the quantum circuit and reduce the impact of noise on the target through oracle optimization.