BHT-QAOA: The Generalization of Quantum Approximate Optimization Algorithm to Solve Arbitrary Boolean Problems as Hamiltonians

Abstract

A new methodology is introduced to solve classical Boolean problems as Hamiltonians, using the quantum approximate optimization algorithm (QAOA). This methodology is termed the “Boolean-Hamiltonians Transform for QAOA” (BHT-QAOA). Because a great deal of research and studies are mainly focused on solving combinatorial optimization problems using QAOA, the BHT-QAOA adds an additional capability to QAOA to find all optimized approximated solutions for Boolean problems, by transforming such problems from Boolean oracles (in different structures) into Phase oracles, and then into the Hamiltonians of QAOA. From such a transformation, we noticed that the total utilized numbers of qubits and quantum gates are dramatically minimized for the generated Hamiltonians of QAOA. In this article, arbitrary Boolean problems are examined by successfully solving them with our BHT-QAOA, using different structures based on various logic synthesis methods, an IBM quantum computer, and a classical optimization minimizer. Accordingly, the BHT-QAOA will provide broad opportunities to solve many classical Boolean-based problems as Hamiltonians, for the practical engineering applications of several algorithms, digital synthesizers, robotics, and machine learning, just to name a few, in the hybrid classical-quantum domain.

1. Introduction

The quantum approximate optimization algorithm (QAOA) was introduced by Farhi et al. [1,2] to mainly solve combinatorial optimization problems, such as the MaxCut [3,4], in the quantum domain. The MaxCut problem is a subset of the classical graph theoretical problems, which is represented by a number of nodes (n) connected through a set of edges {j, k}, where j and k are the indices of two connected nodes. The solutions for a MaxCut problem can be determined by finding the maximum number of cuts (in edges) for the connected nodes. In the quantum domain, the QAOA represents the MaxCut problem in the form of an ansatz Hamiltonian oracle, which is termed the “Hamiltonian clauses (H_C)”, and ansatz Hamiltonian operator, which is termed the “Hamiltonian mixer (H_M)”.

The wording “ansatz” means that H_C and H_M consist of parameterized rotational quantum gates of Pauli-Z (RZ) and Pauli-X (RX), respectively [1,2], such that H_C consists of a number of RZ(v·ɣ), RZZ(v·ɣ), RZZZ(v·ɣ), and so on, while H_M consists of n numbers of RX(ω·β), where v and ω are the coefficients (as the time evolutions for both H_C and H_M), ɣ and β are the parameterized angular rotations, and n is the number of input qubits. Note that ɣ and β are rotated between the angles of [0, 2π] and [0, π], respectively [1,2].

In general, the following steps illustrate the complete construction of QAOA, to find all approximated solutions for a classical MaxCut problem:

• All n nodes of the MaxCut problem are represented into their equivalent n input qubits, which are initially set to the |0⟩ state.
• Hadamard (H) gates are applied to all n input qubits, to create the complete quantum search space of {0,1}^⊗n for QAOA to find all solutions.
• Hamiltonian H_C represents the quantum circuit of a MaxCut problem as the unitary operator $\left({\mathrm{e}}^{- \mathrm{i}\gamma H_C}\right)$, which is a set of non-connected nodes as RZj(v·ɣ) and connected nodes as RZjZk(v·ɣ), where j and k are the indices of input qubits.
• Hamiltonian H_M represents the quantum circuit for the sum of all n input qubits as the unitary operator $\left({\mathrm{e}}^{- \mathrm{i}\beta H_M}\right)$, which is a set of n RX(ω·β). Note that H_M acts as the quantum diffusion operator of QAOA analogous to the diffusion operator in Grover’s algorithm [5,6,7,8], and H_M may include other variants and types of gates, not just RX gates, depending on the model of QAOA used (see the Related Work section).
• To improve the quality of all approximated solutions, H_C and H_M are iterated for a number of repetitions (p), where p ≥ 1, such that every ${\mathrm{e}}^{-\mathrm{i}{\gamma }_p{H}_C}$ consists of RZ(v·ɣ_p), RZZ(v·ɣ_p), etc., and every ${\mathrm{e}}^{- \mathrm{i}{\beta }_p{H}_M}$ consists of RX(ω·β_p).
• The numerical values of coefficients (v and ω) are calculated during the construction of H_C and H_M in the classical domain.
• The numerical values of angles (ɣ and β) are initially randomized as [ɣ₁…ɣ_p, β₁…β_p] for H_C and H_M, respectively, in the classical domain. Note that some studies initialized such angles to defined values using machine learning and tensor techniques [9,10,11,12,13].
• The quantum circuit of QAOA (H {H_C H_M}^p) is executed with a quantum processing unit (QPU) and then measured (in the classical domain) for approximated solutions depending on the chosen values of ɣ and β.
• The measured solutions (as the energy cost of QAOA [1,2]), the chosen values of ɣ and β (as the optimization parameters of QAOA), and the Hamiltonians (H_C and H_M as an objective function) are fed to a classical optimization minimizer [14,15,16]. This minimizer re-calculates the numerical values of these optimization parameters based on the energy cost from the objective function and updates the H_C and H_M of QAOA with a new set of optimized numerical values of ɣ and β, respectively.
• For a number of objective function evaluations (nfev), Steps 8 and 9 are concurrently repeated between a QPU and a minimizer, until finding all optimized approximated solutions for a MaxCut problem or stopping based on a pre-defined “halt condition”.

The aforementioned ten steps show why QAOA is considered a variational quantum algorithm solving combinatorial optimization problems in the hybrid classical-quantum domain [17,18,19]. The wording “variational” is equivalent to the meaning of “ansatz”.

The goal of this article is to introduce a new methodology to solve classical Boolean problems as Hamiltonians (H_C and H_M) using QAOA. For that, our methodology is termed the “Boolean-Hamiltonians Transform for QAOA” (BHT-QAOA), which can be summarized as follows. Firstly, an arbitrary classical Boolean problem is constructed as a quantum Boolean oracle [8,20]. This constructed oracle can be expressed in arbitrary structures, such as the Product-Of-Sums (POS) [21,22], Sum-Of-Products (SOP) [21,23], Exclusive-or Sum-Of-Products (ESOP) [24,25], XOR-Satisfiability (CNF-XOR SAT and DNF-XOR SAT) [26,27], and Algebraic Normal Form (ANF) (or Reed–Muller expansion) [28,29], just to name a few. Secondly, this constructed oracle (in any structure) is converted into its equivalent quantum Boolean oracle in ESOP structure, unless it was initially constructed in ESOP structure. Thirdly, the quantum Boolean oracle in ESOP structure is transformed into its equivalent quantum Phase oracle [8,20]. Fourthly, the Hamiltonians (H_C and H_M) of QAOA are generated from this transformed quantum Phase oracle, based on our modified composition rules originally presented by Hadfield [30]. Finally, all the above-mentioned ten steps of QAOA are performed in sequence using the generated H_C and H_M.

Please observe that a quantum Boolean oracle is easier and more straightforward in expressing an arbitrary classical Boolean problem than a quantum Phase oracle, because (i) the quantum Boolean-based gates can be directly realized using the truth tables (and De Morgan’s Laws [21]) of their equivalent classical Boolean gates, and (ii) the quantum Boolean-based gates and their qubits can be easily analyzed using classical Boolean logic, such as a Boolean logic of ‘0’ represents a quantum state of |0⟩ and a Boolean logic of ‘1’ represents a quantum state of |1⟩. For ease of description, the quantum Boolean oracle and the quantum Phase oracle will be simply denoted as the “Boolean oracle” and the “Phase oracle”, respectively.

In BHT-QAOA, converting a Boolean oracle (in any structure) into a Phase oracle will (i) remove all ancilla qubits (including the output qubit), i.e., the total number of utilized qubits will be dramatically reduced to the number of input qubits only, and (ii) omit the mirror (as the uncomputing part) of an oracle, i.e., the total number of quantum gates are significantly minimized for the quantum circuit of a Phase oracle, depending on the initial construction of a Boolean oracle that expresses a classical Boolean problem.

In this article, arbitrary classical Boolean problems (as applications) are expressed as Boolean oracles in various structures, and these Boolean oracles are then solved using BHT-QAOA for p repetitions, with an IBM QPU and SciPy optimization minimizer [31]. These applications are (i) an arbitrary Boolean problem in POS structure, (ii) an arbitrary Boolean problem in SOP structure, (iii) an arbitrary Boolean problem in ESOP structure, (iv) a 2 × 2 Sudoku game, and (v) a 4-bit conditioned half-adder digital circuit. Eventually, our proposed BHT-QAOA successfully finds all optimized approximated solutions for these applications, as a proof of concept for utilizing BHT-QAOA to solve arbitrary and practical classical Boolean problems in the hybrid classical-quantum domain.

2. Related Work

Various research works and different implementations have been proposed to focus on enhancing the optimization workflow of the following essential topics of QAOA:

• Solving combinatorial optimization problems, such as graphs, k-SAT, and MaxCut problems [3,4,32,33], where k ≥ 3 literals (inputs).
• Finding the optimized numerical values of the angles (ɣ and β) for the Hamiltonians (H_C and H_M), respectively, with fewer function evaluations (nfev) and repetitions (p) [34,35,36,37,38], or initially using machine learning techniques [9,10,11,12,13].
• Developing variants of H_M for a better QAOA in finding all optimized approximated solutions for combinatorial optimization problems [11,39,40,41,42,43,44,45].

On the other hand, Hadfield [30] proposed a set of composition rules for constructing the Hamiltonians (H_f), to represent a wide variety of Boolean operators and functions. These Hamiltonians (H_f) are then combined to generate simpler clauses (building blocks) of the final Hamiltonians for the applications of quantum annealing [46,47] and QAOA.

In BHT-QAOA, based on our modified sets of Hadfield’s composition rules, the Hamiltonians (H_C and H_M) of QAOA are simply generated from a Phase oracle, which is transformed from a Boolean oracle (in any structure) representing a Boolean problem.

3. Materials and Methods

The essential methodology of BHT-QAOA can be discussed and evaluated using the following illustrative example. Assume an arbitrary classical Boolean problem is given, as stated in Equation (1) below, and then expressed as a Boolean oracle in POS structure, as shown in Figure 1. The following subsections discuss how to (i) convert this Boolean oracle in POS structure into the Boolean oracle in ESOP structure, (ii) transform the Boolean oracle in ESOP structure into the Phase oracle, (iii) generate the Hamiltonians (H_C and H_M) based on the transformed Phase oracle, and (iv) construct the overall architecture of BHT-QAOA for H_C and H_M in p repetitions, where p ≥ 1. Note that, for other classical Boolean problems, differently expressed Boolean oracles (in any structure) can simply follow the same steps of conversion, transformation, and generation stated in these subsections, and the fqubit (functional qubit) is the output ancilla qubit of a Boolean oracle (in any structure).

(a ∨ b ∨ ¬ c) ∧ (¬ a ∨ c) ∧ (¬ b ∨ c)

(1)

3.1. Converting Boolean Oracles from Any Structure to ESOP Structure

There are many synthesis methods to convert a Boolean oracle (in any structure) to its equivalent Boolean oracle in ESOP structure. These synthesis methods include ESOP synthesis [24], Karnaugh map synthesis [21], and binary decision diagram (BDD) synthesis [48,49], just to name a few. For instance, the Karnaugh map synthesis for a Boolean oracle (from any structure to ESOP structure) can be summarized in the following steps.

• Sketch an empty Karnaugh map with literals (a, b, c, …) and their binary Gray codes.
• Evaluate a Boolean oracle (in any structure) for solutions (as the true minterms of ‘1’) and non-solutions (as the false minterms of ‘0’).
• Group all solutions together from step 2, using 1-cell groups, 2-cell groups, etc.
• Formulate each group from step 3, to generate products (∧) of literals.
• XOR (⊕) all formulated groups together from step 4, to generate an ESOP structure.

From Equation (1) above, since the Boolean oracle in POS structure is simple, the Karnaugh map synthesis is utilized to convert it to the Boolean oracle in ESOP structure, as stated in Equation (2) below and illustrated in Figure 2a,b, and the final quantum circuit of this Boolean oracle in ESOP structure is shown in Figure 2c. Note that in Figure 2c, (i) there is no need to optimize this Boolean oracle by removing the identical neighboring X gates, since all these gates are required for generating Hamiltonians (H_C and H_M) and calculating their coefficients (v and ω), respectively, and (ii) all mirrored gates and ancillae (except for fqubit) are removed when a Boolean oracle is in ESOP structure.

(¬ a ∧ ¬ b ∧ ¬ c) ⊕ (a ∧ ¬ b ∧ c) ⊕ (b ∧ c)

(2)

Please observe that the aforementioned steps of Karnaugh map synthesis may not generate the minimized ESOP structure, as shown in Figure 2b, since these steps usually create the DSOP (Disjoint Sum-Of-Products) structure, as shown in Figure 2c, which is an expensive structure as compared to the minimized ESOP structure depending on the numbers of n-bit Toffoli gates, where n ≥ 3 qubits. However, we just want to illustrate how to convert a Boolean oracle (in any structure) to its equivalent Boolean oracle in ESOP (or DSOP) structure.

3.2. Transforming Boolean Oracles in ESOP Structure to Phase Oracles

In this article, we utilize the technique originally discussed by Figgatt et al. [20] for transforming 4-bit Toffoli gates to 3-bit controlled-Z (CCZ) gates, for Grover’s algorithm of single-solution [5,6,7,8]. We efficiently generalize their technique to involve the Feynman (CX) and n-bit Toffoli gates, where n ≥ 3 qubits, for transforming Boolean oracles in ESOP structure to their equivalent Phase oracles, as presented in the following three rules and shown in Figure 3. For that, we termed these rules the “generalized transformation rules”.

Rule 1: A Feynman (CX) gate is transformed into a Pauli-Z (Z) gate when Equation (3) stated below is a solution-satisfiable as demonstrated in Figure 3a, where j is the index of an input qubit (q). The left side of Equation (3) is the Boolean-based output of a CX gate, and its right side is the phase-inverted output of a Z gate.

$${\mathrm{q}}_{\mathrm{j}}\oplus \mathit{fqubit} =-{\left(- 1\right)}^{{\mathrm{q}}_{\mathrm{j}}}$$

(3)

Rule 2: A Toffoli gate is transformed into a controlled-Z (CZ) gate when Equation (4) stated below is a solution-satisfiable as shown in Figure 3b, where j and k are the indices of input qubits (q). The left side of Equation (4) is the Boolean-based output of a Toffoli gate, and its right side is the phase-inverted output of a CZ gate.

$$\left({\mathrm{q}}_{\mathrm{j}}\wedge {\mathrm{q}}_{\mathrm{k}}\right)\oplus \mathit{fqubit}=-{\left(- 1\right)}^{{\mathrm{q}}_{\mathrm{j}} · {\mathrm{q}}_{\mathrm{k}}}$$

(4)

Rule 3: An n-bit Toffoli gate is transformed into an (n−1)-bit multi-controlled Z (MCZ) gate when Equation (5) stated below is a solution-satisfiable as shown in Figure 3c, where j is the index of an input qubit (q) and n ≥ 3 qubits (q + fqubit). The left side of Equation (5) is the Boolean-based output of an n-bit Toffoli gate, and its right side is the phase-inverted output of an (n−1)-bit MCZ gate.

$$\left({\bigwedge }_{\mathrm{j}=1}^{n–1}{\mathrm{q}}_{\mathrm{j}}\right)\oplus \mathit{fqubit}=-{\left(- 1\right)}^{{\prod }_{\mathrm{j}=1}^{n–1}{\mathrm{q}}_{\mathrm{j}}}$$

(5)

After applying our generalized transformation rules on the Boolean oracle in ESOP (or DSOP) structure, as stated in Equation (2) above and shown in Figure 2c, the resultant quantum circuit of the Phase oracle is then simply constructed, as illustrated in Figure 4.

Table 1. Comparison of the number of qubits and quantum gates for the Boolean and Phase oracles for the Boolean problem of Equation (1) stated above, after applying the generalized transformation rules.

Oracular Problems	Number of Qubits			Number of Multi-Controlled Gates			Quantum Circuit Required a Mirror?
	Inputs	Ancillae (with fqubit)	Total	Feynman (CX)	3-bit Toffoli	4-bit Toffoli
Boolean oracle in POS structure	3	4	7	0	4	3	Yes
Boolean oracle in ESOP structure	3	1	4	0	1	2	No
Phase oracle	3	0	3	1 (as a CZ)	2 (as a CCZ)	0	No

summarizes the advantages of converting the Boolean oracle in POS structure to the Boolean oracle in ESOP structure, and transforming the Boolean oracle in ESOP structure to the Phase oracle, in the context of (i) the utmost removal of all ancilla qubits (including the fqubit), i.e., the width of the final quantum circuit is reduced, and (ii) the dramatic minimization of multi-controlled quantum gates (after transforming the POS structure into the ESOP structure and then applying the three aforementioned generalized transformation rules), i.e., the depth of the quantum circuit is shrunk.

3.3. Generating Hamiltonians (H_C and H_M) from Phase Oracles

Hadfield discussed, in [30], the composition rules for generating H_C from a set of Hamiltonians (H_f), which represent a variety of Boolean functions as simpler clauses, as stated in

Table 2. Some of Hadfield’s Boolean-based composition rules (H_f) [30], where j and k are the indices of input qubits (q), Z_j is the RZ gate applied on q_j, and fqubit initially sets to the |0⟩ state.

Gate	Type	f(x)	Hf
Feynman (CX)	Boolean	qj ⊕ fqubit = qj	${\displaystyle \frac{1}{ 2 }} \mathrm{I} -{\displaystyle \frac{1}{ 2 }}{\mathrm{Z}}_{\mathrm{j}}$
Toffoli	Boolean	qj ∧ qk	${\displaystyle \frac{1}{ 4 }} \mathrm{I} -{\displaystyle \frac{1}{ 4 }}\left({\mathrm{Z}}_{\mathrm{j}}+{\mathrm{Z}}_{\mathrm{k}}-{\mathrm{Z}}_{\mathrm{j}}{\mathrm{Z}}_{\mathrm{k}}\right)$
n-bit Toffoli	Boolean	${\bigwedge }_{ \mathrm{j}=1}^{n-1}{\mathrm{q}}_{\mathrm{j}}$	${\displaystyle \frac{1}{{ 2}^{n–1}}}{\prod }_{ \mathrm{j}=1}^{n–1}\left( \mathrm{I} -{\mathrm{Z}}_{\mathrm{j}}\right)$

. In this article, to generate H_C and H_M from Phase oracles, we generalize some of Hadfield’s Boolean-based composition rules (H_f) to Phase-based composition rules, which we termed the “generalized composition rules (H_g)”. Based on our proposed three generalized transformation rules stated above, four generalized composition rules (H_g) are derived from H_f, as expressed in

Table 3. Our proposed generalized composition rules (H_g) for Phase oracles, where j and k are the indices of input qubits (q), Z_j is the RZ gate applied on q_j, Q = {q_j, q_k…q_jq_k…}, and Z_Q = {Z_j, Z_k…Z_jZ_k…}.

Rules	Gate	Type	g(x)	Hg
Rule 1	Pauli-Z (Z)	Phase	${\left(-1\right)}^{{\mathrm{q}}_{\mathrm{j}}}$	$-{\displaystyle \frac{1}{ 2 }} \mathrm{I}+{\displaystyle \frac{1}{ 2 }}{\mathrm{Z}}_{\mathrm{j}}$
Rule 2	CZ	Phase	${\left(-1\right)}^{{\mathrm{q}}_{\mathrm{j}}·{\mathrm{q}}_{\mathrm{k}}}$	$-{\displaystyle \frac{1}{ 4 }} \mathrm{I}+{\displaystyle \frac{1}{ 4 }}\left({\mathrm{Z}}_{\mathrm{j}}+{\mathrm{Z}}_{\mathrm{k}}-{\mathrm{Z}}_{\mathrm{j}}{\mathrm{Z}}_{\mathrm{k}}\right)$
Rule 3	MCZ	Phase	${\left(-1\right)}^{{\prod }_{\mathrm{j}=1}^n{\mathrm{q}}_{\mathrm{j}}}$	${\displaystyle \frac{1}{{ 2}^n}}{\prod }_{ \mathrm{j}=1}^n{\left(- 1\right)}^{ \mathrm{j}+1}\left( \mathrm{I}-{\mathrm{Z}}_{\mathrm{j}}\right)$
Rule 4	Pauli-X (X)	Phase	${\left(-1\right)}^{\forall \mathrm{j} \in \mathrm{Q}}$	Invert signs (±) of all jth qubits in ZQ

, where Rules 1, 2, and 3 of H_g are simply inverting the signs (±) of their corresponding H_f, for both identity (I) and RZ gates.

Rule 1: Performs Rule 1 of the generalized transformation rules, as stated in Equation (3) above and previously shown in Figure 3a.

Rule 2: Performs Rule 2 of the generalized transformation rules, as stated in Equation (4) above and previously shown in Figure 3b.

Rule 3: Performs Rule 3 of the generalized transformation rules, as stated in Equation (5) above and previously shown in Figure 3c.

Rule 4: Inverts all signs (±) of generated RZ gates in H_g (Rules 1, 2, and 3), since the X gates are proposed here to only invert the phases of qubits in an H_g.

Consequently, from Table 3, the four generalized compositions rules (H_g) will be then directly applied to the Phase oracle (shown in Figure 4) to generate H_C and calculate its v coefficient, as demonstrated in Figure 5 and expressed in the following steps (starting from the left side of this figure).

• Construct one H_g for one Z, CZ, or MCZ, using Rule 1, Rule 2, or Rule 3, respectively.
• If there are X gates (with their mirrored gates) surrounding Z, CZ, or MCZ in Step 1, then apply Rule 4 on H_g from Step 1 to construct a new H_g. If not, proceed to Step 3.
• Repeat Steps 1 and 2 for another H_g until there are no remaining Z, CZ, and MCZ.
• Group all constructed H_g into one Hamiltonian, which is H_C.
• Calculate (add or subtract) all the identical terms of H_C to find the v coefficient.

From Table 3 and Figure 5, the Hamiltonians (H_g) are step-by-step calculated, as stated in Equation (6) below. Next, the H_C is simply generated from H_g2 + H_g4 + H_g5, as expressed in Equation (7) below.

$$\begin{array}{ll}{H_g}_1& ={\displaystyle \frac{1}{ 8 }}\left(\left(\mathrm{I}-{\mathrm{Z}}_a\right)\left(-\mathrm{I}+{\mathrm{Z}}_b\right)\left(\mathrm{I}-{\mathrm{Z}}_c\right)\right)={\displaystyle \frac{1}{ 8 }}\left(-\mathrm{I}+{\mathrm{Z}}_a+{\mathrm{Z}}_b+{\mathrm{Z}}_c-{\mathrm{Z}}_a{\mathrm{Z}}_b-{\mathrm{Z}}_a{\mathrm{Z}}_c-{\mathrm{Z}}_b{\mathrm{Z}}_c+{\mathrm{Z}}_a{\mathrm{Z}}_b{\mathrm{Z}}_c\right)\\ {H_g}_2& ={\displaystyle \frac{1}{ 8 }}\left(-\mathrm{I}-{\mathrm{Z}}_a-{\mathrm{Z}}_b-{\mathrm{Z}}_c-{\mathrm{Z}}_a{\mathrm{Z}}_b-{\mathrm{Z}}_a{\mathrm{Z}}_c-{\mathrm{Z}}_b{\mathrm{Z}}_c-{\mathrm{Z}}_a{\mathrm{Z}}_b{\mathrm{Z}}_c\right)\\ {H_g}_3& ={\displaystyle \frac{1}{ 8 }}\left(\left(\mathrm{I}-{\mathrm{Z}}_a\right)\left(-\mathrm{I}+{\mathrm{Z}}_b\right)\left(\mathrm{I}-{\mathrm{Z}}_c\right)\right)={\displaystyle \frac{1}{ 8 }}\left(-\mathrm{I}+{\mathrm{Z}}_a+{\mathrm{Z}}_b+{\mathrm{Z}}_c-{\mathrm{Z}}_a{\mathrm{Z}}_b-{\mathrm{Z}}_a{\mathrm{Z}}_c-{\mathrm{Z}}_b{\mathrm{Z}}_c+{\mathrm{Z}}_a{\mathrm{Z}}_b{\mathrm{Z}}_c\right)\\ {H_g}_4& ={\displaystyle \frac{1}{ 8 }}\left(-\mathrm{I}+{\mathrm{Z}}_a-{\mathrm{Z}}_b+{\mathrm{Z}}_c+{\mathrm{Z}}_a{\mathrm{Z}}_b-{\mathrm{Z}}_a{\mathrm{Z}}_c+{\mathrm{Z}}_b{\mathrm{Z}}_c-{\mathrm{Z}}_a{\mathrm{Z}}_b{\mathrm{Z}}_c\right)\\ {H_g}_5& ={\displaystyle \frac{1}{ 4 }}\left(\left(\mathrm{I}-{\mathrm{Z}}_b\right)\left(-\mathrm{I}+{\mathrm{Z}}_c\right)\right)={\displaystyle \frac{1}{ 4 }}\left(-\mathrm{I}+{\mathrm{Z}}_b+{\mathrm{Z}}_c-{\mathrm{Z}}_b{\mathrm{Z}}_c\right)\end{array}$$

(6)

$$H_C={H_g}_2+{H_g}_4+{H_g}_5=-{\displaystyle \frac{1}{2}}\mathrm{I}+{\displaystyle \frac{1}{4}}{\mathrm{Z}}_c-{\displaystyle \frac{1}{4}}\left({\mathrm{Z}}_a{\mathrm{Z}}_c+{\mathrm{Z}}_b{\mathrm{Z}}_c\right)-{\displaystyle \frac{1}{4}}{ \mathrm{Z}}_a{\mathrm{Z}}_b{\mathrm{Z}}_c$$

(7)

Hence, from Equation (7) above, v = [v₁, v₂, v₃, v₄] = [$-{\displaystyle \frac{1}{ 2 }}$, ${\displaystyle \frac{1}{ 4 }}$, $-{\displaystyle \frac{1}{ 4 }}$, $-{\displaystyle \frac{1}{ 4 }}$], where v₁ is for all non-connected input qubits (as the identity ‘I’), v₂ is for c input qubit only, i.e., RZ_c(0.25·ɣ), v₃ is for only two connected input qubits {a and c; b and c}, i.e., RZ_aZ_c(−0.25·ɣ) and RZ_bZ_c(−0.25·ɣ), and v₄ is for all connected input qubits {a, b, c}, i.e., RZ_aZ_bZ_c(−0.25·ɣ). For a practical quantum implementation of QAOA as well as our introduced BHT-QAOA, H_C in Equation (7) is rewritten as the following format for the sequence of three qubits {c, b, a}, as stated in Equation (8) below, where ‘ZII’ is equivalent to RZ_c, ‘ZIZ’ is equivalent to RZ_aZ_c, ‘ZZZ’ is equivalent to RZ_aZ_bZ_c, and so on.

H_C = ([‘III’, ‘ZII’, ‘ZIZ’, ‘ZZI’, ‘ZZZ’], coeffs = [−0.5, 0.25, −0.25, −0.25, −0.25])

(8)

Because β (as a set of rotational angles of H_M) rotates between [0, π] [1,2], we set its coefficient (ω) to cover the entire range between [0, 2π] for possible phase values of RX gates in H_M, to find all optimized approximated solutions for an arbitrary classical Boolean problem. In other words, ω (as the coefficient of β) is initially set to ‘2.0’ for all n numbers of RX(ω·β) gates in H_M, where n is the total number of input qubits. Similar to the practical implementation of H_C, H_M is rewritten as the following format for the sequence of three qubits {c, b, a}, as stated in Equation (9) below, where ‘XII’ is equivalent to RX_c, ‘IXI’ is equivalent to RX_b, and ‘IIX’ is equivalent to RX_a.

H_M = ([‘XII’, ‘IXI’, ‘IIX’], coeffs = [2.0, 2.0, 2.0])

(9)

From Equations (8) and (9) above, the quantum circuit of BHT-QAOA for the generated Hamiltonians (H_C and H_M) of the Boolean problem (a ∨ b ∨ ¬ c) ∧ (¬ a ∨ c) ∧ (¬ b ∨ c) is eventually constructed for one repetition (p = 1), as illustrated in Figure 6.

3.4. Architecture of BHT-QAOA

After transforming an arbitrary classical Boolean problem to the Hamiltonians (H_C and H_M) and calculating their coefficients (v and ω), respectively, the numerical values of ɣ and β are initially randomized and then plugged into the architecture of BHT-QAOA for first execution, as shown in Figure 7. Subsequently, the SciPy optimization minimizer [31] is utilized to optimize these numerical values (ɣ and β) for better-approximated solutions, in a number of function evaluations (nfev), by employing three cofactors as follows.

• H_C and H_M (in a number of p), as the “objective function” needs to be minimized.
• Measured solutions of BHT-QAOA, as the “energy cost” of the objective function.
• Previously calculated ɣ and β, as their “numerical values” need to be optimized.

For the SciPy optimization minimizer, we use the constrained optimization by linear approximation (COBYLA) algorithm [14,16,31], which is a parametric iterative method for derivative-free constrained optimization that updates and minimizes the approximation values (as ɣ and β) for an objective function (as H_C and H_M of lower energy cost). On the other hand, our future work will focus on finding a cost-effective minimizer algorithm, to efficiently implement BHT-QAOA with a smaller value of p (in the quantum domain) and fewer nfev (in the classical domain).

4. Results and Discussion

Arbitrary classical Boolean problems (applications) are designed as Boolean oracles (in different structures), and these Boolean oracles are then solved using our introduced BHT-QAOA for p repetitions, where p ≥ 1. In our experiments, the ibm_brisbane [50] QPU of 127 qubits performs the quantum processing domain of BHT-QAOA, i.e., executes the quantum circuit of an application in p repetitions, and the SciPy minimizer function performs the classical processing domain of BHT-QAOA, i.e., optimizes the numerical values of ɣ and β based on the minimized energy cost of their Hamiltonians (H_C and H_M), for a number of function evaluations (nfev).

Because of our IBM Quantum Platform account limitations, the complete architecture of BHT-QAOA (shown in Figure 7) is completely simulated in the classical domain using IBM quantum libraries (Qiskit, AerSimulator, and Aer-EstimatorV2 [50,51,52]), for 1024 resampling times, which are the so-called “shots” [53]. After this classically simulated BHT-QAOA, the final optimized numerical values of ɣ and β (from the SciPy minimizer) are plugged into their respective Hamiltonians (H_C and H_M) of the quantum circuit for an application, in which it is then executed once with ibm_brisbane QPU.

Please observe that due to the limited physical connectivity of four neighboring qubits for the recent quantum layouts of IBM QPUs, the constructed Boolean oracles (in various structures) for the following applications must have n input qubits and m ancilla qubits (including fqubit), where 2 ≤ n ≤ 4 and m ≥ 1. The m ancilla qubits (i) do not affect the fidelity of the final optimized approximated solutions of applications utilizing the BHT-QAOA and (ii) have no relation to the limited physical connectivity of any IBM QPU, because all these constructed Boolean oracles are transformed into Phase oracles and then into Hamiltonians (H_C and H_M). In other words, Hamiltonians do not have any ancilla qubits in their quantum circuits, and all m ancilla qubits are removed. Figure 8 demonstrates the classical representations and the quantum circuits of Boolean oracles for these applications, as follows.

• An arbitrary Boolean problem in POS structure, as stated in Equation (1) above and shown in Figure 1.
• An arbitrary Boolean problem in SOP structure, as stated in Equation (10) below and shown in Figure 8a.

(a ∧ b ∧ ¬ c) ∨ (¬ a ∧ c) ∨ (¬ b ∧ c)

(10)

3.

An arbitrary Boolean problem in ESOP structure, as stated in Equation (11) below and shown in Figure 8b.

(a ∧ b ∧ ¬ c) ⊕ (¬ a ∧ c) ⊕ (¬ b ∧ c)

(11)

4.

A 2 × 2 Sudoku game, which is the constraints satisfaction problem—satisfiability (CSP-SAT) [54,55], as stated in Equation (12) below and illustrated in Figure 8c,d.

(cell₁ ⊕ cell₂) ∧ (cell₁ ⊕ cell₃) ∧ (cell₂ ⊕ cell₄) ∧ (cell₃ ⊕ cell₄)

(12)

5.

A 4-bit conditioned half-adder digital circuit, which is ORing two 1-bit sums and then ANDing them with one 1-bit carry-out, as stated in Equation (13) below and demonstrated in Figure 8e,f.

[(a₀ ⊕ b₀) ∨ ((a₀ ∧ b₀) ⊕ (a₁ ⊕ b₁))] ∧ [(a₁ ∧ b₁) ∨ ((a₀ ∧ b₀) ∧ (a₁ ⊕ b₁))]

(13)

Table 4. The effect of generalized transformation rules on removing all ancilla qubits (including fqubit) and reducing the numbers of quantum gates for the final Phase oracles for BHT-QAOA.

	Entities in a Boolean Oracle → Entities in a Phase Oracle
Qubits and Quantum Gates (Entities)	Arbitrary Problem in POS	Arbitrary Problem in SOP	Arbitrary Problem in ESOP	2 × 2 Sudoku Game	4-bit Conditioned Half-Adder Circuit
Input qubits	3 → 3	3 → 3	3 → 3	4 → 4	4 → 4
Ancilla qubits	4 → 0	4 → 0	1 → 0	5 → 0	9 → 0
Pauli-X (X)	16 → 8	15 → 6	6 → 6	0 → 8	12 → 2
Feynman (CX)	0 → 1	0 → 1	0 → 2	16 → 0	12 → 0
3-bit Toffoli	4 → 2	4 → 2	2 → 1	–	11 → 1
4-bit Toffoli	3 → 0	3 → 0	1 → 0	0 → 2	0 → 1
5-bit Toffoli	–	–	–	1 → 0	–

states the removal of all ancilla qubits (including fqubit) and the reduction number of quantum gates, after applying the generalized transformation rules to form Phase oracles. These Phase oracles are then transformed into the Hamiltonians (H_C and H_M) of BHT-QAOA. Note that, in Table 4, (i) a Pauli-X (X) gate in a Boolean oracle remains as-is for a Phase oracle, (ii) a Feynman (CX) gate in a Boolean oracle is equivalent to the controlled Pauli-Z (CZ) gate in a Phase oracle, and (iii) an n-bit Toffoli gate in a Boolean oracle is equivalent to an n-bit MCZ gate in a Phase oracle, where n ≥ 3 qubits.

On the one hand, the classically simulated BHT-QAOA successfully optimizes the numerical values of ɣ and β and finds all approximated solutions for these applications, as a proof of concept for utilizing our introduced BHT-QAOA in solving arbitrary classical Boolean problems in the simulated classical-quantum domain.

On the other hand, the quantum circuit of every application (using the simulated optimized numerical values of ɣ and β) is executed once with ibm_brisbane QPU for solution fidelity, as a proof of concept for utilizing BHT-QAOA to solve arbitrary classical Boolean problems in the hybrid classical-quantum domain.

Figure 9 depicts the final measured solutions for every application from the real quantum executions using ibm_brisbane QPU. In Figure 9, the first measured bit (the upper-right) of a solution is equivalent to the first input qubit, and the last measured bit (the bottom-left) of a solution is equivalent to the last input qubit for the Boolean oracle of an arbitrary application.

As illustrated in Figure 9a–e, the histograms represent the final measured outputs for the arbitrary Boolean problems (as applications), and each histogram of an application denotes the results of (a) four solutions {$\stackrel{\mathrm{-}}{a}\stackrel{\mathrm{-}}{b}\stackrel{\mathrm{-}}{c}$, $a\stackrel{\mathrm{-}}{b}c$, $\stackrel{\mathrm{-}}{a}\mathit{bc}$, $\mathit{abc}$} for the Boolean oracle in POS structure of Equation (1) above, (b) four solutions {$\mathit{ab}\stackrel{\mathrm{-}}{c}$, $\stackrel{\mathrm{-}}{a}\stackrel{\mathrm{-}}{b}c$, $a\stackrel{\mathrm{-}}{b}c$, $\stackrel{\mathrm{-}}{a}\mathit{bc}$} for the Boolean oracle in SOP structure of Equation (10) above, (c) three solutions {$\mathit{ab}\stackrel{\mathrm{-}}{c}$, $a\stackrel{\mathrm{-}}{b}c$, $\stackrel{\mathrm{-}}{a}\mathit{bc}$} for the Boolean oracle in ESOP structure of Equation (11) above, (d) two permutative solutions {solution 1: cell₁ = cell₄ = 0 and cell₂ = cell₃ = 1; solution 2: cell₁ = cell₄ = 1 and cell₂ = cell₃ = 0} for the 2 × 2 Sudoku of Equation (12) above, and (e) three solutions {$a_0{a}_1\overline{b_0}{b}_1$, $\overline{a_0}{a}_1{b}_0{b}_1$, $a_0{a}_1{b}_0{b}_1$} for the 4-bit conditioned half-adder of Equation (13) above.

Note that, in Figure 9, (i) the first measured bit (the upper-right in a histogram) is equivalent to the first input qubit of QAOA, (ii) the final measured bit (the bottom-left in a histogram) is equivalent to the final input qubit of QAOA, (iii) p states the number of repetitions for the Hamiltonians (H_C and H_M) in the quantum circuit of QAOA, (iv) nfev is the number of function evaluations from the SciPy optimization minimizer, (v) ‘Count’ is the total number of 1024 shots for all input qubits, where the higher Count indicates a solution (as a higher probability of qubits measurement) and the lower Count indicates a non-solution (as a lower probability of qubits measurement), and (vi) $\stackrel{\mathrm{-}}{x}$ means x has a false binary value of ‘0’; otherwise, x has a true binary value of ‘1’, where x is a literal (variable) in an equation that represents a Boolean problem (application), in the classical domain.

Please observe that the required nfev for the SciPy optimization minimizer varies and fluctuates, since such a minimizer mainly depends on two factors, as follows.

• The initially randomized numerical values of ɣ and β for H_C and H_M, respectively.
• The noisy simulation models (AerSimulator and Aer-EstimatorV2), which are utilized for simulating BHT-QAOA, in the classical domain.

Accordingly, the BHT-QAOA will provide broad opportunities to find all solutions for many classical Boolean problems constructed as Hamiltonians (H_C and H_M), which are neither designed nor solved using the standard QAOA [1,2]. Therefore, various classical Boolean problems for the applications of digital logic circuits, synthesizers, robotics, and machine learning can be realized as Hamiltonians and then solved using BHT-QAOA in the hybrid classical-quantum domain.

5. Conclusions

A new methodology is introduced to solve arbitrary classical Boolean problems as Hamiltonians (H_C and H_M), using the quantum approximate optimization algorithm (QAOA) [1,2]. Our methodology is termed the “Boolean-Hamiltonians Transform for QAOA” (BHT-QAOA), which is summarized as follows: (i) an arbitrary classical Boolean problem is expressed as a Boolean oracle in arbitrary structures, e.g., POS, SOP, ESOP, and XOR SAT, just to name a few, (ii) this Boolean oracle (in any structure) is converted into its equivalent Boolean oracle in ESOP structure, unless it was firstly constructed in ESOP structure, (iii) this Boolean oracle in ESOP structure is transformed into its equivalent Phase oracle based on our modified transformations of Toffoli gates, which are originally presented by Figgatt et al. [20], (iv) the Hamiltonians (H_C and H_M) are generated from this transformed Phase oracle based on our modified set of Hamiltonian compositions, which are originally presented by Hadfield [30], and (v) all execution steps of the standard QAOA are performed on the generated H_C and H_M. A classical optimization minimizer is utilized to find better-approximated solutions for an arbitrary classical Boolean problem based on the optimized numerical values of ɣ and β angles for H_C and H_M, respectively.

In BHT-QAOA, all ancilla qubits (including the output qubit) and the mirror (as the uncomputing part) of a quantum circuit will be completely removed when transforming a Boolean oracle (in any structure) into its equivalent Phase oracle. In other words, during the conversion and transformation steps of BHT-QAOA, the total number of utilized qubits will be dramatically reduced to the number of input qubits only, and the total number of quantum gates will be significantly minimized for the final quantum circuit of a Phase oracle, for an arbitrary classical Boolean problem.

In this article, arbitrary Boolean applications are constructed as Boolean oracles (in various structures), and then BHT-QAOA successfully finds all optimized approximated solutions for these applications using a classical optimization minimizer and an IBM quantum computer, since our introduced BHT-QAOA is considered as a hybrid classical-quantum algorithm. In conclusion, further classical Boolean problems can be constructed as Boolean oracles (in mixed structures) for the practical engineering applications in the topics of digital synthesizers, computer vision, robotics, and machine learning, just name a few, and BHT-QAOA will successfully solve such practical applications effectively in the hybrid classical-quantum domain.