Toward an Algorithmic Framework and Grover’s search speedup for Quantum Circuit Design—Leveraging the Minimum Connected Dominating Set Problem as an Example

In the following, we will try to stand on a computer scientist point of view to describe the proposed framework while designing a quantum-logic algorithm using an algorithmic approach.

2.2.1.

State Enumeration

For solving an optimization problem, the brute-force method is traditionally used to find the optimal solution by enumerating all the states of the solution space. The superposition property of qubits fits the need to enumerate all possible states of a solution space. For example, as shown in Figure 3(a), the CDS problem in graph G = (V,E) aims to find the minimum size of a connected dominating set D. Thus, the solution space of the considered problem is equal to the collection of all possible subsets of V. For the state enumeration, we use six qubits |v_i>, 0 ≤ i ≤ 5 to represent the vertex selection (or not selection) into a solution. Figure 3(b) shows one of the candidate connected dominating sets ({v₁, v₄}). In this case, the 6 qubit states are |v₁ >= |v₄ >= |1> and |v0 >= |v₂ > = |v₃ >= |v₅ >= |0>. For ease of discussion, we will use v_i and |v_i> interchangeably to represent the state of a qubit for later discussions. Note that one can adopt the Hardamard gate to apply to each qubit with an initial state of |0> to generate the entire solution space in one quantum operation step (see Figure 3(c)). And we use |φvertex>=⊗i=0|V|−1H(|vi=0>)|{\varphi _{vertex}} > = \otimes _{i = 0}^{|V| - 1}H\left( {|{v_i} = 0 > } \right) to denote the results (i.e., the entire solution space).

Figure 3.

A numerical example of a CDS problem.

2.2.2.

Graph and the Cost Function Representation

In a graph optimization problem, there will generally be a cost function associated with the vertex set (or the edge set). For example, the vertex cost function values are shown in Figure 4(a). Now one can apply the Pauli-y quantum gate to each qubit to represent the required cost function value on the amplitude of the qubit by the given proper angle θ. Let the cost value that is associated with vertex v_i be c_i, 0 ≤ i ≤ |V| − 1. Let the angle be θi=sin−1(ci),0≤i≤|V|−1{\theta _i} = {\sin ^{ - 1}}\left( {\sqrt {{c_i}} } \right),0 \le i \le |V| - 1 and then apply the Pauli-y quantum gate on each qubit using the angle θ_i, 0 ≤ i ≤|V| − 1. For example, since c₀ = 0.7 in Figure 4(a), then θ0=sin−1(0.7)=56.790{\theta _0} = {\sin ^{ - 1}}(\sqrt {0.7} ) = {56.79^0}. The resulting qubit states will associate with the cost function on the amplitude of state |1>. And we use |φvertex>=⊗i=0|V|−1ci|vi=1>+1−ci|vi=0>)|{\varphi _{vertex}} > = \otimes _{i = 0}^{|V| - 1}\sqrt {{c_i}} |{v_i} = 1 > + \sqrt {1 - {c_i}} |{v_i} = 0 > ) to denote the resulting (i.e., the entire solution space) after performing the Pauli-y gate operation on each qubit by given each designate angle θ_i, 0 ≤ i ≤|V| − 1 (see Figure 4(b)). Besides, the edge qubits set |φ_edge >= ⊗_eij∈E|e_ij = 1> can be used to represent a graph topology. For example, the edge qubits set with respect to the graph topology in Figure 4(a) is |φ_edge>= ⊗{e₀₁ = e₁₂ = e₁₄ = e₂₃ = e₃₄ = e₄₅ = 1}. Note that, we omit the symmetric property here for the undirected graph representation.

Figure 4.

A numerical example for cost function representation.

2.2.3.

Characteristic Determination

Generally, the difficult of quantum algorithm design is due to measure the states of quantum bits will cause the states to collapse, and then no more quantum process execution can be done on these quantum bits. In the traditionary algorithm design behavior for the Von Neumann computer, one can easily performe some characteristic determination by Boolean Algebra operations (i.e., using AND, OR, and NOT gates to perform computation for the Disjunctive Normal Form (DNF) formula (or Conjunction Normal Form (CNF) formula). However, the computation for the characteristic determination in quantum computing needs some adjustments.

Firstly, the AND and OR quantum operations (see Figure 5(c)) can be accomplished using the NOT, CNOT, and CCNOT (the so-called Toffoli gate) quantum gates (see Figure 5(a)). Note that the intrinsic of the CNOT series of quantum gates (the CNOT, CCNOT, CCCNOT, etc.) is that if the input value of the target line is |0> (or |1>), then the result of the target line will be equal to the AND (or NAND) operations made on the values of all control lines (see Figure 5(b)). One can easily check and conclude that, if the value of the control lies is all equal to |1 >, then the target line will flip the input value (no matter whether the input value is |0> or |1> on the target line). In the rest of this article, for convention, we will regard the results of applying the CNOT series of quantum gates as the determination of the flip (or not flip) of the input value on the target line.

Figure 5.

The AND and OR quantum operations.

Though the AND and OR quantum operations can be implemented for quantum operations, one auxiliary flag qubit is required to store the operation result. This kind of flag qubit is generally used to store the computation results of the characteristic determinations. However, in case one would like to update a property determination in one qubit, then a technique is required to perform this task as follows. And we also try to give the technique a theoretical proof as follows.

To generalize this technique, we assume the required task for performing the value update of the formula x = x + P₁ + P₂ + … + P_n, where x denotes a quantum bit and P_i, 1 ≤ i ≤ n is the boolean condition determination, i.e., the result for each P_i, 1 ≤ i ≤ n is either true/false (0/1). The operator + denotes the OR operation. Note that, P_i, 1 ≤ i ≤ n may represent the true/false results for the quantum operations that are performed in prior. For ease of illustration, we use the case of n = 2 as an example (i.e., the boolean formula is x + P₁ + P₂. Since this formula computation would like to keep the result in the qubit x. Thus, the traditional quantum OR and AND operations that shown in Figure 5 no longer fit. To achieve this objective, two steps are performed as follows: At first, the original boolean formula needs to be transformed to its equivalent form by x + (1 − x) · P₁ + (1 − x) · (1−P₁) · P₂, where operator · stands for the AND operation. Then, the equivalent form can be implemented using the CNOT, CCNOT, CCCNOT, … quantum gates (see Figure 6). We called the above implementation the qubit formula update. And to shorten the representation length, we will use Pi¯\overline {{P_i}} interchangeably with 1 − P_i, 1 ≤ i ≤ n. The generalized correctness proof of the above two steps for implementation of the original boolean formula x + P₁ + P₂ + … + P_n is shown as follows.

Figure 6.

An example for the qubit formula update.

Lemma 1.

The boolean formula x + P₁ + P₂ + … + P_n−2 + P_n−1 + P_n and the formula x+P1+P2+⋯+Pn−2+Pn−1+(x¯P1P2¯⋯Pn−2Pn−1¯Pn)\overline {{P_i}} x + {P_1} + {P_2} + \cdots + {P_{n - 2}} + {P_{n - 1}} + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 2}}{P_{n - 1}}} {P_n}} \right) are equivalent for any given true/false values of P_i, 1 ≤ i ≤ n, where + denotes the OR operation, and · denotes the AND operation.

Proof.

Since, x+x¯P=(x+x¯)(x+P)(by distributive law of OR operation)=1·(x+P)=x+P\matrix{ {x + \bar xP} \hfill & = \hfill & {(x + \bar x)(x + P)\quad {\rm{(by distributive law of OR operation)}}} \hfill \cr {} \hfill & = \hfill & {1\cdot(x + P)} \hfill \cr {} \hfill & = \hfill & {x + P} \hfill \cr }

Then apply the above result iteratively on each term of P_n−1, P_n−2, …, P₂, P₁, we have that, 2x+P1+P2+…+Pn−2+Pn−1+Pn=x+P1+P2+…+Pn−2+Pn−1+Pn−1¯Pn(by applying Eq.(2) on thePn−1term)=x+P1+P2+…+Pn−2+Pn−1+Pn−2Pn−1¯Pn(by applying Eq.(2) on thePn−2term)=⋯=x+P1+P2+…+Pn−2+Pn−1+(x¯P1P2¯⋯Pn−2Pn−1¯Pn)\matrix{ {} \hfill & {x + {P_1} + {P_2} + \ldots + {P_{n - 2}} + {P_{n - 1}} + {P_n}} \hfill \cr = \hfill & {x + {P_1} + {P_2} + \ldots + {P_{n - 2}} + {P_{n - 1}} + \overline {{P_{n - 1}}} {P_n}{\rm{(by applying Eq}}{\rm{.(2) on the}}\;{P_{n - 1}}\;{\rm{term)}}} \hfill \cr = \hfill & {x + {P_1} + {P_2} + \ldots + {P_{n - 2}} + {P_{n - 1}} + \overline {{P_{n - 2}}{P_{n - 1}}} {P_n}{\rm{(by applying Eq}}{\rm{.(2) on the}}\;{P_{n - 2}}\;{\rm{term)}}} \hfill \cr = \hfill & \cdots \hfill \cr = \hfill & {x + {P_1} + {P_2} + \ldots + {P_{n - 2}} + {P_{n - 1}} + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 2}}{P_{n - 1}}} {P_n}} \right)} \hfill \cr }

Hence the lemma. Q.E.D.

Lemma 2.

The boolean formula x + P₁ + P₂ + … + P_n−2 + P_n−1 + P_n and the transformed formula x+x¯P1+x¯P1¯P2+…+(x¯P1P2¯⋯Pn−2Pn−1¯Pn)x + \bar x{P_1} + \bar x\overline {{P_1}} {P_2} + \ldots + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 2}}{P_{n - 1}}} {P_n}} \right) are equivalent for any given true/false values of P_i, 1 ≤ i ≤ n, where + denotes the OR operation, and · denotes the AND operation.

Proof.

Applying the result of Lemma 1 iteratively on each term of P_n, P_n−1, P_n−2, …, P₁, then we have that, 3x+P1+P2+…+Pn−2+Pn−1+Pn=x+P1+P2+…+Pn−2+Pn−1+(x¯P1P2¯⋯Pn−2Pn−1¯Pn)(by Lemma 1)=x+P1+P2+…+Pn−2+(x¯P1P2¯⋯Pn−2¯Pn−1)+(x¯P1P2¯⋯Pn−2Pn−1¯Pn)=⋯=x+x¯P1+x¯P1¯P2+…+(x¯P1P2¯⋯Pn−2¯Pn−1)+(x¯P1P2¯⋯Pn−2Pn−1¯Pn)\matrix{ {} \hfill & {x + {P_1} + {P_2} + \ldots + {P_{n - 2}} + {P_{n - 1}} + {P_n}} \hfill \cr = \hfill & {x + {P_1} + {P_2} + \ldots + {P_{n - 2}} + {P_{n - 1}} + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 2}}{P_{n - 1}}} {P_n}} \right)\left( {{\rm{by Lemma 1}}} \right)} \hfill \cr = \hfill & {x + {P_1} + {P_2} + \ldots + {P_{n - 2}} + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 2}}} {P_{n - 1}}} \right) + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 2}}{P_{n - 1}}} {P_n}} \right)} \hfill \cr = \hfill & \cdots \hfill \cr = \hfill & {x + \bar x{P_1} + \bar x\overline {{P_1}} {P_2} + \ldots + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 2}}} {P_{n - 1}}} \right) + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 2}}{P_{n - 1}}} {P_n}} \right)} \hfill \cr }

Hence the lemma. Q.E.D.

At last, we will try to show that the implementation for the qubit formula update will correctly determine the result of the given boolean formula. By Lemma 2, the original boolean formula x + P₁ + P₂ + … + P_n is equivalent to the transformed formula x+x¯P1+x¯P1¯P2+⋯+(x¯P1P2¯⋯Pn−1¯Pn)x + \bar x{P_1} + \bar x\overline {{P_1}} {P_2} + \cdots + \left( {\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{n - 1}}} {P_n}} \right), thus we only need to try to implement the transformed formula using existing quantum gates. According to the quantum circuit design for the qubit formula update, we denote the quantum circuit for each subpart of the transformed formula x¯P1¯P2¯⋯Pi−1¯Pi),1≤i≤n\bar x{P_1} by QC_i. For example, as shown in Figure 6, QC₁ (and QC₂) are trying to implement the computation for x¯P1\bar x\overline {{P_1}} {P_2} (and x¯P1¯P2\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{i - 1}}} {P_i}), respectively. Note that, for a higher number of control input of control NOT gate can be easily implemented by some combination of quantum gates, and we will ignore the details here. Now, the following theorem will give the proof of the correction for the qubit formula update implementation.

Theorem 1.

The qubit formula update can correctly implement the original boolean formula x + P₁ + P₂ + … + P_n, for any given true/false values of P_i, 1 ≤ i ≤ n, where + denotes the OR operation.

Proof.

At first, by Lemma 2, we can focus on the implementation of the transformed boolean formula, since it is equivalent to the original boolean formula. Let the collection of all possible input values for x, P₁, P₂, …, and P_n be S* (i.e., S* = {0, 1}ⁿ⁺¹). Let the collection of input values data set that can enable quantum circuit Q_i, 1 ≤ i ≤ n to flip the results of qubit x be S_i. Since QC_i is designed for implementing the boolean formula subpart x¯P1P2¯⋯Pi−1¯Pi\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{i - 1}}} {P_i} that is synthesizing by the control NOT series of quantum gates. Thus, Si={ (x,P1,P2,…,Pn)∈{0,1}n+1∣x=0,x¯P1P2¯⋯Pi−1¯Pi=1 }{S_i} = \left\{ {\left( {x,{P_1},{P_2}, \ldots ,{P_n}} \right) \in {{\{ 0,1\} }^{n + 1}}\mid x = 0,\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{i - 1}}} {P_i} = 1} \right\}. Let S₀ = {(x, P₁, P₂, …, P_n) ∈ {0, 1}ⁿ⁺¹ |x = 1} and S_n+1 = {(x, P₁, P₂, …, P_n) ∈ {0,1}ⁿ⁺¹|x = P₁ = P₂ = … = P_n = 0}. It is obviously that (1) ∪i=0n+1Si=S* \cup _{i = 0}^{n + 1}{S_i} = {S^*}; (2) S_i ∩ S_j = ∅, ∀i,j ∈ {0, 1, …, n + 1} and i ≠ j. Note that the first property means that the union of all sets S_i, 0 ≤ i ≤ n + 1 will exhaust the entire solution space, and the second property means that these sets are disjoint with each other. And consequently, if the input data causes one of the quantum circuit (say, QC_i) to flip the result, then the other quantum circuits will not flip the result again, which means the total number of flips for the entire sequential operation will be at most once.

Now we will check the transformed formula results by given the input data that comes from set S_i, 0 ≤ i ≤ n + 1, and to see whether or not it is equal to the final results of the qubit x. For the case of the input values (x, P₁, P₂, …, P_n) ∈ S₀, then the result for the transformed formula will be equal to 1, and none of the quantum circuits will flip the initial input value of x = 1. Thus, the final result of the qubit x will be 1. For the case of the input values (x, P₁, P₂, …, P_n) ∈ S_i, for any i ∈ {1, 2, …, n}, by definition, since x¯P1P2¯⋯Pi−1¯Pi=1\bar x\overline {{P_1}{P_2}} \cdots \overline {{P_{i - 1}}} {P_i} = 1 the transformed boolean formula will be equal to 1. And since QC_i will cause x = 0 to flip once, thus the resulting value will obtain value 1. For the last possible input case of (x, P₁, P₂, …, P_n) ∈ S_n+1, obviously the transformed boolean formula will be 0. And since this case of data will not enable any quantum circuit QC_i, 1 ≤ i ≤ n to flip, thus the result will equal to the original input data, the 0. By the results of Lemma 2 and the above discussions, we have that the result for the original boolean formula will be equal to the result that performing the qubit formula update. Hence the theorem. Q.E.D.

Now, we will give a numerical example to illustrate the application of this technique. Figure 7(a) gives a single edge graph, that is, G = (V, E) = ({v_i, v_j}, {e_ij}). In case one wants to determine whether or not a message can be obtained by vertex v_j. Two vertex qubits v_i and v_j are used to represent the status of whether or not a message can be obtained by vertices v_i and v_j, respectively. A qubit e_ij is used to represent the existence of edge e_ij. Then the case of vertex v_j will obtain the message that are basing on either one of the following two conditions is met: (1) vertex v_j is already having the message (that is v_j = 1) or; (2) vertex v_j’s neighbor v_i is having the message (that is v_i = 1 and e_ij = 1). Thus, the boolean formula for updating v_j is v_j = v_j + v_ie_ij. By the above proposed technique, we have the transformed formula vj=vj+vj¯vieij{v_j} = {v_j} + \overline {{v_j}} {v_i}{e_{ij}}. And the quantum circuit is shown in Figure 7(b). Note that the ancilla qubit |φ_aux1 > is initialized in the zero state |0>.

Figure 7.

A numerical example for characteristic determination.

2.2.5.

Results Output and the Measurement

For solving the combinatorial optimization problem, after generating the entire solution space using the superposition characteristic on the decision variable set (see Figure 8). One may design several quantum circuits (say QC₁, QC₂, …, QC_k) to perform some characteristic determination processes one by one sequentially to obtain the minimum (or maximum) object function values. However, the main objective is to known which solution will result in the optimum solution value. Therefore, the unitary characteristic (that is, U*U = UU* = I) of the quantum circuit can reverse the operation to obtain the original decision variable values (that is, the optimum solution). Thus, the right part of the quantum circuit in Figure 8 can achieve this objective.

Figure 8.

An example for results output and the measurement.

In this process, the graph input and the state space generation follow the above-mentioned technique. Therefore, given a graph topology G = (V, E) for the considered problem, we use qubits |φ_edge >= ⊗_eij∈E|e_ij = 1> to denote the resulting graph topology, and let qubits |φ_vertex > to represent the vertex set. We then apply the Hardamard gate to each vertex qubit with an initial value of 0, to obtain the entire solution space of the considered problem; that is, ⊗i=0|V|−1H(|vi=0>) \otimes _{i = 0}^{|V| - 1}H\left( {|{v_i} = 0 > } \right). We denote this quantum circuit for the state enumeration process as QC₁. Note that some auxiliary qubits and characteristic determination qubits are also added to this quantum circuit QC₁, which will be used for later quantum computations.

In this process, we add |V| auxiliary qubits | φvertex^>=⊗i=0|V|−1 |v^i=0>\left| {{\varphi _{\widehat {vertex}}} > = \otimes _{i = 0}^{|V| - 1}} \right|{{\hat v}_i} = 0 > to be the dominated flag with respect to each vertex v_i ∈ V, for representing whether or not the vertex is dominated. According to the definition of a vertex v_i ∈ V being dominated, it is to test whether or not one of the following two conditions is met: (1) vertex v_i belongs to the dominating set (the P₁ clause); (2) there exists a neighbor of v_i that belongs to the dominating set (the P₂ clause). Thus, by the above proposed technique, the dominated flag qubit v^i{{\hat v}_i} with respect to vertex v_i can be updated by vi^=vi^+v^¯ivi+v^¯iv¯ivjeij\widehat {{v_i}} = \widehat {{v_i}} + {\overline {\hat v} _i}{v_i} + {\overline {\hat v} _i}{{\bar v}_i}{v_j}{e_{ij}}, and the quantum circuit is denoted by QC2_ij. Since the process on each edge (v_i, v_j) ∈ E must be performed bidirectionally, each edge must perform the quantum operations of QC2_ij and QC2_ji, respectively. As shown in Figure 10(a), after performing the state enumeration process, the entire solution space will be generated. Then any solution (for example, the |φ_vertex >= |010010 >, which stands for the candidate vertex set {v₁, v₄}), will perform the above quantum operations (see Figure 10(b)). The complete operations for updating all dominated flags must be performed on each edge of the given graph. Thus, a loop is required for the operations. Figure 11(a) shows the loop implementation of the numerical example.

Figure 10.

The solution method for the dominating test process (the dominated flag qubits updating operations).

Figure 11.

The solution method for the dominating test process (the dominating test qubit characteristic determination operations).

Now, we need to determine whether this solution is a dominating set or not, and store the result into the characteristic determination qubit |φ_dominated = 0>. Note that if all of the dominated flag qubits v^i=1,∀vi∈V{{\hat v}_i} = 1,\forall {v_i} \in V, then the characteristic determination qubit will be |φ_dominated = 1>, which means the solution is a dominating set. For the rest of the cases the qubit remains |φ_dominated = 0>, which means that the solution is not a dominating set. Since we need to test whether every dominated flag qubit is equal to 1 or not, it can be easily implemented using CCCNOT quantum gates, and we use QC2_b to denote the quantum circuit. Figure 11(b) gives a general description of the implementation. In the illustration, we only give a simple description to determine the result. In general, one can try to modify the quantum circuit design by reusing the auxiliary qubits, and we omit them here.

In this process, the operations of the quantum circuit (QC3) will determine whether a candidate solution (|φ_vertex>) is connected or not, and then it stores the true/false result into the quantum bit |φ_connected >. At first, we propose a subprocess called Reachability testing to test whether or not all of the vertices in the candidate solution are reachable from a given seed vertex v_k ∈ V and the true/false result will be stored in an auxiliary qubit NOT-pass^k. Note that if the seed vertex v_k ∈ V belongs to the candidate solution, then the Reachability testing is an effective operation. If the resulting auxiliary qubit NOT-pass^k = 0 (or 1), then it means the candidate solution is connected (or disconnected). On the contrary, if the seed vertex v_k ∈ V does not belong to the candidate solution, then the Reachability testing is an ineffective process, and the resulting auxiliary qubit will obtain NOT-pass^k = 1. Since one cannot guarantee that the planting seed vertex belongs to the candidate solution, the Connected test process will invoke the Reachability testing for n(= |V|) times and one for letting any vertex v_k ∈ V as a seed vertex. In case the auxiliary qubits NOT-pass^k, v_k ∈ V returns a value of 0, then we can conclude that the candidate solution is connected; otherwise, it is disconnected.

The main operations for the subprocess Reachability testing are as follows: A reachable flag qubit v^i{{\hat v}_i} is associated with each vertex v_i ∈ V and is initially set to be 0. Note that since these qubits |φvertex^>|{\varphi _{\widehat {vertex}}} > can be reused with the dominated flag qubits in the above Dominating test process, we used the same notation here (v^i,∀vi∈V{{\hat v}_i},\forall {v_i} \in V). Each time a vertex (say v_k ∈ V) is chosen to be a seed vertex, then the corresponding reachable flag qubit will be set to be v^k=1{{\hat v}_k} = 1. The reachable characteristic can propagate from a vertex v_i ∈ V to its neighbors v_j ∈ V according to the following two either-or conditions: (1) either vertex v_j is already reachable from the seed vertex (that is v^j=1{{\hat v}_j} = 1); or (2) vertex v_i is reachable from the seed vertex (v^i=1{{\hat v}_i} = 1), vertex v_j belongs to the candidate solution (v_j = 1), and vertex v_j is a neighbor of v_i(e_ij = 1). Again, one can easily apply the above-mentioned technique to perform the updated formula (v^j=v^j+v^¯j·v^ivjeij)\left( {{{\hat v}_j} = {{\hat v}_j} + {{\overline {\hat v} }_j}\cdot{{\hat v}_i}{v_j}{e_{ij}}} \right) on each edge e_ij. The corresponding quantum circuit is shown in Figure 12(b), and we denote this quantum circuit as QC3_ij.

Figure 12.

The solution method for the Connected test process (the reachable flag qubit updating operations).

Before performing the Reachability testing subprocess, we will set the reachable flag qubits |φvertex^>=⊗vi∈V|v^i=0>|{\varphi _{\widehat {vertex}}} > = { \otimes _{{v_i} \in V}}|{{\hat v}_i} = 0 > for initialization. We then pick a seed vertex v_k for planting the value 1 into its reachable flag qubit (that is, v^k=1{{\hat v}_k} = 1). Then an expanding operation is applied to perform a double loop on each vertex in v_i ∈ V with its adjacent edge e_ij ∈ E to propagate the reachable characteristic as much as it can (that is, the performing of the quantum operations QC3_ij and QC3_ji with respect to edge e_ij ∈ E). The quantum circuit with respect to the expanding operations of the Reachability testing process is denoted by QC3Reach-akQC3_{{\rm{Reach - a}}}^k (see Figure 13). As shown in Figure 13, the red dashed rectangle of the pseudo code is equivalent to the red dashed rectangle of the quantum circuit, which is the implementation of the numerical example shown in the upper right of Figure 13.

Figure 13.

The quantum operations for the Connected test process (the Reachability test operations (QC3Reach-akQC3_{{\rm{Reach - a}}}^k)).

The above expanding operation will let the seed of the initial reachable flag value propagate as much as it can. If a seed is planted into a vertex that belongs to the candidate solution vertex set and the solution set is connected, then both of the qubit values of v_i and v^i{{\hat v}_i} will be equal to 1, for every vertex v in the candidate solution. We will say that every vertex in the candidate solution is reachable, which means that the candidate solution is connected, and the auxiliary qubit will obtain the result of NOT-pass^k = 0. On the contrary, some violations will occur in the case of the qubit v_i = 1, but the vertex is not reached by the expanding operation (that is, the reachable flag qubit of this vertex is v^i=0{{\hat v}_i} = 0) (see Figure 12(a)). Of course, the auxiliary qubit will obtain the result of NOT-pass^k = 1. In order to obtain the above-mentioned results, one can apply the following updated formula to each vertex v_i ∈ V, NOT-passk=NOT-passk+NOT-passk·viv^¯i{\rm{NOT - pas}}{{\rm{s}}^k} = {\rm{NOT - pas}}{{\rm{s}}^k} + {\rm{NOT - pas}}{{\rm{s}}^k} \cdot {v_i}{{\bar \hat v}_i} (the corresponding quantum circuit is shown in Figure 14(a) and (b)). Lastly, combining the two quantum circuits QC3Reach-akQC3_{{\rm{Reach - a}}}^k and QC3Reach-bkQC3_{{\rm{Reach - b}}}^k, then the implementation for the Reachability testing process is obtained, and we denoted it by QC3ReachkQC3_{{\rm{Reach}}}^k (see Figure 14(c)). The detailed operations of the Reachability testing process are shown in Figure 15.

Figure 14.

The quantum operations for the Connected test process (the Reachability test operations (QC3Reach-bkQC3_{{\rm{Reach - b}}}^k and QC3ReachkQC3_{{\rm{Reach}}}^k)).

Figure 15.

The operation steps for the Reachability testing process.

Now we will illustrate the complete operations for the Connected test process as follows: Initially, we let the characteristic determination qubit |φ_connected > be 0. Since we do not know whether the seed will be planted into a vertex in the candidate solution set or not, a loop will be performed for the seed being planted into each vertex v_k ∈ V. When a seed is planted into a vertex v_k ∈ V, an auxiliary qubit NOT-pass^k is used to store the result of this Reachability testing process and we set it to 0 and let v^k=1{{\hat v}_k} = 1 for initialization. After performing the Reachability testing process, if the candidate solution |φ_vertex> is connected, then one of the Reachability testing subprocesses for the loop will return a successful result; that is, the auxiliary qubit NOT-pass^k = 0, ∃v_k ∈ V. Otherwise, none of the Reachability testing subprocesses for the loop will return a successful result. Again, the characteristic determination qubit |φ_connected> can perform the following updated formula: φconnected=φconnected+φconnected¯·NOT-pass¯k·vk{\varphi _{connected}} = {\varphi _{\overline {connected} }} + {\varphi _{\overline {connected} }} \cdot {\overline {{\rm{NOT - pass}}} ^k} \cdot {v_k}, for each time of Reachability testing subprocess for the seed vertex to be v_k ∈ V. Note that the term v_i in the updated formula is to ensure that if the seed is planted into a non-solution set vertex (that is, v_i = 0), then the Reachability testing subprocess will fail. The complete operations of the Connected test process are shown in Figure 16.

Figure 16.

The operation steps for the Connected test process.

The corresponding quantum circuit for the Connected test process is shown in Figure 17. Note that, since the quantum gate operation cannot directly implement the if-then-clause of the seed planted process in Figure 16, we will use the CNOT quantum gate to apply it to the control line qubit v_k ∈ V and let the target line be the qubit vk^=0\widehat {{v_k}} = 0. If the seed is being planted into a non-candidate solution vertex v_k ∈ V, then the resulting vk^\widehat {{v_k}} will remain unchanged (that is, vk^=0\widehat {{v_k}} = 0). In such a case, the resulting auxiliary qubit will obtain a fail result (that is, NOT-pass^k = 1). Otherwise, if the seed is planted into a candidate solution vertex v_k ∈ V (that is v_k = 1), then the resulting auxiliary qubit NOT-pass^k will follow the Reachability testing process result and then be integrated by the updated formula: φconnected=φconnected+φconnected¯·NOT-pass¯k·vk{\varphi _{connected}} = {\varphi _{connected}} + {\varphi _{\overline {connected} }} \cdot {\overline {{\rm{NOT - pass}}} ^k} \cdot {v_k} (see Figure 17(a)). The complete quantum circuit (QC3) for the Connected test process is shown in Figure 17(b).

Figure 17.

The quantum circuit for the Connected test process (QC3).

In this process, the size of a solution set |φ_vertex > will be determined, and the result will be stored into an auxiliary qubit set |φ_size > using the binary numeral system representation. For the example shown in Figure 13, the size of the candidate solution set |φ_vertex >= |011010 > is equal to 3; thus, |φ_size >= |s₂s₁s₀ >= |011 >. Obviously, the number of auxiliary qubits required to store the result is equal to ⌈log₂ n⌉ + 1, where n stands for the number of vertices (that is, |V|). In the following, two approaches (the Half adder approach and the Toffoli gate approach) are proposed to achieve the above objective. Detailed descriptions are illustrated using the numerical example of |φ_vertex >= |v₀v₁v₂v₃ > and |φ_size >= |s₂s₁s₀>. For any input graph size n can be easily generalized, so we omit it here.

A half adder is quite simple for traditional digital logic. It can add two digits (a and b), and produce a sum bit (S) and a carry bit (C). The carry bit C (and the sum bit S) is equal to the result of performing operations a AND b (and a XOR b), respectively. The quantum circuit with respect to a half adder can be easily implemented (see Figure 18(a)). Now, the main idea for the Half adder approach is to perform the addition for each group of two vertices (say, v_i and v_i+1), which are shown in the first column of the quantum circuit in Figure 18(b). Note that the carry bits of a half adder are the weight of 2¹. If we continue to apply a half adder to both of the carry bits of two half adders, the weight of the resulting carry bit will be equal to 2². Following this principle and taking the weight of each output into consideration, the quantum circuit with respect to the Size computation process can then be built. Figure 18(b) gives a quantum circuit (QC4) for a graph with order 4 (that is, |φ_vertex >= |v₀v₁v₂v₃ > and the auxiliary qubits set is |φ_size >= |s₂s₁s₀ >). In this numerical example, if |φ_vertex>= |v₀v₁v₂v₃>= |1111>. As shown in Figure 18(b), one can easily check and obtain the result |φ_size >= |s₂s₁s₀ >= |100>.

Figure 18.

The quantum circuit for the Size computation process (QC4) (the Half adder approach).

This approach first builds a truth table for the size determination results. We use the same numerical example that was used for the Half adder approach (see Figure 19(a)). Then, for each resulting auxiliary qubit, s₀, s₁, and s₂ can be emulated using a series of Toffoli gates (see Figure 19(b)). Detailed descriptions are omitted here.

Figure 19.

The quantum circuit for the Size computation process (QC4) (the Toffoli gate approach).

Now, we can apply the quantum-logic algorithm design technique discussed in Section 2 to build the final stage of the quantum circuit for our proposed method. After that, one can start to measure the minimum connected dominating set by giving the following conditions: |φ_dominated = 1>, |φ_connected = 1>, and |φ_size = 001> (see Figure 20). Note that if the measure returns that the solution is empty, then the size value can increase by 1 and try to measure the result again until the solution is not empty.

Figure 20.

The illustration of the Results output & the measurement.

Standard derivations of Grover’s algorithm, such as in [6,7,28], assume a uniform superposition as the initial state: |v〉=1N∑x=0N−1|x〉|v\rangle = {1 \over {\sqrt N }}\sum _{x = 0}^{N - 1}|x\rangle . These standard treatments do not address the case of a weighted initial state, such as the one defined by the amplitude distribution αx=w(x)‖w‖{\alpha _x} = {{w(x)} \over {{\bf{w}}}} used in this work. Therefore, to ensure the integrity of our proposed method, it is necessary to provide a proof of its correctness.

Recall that our initial state is: |v〉=∑x=0N−1αx|x〉|v\rangle = \sum _{x = 0}^{N - 1}{\alpha _x}|x\rangle . Let |x_t〉 be the target state and θ2{\theta \over 2} be the angle between |v〉 and horizontal axis, assuming |x_t〉 is taken as the vertical axis. We first count the angle π2−θ2{\pi \over 2} - {\theta \over 2} between |x_t〉 and |v〉. The inner product 〈xt|v〉=αxt=n−s2(xt)∑x=0N−1(n−s2(x))2=n−s2(xt)2n−2n(n+1)\langle {x_t}|v\rangle = {\alpha _{{x_t}}} = {{n - {s_2}\left( {{x_t}} \right)} \over {\sqrt {\mathop \sum \nolimits_{x = 0}^{N - 1} {{\left( {n - {s_2}(x)} \right)}^2}} }} = {{n - {s_2}\left( {{x_t}} \right)} \over {\sqrt {{2^{n - 2}}n(n + 1)} }}. Since 〈xt|v〉=‖xt‖‖v‖cos(π2−θ2)=cos(π2−θ2)=αxt\langle {x_t}|v\rangle = {x_t}v\cos \left( {{\pi \over 2} - {\theta \over 2}} \right) = \cos \left( {{\pi \over 2} - {\theta \over 2}} \right) = {\alpha _{{x_t}}}, when 2ⁿ is large, αxt=cos(π2−θ2)≈0{\alpha _{{x_t}}} = \cos \left( {{\pi \over 2} - {\theta \over 2}} \right) \approx 0 implies π2−θ2≈π2{\pi \over 2} - {\theta \over 2} \approx {\pi \over 2}. See Figure 21 for visualizing the angle θ2{\theta \over 2}. Since π2−θ2≈π2{\pi \over 2} - {\theta \over 2} \approx {\pi \over 2}, the angle θ2{\theta \over 2} between |v〉 and horizontal axis is small. Thus, θ2≈sin(θ2)=cos(π2−θ2){\theta \over 2} \approx \sin \left( {{\theta \over 2}} \right) = \cos \left( {{\pi \over 2} - {\theta \over 2}} \right). Since αxt=〈xt|v〉=‖|xt〉‖‖|v〉‖cos(π2−θ2)=sin(θ2)≈θ2{\alpha _{{x_t}}} = \langle {x_t}|v\rangle = |{x_t}\rangle |v\rangle \cos \left( {{\pi \over 2} - {\theta \over 2}} \right) = \sin \left( {{\theta \over 2}} \right) \approx {\theta \over 2}, we have θ ≈ 2_αxt. Visualized geometrically, an increase in α_xt corresponds to an increase in θ, indicating that initial states with higher amplitudes are positioned in closer proximity to the target state |x_t〉.

Figure 21.

Geometric visualization of the weighted search algorithm in the two-dimensional subspace. The initial state |v〉 makes angle θ2{\theta \over 2} with the horizontal axis, while |x_t〉 represents the target state (vertical). Each gu_f iteration rotates the quantum state by θ, where θ ≈ 2_αxt depends on the initial target amplitude. After k iterations, the initial state |v〉 is rotated into a final state, denoted |ϕ〉, that is closely aligned with the target state |x_t〉.

Oracle u_f flips the sign of the amplitude corresponding to |x_t〉. That is u_f|v〉 = (∑_x≠xt α_x|x〉) – α_xt|x_t〉 — applying u_f to |v〉 results in the reflection of |v〉 across the horizontal axis. The position of u_f|v〉 is illustrated in Figure 21.

Next, we describe the action of the operator g. Let u_f|v〉 = |ψ〉. To understand the action of g on |ψ〉, we first decompose |ψ〉 into |ψ〉 = a|v〉 + b|v^⊥〉 — the state |ψ〉 can be expressed as a linear combination of the mutually perpendicular states |v〉 and |v^⊥〉. Then, the operator g is applied to |ψ〉 producing g|ψ〉 = a|v〉 − b|v^⊥〉 because g|v〉 = |v〉 and g|v^⊥〉 = (2|v〉 〈v|−I_N)|v^⊥〉 = 2|v〉 〈v||v〉^⊥ − |v^⊥〉 = −|v^⊥〉 where 〈v|v^⊥〉 = 0. This result shows that the component of |ψ〉 parallel to |v〉 is unchanged, while the component orthogonal to |v〉 is inverted. This is precisely the definition of a reflection of the state |ψ〉 across the axis defined by |v〉. The position of gu_f|v〉 is illustrated in Figure 21.

To summarize the analysis presented above, the application of gu_f to |v〉 results in a rotation of |v〉 toward |x_t〉 by angle θ, with the rotation angle θ increasing as α_xt increases. Now, we proceed to determine the required number of iterations of the gu_f operator and analyze the probability for finding our target state |x_t〉.

Since the initial angle between |v〉 and the horizontal axis is θ2{\theta \over 2}, each application of the operator gu_f rotates the state toward |x_t〉 by an additional angle of θ. We expect that after performing k iterations of gu_f, the resulting state |ϕ〉 forms a very small angle with |x_t〉. Thus, we have kθ=π2−θ2k\theta = {\pi \over 2} - {\theta \over 2}, which gives k=⌊ π2θ−12 ⌋≈⌊ π4αxt−12 ⌋k = \left\lfloor {{\pi \over {2\theta }} - {1 \over 2}} \right\rfloor \approx \left\lfloor {{\pi \over {4{\alpha _{{x_t}}}}} - {1 \over 2}} \right\rfloor . After k iterations, the state of the qubits is |ϕ〉≈(guf)⌊ π4αxt−12 ⌋|v〉|\phi \rangle \approx {\left( {g{u_f}} \right)^{\left\lfloor {{\pi \over {4{\alpha _{{x_t}}}}} - {1 \over 2}} \right\rfloor }}|v\rangle . The maximum angle between |ϕ〉 and |x_t〉 is θ2{\theta \over 2}. Let ℓ be the length of the projection of |ϕ〉 onto |x_t〉. Thus, when we measure the state |ϕ〉, the probability of obtaining |x_t〉 is |ℓ|², where ℓ = 〈x_t|ϕ〉 is the projection amplitude of |ϕ〉 onto |x_t〉. Let ϵ be the small angle between the final state |ϕ〉 and the target |x_t〉. From the relation ℓ = 〈x_t|ϕ〉 = ‖x_t‖‖ϕ‖ cos(ϵ), and under the normalization ‖x_t‖ = ‖ϕ‖ = 1, it follows that ℓ = cos⁡(ϵ). Since this angle is bounded by ϵ ≤ θ/2, the success probability is lower bounded by: |l|2=cos2(ϵ)≥cos2(θ/2)=1−sin2(θ/2)≈1−αxt2|\ell {|^2} = {\cos ^2}() \ge {\cos ^2}(\theta /2) = 1 - {\sin ^2}(\theta /2) \approx 1 - \alpha _{{x_t}}^2, which is very close to 1 since α_xt is small.

In the Grover’s search, if M (the number of solutions) is unknown, the optimal iteration count k cannot be computed exactly. To handle this, we use an adaptive strategy. The algorithm runs step by step with k adjusted based on measurement results. We begin with an initial guess k0≈π42n{k_0} \approx {\pi \over 4}\sqrt {{2^n}} . The optimal number of iterations for Grover’s algorithm is approximately (π/4)2n/M(\pi /4)\sqrt {{2^n}/M} , where M is the number of solutions. Since M is unknown a priori, we adopt the most difficult case where there is only a single solution (M = 1). After each measurement, we check the output bitstring x with the oracle (from Section 3) to see if it is a valid CDS. Counting the successes over multiple trials gives P^{\hat P}. If P^{\hat P} is too low, we increase k; if P^{\hat P} starts to decrease, we reduce k. This feedback allows k to adaptively converge to a near-optimal value.

Grover operators u_f and g can be represented as 2ⁿ-dimensional unitary matrices. Based on the previously mentioned method [27], each of them can be implemented using 22484n−322n+53{{22} \over {48}}{4^n} - {3 \over 2}{2^n} + {5 \over 3} CNOT gates. Since the operator gu_f is repeated k≈⌊π4αxt−12⌋k \approx \left\lfloor {{\pi \over {4{\alpha _{{x_t}}}}} - {1 \over 2}} \right\rfloor times, the total number of CNOT gates required by the proposed non-uniform Grover search for the minimum CDS is (2⌊π4αxt−12⌋+1)(22484n−322n+53)\left( {2\left\lfloor {{\pi \over {4{\alpha _{{x_t}}}}} - {1 \over 2}} \right\rfloor + 1} \right)\left( {{{22} \over {48}}{4^n} - {3 \over 2}{2^n} + {5 \over 3}} \right) CNOT gates.

This section provides an analysis to estimate the difference in the final measurement probability between two solution states whose number of 0 differ by one. This analysis relies on the geometric intuition of the amplitude amplification process derived previously.

A complete mathematical derivation of the probability difference ΔP is hard because we do not know all the required information in advance. To obtain an exact formula such as ΔP = f(n, M, w(x₁), w(x₂),…), we would need to know how many solutions there are (M) and what the weight of each solution is. Since this information is unavailable, we focus on analyzing one target state at a time. Using simple approximations (for example, θ ≈ 2α_xt), we can still understand how the final measurement probability depends on the initial amplitude of a solution.

Let |x₁〉 and |x₂〉 be two distinct target states (Connected Dominating Sets) corresponding to bitstrings whose number of 1s differ by one: s2(x2)=s2(x1)+1,{s_2}\left( {{x_2}} \right) = {s_2}\left( {{x_1}} \right) + 1, where, s₂(x) denotes the number of ones in the bitstring x. By the definition of the weight function w(x) = n − s₂(x): w(x1)=n−s2(x1)w(x2)=n−s2(x2)=n−(s2(x1)+1)=w(x1)−1.\matrix{ {w\left( {{x_1}} \right)} \hfill & = \hfill & {n - {s_2}\left( {{x_1}} \right)} \hfill \cr {w\left( {{x_2}} \right)} \hfill & = \hfill & {n - {s_2}\left( {{x_2}} \right) = n - \left( {{s_2}\left( {{x_1}} \right) + 1} \right) = w\left( {{x_1}} \right) - 1.} \hfill \cr }

The state |x₁〉 is the preferred solution as it corresponds to a smaller CDS (fewer ones, more zeros). The initial amplitudes are: αx1=w(x1)‖w‖ andαx2=w(x1)−1‖w‖.{\alpha _{{x_1}}} = {{w\left( {{x_1}} \right)} \over {{\bf{w}}}}\quad {\rm{and}}\quad {\alpha _{{x_2}}} = {{w\left( {{x_1}} \right) - 1} \over {{\bf{w}}}}.

This confirms that the preferred solution |x₁〉 has a greater initial amplitude: α_x1 > α_x2.

We adopt the approximations derived from the weighted amplitude amplification (where the angle of rotation θ is approximately 2α_xt).

The number of iterations required to optimally amplify the preferred state |x₁〉 is: k1≈⌊π4αx1−12⌋.{k_1} \approx \left\lfloor {{\pi \over {4{\alpha _{{x_1}}}}} - {1 \over 2}} \right\rfloor .

We run the algorithm for this fixed number of iterations, resulting in the final state |ϕ〉.

The final probability of measuring |x₁〉, P(x₁), is given by P(x₁) = cos²(ϵ₁), where ϵ₁ is the small angle between |ϕ〉 and |x₁〉. When number of iterations is k₁, ϵ₁ is bounded by θ12{{{\theta _1}} \over 2}: P(x1)≈cos2(θ12)=1−sin2(θ12)≈1−αx12.P\left( {{x_1}} \right) \approx {\cos ^2}\left( {{{{\theta _1}} \over 2}} \right) = 1 - {\sin ^2}\left( {{{{\theta _1}} \over 2}} \right) \approx 1 - \alpha _{{x_1}}^2.

Since α_x1 is small for large n, this probability P(x₁) is very close to 1.

Each Grover iteration, gu_f, rotates the state vector by an angle of θ₂ towards |x₂〉. The algorithm is executed for k₁ iterations, where k₁ is the number of iterations optimized for the preferred target |x₁〉, not for |x₂〉. After k₁ iterations, the total angle θ_total of the state vector with respect to the horizontal axis is given by the initial angle plus the accumulated rotation: θtotal=θ22+k1θ2{\theta _{{\rm{total}}}} = {{{\theta _2}} \over 2} + {k_1}{\theta _2}.

The quantity of interest is the final angle, ϵ₂, between the final state |ϕ〉 and the target axis |x₂〉 (which is at angle π/2). This angle is the absolute difference between their final angular positions: ϵ2=|(θ22+k1θ2)−π2|.{_2} = \left| {\left( {{{{\theta _2}} \over 2} + {k_1}{\theta _2}} \right) - {\pi \over 2}} \right|.

From the analysis for the preferred state |x₁〉, we know that the optimal number of iterations is approximately: k1≈π2θ1−12.{k_1} \approx {\pi \over {2{\theta _1}}} - {1 \over 2}.

We substitute this expression for k₁ into the equation for ϵ₂: ϵ2≈|(θ22+(π2θ1−12)θ2)−π2|.{_2} \approx \left| {\left( {{{{\theta _2}} \over 2} + \left( {{\pi \over {2{\theta _1}}} - {1 \over 2}} \right){\theta _2}} \right) - {\pi \over 2}} \right|.

We now simplify the expression inside the absolute value. First, distribute θ₂: ϵ2≈|θ22+πθ22θ1−θ22−π2|=|πθ22θ1−π2|=π2|1−θ2θ1|.{_2} \approx \left| {{{{\theta _2}} \over 2} + {{\pi {\theta _2}} \over {2{\theta _1}}} - {{{\theta _2}} \over 2} - {\pi \over 2}} \right| = \left| {{{\pi {\theta _2}} \over {2{\theta _1}}} - {\pi \over 2}} \right| = {\pi \over 2}\left| {1 - {{{\theta _2}} \over {{\theta _1}}}} \right|.

Finally, using the approximation θ ≈ 2α, we can express the angle in terms of the initial amplitudes: ϵ2≈π2|1−2αx22αx1|=π2|1−αx2αx1|.{_2} \approx {\pi \over 2}\left| {1 - {{2{\alpha _{{x_2}}}} \over {2{\alpha _{{x_1}}}}}} \right| = {\pi \over 2}\left| {1 - {{{\alpha _{{x_2}}}} \over {{\alpha _{{x_1}}}}}} \right|.

We analyze the ratio α_x2/α_x1 for the two target states: αx2αx1=w(x1)−1w(x1)=1−1w(x1).{{{\alpha _{{x_2}}}} \over {{\alpha _{{x_1}}}}} = {{w\left( {{x_1}} \right) - 1} \over {w\left( {{x_1}} \right)}} = 1 - {1 \over {w\left( {{x_1}} \right)}}.

Substituting this ratio back into the expression for the final angle ϵ₂: ϵ2≈π2|1−(1−1w(x1))|=π2w(x1).{_2} \approx {\pi \over 2}\left| {1 - \left( {1 - {1 \over {w\left( {{x_1}} \right)}}} \right)} \right| = {\pi \over {2w\left( {{x_1}} \right)}}.

Since w(x₁) is large (it is at most n), ϵ₂ is a small angle. We utilize the small-angle approximation for the cosine function: cos(δ)≈1−δ22\cos (\delta ) \approx 1 - {{{\delta ^2}} \over 2} (based on Taylor Series for cos(δ)), which gives cos2(δ)=12−2δ22+δ44≈1−δ2{\cos ^2}(\delta ) = {1^2} - 2{{{\delta ^2}} \over 2} + {{{\delta ^4}} \over 4} \approx 1 - {\delta ^2}. The final probability of measuring |x₂〉 is: P(x2)≈1−ϵ22≈1−(π2w(x1))2=1−π24w(x1)2.P\left( {{x_2}} \right) \approx 1 - _2^2 \approx 1 - {\left( {{\pi \over {2w\left( {{x_1}} \right)}}} \right)^2} = 1 - {{{\pi ^2}} \over {4w{{\left( {{x_1}} \right)}^2}}}.

The difference in the final measurement probabilities ΔP is: 4ΔP=P(x1)−P(x2)≈(1−αx12)−(1−π24w(x1)2)=π24w(x1)2−αx12.\matrix{ {{\rm{\Delta }}P} \hfill & = \hfill & {P\left( {{x_1}} \right) - P\left( {{x_2}} \right)} \hfill \cr {} \hfill & \approx \hfill & {\left( {1 - \alpha _{{x_1}}^2} \right) - \left( {1 - {{{\pi ^2}} \over {4w{{\left( {{x_1}} \right)}^2}}}} \right)} \hfill \cr {} \hfill & = \hfill & {{{{\pi ^2}} \over {4w{{\left( {{x_1}} \right)}^2}}} - \alpha _{{x_1}}^2.} \hfill \cr }

To confirm that ΔP > 0, we must show that the first term in Equation 4 is greater than the second term, i.e., π24w(x1)2>αx12{{{\pi ^2}} \over {4w{{\left( {{x_1}} \right)}^2}}} > \alpha _{{x_1}}^2. By substituting the definition α_x1 = w(x₁)/‖w‖, this inequality can be rewritten as: π24w(x1)2>w(x1)2‖w‖2,{{{\pi ^2}} \over {4w{{\left( {{x_1}} \right)}^2}}} > {{w{{\left( {{x_1}} \right)}^2}} \over {{\bf{w}}{^2}}}, which is equivalent to showing that π²‖w‖² > 4w(x₁)⁴. Using the known normalization factor described earlier, ‖w‖² = 2ⁿ⁻²n(n + 1), our condition becomes: π2·2n−2n(n+1)>4(n−s2(x1))4.{\pi ^2}\cdot{2^{n - 2}}n(n + 1)\rangle 4{\left( {n - {s_2}\left( {{x_1}} \right)} \right)^4}.

The left-hand side of this inequality grows exponentially with the number of qubits n (dominated by the 2ⁿ term), while the right-hand side grows only polynomially (O(n⁴)). This condition therefore holds for any reasonably large n, which rigorously confirms that ΔP > 0 and thus P(x₁) > P(x₂).

Using mathematical induction, one can prove that the inequality remains valid for all n ≥ 6 under the worstcase condition s₂(x₁) = 0. Since practical graph problems typically involve n well above this threshold, we can confidently conclude that ΔP > 0 for any meaningful problem size.

By selecting the iteration count k₁ optimized for the preferred solution |x₁〉, the algorithm leverages this initial advantage, resulting in a final probability distribution that significantly favors the smaller CDS |x₁〉 over the larger one |x₂〉.

We summarize the results of this section with the following theorem.

To demonstrate and verify the proposed scheme, we use Qiskit [29], an open-source software framework for quantum computing, to implement the algorithm and test it using the problem instance described in the previous sections.

The problem instance is the graph G = (V, E) where V = {v₅, v₄, v₃, v₂, v₁, v₀} and E = {e₀₁, e₁₂, e₁₄, e₂₃, e₃₄, e₄₅}. In Figure 10, the visual representation of this graph is shown. To demonstrate the impact of graph complexity on solving time, we also tested our proposed method using another graph, G′. Graph G′ is formed by removing edge e₁₄ from graph G. That is, G′ = (V′ = V, E′ = E − {e₁₄}). We used Qiskit to implement the method proposed in this paper to find the smallest connected dominating set on G and G′. The library Qiskit has been adopted as a standard tool by many quantum computers, so our developed programs can be executed on real quantum computers. Given that access to real quantum computers is limited, this paper uses Qiskit’s simulation component, Qiskit Aer, to conduct our experiments. The simulation method used in this paper is matrix_product_state, one of several simulation methods available in Qiskit Aer. The simulation method matrix_product_state, originally proposed by Vidal [30], is further detailed in [31]. All simulation experiments were conducted on a computer running the Ubuntu 22.04 operating system and using an AMD Ryzen 7 3700X 8-core processor. This CPU has a clock speed of 2200 MHz and a cache size of 512 KB.

Next, we describe how to implement the proposed method for finding the connected dominating set of graph G. The circuit for finding the dominating set on G′ is similar to that of G, except for the removal of the components related to edge e₁₄. Six qubits |v〉 = |v₅v₄v₃v₂v₁v₀〉 are used to represent vertices, and six qubits |e₀₁〉, |e₁₂〉, |e₁₄〉, |e₂₃〉, |e₃₄〉, |e₄₅〉 are used to represent edges. Qubits |e₀₁e₁₂e₁₄e₂₃e₃₄e₄₅〉 are initialized to |111111〉. In the initial stage, v_i are initialized to |0〉 where 0 ≤ i ≤ 5 and Hadamard gates are used to transform each of the six vertices into a superposition state, allowing the simultaneous execution of the dominating test and the connecting test on all vertex subsets. That is H|vi〉=|0〉+|1〉2H|{v_i}\rangle = {{|0\rangle + |1\rangle } \over {\sqrt 2 }} where 0 ≤ i ≤ 5. Therefore, after completing all the processing stages and measuring v_i, there is a 12{1 \over 2} chance of obtaining a measurement value of 0 (indicating that this vertex is not included in the candidate set for the dominating set) and a 12{1 \over 2} chance of obtaining a measurement value of 1 (indicating that this vertex is included in the candidate set for the dominating set). After preparing the superposition of vertices, six additional auxiliary qubits |v^〉=|v^5v^4v^3v^2v^1v^0〉|{\bf{\hat v}}\rangle = |{{\hat v}_5}{{\hat v}_4}{{\hat v}_3}{{\hat v}_2}{{\hat v}_1}{{\hat v}_0}\rangle are used to implement the dominating test process.

Now, we are ready to implement the dominating test process. The circuit shown in Figure 22 implements the method mentioned in Section 3.2. For simplicity, we only show QC2₀₁ and QC2₁₀ in Figure 22. Using the same construction rules as in Figure 22, readers can extend this to obtain QC2₁₂, QC2₂₁, QC2₂₃, QC2₃₂, QC2₃₄, QC2₄₃, QC2₄₅, QC2₅₄, QC2₁₄, and QC2₄₁. Notice in Figure 22 that we use aux₀ and aux₁ to respectively store |vi¯〉|\overline {{v_i}} \rangle and |v^i¯〉|\overline {{{\hat v}_i}} \rangle where 0 ≤ i ≤ 5. Also, aux₀ and aux₁ can be reused in QC2₁₂, QC2₂₁, QC2₂₃, QC2₃₂, QC2₃₄, QC2₄₃, QC2₄₅, QC2₅₄, QC2₁₄, and QC2₄₁. After completing QC2₀₁, QC2₁₀, QC2₁₂, QC2₂₁, QC2₂₃, QC2₃₂, QC2₃₄, QC2₄₃, QC2₄₅, QC2₅₄, QC2₁₄, and QC2₄₁, the circuit in Figure 11(b) is employed to detect whether |v〉_i where 0 ≤ i ≤ 5 are all set to 1. If they are all set to 1, |φ_dominated〉 is set to 1; otherwise, |φ_dominated〉 is set to 0.

Figure 22.

QC2₀₁ and QC2₁₀.

After completing the implementation of the dominating test, we then implemented the connecting test. First, the circuit uses a controlled NOT gate to implement the setting of the value of v^k{{\hat v}_k} based on the quality of v_k as described in Algorithm Process Connected-test, line 4. See the leftmost CNOT in Figure 23 for illustration. Then QC3₀₁, QC3₁₀, QC3₁₂, QC3₂₁, QC3₂₃, QC3₃₂, QC3₃₄, QC3₄₃, QC3₄₅, QC3₅₄, QC3₁₄, and QC3₄₁ are implemented as shown in Figure 23. Note the repeated structure as illustrated in Figure 13. A similar circuit to that shown in Figure 23 will be repeated six times in total, with a different seed v^k{{\hat v}_k} set at the beginning of each iteration. Finally, the circuit shown in Figure 17 was implemented to integrate the six sub-circuits to determine |ϕ_connected〉.

Figure 23.

Implementation of QC3₀₁, QC3₁₀, QC3₁₂, QC3₂₁, QC3₂₃, QC3₃₂, QC3₃₄, QC3₄₃, QC3₄₅, QC3₅₄, QC3₁₄, and QC3₄₁.

After completing the connecting test, we implemented two methods to determine the size of the dominating set: one using half-adders and the other using truth tables.

In the truth table approach, we use Toffoli gates to implement the circuit for converting unary to binary representation. See Figure 24 for an illustration of the circuit used to calculate the size of the dominating set. Here, we reuse |v^2v^1v^0〉|{{\hat v}_2}{{\hat v}_1}{{\hat v}_0}\rangle to store the binary representation of the dominating set size. For example, if there are five ‘1’s in |v₅v₄v₃v₂v₁v₀〉 = |110111〉, then |v^2v^1v^0〉=|101〉|{{\hat v}_2}{{\hat v}_1}{{\hat v}_0}\rangle = |101\rangle .

Figure 24.

Implementation of the truth table approach for finding the size of the dominating set.

In Figure 25, a circuit utilizing several half adders to calculate the size of the dominating set and convert it to a binary representation is implemented. Notice that the maximum dominating set size in this example is 6, which is not exactly a power of 2. As a result, some intermediate results calculated by the half adders will not be used in determining the final result. For example, t₁₆, t₁₉, and t₂₀ can be ignored in this instance. Although t₁₆, t₁₉, and t₂₀ in Figure 25 can be disregarded and some auxiliary qubits can be reused, for the sake of clarity in demonstrating the relationships between the half adders, we present the complete input and output relationships of all the half adders.

Figure 25.

The implementation of the half-adder approach for finding the size of the dominating set.

In Figure 26, we compare the difference in computation time caused by using the truth table approach (the fast adder approach) versus the half adder approach, while keeping all other circuits identical. The x-axis represents the number of measurements, and the y-axis represents the computation time required. From the figure, we can observe that as the number of shots increases, the required time increases linearly. Additionally, the time required using the half adder approach remains consistently higher compared to the truth table approach.

Figure 26.

Comparison of the simulation time of graph G between using fast adder and half adder. The x-axis is the number of shots in the simulation, and the y-axis represents the simulation time (in seconds).

To demonstrate the impact of different edge counts in the graph, we removed edge e₁₄ from graph G to create graph G′. It is evident that the minimum connected dominating set of G is {v₁, v₄}, while the minimum connected dominating set of G′ is {v₁, v₂, v₃, v₄}. The aforementioned experiments conducted on graph G were also applied to graph G′, and the results are shown in Figure 27. We compared the total computation time required to calculate the connected dominating set and size of the connected dominating set of graph G′ using both the half adder approach and the truth table approach under different numbers of shots. Based on Figure 27, we observe a trend similar to that in Figure 26: as the number of shots increases, the computation time also increases linearly. Additionally, the time required using the truth table approach remains consistently lower than that of the half adder approach. By comparing Figure 26 with Figure 27, we observe that, for the same number of nodes, a lower number of edges results in reduced computational time. This result aligns with theoretical expectations. Although the number of nodes remains unchanged, an increase in the number of edges leads to an increase in the number of sub-circuits in QC2, QC3, and QC4, thereby extending the overall computation path length.

Figure 27.

Comparison of the simulation time of graph G′ = (V, E – {e₁₄}) between using fast adder and half adder The x-axis represents the number of shots in the simulation, and the y-axis represents the simulation time (in seconds).

Now, we try to analyze the worst case bound for the number of qubits and the universal quantum gates used in our proposed method. Note that the proposed method consists of 5 processes, namely, the state enumeration, the dominating test process, the connected test process, the size computation process, and the results output & measurement. In the following, we will examine the number of qubits used in each process. Note that, since the process of the results output & measurement takes no auxiliary qubits used, we omit it here.