Quantum computing promises transformative advances, but remains constrained by recurring misconceptions and methodological pitfalls. This paper demonstrates a fundamental incompatibility between traditional agent-based modeling (ABM) implementations and quantum optimization frameworks like Quadratic Unconstrained Binary Optimization (QUBO). Using Schelling's segregation model as a case study, we show that the standard practice of directly translating ABM state observations into QUBO formulations not only fails to deliver quantum advantage, but actively undermines computational efficiency. The fundamental issue is architectural. Traditional ABM implementations entail observing the state of the system at each iteration, systematically destroying the quantum superposition required for computational advantage. Through analysis of Schelling's segregation dynamics on lollipop networks, we demonstrate how abandoning the QUBO reduction paradigm and instead reconceptualizing the research question, from "simulate agent dynamics iteratively until convergence" to "compute minimum of agent moves required for global satisfaction", enables a faster classical solution. This structural reconceptualization yields an algorithm that exploits network symmetries obscured in traditional ABM simulations and QUBO formulations. It establishes a new lower bound which quantum approaches must outperform to achieve advantage. Our work emphasizes that progress in quantum agent-based modeling does not require forcing classical ABM implementations into quantum frameworks. Instead, it should focus on clarifying when quantum advantage is structurally possible, developing best-in-class classical baselines through problem analysis, and fundamentally reformulating research questions rather than preserving classical iterative state change observation paradigms.
Quantum computing promises transformative advances, but remains constrained by recurring misconceptions and methodological pitfalls. This paper demonstrates a fundamental incompatibility between traditional agent-based modeling (ABM) implementations and quantum optimization frameworks like Quadratic Unconstrained Binary Optimization (QUBO). Using Schelling's segregation model as a case study, we show that the standard practice of directly translating ABM state observations into QUBO formulations not only fails to deliver quantum advantage, but actively undermines computational efficiency. The fundamental issue is architectural. Traditional ABM implementations entail observing the state of the system at each iteration, systematically destroying the quantum superposition required for computational advantage. Through analysis of Schelling's segregation dynamics on lollipop networks, we demonstrate how abandoning the QUBO reduction paradigm and instead reconceptualizing the research question, from "simulate agent dynamics iteratively until convergence" to "compute minimum of agent moves required for global satisfaction", enables a faster classical solution. This structural reconceptualization yields an algorithm that exploits network symmetries obscured in traditional ABM simulations and QUBO formulations. It establishes a new lower bound which quantum approaches must outperform to achieve advantage. Our work emphasizes that progress in quantum agent-based modeling does not require forcing classical ABM implementations into quantum frameworks. Instead, it should focus on clarifying when quantum advantage is structurally possible, developing best-in-class classical baselines through problem analysis, and fundamentally reformulating research questions rather than preserving classical iterative state change observation paradigms.
Quantum computing promises transformative advances, but recurring misconceptions and methodological pitfalls limit progress. This paper examines challenges that arise when traditional agent-based modeling implementations are directly mapped to quantum optimization frameworks like quadratic unconstrained binary optimization. Using Schelling’s segregation model as a case study, we show that directly translating agent-based modeling state observations into quadratic unconstrained binary optimization formulations not only fails to deliver quantum advantage, but also actively undermines computational efficiency. The fundamental issue is architectural. Traditional agent-based modeling frameworks observe the complete system state at each iteration, which can destroy quantum superposition. This motivates reconsidering the computational structure when seeking quantum advantage. Through analysis of Schelling’s segregation dynamics on lollipop networks, we demonstrate that abandoning the quadratic unconstrained binary optimization reduction paradigm and reconceptualizing the research question—from “simulate agent dynamics iteratively until convergence” to “compute the minimum number of agent moves required for global satisfaction”—enables a faster classical solution. This structural reconceptualization yields an algorithm that exploits network symmetries obscured in traditional agent-based modeling simulations and quadratic unconstrained binary optimization formulations. It establishes an algorithmic lower bound of O(n) for the decision problem on lollipop networks, which any quantum approach must outperform to achieve advantage. This result also extends the equilibrium characterization of Schelling’s model across various graph structures. Our work emphasizes that progress in quantum agent-based modeling should not force classical implementations into quantum frameworks. Instead, it should focus on clarifying when quantum advantage is structurally possible, developing best-in-class classical baselines, and fundamentally reformulating research questions rather than preserving classical iterative paradigms.
Recent advances in quantum computing and the increasing availability of quantum hardware have substantially enhanced the practical relevance of quantum approaches to discrete optimization. Among these, the Quadratic Unconstrained Binary Optimization (QUBO) formulation provides a unifying modeling framework for a broad class of NP-hard problems and is naturally suited to quantum computing and quantum-inspired algorithms. Location science, network design, and logistics represent core application domains of discrete optimization, combining high practical impact with substantial computational challenges. In this work, we develop QUBO formulations for several fundamental problems in these domains, including a nonlinear integer formulation of the Discrete Ordered Median Problem (DOMP). Beyond their modeling relevance, these QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware. We further derive a tight bound for the penalty parameter ensuring equivalence between the QUBO formulation and its underlying integer program. Finally, we conduct a comprehensive computational study using QAOA, WS-QAOA, and classical heuristics for QUBO instances of the p-Median Problem and the Fixed-Charge Facility Location Problem (FCFLP), and introduce two effective warm-start strategies for WS-QAOA based on its linear programming relaxation.
Quadratic Unconstrained Binary Optimization (QUBO) is a central formulation for combinatorial optimization and has gained increasing attention due to its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. However, translating natural-language problem descriptions into correct QUBO formulations remains difficult, requiring the identification of binary variables, constraints, objective functions, penalty terms, and suitable penalty weights. This process is time-consuming and often demands substantial domain expertise. To address this challenge, we propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by structured or unstructured test cases. To evaluate its performance, We also introduce QUBOBench, a benchmark containing 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and canonical NP-hard problems. Experimental results show that our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%. Further analysis identifies iterative self-repair as the most important component contributing to improved performance. The data and code are open-sourced at https://quitttcat.github.io/QuantumQUBOAgent.
Quantum optimization shows significant potential in tackling complex combinatorial challenges, prompting our research exploration into the domain of quantum computing to address the Bin Packing Problem (BPP) through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work-in-progress paper outlines our proposal for a thorough study that encompasses classical bin packing formulations, initiating with the Mixed Integer Linear Program, followed by a comparative analysis of the corresponding QUBO representations, and adopting a structured approach of Quantum Annealing on the D-Wave machine. While our work is still in progress, continuous comparative analyses are being conducted to evaluate various QUBO formulations, derived from diverse classical bin packing models, aiming to identify the most efficient QUBO for addressing the BPP. On another front, efforts are dedicated to refining the solution process further, with a focus on enhancing the precision of the selected QUBO formulation.
With the development of quantum computing, the use of quantum algorithms to solve combinatorial optimization problems on quantum computers has become a major research focus. The Quadratic Unconstrained Binary Optimization (QUBO) model serves as a bridge between combinatorial optimization problems and quantum computers, and is a prerequisite for these studies. In combinatorial optimization problems, the Domination Problem (DP) is related to many practical issues in the real world, such as the fire station problem, social network theory, and so on. Additionally, the DP has numerous variants, such as independent DP, total DP, k-domination, and so forth. However, there is a scarcity of quantum computing research on these variant problems. A possible reason for this is the lack of research on QUBO modeling for these issues. This paper investigates the QUBO modeling methods for the classic DP and its variants. Compared to previous studies, the QUBO modeling method we propose for the classic DP can utilize fewer qubits. This will lower the barrier for solving DP on quantum computers. At the same time, for many variants of DP problems, we provide their QUBO modeling methods for the first time. Our work will accelerate the entry of DP into the quantum era.
Quantum computers have the potential to solve Quadratic Unconstrained Binary Optimization (QUBO) problems with lower computational complexity than classical ones. Considering the current limitations of quantum hardware, the joint use of classical and quantum paradigms could exploit both advantages. Quantum routines can make some complex tasks for classical computers feasible. For example, in the Grover Adaptive Search (GAS) procedure, the problem cost function is classically shifted iteratively, whenever a negative value is found through the quantum Grover Search (GS) algorithm, until the minimum is achieved. This quantum-classical approach is characterized by many degrees of freedom, e.g. the number of GS iterations in each call and the stop condition of the algorithm, which should be appropriately tuned for an effective and fast convergence to the optimal solution. The availability of software routines could permit the best management of the GAS parameters. This work proposes new mechanisms for GAS parameters management and compares them with the existing ones, like one available in the Qiskit framework. The proposed mechanisms can automatically arrange the parameters according to the algorithm evolution and their previous experience, thus ensuring a more frequent and faster achievement of the optimal solution. Even though these strategies can be further improved, the results are encouraging. The analysis is done to identify the best policy for different problems. It lays the foundation for designing an automatic toolchain for QUBO solving, which can obtain the best possible implementation of the GAS algorithm for each submitted problem.