Neuromorphic computing has so far been driven predominantly by machine-learning workloads, yet its underlying properties also make it particularly well suited to combinatorial optimization problems expressed in Ising or QUBO form. While neuromorphic Ising solvers have been demonstrated, how a given problem should be formulated to best suit neuromorphic dynamics has received far less attention. Maximum-likelihood (ML) channel decoding can be expressed as an Ising/QUBO problem, and two distinct formulations already exist in the quantum-annealing literature: a squared-penalty formulation that uses few spins but produces dense intra-check couplings, and a chain-product formulation that improves locality at the cost of additional auxiliary spins. Both place the ML codeword at the ground state under sufficient constraint enforcement, but they have not been compared under the constraints that neuromorphic hardware imposes. This work provides the first systematic side-by-side comparison of QUBO/Ising formulations of ML decoding for linear codes. We show that the two formulations impose fundamentally different tradeoffs in neuron count, synaptic density, locality, and convergence behavior. The preferred formulation is inseparable from the choice of solver, and the two must be considered jointly. Finally, we show that ground-state correctness alone is an insufficient design criterion, and that signal processing tasks should ideally be co-formulated with their neuromorphic hardware models if neuromorphic computing is to extend into the receiver pipeline.
Neuromorphic computing has so far been driven predominantly by machine-learning workloads, yet its underlying properties also make it particularly well suited to combinatorial optimization problems expressed in Ising or QUBO form. While neuromorphic Ising solvers have been demonstrated, how a given problem should be formulated to best suit neuromorphic dynamics has received far less attention. Maximum-likelihood (ML) channel decoding can be expressed as an Ising/QUBO problem, and two distinct formulations already exist in the quantum-annealing literature: a squared-penalty formulation that uses few spins but produces dense intra-check couplings, and a chain-product formulation that improves locality at the cost of additional auxiliary spins. Both place the ML codeword at the ground state under sufficient constraint enforcement, but they have not been compared under the constraints that neuromorphic hardware imposes. This work provides the first systematic side-by-side comparison of QUBO/Ising formulations of ML decoding for linear codes. We show that the two formulations impose fundamentally different tradeoffs in neuron count, synaptic density, locality, and convergence behavior. The preferred formulation is inseparable from the choice of solver, and the two must be considered jointly. Finally, we show that ground-state correctness alone is an insufficient design criterion, and that signal processing tasks should ideally be co-formulated with their neuromorphic hardware models if neuromorphic computing is to extend into the receiver pipeline.
We formulate maximum likelihood (ML) channel decoding as a quadratic unconstraint binary optimization (QUBO) and simulate the decoding by the current commercial quantum annealing machine, D-Wave 2000Q. We prepared two implementations with Ising model formulations, generated from the generator matrix and the parity-check matrix respectively. We evaluated these implementations of ML decoding for low-density parity-check (LDPC) codes, analyzing the number of spins and connections and comparing the decoding performance with belief propagation (BP) decoding and brute-force ML decoding with classical computers. The results show that these implementations are superior to BP decoding in relatively short length codes, and while the performance in the long length codes deteriorates, the implementation from the parity-check matrix formulation still works up to 1k length with fewer spins and connections than that of the generator matrix formulation due to the sparseness of parity-check matrices of LDPC.
The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.
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.
The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.
Although machine learning currently relies on conventional computer architectures, the looming end of Moore's Law necessitates exploration of novel computational platforms. Neuromorphic and quantum systems are a natural path to pursue; biological neurons are incredibly efficient, and quantum mechanics provides theoretical foundations for fast solutions to optimization problems. Here, we make the first comparison of emerging hardware (D-Wave quantum annealer and Intel Loihi spiking processor) on an identically-posed machine learning problem. We implement the bioinspired Locally Competitive Algorithm (LCA) for solving sparse coding on the different substrates. To make the comparison valid, our dataset of choice (Fashion MNIST) is dimensionally-reduced via sparse principal component analysis, under the constraint that both classification performance and a graph-based clustering metric remain unchanged. This enables the problem to be mapped identically to both devices. An analysis of several metrics, including power consumption, reconstruction, and classification accuracy are presented. When given the same specifically-constructed challenge, both substrates perform similarly. Our results suggest while neuromorphic and quantum systems are still in their infancy, they present a possible route to address certain types of classically challenging problems, such as sparse coding, in a way that leverages the unique aspects of the substrates.
Ising Machines are emerging hardware architectures that efficiently solve NP-Hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ~10000x performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5-4x over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.