Probabilistic methods serve as the underlying frame-work of various machine learning techniques. When using these models, a central problem is that of computing the partition function, whose computation is intractable for many models of interest. Here, we present the first quantum-inspired method that is especially designed for computing fast approximations to the partition function. Our approach uses a novel hardware solver for quadratic unconstrained binary optimization problems that relies on evolutionary computation. The specialized design allows us to assess millions of candidate solutions per second, leading to high quality maximum a-posterior (MAP) estimates, even for hard instances. We investigate the expected run-time of our solver and devise new ultra-sparse parity constraints to combine our device with the WISH approximation scheme. A SIMD-like packing strategy further allows us to solve multiple MAP instances at once, resulting in high efficiency and an additional speed-up. Numerical experiments show that our quantum-inspired approach produces accurate and robust results. While pure software implementations of the WISH algorithm typically run on large compute clusters with hundreds of CPUs, our results are achieved on two FPGA boards which both consume below 10 Watts. Moreover, our results extend seamlessly to adiabatic quantum computers.
Probabilistic methods serve as the underlying frame-work of various machine learning techniques. When using these models, a central problem is that of computing the partition function, whose computation is intractable for many models of interest. Here, we present the first quantum-inspired method that is especially designed for computing fast approximations to the partition function. Our approach uses a novel hardware solver for quadratic unconstrained binary optimization problems that relies on evolutionary computation. The specialized design allows us to assess millions of candidate solutions per second, leading to high quality maximum a-posterior (MAP) estimates, even for hard instances. We investigate the expected run-time of our solver and devise new ultra-sparse parity constraints to combine our device with the WISH approximation scheme. A SIMD-like packing strategy further allows us to solve multiple MAP instances at once, resulting in high efficiency and an additional speed-up. Numerical experiments show that our quantum-inspired approach produces accurate and robust results. While pure software implementations of the WISH algorithm typically run on large compute clusters with hundreds of CPUs, our results are achieved on two FPGA boards which both consume below 10 Watts. Moreover, our results extend seamlessly to adiabatic quantum computers.
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.
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.
Hard combinatorial optimization problems, often mapped to Ising models, promise potential solutions with quantum advantage but are constrained by limited qubit counts in near-term devices. We present an innovative quantum-inspired framework that dynamically compresses large Ising models to fit available quantum hardware of different sizes. Thus, we aim to bridge the gap between large-scale optimization and current hardware capabilities. Our method leverages a physics-inspired GNN architecture to capture complex interactions in Ising models and accurately predict alignments among neighboring spins (aka qubits) at ground states. By progressively merging such aligned spins, we can reduce the model size while preserving the underlying optimization structure. It also provides a natural trade-off between the solution quality and size reduction, meeting different hardware constraints of quantum computing devices. Extensive numerical studies on Ising instances of diverse topologies show that our method can reduce instance size at multiple levels with virtually no losses in solution quality on the latest D-Wave quantum annealers. Additionally, we demonstrate that GNN architectures can address the parameter initialization challenge in variational quantum algorithms, specifically QAOA for MaxCut problems, by learning structure-to-parameter mappings that achieve performance comparable with physics-based heuristics when trained on sufficiently large datasets.
Quantum computing promises to have a tremendous advantage over its classical counterpart for solving computationally hard problems, yet remains in a relatively early stage for practical applications owing to the limited capabilities of today’s quantum computers. The approach to the special purposes of quantum computers by exploiting the special-purpose physics-inspired or quantum-inspired computers is emerging as a novel alternative to its quantum counterpart in tackling hard problems in high-performance computing. Inspired by physics, the Ising machine — a type of special-purpose computer that implements or emulates physics or quantum effects of the Ising model to speed up finding solutions to optimization problems — has recently become an active research area in the field of combinatorial optimization. This paper is to address the key enabling software and hardware technology underlying physics-inspired optimization using Ising machines in the unified quadratic unconstrained binary optimization (QUBO) framework for modeling and solving computationally hard combinatorial optimization problems, and with an aim to shed some light on the challenges and opportunities associated with the ever-growing landscape of this novel high-performance computing.
Combinatorial optimization problems are pivotal across many fields. Among these, Quadratic Unconstrained Binary Optimization (QUBO) problems, central to fields like portfolio optimization, network design, and computational biology, are NP-hard and require exponential computational resources. To address these challenges, we develop a novel Quantum-Inspired Mean Field (QIMF) probabilistic model that approximates solutions to QUBO problems with enhanced accuracy and efficiency. The QIMF model draws inspiration from quantum measurement principles and leverages the mean field probabilistic model. We incorporate a measurement grouping technique and an amplitude-based shot allocation strategy, both critical for optimizing cost functions with a polynomial speedup over traditional methods. Our extensive empirical studies demonstrate significant improvements in solution evaluation for large-scale problems of portfolio selection, the weighted maxcut problem, and the Ising model. Specifically, using S&P 500 data from 2022 and 2023, QIMF improves cost values by 152.8% and 12.5%, respectively, compared to the state-of-the-art baselines. Furthermore, when evaluated on increasingly larger datasets for QUBO problems, QIMF's scalability demonstrates its potential for large-scale QUBO challenges.
Abstract The ultimate goal of any sparse coding method is to accurately recover from a few noisy linear measurements, an unknown sparse vector. Unfortunately, this estimation problem is NP-hard in general, and it is therefore always approached with an approximation method, such as lasso or orthogonal matching pursuit, thus trading off accuracy for less computational complexity. In this paper, we develop a quantum-inspired algorithm for sparse coding, with the premise that the emergence of quantum computers and Ising machines can potentially lead to more accurate estimations compared to classical approximation methods. To this end, we formulate the most general sparse coding problem as a quadratic unconstrained binary optimization (QUBO) task, which can be efficiently minimized using quantum technology. To derive at a QUBO model that is also efficient in terms of the number of spins (space complexity), we separate our analysis into three different scenarios. These are defined by the number of bits required to express the underlying sparse vector: binary, 2-bit, and a general fixed-point representation. We finally conduct numerical experiments with simulated data on LightSolver's quantum-inspired digital platform to verify the correctness of our QUBO formulation and to demonstrate that we obtain more accurate solutions in regimes where the baseline methods fail.