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.
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.
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.
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 and physics-inspired solvers provide specialized sampling interfaces for Ising and quadratic unconstrained binary optimization models, but constrained optimization requires broader coordination and certification. This survey uses classical decomposition to analyze how such solvers can be integrated into hybrid quantum-classical algorithms. We distinguish formal decomposition, reformulation and reduction, and computational orchestration. For each interface, we ask what the transformation preserves, which assumptions make the outer method converge, and which certificates the implemented inner routine supplies. The central questions are whether that information meets the classical algorithm's requirements and whether hybridization improves solution quality or total cost enough to justify its coordination overhead. Benders decomposition, column generation, graph reduction, and copositive methods illustrate this distinction by separating heuristic proposals from classical certification. We also distinguish component effects within a fixed wrapper, reduction--solver interactions, and comparisons between complete quantum-enabled and classical systems. The analyzed studies provide conditional component benefits and favorable co-design evidence, but do not establish transferable end-to-end superiority over strong classical comparators. The resulting framework identifies opportunities for constraint programming and operations research in structure-preserving design, safeguarded hybrid algorithms, and controlled benchmarking.
Graph partitioning is a fundamental problem in various fields, including computer graphics, high-performance computing, and network design. Traditional graph partitioning algorithms often suffer from high computational complexity, particularly when dealing with large and complex graphs. This research investigates the potential of quantum-inspired optimization techniques, specifically leveraging concepts from quantum annealing, to accelerate the graph partitioning process. We formulate the graph partitioning problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, allowing us to simulate the behavior of a quantum annealer on classical hardware. The core of our approach involves mapping the graph's connectivity structure onto a QUBO, representing nodes as binary variables and edges as constraints. By exploiting the inherent parallelism of quantum annealing, we aim to find optimal or near-optimal partitions significantly faster than conventional methods. The results demonstrate the feasibility and potential advantages of this quantum-inspired strategy for graph partitioning, offering a promising direction for tackling computationally intensive graph problems.
The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.
This paper presents the application of a quantum optimization technique to a mining problem. A mine planning problem in an open-pit mine is reformulated as a Quadratic Unconstrained Binary Optimization (QUBO) model and solved using the Quantum Approximate Optimization Algorithm (QAOA). The problem seeks to maximize the monetary benefit while respecting precedence constraints between blocks and extraction capacity limitations. The methodology is validated through a fictitious copper deposit case study, where the quantum algorithm identifies the optimal extraction, a result validated with Gurobi solver. Although the approach demonstrates technical feasibility, the scalability limitations of current quantum simulators restrict applications to large-scale problems. This work establishes fundamental foundations for applying quantum computing to mine planning challenges and represents a step toward leveraging quantum computational advantages for NP-hard problems in the mining industry.