Grover Algorithm-based Quantum Scheduling Framework for Constrained Graph Coloring

2.1 QAOA

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm designed to tackle optimization problems by combining classical and quantum processing (Zhou et al., 2020). To solve graph coloring problem using QAOA, it is necessary to formulate the cost Hamiltonian, which represents the number of conflicts, in this case is adjacent vertices with the same color. The cost Hamiltonian is defined as:

where δ(c_i, c_j) is an indicator function that takes the value 1 if the colors assigned to vertices i and j are the same, and 0 otherwise. This Hamiltonian captures the essence of the graph coloring problem by penalizing configurations in which adjacent vertices are assigned the same color (Lucas, 2014).

In QAOA, the quantum system is initialized in a superposition of all possible color assignments. The algorithm alternates between applying the Cost Hamiltonian H_c and a Mixer Hamiltonian H_M, which introduces transitions between different states. The mixer Hamiltonian is typically chosen to be:

where X_v is the Pauli-X operator acting on the qubit corresponding to vertex v. This operator ensures that the system explores different color assignments by flipping the qubit states.

The QAOA is parameterized by angles γ and β, which are optimized to minimize the expected value of the cost Hamiltonian (Farhi et al., 2014). The quantum state after p steps of the algorithm is given by:

where $$ U_C\left(\gamma \right)=e^{-i\gamma H_C}$$ and $$ U_M\left(\beta \right)=e^{-i\beta H_M}$$. This process encodes the graph coloring problem into a quantum algorithm, alternating between cost and mixer Hamiltonians to gradually converge towards a solution.

Lastly, the optimization process involves finding the value of γ and β that minimize the expectation value of the cost Hamiltonian, which is expressed as:

This expected value represents the total number of conflicts in the current solution, and minimizing it leads to an optimal or near-optimal graph coloring solution.

2.2 Quantum Annealing

In Quantum Annealing, the system starts in a simple quantum state, and then slowly evolves to the final Hamiltonian that encodes the solution to the problem. The evolution is governed by a time-dependent Hamiltonian H_(t), which interpolates between an initial Hamiltonian H_i and the cost Hamiltonian H_c:

where t is the time and T is the total annealing time. The system is initialized in the ground state of H_i, which is easy to prepare. Over time, H_(t) transitions from the initial Hamiltonian to the cost Hamiltonian H_c, with the goal of reaching the ground state of H_c, which corresponds to the optimal graph coloring configuration.

The initial Hamiltonian H_i typically takes the form of a transverse field, which promotes quantum tunneling between different states:

where $$ {\sigma }_v^x$$ is the Pauli-X operator applied to vertex v, enabling transitions between different color states for each vertex during the annealing process.

The annealing process is designed to find the minimum of the final Hamiltonian H_c, which represents the optimal or near-optimal solution to the graph coloring problem. By slowly evolving the Hamiltonian and maintaining the system in the ground state, quantum annealing exploits quantum tunneling to overcome local minima and explore the solution space efficiently.

2.3 Grover’s Algorithm

Grover's Algorithm is designed for searching an unstructured database where the correct solution is known but needs to be found among multiple possibilities, such as identifying the correct coloring in a graph coloring problem (Mukherjee, 2022). Grover’s algorithm leverages quantum amplitude amplification to efficiently search through the solution space, offering a quadratic speedup over classical search methods (Chakrabarty et al., 2017).

The solution space for a graph with n vertices and k possible color per vertex contains kⁿ possible color assignments. Let the set of possible colorings be denoted as:

where each x₁ represents a unique coloring assignment for the vertices. Grover’s algorithm seeks to find the valid coloring from this set.

The essential part of Grover’s algorithm is the oracle function, which identifies valid colorings by checking if adjacent vertices share the same color. The oracle applies a phase flip to the valid solutions, denoted as:

This oracle marks valid graph colorings by flipping their phase, differentiating them from invalid solutions.

Grover’s algorithm begins by initializing a quantum state in a superposition of all possible colorings:

This superposition equally represents all possible color assignments. The algorithm iteratively applies two key operations: the oracle O, which identifies valid colorings, and the diffusion operator D, which amplifies the amplitude of valid solutions (Perkowski, 2022). The diffusion operator can be expressed as:

where I is the identity matrix, and the operator reflects the quantum state about the average amplitude of all states.

3.1 Initialization

In the initialization phase of Grover's algorithm, we aim to define the structure of the quantum states representing the solution space. The representation of each product is encoded using three qubits, where the first two qubits, q₀ and q₁, denote the machine assigned to the product, and the third qubit, q₂ represents the day of production.

We initialize the quantum state to represent all possible assignments of machines and production days for each product. This is achieved by preparing a uniform superposition over all possible qubit states using the Hadamard gate. For each product i, the state $$ \left|q_0^i,q_1^i,q_2^i\right.⟩$$ represents a binary encoding of the machine and day assignment, where $$ q_0^i{q}_1^i=\left\{\mathrm{00,01,10,11}\right\}$$corresponds to the four machines available, and $$ q_2^i=\left\{\mathrm{0,1}\right\}$$encodes two possible days for production. The superposition is generated as follows:

where n = 3k (with k being the number of products), ensuring that each combination of machine and day for every product is equally probable. Thus, x takes on all possible binary combinations of machine and day assignments for all k products. the sum runs over all 2ⁿ possible states in the superposition, representing all potential machine and day allocations for each product. In our case, k = 4 products, so x would take values from 000000000000 to 111111111111, representing different combinations of machine and day assignments for the products.

This initialization sets up the quantum state with all possible solutions, from which Grover's algorithm will search for the valid coloring of the graph where adjacent nodes (representing products) are assigned distinct machine-day pairs. This ensures that no two adjacent nodes share the same machine or day, as dictated by the scheduling constraints.

3.2 Oracle

In addition to ensure that adjacent nodes in the graph are assigned different colors (representing machines), our oracle incorporates a summation process to verify whether the total processing time assigned to any machine exceeds its allowable daily limit of 6 hours. This is achieved using a quantum full-adder circuit that performs binary addition to sum the processing times of products assigned to adjacent nodes.

The binary addition process is carried out by encoding the processing times as binary numbers in quantum registers. For instance, we add two products with processing times 4 hours (binary 100) and 3 hours (binary 011), resulting in a total of 7 (binary 0111). The summation is performed bit by bit using a full-adder structure. For each bit position i, the quantum circuit calculates both the sum S_i and the carry C_i for the next bit. The sum for the i-th qubit is given by the equation:

where a_i and b_i are the i-th bits of the processing times a and b, respectively, and C_i-1 is the carry from previous bit. For the least significant bit (LSB), the carry is initialized to zero (C_-1 = 0). The quantum circuit uses controlled-NOT (CX) gates to implement the XOR operation, and the sum is stored in a separate quantum register.

The carry for each bit is computed using a combination of AND and OR operations, which are implemented in the quantum using Toffoli (CCX) gates. Mathematically, the carry for bit i is expressed as:

This equation ensures that a carry is propagated if both a_i and b_i are 1, or if there was a carry from the previous bit that combines with either a_i or b_i. In the circuit, the first part $$ \left(a_i\wedge b_i\right)$$ is implemented using a CCX gate, and the second part $$ C_{i-1}\wedge \left(a_i\oplus b_i\right)$$ is handled by a series of CX and CCX gates.

Based on equation (12), for the LSB, the sum is calculated using the operation $$ S_0=a_0\oplus b_0$$ and the carry is computed as $$ C_0=\left(a_0\wedge b_0\right)$$. The circuit used for the summation process is shown in <Figure 2>. In the circuit, this is done by applying CX gates to qubits a₀ and b₀ to compute the XOR, and a CCX gate to compute the carry. For the second bit, the sum is calculated as $$ S_1=a_1\oplus b_1\oplus C_0$$ and the carry is $$ C_1=\left(a_1\wedge b_1\right)\wedge \left(C_0\wedge \left(a_1\oplus b_1\right)\right)$$. The CX gates are again used for XOR operations, while CCX gates manage the carry propagation.

Figure 2.

Quantum circuit for summation process of product’s processing time.

The process continues for the most significant bit (MSB), where the final carry C₂ is propagated to detect any overflow. For instance, if the circuit is tasked with adding $$ a_2{a}_1{a}_0={100}_2$$ (4 hours) and b = 011₂ (3 hours), the result is $$ S_3{S}_2{S}_1{S}_0={0111}_2$$ which equals 7 hours in decimal form. Once the summation is complete, the result is stored in a quantum register and then the quantum circuit compares the summation result to the time limitation of the machine, which is set to 6 hours.

The quantum circuit for comparison implements custom gates and controlled operations to determine whether the input number is less than or equal to 6, marking the state as valid if the condition is satisfied. The details of the circuit are presented in <Figure 3>.

Figure 3.

Quantum circuit for checking whether the summation result exceed the time limitation of each machine.

The circuit operates on two main sets of qubits, the qubits $$ a_2{a}_1{a}_0$$ which represents the result of the previous summation operation that we aim to compare, and the qubits $$ b_2{b}_1{b}_0$$ which are fixed to represent the binary value of 6. The circuit also involves ancilla qubits which serve as intermediate storage to facilitate the comparison process. These ancilla qubits play a crucial role in propagating information about the intermediate steps of the binary comparison. Additionally, a control qubit c is included to store the final result of the comparison and will be measured to determine if the number is valid based on the comparison criteria.

The first stage of the circuit involves preparing the binary value of 6 using X-gates. An X-gate is a quantum operation that flips the state of a qubit. Initially, the qubits are prepared in the state |0> and the X-gate flips the required qubits to |1> to match the binary representation of 6. No X-gates are applied to b₂ and b₁ since they are already in the state |1> but an X-gate is applied to b₀ to ensure that it is in the state |0> completing the binary setup for 6. The primary comparison between the two binary numbers is performed using custom quantum gates, labeled U< and U0. The details of U< gates and U0 gates can be seen in <Figure 4>.

Figure 4.

The gate U< (left) checks whether the binary number a2a1a0 is less than the corresponding bits of a2a1a0, while the gate U0 (right) checks whether the binary number is equal to 6.

The final result of the comparison is stored in the ancilla qubits. If they contain the state |1> this indicates that the binary number represented by $$ a_2{a}_1{a}_0$$ is greater than 6, marking it as an invalid solution. If they contain |0> it means the number is less than or equal to 6.

3.3 Diffusion

The last step of Grover’s algorithm is known as diffusion or amplitude amplification. This process is applied to the variable registers after the oracle has marked the correct solution by inverting its amplitude. The purpose of diffusion is to increase the probability of measuring the marked state by amplifying its amplitude and reducing the amplitudes of the non-solution states.

The diffusion operator is calculated by using (10). After each application of the oracle, the diffusion process increases the likelihood of finding the solution that does not violate the time limitation of 6 hours per machine, ensuring efficient machine scheduling.

3.4 Algorithm Overview

To provide a clear and concise overview of the proposed Grover-based quantum scheduling algorithm, we present its detailed procedural steps in Algorithm 1. This algorithm integrates the core components described above, including initialization, oracle construction with coloring and capacity constraints, and the diffusion operator, into a unified framework. The pseudocode highlights the iterative nature of Grover’s search adapted for the scheduling problem and illustrates how constraint checks and amplitude amplification are systematically performed to efficiently identify feasible and optimal scheduling solutions.

4.1 4 Nodes Problem

Let G=({1,2,3,4},{12,13,24,34}), we utilized 34 qubits that were allocated as follows: 12 qubits representing the nodes, 3 qubits for carry operations, 8 qubits for sum calculations, 3 qubits encoding the time limit, and 7 ancilla qubits. The initial state in Grover's algorithm is a uniform superposition over all possible solutions, where each solution corresponds to a distinct binary string from |000000000000⟩ to |111111111111⟩. The total number of possible states N in 12-qubit system is $$ N=2^{12}=4096$$.

At the beginning of Grover’s search, the algorithm starts by preparing a uniform superposition of all states. The amplitude of each state in this superposition is equal, and due to the normalization condition, the amplitude α of each state is $$ \alpha =\frac{1}{\sqrt{N}}=\frac{1}{\sqrt{4096}}=\frac{1}{64}$$. After applying the oracle, the amplitudes of the valid states are inverted, while the invalid states remain unchanged. This condition expresses as $$ {\alpha }_{afteroracle}=\left[\frac{-1}{64},\frac{1}{64},\frac{-1}{64},\cdots ,\frac{-1}{64},\right]$$.

Following oracle step, the diffusion operator is applied. The diffusion operator amplifies the amplitude of valid states while suppressing the invalid ones. This amplification process works by reflecting the amplitudes of all states about the mean, which results in an increase in the amplitude of valid states and a decrease in the amplitude of invalid states. The calculation of the mean amplitude α can be expressed as:

Next, we apply the diffusion operator to each amplitude by reflecting it around the mean amplitude $$ \overline{\alpha }$$. After executing the circuit, the result with the highest amplitude was 001010010000, corresponding to a valid solution for the graph coloring problem, as shown in <Figure 5>. This binary string represents the assignment of machines and days for each node, and the associated measurement result frequency was 8. This means that in the sampling process, the quantum state 001010010000 appeared most frequently, indicating that it is the most likely valid solution found by Grover's search.

Figure 5.

The result of proposed framework for 4 nodes problem after running the circuit on ibmq_brisbane processor provided by the IBM Quantum Experience.

As previously noted, each node is represented by 3 qubits, with the first two qubits indicating the machine and the last qubit indicating the day. Based on this representation, product 1 is allocated to machine 1 on day 2, product 2 to machine 2 on day 1, product 3 to machine 2 on day 1, and product 4 to machine 1 on day 1. The resulting allocation is illustrated in <Figure 6>, providing a visual representation of the product-machine-day assignments.

Figure 6.

Visual representation of product-machine-day allocation for 4 nodes.

The obtained result satisfies all the problem constraints, ensuring that no two adjacent nodes are assigned to the same machine or the same day and the total processing time for each machine within a single day does not exceed the maximum limit of 6 hours.

4.2 5 Nodes Problem

Let G=({1,2,3,4,5},{12,13,14,24,25,35,45}), we utilized 39 qubits that were allocated as follows: 15 qubits representing the nodes, 3 qubits for carry operations, 12 qubits for sum calculations, 3 qubits encoding the time limit, and 7 ancilla qubits. <Figure 7> presents the results of these executions.

Figure 7.

The result of proposed framework for 5 nodes problem after running the circuit on ibmq_brisbane processor provided by the IBM Quantum Experience.

After executing the circuit, the result with the highest amplitude was 100110000000001, corresponding to a valid solution for the graph coloring problem, as shown in <Figure 7>. This binary string represents the assignment of machines and days for each node, and the associated measurement result frequency was 10. This means that in the sampling process, the quantum state 100110000000001 appeared most frequently, indicating that it is the most likely valid solution found by Grover's search. The resulting allocation is illustrated in <Figure 8>, providing a visual representation of the product-machine-day assignments.

Figure 8.

Visual Representation of Product-machine-day Allocation for 5 Nodes

Based on <Figure 7>, product 1 is allocated to machine 2 on day 1, product 2 to machine 3 on day 1, product 3 to machine 1 on day 1, product 4 to machine 1 on day 1 and product 5 to machine 1 on day 2. The obtained result satisfies all the problem constraints, ensuring that no two adjacent nodes are assigned to the same machine or the same day and the total processing time for each machine within a single day does not exceed the maximum limit of 6 hours.

<Table 1> presents a comparison of 4-node and 5-node graph for solving the graph coloring problem using Grover's algorithm with k=8 colors. The comparison is based on four key aspects: Possible States, Initial Amplitude, Time Complexity, and Circuit Depth. The number of Possible States represents the size of the search space, which increases exponentially with the number of nodes, calculated as k^nodes. For the 4 nodes graph, there are 4,096 possible states, while for the 5 nodes graph, the search space expands to 32,768 states. The Initial Amplitude, given by $$ 1/\sqrt{N}$$, where N is the number of possible states, is approximately 0.015625 for the 4 nodes graph and decreases to 0.005525 for the 5 nodes graph. This reduction in amplitude reflects the greater difficulty of identifying a solution as the search space grows.

Table 1.

Comparison of 4-node and 5-node Graph Coloring Problem

Time Complexity in Grover's algorithm scales proportionally to $$ O\left(\sqrt{N}\right)$$. Consequently, the time complexity for the 4 nodes graph is O(64), which increases to O(181) for the 5 nodes graph. This aligns with the square root relationship between the number of states and the number of Grover iterations needed. The Circuit Depth, which indicates the number of quantum gates required, also increases from 56 for the 4 nodes graph to 80 for the 5 nodes graph, reflecting the additional computational required to handle a larger problem instance.

4.3 Comparison With Other Quantum Algorithm

To evaluate the performance and suitability of our algorithm for solving the graph coloring problem on quantum processors, two performance metrics are employed, accuracy and success rate. Accuracy quantifies the proportion of measurement outcomes that correspond to feasible schedules satisfying both the graph coloring constraint (no two adjacent products are assigned to the same machine) and the machine capacity constraint (the total processing time allocated to any machine within a single day does not exceed 6 hours). Success rate measures the consistency of the algorithm in producing a valid schedule as its most probable outcome. Specifically, it is computed as the fraction of independent experimental runs in which the highest-frequency measurement result satisfies all problem constraints. It is also essential to compare it with other well-known quantum algorithms, including Grover's algorithm, Quantum Approximate Optimization Algorithm (QAOA), and Quantum Annealing.

The results obtained from solving the graph coloring problem using various quantum algorithms demonstrate distinct performance patterns can be seen in <Figure 9>.

Figure 9.

Accuracy Comparison between all Models for 4 Nodes

The proposed algorithm consistently achieved higher success rates, with values ranging from 0.35 to 0.75, and an average value around 0.50 to 0.60. The success rates observed in our experiments are consistent with the influence of noise inherent to noisy intermediate-scale quantum (NISQ) processors. The ibmq_brisbane device, on which our framework was executed, is subject to several dominant error sources, including single-qubit and two-qubit gate infidelities, qubit relaxation, dephasing, and readout errors. These noise processes cumulatively reduce the fidelity of the quantum state, decreasing the amplitude of marked solutions and thereby lowering the measured success probability of Grover’s algorithm. This phenomenon aligns with the recent theoretical and experimental findings of Sun (2024), who demonstrated a quantitative complementarity between Grover’s success probabilities and decoherence rate. Specifically, the maximum success probability depends on an equation involving the decoherence rate and the total runtime. As noise gets worse (larger decoherence rate), the ability of the algorithm to amplify the correct answer drops, reducing success rates. To mitigate these effects, several strategies were adopted. First, we employed qubit mapping and transpilation at optimization level 0 to minimize unnecessary SWAP operations, thereby reducing circuit depth and exposure to decoherence. Second, measurement error mitigation techniques provided by Qiskit were applied to calibrate readout errors based on the device’s current calibration data. Third, we minimized the use of multi-controlled gates by optimizing the oracle and comparator circuits, as such gates are particularly error-prone on NISQ devices.

In comparison, Grover's algorithm displayed moderate success, with results fluctuating between 0.30 and 0.60. While Grover's algorithm performed well in some cases, it was less consistent overall, suggesting that it is effective but not as stable as the proposed method.

On the other hand, the Quantum Approximate Optimization Algorithm (QAOA) exhibited a lower overall performance, with values ranging between 0.25 and 0.50. Finally, quantum annealing produced stable yet modest results, with values tightly between 0.30 and 0.35. While quantum annealing demonstrated reliability, its performance was consistently lower than that of the other algorithms. In terms of solving graph coloring, quantum annealing performs well in satisfying adjacent nodes constraint with optimal value, but this lead fails to satisfy the machine time limitation.

The accuracy comparison for 5 nodes problem can be seen in <Figure 10>. The plot reveals that the Proposed Algorithm consistently achieves higher accuracy than the other methods across multiple runs, often reaching values around 0.5 to 0.7, although it shows some variability. This suggests that while it may be sensitive to noise of real quantum computer, it generally outperforms the other approaches in terms of accuracy. Grover’s Algorithm demonstrates moderate variability, typically in the range of 0.3 to 0.5, providing stable results but not reaching the higher accuracy levels seen with the Proposed Algorithm. QAOA (Quantum Approximate Optimization Algorithm) fluctuates significantly, with accuracy values between 0.2 and 0.5. Quantum Annealing, on the other hand, displays the most consistent performance, in the range of 0.3 to 0.4 across all runs. For solving graph coloring, quantum annealing performs effectively in meeting the adjacent nodes constraint with optimal values. However, this success often results in failing to satisfy the machine time limitation.

Figure 10.

Accuracy Comparison between all models for 5 nodes

In summary, the proposed algorithm demonstrated superior performance and higher accuracy compared to other quantum algorithms, such as Grover's algorithm, the Quantum Approximate Optimization Algorithm (QAOA), and quantum annealing, making it a promising approach for solving the graph coloring problem with additional constraint in quantum computing.