Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.30991

Solving Graph Coloring Problems Using Feedback-Based Algorithm for Quantum Optimization

Yuika Kawatomi, Yukina Tatsuta, Kazue Kudo

quant-phSubmitted Sep 25, 2026• Announced Sep 28, 2026• 0 citations
arXivHTMLPDF

Abstract

The feedback-based algorithm for quantum optimization (FALQON), which is an extension of the quantum approximate optimization algorithm (QAOA), is a promising approach for finding approximate solutions to combinatorial optimization problems. The FALQON avoids the optimization of variational parameters by using information derived from iterative measurements. To solve a constrained combinatorial optimization problem, it is sometimes more efficient to use an XY mixer rather than the conventional X mixer. We applied the FALQON with the XY mixer to graph coloring and investigated the expectation value of the problem Hamiltonian, success probability of graph coloring, and fair sampling for several small-scale problems. The FALQON with the XY mixer exhibited better performance than that with the X mixer.

AI Summary

The paper studies whether constraint-preserving XY mixers improve feedback-based quantum optimization (FALQON) for graph coloring relative to transverse-X mixers. It uses one-hot color encoding: the X formulation includes a constraint penalty, while the XY mixer preserves feasibility from an initial product of W states and removes that penalty. It explicitly derives the XY feedback observable $H_{\rm f}=i[H_{\rm m},H_{\rm p}]$ and compares energy, coloring success probability, and sampling of degenerate solutions. Evidence comes from noiseless statevector simulations of three graphs with 3–5 vertices and 3–4 colors. At 800 FALQON layers, XY versus X success probabilities are 98.9% versus 72.0%, 69.3% versus 40.7%, and 87.7% versus 39.7%. Ten-layer QAOA comparisons, using medians over 20 optimization runs, give XY success probabilities of 99.6%, 38.2%, and 73.8%. Energy-versus-layer fits favor exponential decay for XY-FALQON and power-law decay for X-FALQON over the simulated range. XY-FALQON also has lower reported root-mean-square relative error from a uniform distribution over valid colorings, although this error can increase while energy decreases. The simulations fix the time step at $\Delta t=0.025$ and the X-mixer penalty at $\lambda=0.5$; both are identified as parameters that could be tuned. FALQON has not converged by 800 layers, and the observed decay forms are not claimed to persist at larger depths. The paper also notes that hardware evaluation of the feedback term incurs additional costs.

Little sign of AI-generated textIncrementalSmall numerics onlyOverclaims

Error found: The fair-sampling metric conflates failure probability with nonuniformity among successful outcomes, so its smaller values do not establish the claimed fair-sampling advantage. The conclusion generalizes the observed advantage to one-hot-constrained problems without evidence beyond three tiny noiseless instances and a fixed, untuned X-mixer penalty.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
13 pages, 5 figures

Related papers

Efficient hybrid variational quantum algorithm for solving graph coloring problem

Dongmei Liu, Li, Jian, Cheng, Xiubo +3 more

In the era of Noisy Intermediate Scale Quantum (NISQ) computing, available quantum resources are limited. Many NP-hard problems can be efficiently addressed using hybrid classical and quantum computational methods. This paper proposes a hybrid variational quantum algorithm designed to solve the $k$-coloring problem of graph vertices. The hybrid classical and quantum algorithms primarily partition the graph into multiple subgraphs through hierarchical techniques. The Quantum Approximate Optimization Algorithm (QAOA) is employed to determine the coloring within the subgraphs, while a classical greedy algorithm is utilized to find the coloring of the interaction graph. Fixed coloring is applied to the interaction graph, and feedback is provided to correct any conflicting colorings within the subgraphs. The merging process into the original graph is iteratively optimized to resolve any arising conflicts. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring of arbitrary graph vertices. Through experimental analysis, we demonstrate the effectiveness of the algorithm, highlighting the rapid convergence of conflict evolution and the fact that iterative optimization allows the classical algorithm to approximate the number of colorings. Finally, we apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.

arXiv:2504.21335•Apr 30, 2025•2 citations

Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning

Michael Mancini, Shabnam Sodagari

Feedback-based adaptive quantum optimization (FALQON) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum devices, but prior studies report that standard fixed-parameter schedules can require relatively deep circuits to reach strong solution quality. We study Optimal FALQON, a layer-wise formulation that treats the time-step $δ_k$ and scaling parameter $w_k$ as classical decision variables optimized per layer. The benchmark uses all 94 non-isomorphic 3-regular graphs with 12 vertices under 8192-shot simulation and compares standard FALQON, Optimal FALQON, and QAOA/QAOA-MA Powell runs warm-started from FALQON-derived schedules. Across approximation ratio, success probability, evaluation-normalized efficiency, and layer-normalized efficiency, Optimal FALQON substantially improves on standard FALQON, and Optimal-FALQON warm starts substantially improve on standard-FALQON warm starts.

quant-pharXiv:2605.08332•May 11, 2026•1 citation

Solving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum Algorithms

Young-Hyun Oh, Hamed Mohammadbagherpoor, Patrick Dreher +3 more

The design of a good algorithm to solve NP-hard combinatorial approximation problems requires specific domain knowledge about the problems and often needs a trial-and-error problem solving approach. Graph coloring is one of the essential fields to provide an efficient solution for combinatorial applications such as flight scheduling, frequency allocation in networking, and register allocation. In particular, some optimization algorithms have been proposed to solve the multi-coloring graph problems but most of the cases a simple searching method would be the best approach to find an optimal solution for graph coloring problems. However, this naive approach can increase the computation cost exponentially as the graph size and the number of colors increase. To mitigate such intolerable overhead, we investigate the methods to take the advantages of quantum computing properties to find a solution for multi-coloring graph problems in polynomial time. We utilize the variational quantum eigensolver (VQE) technique and quantum approximate optimization algorithm (QAOA) to find solutions for three combinatorial applications by both transferring each problem model to the corresponding Ising model and by using the calculated Hamiltonian matrices. Our results demonstrate that VQE and QAOA algorithms can find one of the best solutions for each application. Therefore, our modeling approach with hybrid quantum algorithms can be applicable for combinatorial problems in various fields to find an optimal solution in polynomial time.

arXiv:1911.00595•Nov 1, 2019•30 citations

XY vs X mixer in Quantum Alternating Operator Ansatz for optimization problems with constraints

Zhihui Wang, Nicholas C. Rubin, Eleanor Gilbert Rieffel

Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.

Bulletin of the American Physical Society•Mar 8, 2018•0 citations

Design of quantum approximate optimization algorithm for graph multi coloring problem

Gunsik Min, Jun Heo

We propose a technique to solve the problem of graph multi coloring, which is a problem corresponding to channel allocation problem, with the quantum approximate optimization algorithm(QAOA). QAOA is an algorithm that solve an optimization problem. Among the optimization problems, this algorithm is specialized as solving the quadratic unconstrained binary optimization(QUBO) problems. It is designed to find approximate solutions to combinatorial optimization problems by leveraging quantum resources. In general, it is evaluated to have strengths in optimizing the base of optimal path exploration, small factor resolution, and mass data exploration. The study on coloring problem using digital algorithm has solved the problem of coloring by replacing the graph with simple graph or applying algorithm or reducing the number of nodes. Despite these efforts, however, the digital algorithm that solves the coloring problem studied so far has not achieved satisfactory performance by some limitations. Therefore, in order to overcome these limitations, this paper will show the result of solving multi coloring problem by reducing initial state dimension of the QAOA

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 11, 2023•1 citation

Approximation Meets Quantum: A Parameterized Framework for Large-Scale Graph Coloring

Rahul Pitale, Kapil Tajane, Prashant Ahire +4 more

Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.

Asian Conference on Innovation in Technology (ASIANCON)•Aug 22, 2025•0 citations
The feedback-based algorithm for quantum optimization (FALQON), which is an extension of the quantum approximate optimization algorithm (QAOA), is a promising approach for finding approximate solutions to combinatorial optimization problems. The FALQON avoids the optimization of variational parameters by using information derived from iterative measurements. To solve a constrained combinatorial optimization problem, it is sometimes more efficient to use an XY mixer rather than the conventional X mixer. We applied the FALQON with the XY mixer to graph coloring and investigated the expectation value of the problem Hamiltonian, success probability of graph coloring, and fair sampling for several small-scale problems. The FALQON with the XY mixer exhibited better performance than that with the X mixer.
The paper studies whether constraint-preserving XY mixers improve feedback-based quantum optimization (FALQON) for graph coloring relative to transverse-X mixers. It uses one-hot color encoding: the X formulation includes a constraint penalty, while the XY mixer preserves feasibility from an initial product of W states and removes that penalty. It explicitly derives the XY feedback observable Hf=i[Hm,Hp]H_{\rm f}=i[H_{\rm m},H_{\rm p}]Hf​=i[Hm​,Hp​] and compares energy, coloring success probability, and sampling of degenerate solutions.
Evidence comes from noiseless statevector simulations of three graphs with 3–5 vertices and 3–4 colors. At 800 FALQON layers, XY versus X success probabilities are 98.9% versus 72.0%, 69.3% versus 40.7%, and 87.7% versus 39.7%. Ten-layer QAOA comparisons, using medians over 20 optimization runs, give XY success probabilities of 99.6%, 38.2%, and 73.8%. Energy-versus-layer fits favor exponential decay for XY-FALQON and power-law decay for X-FALQON over the simulated range. XY-FALQON also has lower reported root-mean-square relative error from a uniform distribution over valid colorings, although this error can increase while energy decreases.
The simulations fix the time step at Δt=0.025\Delta t=0.025Δt=0.025 and the X-mixer penalty at λ=0.5\lambda=0.5λ=0.5; both are identified as parameters that could be tuned. FALQON has not converged by 800 layers, and the observed decay forms are not claimed to persist at larger depths. The paper also notes that hardware evaluation of the feedback term incurs additional costs.
In the era of Noisy Intermediate Scale Quantum (NISQ) computing, available quantum resources are limited. Many NP-hard problems can be efficiently addressed using hybrid classical and quantum computational methods. This paper proposes a hybrid variational quantum algorithm designed to solve the kkk-coloring problem of graph vertices. The hybrid classical and quantum algorithms primarily partition the graph into multiple subgraphs through hierarchical techniques. The Quantum Approximate Optimization Algorithm (QAOA) is employed to determine the coloring within the subgraphs, while a classical greedy algorithm is utilized to find the coloring of the interaction graph. Fixed coloring is applied to the interaction graph, and feedback is provided to correct any conflicting colorings within the subgraphs. The merging process into the original graph is iteratively optimized to resolve any arising conflicts. We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve kkk-coloring of arbitrary graph vertices. Through experimental analysis, we demonstrate the effectiveness of the algorithm, highlighting the rapid convergence of conflict evolution and the fact that iterative optimization allows the classical algorithm to approximate the number of colorings. Finally, we apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.
Feedback-based adaptive quantum optimization (FALQON) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum devices, but prior studies report that standard fixed-parameter schedules can require relatively deep circuits to reach strong solution quality. We study Optimal FALQON, a layer-wise formulation that treats the time-step δkδ_kδk​ and scaling parameter wkw_kwk​ as classical decision variables optimized per layer. The benchmark uses all 94 non-isomorphic 3-regular graphs with 12 vertices under 8192-shot simulation and compares standard FALQON, Optimal FALQON, and QAOA/QAOA-MA Powell runs warm-started from FALQON-derived schedules. Across approximation ratio, success probability, evaluation-normalized efficiency, and layer-normalized efficiency, Optimal FALQON substantially improves on standard FALQON, and Optimal-FALQON warm starts substantially improve on standard-FALQON warm starts.
The design of a good algorithm to solve NP-hard combinatorial approximation problems requires specific domain knowledge about the problems and often needs a trial-and-error problem solving approach. Graph coloring is one of the essential fields to provide an efficient solution for combinatorial applications such as flight scheduling, frequency allocation in networking, and register allocation. In particular, some optimization algorithms have been proposed to solve the multi-coloring graph problems but most of the cases a simple searching method would be the best approach to find an optimal solution for graph coloring problems. However, this naive approach can increase the computation cost exponentially as the graph size and the number of colors increase. To mitigate such intolerable overhead, we investigate the methods to take the advantages of quantum computing properties to find a solution for multi-coloring graph problems in polynomial time. We utilize the variational quantum eigensolver (VQE) technique and quantum approximate optimization algorithm (QAOA) to find solutions for three combinatorial applications by both transferring each problem model to the corresponding Ising model and by using the calculated Hamiltonian matrices. Our results demonstrate that VQE and QAOA algorithms can find one of the best solutions for each application. Therefore, our modeling approach with hybrid quantum algorithms can be applicable for combinatorial problems in various fields to find an optimal solution in polynomial time.
Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.
We propose a technique to solve the problem of graph multi coloring, which is a problem corresponding to channel allocation problem, with the quantum approximate optimization algorithm(QAOA). QAOA is an algorithm that solve an optimization problem. Among the optimization problems, this algorithm is specialized as solving the quadratic unconstrained binary optimization(QUBO) problems. It is designed to find approximate solutions to combinatorial optimization problems by leveraging quantum resources. In general, it is evaluated to have strengths in optimizing the base of optimal path exploration, small factor resolution, and mass data exploration. The study on coloring problem using digital algorithm has solved the problem of coloring by replacing the graph with simple graph or applying algorithm or reducing the number of nodes. Despite these efforts, however, the digital algorithm that solves the coloring problem studied so far has not achieved satisfactory performance by some limitations. Therefore, in order to overcome these limitations, this paper will show the result of solving multi coloring problem by reducing initial state dimension of the QAOA
Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.