Many real-world engineering problems involve hard combinatorial optimizations. Heuristic algorithms, trading off accuracy for time-to-solution, are crucial for their solvability. However, as the problem size increases, time becomes the critical factor and solving these problems motivates the development of more elaborate techniques. In my thesis, I adopt the approach of synergistic co-design of heuristics and computing platforms. I postulate that for scalability, besides providing competitive quality of solution in polynomial time, such deeply custom optimizing machines should be characterized by simplicity, homogeneity and parallelizability of operations and the independence from external computing resources. Bearing these features, I propose a novel class of custom computing machines aimed at solving large quadratic unconstrained binary optimization (QUBO) problems via continuous relaxation. The machines are simultaneously designed at the heuristic and hardware levels, and implementable using the accessible VLSI CMOS technology. At the heuristic level, I approximately solve the QUBO form of max-cut through its relaxed reformulation as two relatively tractable sub-problems. First, the binary constraint on the QUBO variables is relaxed, leading to a system of coupled 2D vectors that evolve to maximize a quantity closely related to the cut. The terminal states are generally non-binary and therefore must be rounded. Optimal rounding, the second sub-problem, is non-trivial as existing parametric rounding algorithms, due to their sequential nature, become the bottleneck. Along the directions of these problems, this work presents two QUBO machines. First, I present an analog QUBO machine that solves a relaxed problem using analog computing methods. The entire machine is designed at the circuit level to implement a network of almost-linearly coupled continuous spins. The analog variables are realized using capacitors and their coupling using a digital-to-analog converter. However, our reliance on external computing resources for optimal rounding and non-idealities inherent to analog computing limits the size of the problem that could be solved by the machine. In the second part of the work, I overcome these challenges and present a digital QUBO machine prototyped on a multi-FPGA system. The machine provides high quality solutions to arbitary 1024-node weighted or 2048-node unweighted QUBO problem by simultaneously solving the relaxed QUBO problem and implementing an optimal rounding procedure in massively parallel fashion. To the best of our knowledge, this is the first self-contained scalable relaxation-based machine that directly solves the problem of optimal rounding.
Many real-world engineering problems involve hard combinatorial optimizations. Heuristic algorithms, trading off accuracy for time-to-solution, are crucial for their solvability. However, as the problem size increases, time becomes the critical factor and solving these problems motivates the development of more elaborate techniques. In my thesis, I adopt the approach of synergistic co-design of heuristics and computing platforms. I postulate that for scalability, besides providing competitive quality of solution in polynomial time, such deeply custom optimizing machines should be characterized by simplicity, homogeneity and parallelizability of operations and the independence from external computing resources. Bearing these features, I propose a novel class of custom computing machines aimed at solving large quadratic unconstrained binary optimization (QUBO) problems via continuous relaxation. The machines are simultaneously designed at the heuristic and hardware levels, and implementable using the accessible VLSI CMOS technology. At the heuristic level, I approximately solve the QUBO form of max-cut through its relaxed reformulation as two relatively tractable sub-problems. First, the binary constraint on the QUBO variables is relaxed, leading to a system of coupled 2D vectors that evolve to maximize a quantity closely related to the cut. The terminal states are generally non-binary and therefore must be rounded. Optimal rounding, the second sub-problem, is non-trivial as existing parametric rounding algorithms, due to their sequential nature, become the bottleneck. Along the directions of these problems, this work presents two QUBO machines. First, I present an analog QUBO machine that solves a relaxed problem using analog computing methods. The entire machine is designed at the circuit level to implement a network of almost-linearly coupled continuous spins. The analog variables are realized using capacitors and their coupling using a digital-to-analog converter. However, our reliance on external computing resources for optimal rounding and non-idealities inherent to analog computing limits the size of the problem that could be solved by the machine. In the second part of the work, I overcome these challenges and present a digital QUBO machine prototyped on a multi-FPGA system. The machine provides high quality solutions to arbitary 1024-node weighted or 2048-node unweighted QUBO problem by simultaneously solving the relaxed QUBO problem and implementing an optimal rounding procedure in massively parallel fashion. To the best of our knowledge, this is the first self-contained scalable relaxation-based machine that directly solves the problem of optimal rounding.
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.
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.
Solving optimization problems is challenging for existing digital computers and even for future quantum hardware. The practical importance of diverse problems, from healthcare to financial optimization, has driven the emergence of specialised hardware over the past decade. However, their support for problems with only binary variables severely restricts the scope of practical problems that can be efficiently embedded. We build analog iterative machine (AIM), the first instance of an opto-electronic solver that natively implements a wider class of quadratic unconstrained mixed optimization (QUMO) problems and supports all-to-all connectivity of both continuous and binary variables.Beyond synthetic 7-bit problems at small-scale, AIM solves the financial transaction settlement problem entirely in analog domain with higher accuracy than quantum hardware and at room temperature. With compute-in-memory operation and spatial-division multiplexed representation of variables, the design of AIM paves the path to chip-scale architecture with 100 times speed-up per unit-power over the latest GPUs for solving problems with 10,000 variables. The robustness of the AIM algorithm at such scale is further demonstrated by comparing it with commercial production solvers across multiple benchmarks, where for several problems we report new best solutions. By combining the superior QUMO abstraction, sophisticated gradient descent methods inspired by machine learning, and commodity hardware, AIM introduces a novel platform with a step change in expressiveness, performance, and scalability, for optimization in the post-Moores law era.
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.
Combinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose new methods for producing approximate solutions to quadratic unconstrained binary optimization problems, which are based on relaxations to local quantum Hamiltonians. We look specifically at approximating solutions for the maximum cut problem and its weighted version. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and is based on the estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors.
Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.