An emerging class of specialized hardware called Ising machines offers a novel approach to tackling computationally intractable combinatorial optimization problems.Specifically, Ising machines are designed to solve problems formulated as the quadratic unconstrained binary optimization (QUBO) problem.However, their widespread practical adoption is currently hindered by several critical obstacles, including the challenge of achieving high solution accuracy, the absence of fair and robust comparative frameworks against traditional optimization methods, and limitations in handling large-scale problems.This dissertation addresses these fundamental challenges through a software-centric approach centered on preprocessing and postprocessing techniques applied to the input and output of Ising machines.This work makes three key contributions.First, a novel preprocessing methodology is proposed to improve accuracy and scalability by linearizing QUBO problems.This technique reduces quadratic terms in the input problem through the extraction of variable ordering relationships, which simplifies the problem structure, enables compact embedding, and offers broader applicability than existing variable reduction methods.The method is successfully validated on QUBO and multi-dimensional knapsack problem instances.Second, a twostage postprocessing methodology is developed to yield feasible, high-quality solutions for constrained problems by adapting basic heuristic principles.This enabled the first fair benchmark of a state-of-the-art Ising machine against traditional heuristics on the quadratic knapsack problem, successfully obtaining high-quality solutions on instances of size up to 2,000 variables.Finally, coefficient reduction techniques for suppressing errors in quantum annealers under realistic minor-embedding conditions are systematically validated.Our findings clarify the practical effectiveness of these methods in improving sample quality on real devices, a crucial area that had been largely unexamined.Collectively, these contributions provide essential software methodologies that bridge the gap between the theoretical promise of Ising machines and their effective real-world application, establishing a foundation for future advancements of Ising machines such as software-hardware co-design to achieve greater improvements in accuracy and scalability.
An emerging class of specialized hardware called Ising machines offers a novel approach to tackling computationally intractable combinatorial optimization problems.Specifically, Ising machines are designed to solve problems formulated as the quadratic unconstrained binary optimization (QUBO) problem.However, their widespread practical adoption is currently hindered by several critical obstacles, including the challenge of achieving high solution accuracy, the absence of fair and robust comparative frameworks against traditional optimization methods, and limitations in handling large-scale problems.This dissertation addresses these fundamental challenges through a software-centric approach centered on preprocessing and postprocessing techniques applied to the input and output of Ising machines.This work makes three key contributions.First, a novel preprocessing methodology is proposed to improve accuracy and scalability by linearizing QUBO problems.This technique reduces quadratic terms in the input problem through the extraction of variable ordering relationships, which simplifies the problem structure, enables compact embedding, and offers broader applicability than existing variable reduction methods.The method is successfully validated on QUBO and multi-dimensional knapsack problem instances.Second, a twostage postprocessing methodology is developed to yield feasible, high-quality solutions for constrained problems by adapting basic heuristic principles.This enabled the first fair benchmark of a state-of-the-art Ising machine against traditional heuristics on the quadratic knapsack problem, successfully obtaining high-quality solutions on instances of size up to 2,000 variables.Finally, coefficient reduction techniques for suppressing errors in quantum annealers under realistic minor-embedding conditions are systematically validated.Our findings clarify the practical effectiveness of these methods in improving sample quality on real devices, a crucial area that had been largely unexamined.Collectively, these contributions provide essential software methodologies that bridge the gap between the theoretical promise of Ising machines and their effective real-world application, establishing a foundation for future advancements of Ising machines such as software-hardware co-design to achieve greater improvements in accuracy and scalability.
Ising machines are next-generation computers expected to efficiently sample near-optimal solutions of combinatorial optimization problems. Combinatorial optimization problems are modeled as quadratic unconstrained binary optimization (QUBO) problems to apply an Ising machine. However, current state-of-the-art Ising machines still often fail to output nearoptimal solutions due to the complicated energy landscape of QUBO problems. Furthermore, the physical implementation of Ising machines severely restricts the size of QUBO problems to be input as a result of limited hardware graph structures. In this study, we take a new approach to these challenges by injecting auxiliary penalties preserving the optimum, which reduces quadratic terms in QUBO objective functions. The process simultaneously simplifies the energy landscape of QUBO problems, allowing the search for near-optimal solutions, and makes QUBO problems sparser, facilitating encoding into Ising machines with restriction on the hardware graph structure. We propose linearization of QUBO problems using variable posets as an outcome of the approach. By applying the proposed method to synthetic QUBO instances and to multi-dimensional knapsack problems, we empirically validate the effects on enhancing minorembedding of QUBO problems and the performance of Ising machines.
Quantum Optimization (QO) is emerging as a promising approach to tackle hard combinatorial optimization problems by leveraging the unique computational properties of quantum hardware. In recent years, QO has gained traction in Machine Learning (ML), where problems such as clustering and vector quantization can be naturally expressed as Quadratic Unconstrained Binary Optimization (QUBO) problems. These ML applications often involve complex, high-dimensional data, which directly influences both the structure and scale of the resulting QUBO formulations. However, current quantum devices fall under the category of Noisy Intermediate-Scale Quantum (NISQ) hardware, which imposes significant limitations on qubit counts and small error rates. This dissertation investigates the impact of data complexity and data scale—as encountered in ML settings—on the effectiveness and feasibility of QO on NISQ devices. We propose novel, hardware-aware methods to overcome these challenges. The first part of this thesis focuses on the effect of data complexity for QO. We analyze how problem structure—particularly when QUBO formulations are derived from ML tasks—affects quantum solvability. We identify the spectral gap as a key factor in the success of adiabatic quantum algorithms and provide a theoretical and empirical analysis linking data-induced complexity to optimization performance.To address noise sensitivity and limited precision, we introduce a preprocessing framework based on a principled Branch-and-Bound algorithm that reduces dynamic range while preserving global optima. This improves robustness on both quantum annealers and classical solvers. In the second part, the thesis addresses challenges introduced by data scale. First, we propose a recursive Divide-and-Conquer strategy that breaks down large QUBO problems into tractable subproblems, demonstrated through an application to Bundle Adjustment in 3D scene reconstruction. Second, we introduce a variable and constraint generation method inspired by column generation for Integer Linear Programming, enabling dynamic QUBO size growth. This technique is successfully applied to Multi-Agent Pathfinding, where it scales well on NISQ devices while maintaining compatibility with classical solvers. Finally, we explore QUBO reformulations that reduce problem size through compact encodings and cyclic expansion, enabling the use of quantum hardware for tasks such as FPGA placement in chip design. Across all contributions, the developed algorithms are evaluated both theoretically and empirically, with experiments conducted on real quantum and quantum-inspired hardware. These methods significantly improve solution quality, scalability, and hardware compatibility, paving the way for more effective use of QO in practical settings. While tailored for NISQ era constraints, the results remain relevant for fault-tolerant quantum computing, offering insights into the long-term viability of QO across hardware generations.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Quantum annealing offers a promising paradigm for solving NP-hard combinatorial optimization problems, but its practical application is severely hindered by two challenges: the complex, manual process of translating problem descriptions into the requisite Quadratic Unconstrained Binary Optimization (QUBO) format and the scalability limitations of current quantum hardware. To address these obstacles, we propose a novel end-to-end framework, LLM-QUBO, that automates this entire formulation-to-solution pipeline. Our system leverages a Large Language Model (LLM) to parse natural language, automatically generating a structured mathematical representation. To overcome hardware limitations, we integrate a hybrid quantum-classical Benders' decomposition method. This approach partitions the problem, compiling the combinatorial complex master problem into a compact QUBO format, while delegating linearly structured sub-problems to classical solvers. The correctness of the generated QUBO and the scalability of the hybrid approach are validated using classical solvers, establishing a robust performance baseline and demonstrating the framework's readiness for quantum hardware. Our primary contribution is a synergistic computing paradigm that bridges classical AI and quantum computing, addressing key challenges in the practical application of optimization problem. This automated workflow significantly reduces the barrier to entry, providing a viable pathway to transform quantum devices into accessible accelerators for large-scale, real-world optimization challenges.