Search

Quantum optimization is a significant area of quantum computing research with anticipated near-term quantum advantages. Current quantum optimization algorithms, most of which are hybrid variational-Hamiltonian-based algorithms, struggle to present quantum devices due to noise and decoherence. Existing techniques attempt to mitigate these issues through employing different Hamiltonian encodings or Hamiltonian clause pruning, but they often rely on optimistic assumptions rather than a deep analysis of the problem structure. We demonstrate how to formulate the problem Hamiltonian for a quantum approximate optimization algorithm that satisfies all the requirements to correctly describe the considered tactical aircraft deconfliction problem, achieving higher probabilities for finding solutions compared to previous works. Our results indicate that constructing Hamiltonians from an unconventional, quantum-specific perspective with a high degree of entanglement results in a linear instead of exponential number of entanglement gates instead and superior performance compared to standard formulations. Specifically, we achieve a higher probability of finding feasible solutions: finding solutions in nine out of nine instances compared to standard Hamiltonian formulations and quadratic programming formulations known from quantum annealers, which only found solutions in seven out of nine instances. These findings suggest that there is substantial potential for further research in quantum Hamiltonian design and that gate-based approaches may offer superior optimization performance over quantum annealers in the future. [ABSTRACT FROM AUTHOR]

Obtaining all perfect matchings of a graph is a tough problem in graph theory, and its complexity belongs to the #P-Complete class. The problem is closely related to combinatorics, marriage matching problems, dense subgraphs, the Gaussian boson sampling, chemical molecular structures, and dimer physics. In this paper, we propose a quadratic unconstrained binary optimization formula of the perfect matching problem and translate it into the quantum Ising model. We can obtain all perfect matchings by mapping them to the ground state of the quantum Ising Hamiltonian and solving it with the variational quantum eigensolver. Adjusting the model’s parameters can also achieve the maximum or minimum weighted perfect matching. The experimental results on a superconducting quantum computer of the Origin Quantum Computing Technology Company show that our model can encode 2n dimensional optimization space with only O(n) qubits consumption and achieve a high success probability of the ground state corresponding to all perfect matchings. In addition, the further simulation results show that the model can support a scale of more than 14 qubits, effectively resist the adverse effects of noise, and obtain a high success probability at a shallow variational depth. This method can be extended to other combinatorial optimization problems. [ABSTRACT FROM AUTHOR]

Joint Transmission (JT) is the dynamic coordination of transmission and/or reception at multiple geographically separated sites to improve end-user service quality. When user equipment receives signals from multiple sites, downstream performance improves. An optimization problem arises in selecting the best user subset for JT within a multiple-input–multiple-output (MIMO) system. Unfortunately, a pure brute-force approach is not feasible due to exponential time growth with user combinations, unsuitable for real-time selection in mobile networks with users continuously changing in time. This article proposes quantum-compliant heuristics using quadratic unconstrained binary optimization (QUBO) for JT user scheduling. QUBO handles initial user selection, followed by brute-force exploration for the solution. Numerical results indicate that quantum-compliant methods decrease solution time without substantial accuracy loss compared to brute-force methods. [ABSTRACT FROM AUTHOR]

Abstract Due to the high degree of automation, automated guided vehicles (AGVs) have been widely used in many scenarios for transportation, and traditional computing power is stretched in large-scale AGV scheduling. In recent years, quantum computing has shown incomparable performance advantages in solving specific problems, especially Combinatorial optimization problem. In this paper, quantum computing technology is introduced into the study of the AGV scheduling problem. Additionally two types of quadratic unconstrained binary optimisation (QUBO) models suitable for different scheduling objectives are constructed, and the scheduling scheme is coded into the ground state of Hamiltonian operator, and the problem is solved by using optical coherent Ising machine (CIM). The experimental results show that compared with the traditional calculation method, the optical quantum computer can save 92% computation time on average. It has great application potential.

Due to the high degree of automation, automated guided vehicles (AGVs) have been widely used in many scenarios for transportation, and traditional computing power is stretched in large-scale AGV scheduling. In recent years, quantum computing has shown incomparable performance advantages in solving specific problems, especially Combinatorial optimization problem. In this paper, quantum computing technology is introduced into the study of the AGV scheduling problem. Additionally two types of quadratic unconstrained binary optimisation (QUBO) models suitable for different scheduling objectives are constructed, and the scheduling scheme is coded into the ground state of Hamiltonian operator, and the problem is solved by using optical coherent Ising machine (CIM). The experimental results show that compared with the traditional calculation method, the optical quantum computer can save 92% computation time on average. It has great application potential. [ABSTRACT FROM AUTHOR]

Quantum computing (QC) is a rapidly growing technology in the field of computation that has garnered significant attention in recent years. This emerging technology has become particularly relevant due to the increasing complexity of optimization problems and their expanding search spaces. As a result, innovative solutions that can surpass the limitations of the current optimization paradigms executed on classic computers are becoming necessary. D-wave, a specialized quantum computer, presents a novel solution for addressing intricate optimization problems with remarkable speed advantages over traditional methods. However, a major hurdle in terms of utilizing the D-wave platform for topology optimization design is the conversion of an optimization problem into formulas that can be comprehended by a quantum annealing machine. This is because the D-wave platform is limited to solving quadratic unconstrained binary optimization problems or Ising model problems, making it necessary to find a way to adapt the task of interest to these specific types of optimization problems. This paper examines the current reality concerning the extremely limited availability of quantum computing resources. We focus on small-scale discrete structural topology optimization problems as a starting point and establish a mapping relationship between quantum bits and the cross-sectional area variables of truss elements. Utilizing this mapping, a quadratic unconstrained binary optimization model is developed with these variables. We propose a nested optimization process with dynamically adjusted cross-sectional areas, which enables the development of a quantum annealing approach for optimizing the topology of discrete variables. Our method is validated through numerical experiments, demonstrating its efficiency. [ABSTRACT FROM AUTHOR]

The development of quantum annealing has stimulated interest in solving NP-hard problems, including various industrial problems, such as quadratic unconstrained binary optimization (QUBO), with specialized solvers. This study focuses on the rectangle packing problem (RPP), which is an NP-hard problem applicable to industrial applications. The objective of this problem is to place given items in a minimum area without overlap. Naive QUBO representations, such as a direct binary encoding of locations, could require a large number of bits, which limits the problem size, hindering the acquisition of the optimal solution. To circumvent this difficulty, we employ the concept of sequence pairs to efficiently represent the locations of items. We also propose a strategy that uses multiple sampling solutions obtained with a QUBO solver, where we employ new constraints on the number of the rectangles contributing to the placement area for restricting the search space to smoothly bridge the QUBO formulation of the sequence pair and the minimization of area of rectangle placement. We estimate an approximate curve for the optimum number of rectangles contributing to the placement area. Then, we add the penalty term concerning the deviation from the estimated optimal value on the objective function. In numerical experiments with instances with 4 to 10 rectangles, we demonstrate that the proposed sampling-based strategy can efficiently find feasible solutions. This strategy would be useful for dealing with more complex problems, such as rectangle orientation and three-dimensional problems, with a relatively small number of bits using sequence pairs.

Annealers leverage quadratic unconstrained binary optimization (QUBO) formulas to address combinatorial optimization problems (COPs) and have shown potential to outperform classical computers. This paper examines three prominent types of annealers: quantum, digital, and GPU annealers. Quantum annealers (QAs) are exemplified by the D-Wave Advantage, which relies on the quantum tunneling phenomenon to rapidly locate the minimum-energy system state corresponding to the optimal solution to a COP. Digital annealers (DAs) are typified by the Fujitsu Digital Annealing Unit (DAU), which is based on a quantum-inspired digital architecture to perform parallel and real-time optimization calculations to solve a COP. GPU annealers (GPUAs) are exemplified by the Compal Quantix solver, which harnesses graphics processing units (GPUs) to conduct the diverse adaptive bulk search for the optimal COP solution. This paper first provides an introductory overview of the QA, DA, and GPUA, and then proceeds to benchmark their performance on solving various well-known COPs such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job-shop scheduling problems. Their performance is also compared with that of state-of-the-art algorithms running on classical computers. Through comprehensive performance benchmarks in terms of the solution quality and the execution time, we identify the strengths and weaknesses of each annealer. In addition, we also provide recommendations to improve the performance of each annealer. Specifically, we recommend using the genetic algorithm, the improved particle swarm optimization algorithm, and the ant colony optimization algorithm in all annealers, using quantum pausing, quenching, and reverse annealing in the QA, using built-in separated penalty terms, one-way/two-way one-hot constraints, and linear inequality constraints in the DA, and implementing some parallel algorithms in the GPUA for performance improvement.

Quantum optimization is a significant area of quantum computing research with anticipated near-term quantum advantages. Current quantum optimization algorithms, most of which are hybrid variational-Hamiltonian-based algorithms, struggle to present quantum devices due to noise and decoherence. Existing techniques attempt to mitigate these issues through employing different Hamiltonian encodings or Hamiltonian clause pruning, but they often rely on optimistic assumptions rather than a deep analysis of the problem structure. We demonstrate how to formulate the problem Hamiltonian for a quantum approximate optimization algorithm that satisfies all the requirements to correctly describe the considered tactical aircraft deconfliction problem, achieving higher probabilities for finding solutions compared to previous works. Our results indicate that constructing Hamiltonians from an unconventional, quantum-specific perspective with a high degree of entanglement results in a linear instead of exponential number of entanglement gates instead and superior performance compared to standard formulations. Specifically, we achieve a higher probability of finding feasible solutions: finding solutions in nine out of nine instances compared to standard Hamiltonian formulations and quadratic programming formulations known from quantum annealers, which only found solutions in seven out of nine instances. These findings suggest that there is substantial potential for further research in quantum Hamiltonian design and that gate-based approaches may offer superior optimization performance over quantum annealers in the future.

Routing and wavelength assignment with protection is an important problem in telecommunications. Given an optical network and incoming connection requests, a commonly studied variant of the problem aims to grant a maximum number of requests by assigning lightpaths with minimum network resource usage, while ensuring the provided services remain functional in the case of a single-link failure through dedicated protection paths. We consider a version where alternative lightpaths for requests are assumed to be given as a precomputed set and show that it is NP-hard. We formulate the problem as an Integer Programming (IP) model and also use it as a foundation to develop a Quadratic Unconstrained Binary Optimization (QUBO) model. We present necessary and sufficient conditions on objective function parameters to prioritize request granting objective over wavelength-link usage for both models, and a sufficient condition ensuring the exactness of the QUBO model. Moreover, we implement a problem-specific branch-and-cut algorithm for the IP model and employ a new quantum-inspired technology, Digital Annealer (DA), for the QUBO model. We conduct computational experiments on a large suite of nontrivial instances to assess the efficiency and efficacy of all of these approaches as well as two problem-specific heuristics. Although the objective penalty coefficient values that guarantee the exactness of the QUBO model were outside the acceptable range for DA, it always yielded feasible solutions even with smaller values in practice. The results show that the emerging technology DA outperforms the considered techniques coupled with GUROBI in finding mostly significantly better or as good solutions in two minutes compared to two-hour run time, whereas problem-specific heuristics fail to be competitive. [ABSTRACT FROM AUTHOR]

In this paper, we consider the inclusion of the solvency capital requirement (SCR) into portfolio optimization by the use of a quadratic proxy model. The Solvency II directive requires insurance companies to calculate their SCR based on the complete loss distribution for the upcoming year. Since this task is, in general, computationally challenging for insurance companies (and therefore, not taken into account during portfolio optimization), employing more feasible proxy models provides a potential solution to this computational difficulty. Here, we present an approach that is also suitable for future applications in quantum computing. We analyze the approximability of the solvency capital ratio in a quadratic form using machine learning techniques. This allows for an easier consideration of the SCR in the classical mean-variance analysis. In addition, it allows the problem to be formulated as a quadratic unconstrained binary optimization (QUBO), which benefits from the potential speedup of quantum computing. We provide a detailed description of our model and the translation into a QUBO. Furthermore, we investigate the performance of our approach through experimental studies. [ABSTRACT FROM AUTHOR]

The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent claims on the capability of quantum computers in "solving" hard combinatorial optimization problems, we propose a quadratic unconstrained binary optimization (QUBO ) formulation for the set partitioning problem with penalty coefficients that are at least as tight as the existing naive ones. We also employ five reduction techniques of Garfinkel and Nemhauser (Operations Research 17(5):848–856, 1969) to reduce the size of an existing set of benchmark instances. We finally use variational quantum eigensolver (VQE ) as a heuristic to find feasible solutions for the problem. Our computational experiments show the efficacy of employing the proposed penalty coefficients and the existing classical reduction techniques in the quantum context. Our codes and data are available on GitHub. [ABSTRACT FROM AUTHOR]

Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy "flips" r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Timetable scheduling is a combinatorial optimization problem that presents formidable challenges for classical computers. This paper introduces a pioneering methodology for addressing the high-speed train timetabling problem through quantum computing. Initially, a comprehensive binary integer programming model, grounded in the space–time network, is proposed (M1). To manage the intricacy of model M1, a knapsack problem reformulation is employed to establish a simplified binary integer programming model (M2). Both M1 and M2 are subsequently converted into quadratic unconstrained binary optimization (QUBO) models to harness the potential of quantum computing. Several techniques, including the Gurobi solver, simulated annealing, and the coherent Ising machine (CIM) quantum simulator, are deployed to solve the model across four distinct scenarios of varying complexity. The findings indicate that CIM quantum simulator outperforms the simulated annealing method in terms of solution quality for medium-scale problems. [ABSTRACT FROM AUTHOR]

Quantum annealing is a promising method for solving hard optimization problems by transforming them into quadratic unconstrained binary optimization (QUBO) problems. However, when constraints are involved, particularly multiple inequality constraints, incorporating them into the objective function poses challenges. In this paper, the authors present two novel approaches for solving problems with multiple inequality constraints on a quantum annealer and apply them to the set cover problem (SCP). The first approach uses the augmented Lagrangian method to represent the constraints, while the second approach employs a higher‐order binary optimization (HUBO) formulation. The experiments show that both approaches outperform the standard approach for solving the SCP on the D‐Wave Advantage quantum annealer. The HUBO formulation performs slightly better than the augmented Lagrangian method in solving the SCP, but its scalability in terms of embeddability in the quantum chip is worse. The results demonstrate that the proposed augmented Lagrangian and HUBO methods can successfully implement a large number of inequality constraints, making them applicable to a broad range of constrained problems beyond the SCP. [ABSTRACT FROM AUTHOR]

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality. [ABSTRACT FROM AUTHOR]

We investigate a framework for binary image denoising via restricted Boltzmann machines (RBMs) that introduces a denoising objective in quadratic unconstrained binary optimization (QUBO) form well-suited for quantum annealing. The denoising objective is attained by balancing the distribution learned by a trained RBM with a penalty term for derivations from the noisy image. We derive the statistically optimal choice of the penalty parameter assuming the target distribution has been well-approximated, and further suggest an empirically supported modification to make the method robust to that idealistic assumption. We also show under additional assumptions that the denoised images attained by our method are, in expectation, strictly closer to the noise-free images than the noisy images are. While we frame the model as an image denoising model, it can be applied to any binary data. As the QUBO formulation is well-suited for implementation on quantum annealers, we test the model on a D-Wave Advantage machine, and also test on data too large for current quantum annealers by approximating QUBO solutions through classical heuristics.

Quantum annealing has emerged as a powerful platform for simulating and optimizing classical and quantum Ising models. Quantum annealers, like other quantum and/or analog computing devices, are susceptible to non-idealities including crosstalk, device variation, and environmental noise. Compensating for these effects through calibration refinement or “shimming” can significantly improve performance but often relies on ad-hoc methods that exploit symmetries in both the problem being solved and the quantum annealer itself. In this tutorial, we attempt to demystify these methods. We introduce methods for finding exploitable symmetries in Ising models and discuss how to use these symmetries to suppress unwanted bias. We work through several examples of increasing complexity and provide complete Python code. We include automated methods for two important tasks: finding copies of small subgraphs in the qubit connectivity graph and automatically finding symmetries of an Ising model via generalized graph automorphism. We conclude the tutorial by surveying additional methods, providing practical implementation tips, and discussing limitations and remedies of the calibration procedure. Code is available at: https://github.com/dwavesystems/shimming-tutorial.

Quantum annealing has the potential to outperform classical transistor-based computer technologies in tackling intricate combinatorial optimization problems. However, ongoing scientific debates cast doubts on whether quantum annealing devices (or quantum annealers) can genuinely provide better problem-solving capabilities than classical computers. The question of whether quantum annealing algorithms (QAAs) running on quantum annealers have computational advantages over classical algorithms (CAs) running on classical computers still remains unclear. This paper aims to clarify the question by classifying and benchmarking QAAs that utilize quadratic unconstrained binary optimization (QUBO) formulas to solve NP-hard problems. It proposes a four-class classification of QUBO formulas and exemplifies each class by QUBO formulas used by QAAs for solving specific NP-hard problems, such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job shop scheduling problems. The classification is based on the following two criteria: (i) Does the number of QUBO variables scale linearly with the problem input size? (ii) Does the QUBO formula have both the constraint term and the optimization term? QAAs are implemented and run on a D-Wave quantum annealer for benchmarking. They are benchmarked against related CAs in terms of the quality of the solution and the time to the solution. The benchmarking results reveal which classes of QUBO formulas are likely to provide advantages to QAAs over CAs. Furthermore, based on the benchmarking results, observations and suggestions are given for each class of QUBO formulas, facilitating the adoption of appropriate actions to improve the performance of QAAs.

The Binary Paint Shop Problem (BPSP) is a combinatorial optimization problem which draws inspiration from the automotive paint shop. Its binary nature, making it a good fit for Quadratic Unconstrained Binary Optimization (QUBO) solvers, has been well studied but its industrial applications are limited. In this paper, in order to expand the industrial applications, QUBO formulations for two generalizations of the BPSP, which are the Multi-Car Paint Shop Problem (MCPSP) and the Multi-Car Multi-Color Paint Shop Problem (MCMCPSP), are proposed. Given the multiple colors, the MCMCPSP is no longer natively binary which increases the problem size and introduces additional constraint factors in the QUBO formulation. Resulting QUBOs are solved using Scatter Search (SS). Furthermore, extensions of the SS that can exploit k-hot constrained structures within the formulations are proposed to compensate the additional complexity introduced by formulating non-binary problems into QUBO. Since no public benchmark database currently exists, random problem instances are generated. Viability of the proposed QUBO solving methods for the MCPSP and MCMCPSP, is highlighted through comparison with an integer-based Random Parallel Multi-start Tabu Search (RPMTS) and a greedy heuristic for the problems. The greedy heuristic has negligible computational requirements and therefore serves as a lower bound on the desired performance. The results for both problems show that better results can be obtained than the greedy heuristic and integer-based RPMTS, by using the novel k-hot extensions of the SS to solve the problems as QUBO.

The use of quantum annealers in black-box optimization to obtain the desired properties of a product with a small number of trials has attracted attention. However, the application of this technique to engineering design problems has been limited. Here, we demonstrate the applicability of black-box optimization with a quantum annealer to the design of electric circuit systems, focusing on $\pi $ -type noise filters as an example. We develop a framework that uses quantum annealing to find the optimal location of electrical components and conductor paths connecting the components, and confirm that the learning process appropriately works over a number of trials to efficiently search for a design with high performance. The results show the potential applicability of quantum annealing to design problems of electric circuit systems.

We present a quantum annealing-based solution method for topology optimization (TO). In particular, we consider TO in a more general setting, i.e., applied to structures of continuum domains where designs are represented as distributed functions, referred to as continuum TO problems. According to the problem's properties and structure, we formulate appropriate subproblems that can be solved on an annealing-based quantum computer. The methodology established can effectively tackle continuum TO problems formulated as mixed-integer nonlinear programs. To maintain the resulting subproblems small enough to be solved on quantum computers currently accessible with small numbers of qubits and limited connectivity, we further develop a splitting approach that splits the problem into two parts: the first part can be efficiently solved on classical computers, and the second part with a reduced number of variables is solved on a quantum computer. By such, a practical continuum TO problem of varying scales can be handled on the D-Wave quantum annealer. More specifically, we concern the minimum compliance, a canonical TO problem that seeks an optimal distribution of materials to minimize the compliance with desired material usage. The superior performance of the developed methodology is assessed and compared with the state-of-the-art heuristic classical methods, in terms of both solution quality and computational efficiency. The present work hence provides a promising new avenue of applying quantum computing to practical designs of topology for various applications.

Simulated Quantum Annealing (SQA) is a heuristic algorithm which can solve Quadratic Unconstrained Binary Optimization (QUBO) problems by emulating the exploration of the solution space done by a quantum annealer. It mimics the quantum superposition and tunnelling effects through a set of correlated replicas of the spins system representing the problem to be solved and performing Monte Carlo steps. However, the effectiveness of SQA over a classical algorithm strictly depends on the cost/energy profile of the target problem. In fact, quantum annealing only performs well in exploring functions with high and narrow peaks, while classical annealing is better in overcoming flat and wide energy-profile barriers. Unfortunately, real-world problems have a heterogeneous solution space and the probability of success of each solver depends on the size of the energy profile region compatible with its exploration mechanism. Therefore, significant advantages could be obtained by exploiting hybrid solvers, which combine SQA and classical algorithms. This work proposes four new quantum-classical algorithms: Simulated Quantum Parallel Tempering (SQPT), Simulated Quantum Population Annealing (SQPA), Simulated Quantum Parallel Tempering - Population Annealing v1 (SQPTPA1) and Simulated Quantum Parallel Tempering - Population Annealing v2 (SQPTPA2). They are obtained by combining SQA, Parallel Tempering (PT), and Population Annealing (PA). Their results are compared with those provided by SQA, considering benchmark QUBO problems, characterized by different profiles. Even though this work is preliminary, the obtained results are encouraging and prove hybrid solvers’ potential in solving a generic optimization problem.

Vehicle routing problems are a class of NP-hard combinatorial optimization problems which attract a lot of attention, as they have many practical applications. In recent years there have been new developments solving vehicle routing problems with the help of machine learning, since learning how to automatically solve optimization problems has the potential to provide a big leap in optimization technology. Prior work on solving vehicle routing problems using machine learning has mainly focused on auto-regressive models, which are connected to high computational costs when combined with classical exact search methods as the model has to be evaluated in every search step. This paper proposes a new method for approximately solving the capacitated vehicle routing problem with time windows (CVRPTW) via a supervised deep learning-based approach in a non-autoregressive manner. The model uses a deep neural network to assist finding solutions by providing a probability distribution which is used to guide a tree search, resulting in a machine learning assisted heuristic. The model is built upon a new neural network architecture, called graph convolutional network, which is particularly suited for deep learning tasks. Furthermore, a new formulation for the CVRPTW in form of a quadratic unconstrained binary optimization (QUBO) problem is presented and solved via quantum-inspired computing in cooperation with Fujitsu, where a learned problem reduction based upon the proposed neural network is applied to circumvent limitations concerning the usage of quantum computing for large problem instances. Computational results show that the proposed models perform very well on small and medium sized instances compared to state-of-the-art solution methods in terms of computational costs and solution quality, and outperform commercial solvers for large instances.

In this paper, we consider the inclusion of the solvency capital requirement (SCR) into portfolio optimization by the use of a quadratic proxy model. The Solvency II directive requires insurance companies to calculate their SCR based on the complete loss distribution for the upcoming year. Since this task is, in general, computationally challenging for insurance companies (and therefore, not taken into account during portfolio optimization), employing more feasible proxy models provides a potential solution to this computational difficulty. Here, we present an approach that is also suitable for future applications in quantum computing. We analyze the approximability of the solvency capital ratio in a quadratic form using machine learning techniques. This allows for an easier consideration of the SCR in the classical mean-variance analysis. In addition, it allows the problem to be formulated as a quadratic unconstrained binary optimization (QUBO), which benefits from the potential speedup of quantum computing. We provide a detailed description of our model and the translation into a QUBO. Furthermore, we investigate the performance of our approach through experimental studies.

Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy “flips” r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.

The aim of this study was to explore the information disclosure (ID) problem, which involves selecting pairs of two sides before matching toward user-oriented optimization. This problem is known to be useful for mobility-on-demand (MoD) platforms because drivers' choice behaviors are appropriately modeled, but solving the problem is still under development, although heuristic solvers have been proposed. We develop new branch-and-bound-based (BnB) solvers and a new heuristic solver based on a quadratic unconstrained binary optimization (QUBO) formulation. Our numerical experiments show that the QUBO-based solver indeed works within the limit of available bits, and the BnB solver performs slightly better than existing heuristic ones.

Many NP-hard combinatorial optimization (CO) problems can be cast as a quadratic unconstrained binary optimization model, which maps naturally to an Ising model. The final spin configuration in the Ising model can adiabatically arrive at a solution to a Hamiltonian, given a known set of interactions between spins. We enhance two photonic Ising machines (PIMs) and compare their performance against classical (Gurobi) and quantum (D-Wave) solvers. The temporal multiplexed coherent Ising machine (TMCIM) uses the bistable response of an electro-optic modulator to mimic the spin up and down states. We compare TMCIM performance on Max-cut problems. A spatial photonic Ising machine (SPIM) convolves the wavefront of a coherent laser beam with the pixel distribution of a spatial light modulator to adiabatically achieve a minimum energy configuration, and solve a number partitioning problem (NPP). Our computational results on Max-cut indicate that classical solvers are still a better choice, while our NPP results show that SPIM is better as the problem size increases. In both cases, connectivity in Ising hardware is crucial for performance. Our results also highlight the importance of better understanding which CO problems are most likely to benefit from which type of PIM. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'. [ABSTRACT FROM AUTHOR]

Mixed Integer Linear Programming (MILP) can be considered the backbone of the modern power system optimization process, with a large application spectrum, from Unit Commitment and Optimal Transmission Switching to verifying Neural Networks for power system applications. The main issue of these formulations is the computational complexity of the solution algorithms, as they are considered NP-Hard problems. Quantum computing has been tested as a potential solution towards reducing the computational burden imposed by these problems, providing promising results, motivating the can be used to speedup the solution of MILPs. In this work, we present a general framework for solving power system optimization problems with a Quantum Computer (QC), which leverages mathematical tools and QCs' sampling ability to provide accelerated solutions. Our guiding applications are the optimal transmission switching and the verification of neural networks trained to solve a DC Optimal Power Flow. Specifically, using an accelerated version of Benders Decomposition , we split a given MILP into an Integer Master Problem and a linear Subproblem and solve it through a hybrid "quantum–classical" approach, getting the best of both worlds. We provide 2 use cases, and benchmark the developed framework against other classical and hybrid methodologies, to demonstrate the opportunities and challenges of hybrid quantum–classical algorithms for power system mixed integer optimization problems. • We provide a framework for transforming MILP models of power system problems to a "quantum–classical solvable form". • We use mathematical tools and quantum solvers to speed up the solution process. • We offer a comprehensive Python code in the form of a tutorial available on our GitHub repository. • We provide extensive numerical results for large enough instances that arrive at the limits of the capacity constraints of the current available Quantum Computers and we discuss the benefits of each method and the challenges that need to be addressed to exploit the future quantum advantage. [ABSTRACT FROM AUTHOR]

The max-flow min-cut theorem in graph theory states that the maximum flow of a network is equal to the minimum cut of edges of the flow network. Max-flow and min-cut are related as two primal–dual linear programs. The theorem is applicable in applications like network connectivity, graph matching problems, transportation and logistics, and scheduling problems. The aim of the paper is to model the classical max-flow and min-cut theorem in quantum computing. Two well-known methods for quantum optimization are quantum annealing and quantum approximate optimization algorithm. The max-flow min-cut is converted to its equivalent model of the above two methods for execution in polynomial time. This paper shows detailed classical to quantum conversion, analysis, implementation, and result of the theorem. • Max-flow min-cut modeling in optimization as CQM, BQM, QUBO or Ising model. • Classical to quantum model conversion analysis, and modeling in QAOA and QA. • Experimental and parametric result analysis of QAOA and QA on various QPUs. [ABSTRACT FROM AUTHOR]

Many studies have attempted to develop simple and efficient methods for solving global optimization problems. Simulated annealing (SA) has been recognized as a powerful tool for performing this task. In this study, we implemented a rejection-free Monte Carlo (RFMC) algorithm, which is a kernel of rejection-free SA (RFSA). We showed its validity and advantage in obtaining globally optimal solution for quadratic unconstrained binary optimization (QUBO) and spin-glass problem embedded in the Lechner–Hauke–Zoller (LHZ) architecture. Landscapes of success probabilities of finding the globally optimal solution as well as feasible solutions were evaluated as a function of a set of hyper-parameters used to characterize the weights of cost and penalty functions. We demonstrated that the efficiency of RFMC was greatly enhanced compared to that of standard MC. Furthermore, we found that the landscapes for QUBO and those for LHZ problem show considerably different views. When we focus on a specific class of problems, the smaller the problem size, the more scattered is the success probability. We also show that the success probabilities can be further improved by avoiding inefficiencies due to cycling of state transitions using short-term memory mechanisms. We suggest a reasonable strategy to tune hyper-parameters and find the correct global solution using RFSA.

The Quadratic Unconstrained Binary Optimization (QUBO) modeling and solution framework is a requirement for quantum and digital annealers. However optimality for QUBO problems of any practical size is extremely difficult to achieve. In order to incorporate the problem-specific insights, a diverse set of solutions meeting an acceptable target metric or goal is the preference in high level decision making. In this paper, we present two alternatives for goal-seeking QUBO for minimizing the deviation from a given target as well as a range of values around a target. Experimental results illustrate the efficacy of the proposed approach over Constraint Programming for quickly finding a satisficing set of solutions.

Binary matrix factorization is an important tool for dimension reduction for high-dimensional datasets with binary attributes and has been successfully applied in numerous areas. This paper presents a collaborative neurodynamic optimization approach to binary matrix factorization based on the original combinatorial optimization problem formulation and quadratic unconstrained binary optimization problem reformulations. The proposed approach employs multiple discrete Hopfield networks operating concurrently in search of local optima. In addition, a particle swarm optimization rule is used to reinitialize neuronal states iteratively to escape from local minima toward better ones. Experimental results on eight benchmark datasets are elaborated to demonstrate the superior performance of the proposed approach against six baseline algorithms in terms of factorization error. Additionally, the viability of the proposed approach is demonstrated for pattern discovery on three datasets. [ABSTRACT FROM AUTHOR]

The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.

Quantum annealing (QA) can be used to quickly obtain near-optimal solutions for quadratic unconstrained binary optimization (QUBO) problems. In QA hardware, each decision variable of a QUBO should be mapped to one or more adjacent qubits in such a way that pairs of variables defining a quadratic term in the objective function are mapped to some pair of adjacent qubits. However, qubits have limited connectivity in existing QA hardware. This has spurred work on preprocessing algorithms for embedding the graph representing problem variables with quadratic terms into the hardware graph representing qubits adjacencies, such as the Chimera graph in hardware produced by D-Wave Systems. In this paper, we use integer linear programming to search for an embedding of the problem graph into certain classes of minors of the Chimera graph, which we call template embeddings. One of these classes corresponds to complete bipartite graphs, for which we show the limitation of the existing approach based on minimum odd cycle transversals (OCTs). One of the formulations presented is exact and thus can be used to certify the absence of a minor embedding using that template. On an extensive test set consisting of random graphs from five different classes of varying size and sparsity, we can embed more graphs than a state-of-the-art OCT-based approach, our approach scales better with the hardware size, and the runtime is generally orders of magnitude smaller. Summary of Contribution: Our work combines classical and quantum computing for operations research by showing that integer linear programming can be successfully used as a preprocessing step for adiabatic quantum optimization. We use it to determine how a quadratic unconstrained binary optimization problem can be solved by a quantum annealer in which the qubits are coupled as in a Chimera graph, such as in the quantum annealers currently produced by D-Wave Systems. The paper also provides a timely introduction to adiabatic quantum computing and related work on minor embeddings. [ABSTRACT FROM AUTHOR]

This work presents the mapping of the traveling salesperson problem (TSP) based in pseudo-Boolean constraints to a graph of the D-Wave Systems Inc. We first formulate the problem as a set of constraints represented in propositional logic and then resort to the SATyrus approach to convert the set of constraints to an energy minimization problem. Next, we transform the formulation to a quadratic unconstrained binary optimization problem (QUBO) and solve the problem using different approaches: (a) classical QUBO using simulated annealing in a von Neumann machine, (b) QUBO in a simulated quantum environment, (c) QUBO using the D-Wave quantum machine. Moreover, we study the amount of time and execution time reduction we can achieve by exploring approximate solutions using the three approaches. Results show that for every graph size tested with the number of nodes less than or equal to 7, we can always obtain at least one optimal solution. In addition, the D-Wave machine can find optimal solutions more often than its classical counterpart for the same number of iterations and number of repetitions. Execution times, however, can be some orders of magnitude higher than the classical or simulated approaches for small graphs. For a higher number of nodes, the average execution time to find the first optimal solution in the quantum machine is 26% ( n = 6 ) and 47% ( n = 7 ) better than the classical. [ABSTRACT FROM AUTHOR]

The recent emergence of novel computational devices, such as quantum computers, coherent Ising machines, and digital annealers presents new opportunities for hardware-accelerated hybrid optimization algorithms. Unfortunately, demonstrations of unquestionable performance gains leveraging novel hardware platforms have faced significant obstacles. One key challenge is understanding the algorithmic properties that distinguish such devices from established optimization approaches. Through the careful design of contrived optimization tasks, this work provides new insights into the computation properties of quantum annealing and suggests that this model has the potential to quickly identify the structure of high-quality solutions. A meticulous comparison to a variety of algorithms spanning both complete and local search suggests that quantum annealing's performance on the proposed optimization tasks is distinct. This result provides new insights into the time scales and types of optimization problems where quantum annealing has the potential to provide notable performance gains over established optimization algorithms and suggests the development of hybrid algorithms that combine the best features of quantum annealing and state-of-the-art classical approaches. [ABSTRACT FROM AUTHOR]

Quantum annealing is an emerging new platform for combinatorial optimization, requiring an Ising model formulation for optimization problems. The formulation can be an essential obstacle to the permeation of this innovation into broad areas of everyday life. Our research is aimed at the proposal of a Petri net modeling approach for an Ising model formulation. Although the proposed method requires users to model their optimization problems with Petri nets, this process can be carried out in a relatively straightforward manner if we know the target problem and the simple Petri net modeling rules. With our method, the constraints and objective functions in the target optimization problems are represented as fundamental characteristics of Petri net models, extracted systematically from Petri net models, and then converted into binary quadratic nets, equivalent to Ising models. The proposed method can drastically reduce the difficulty of the Ising model formulation. [ABSTRACT FROM AUTHOR]

The longest path problem on graphs is an NP-hard optimization problem, and as such, it is not known to have an efficient classical solution in the general case. This study develops two quadratic unconstrained binary optimization (QUBO) formulations of this well-known problem. The first formulation is based on an approach outlined by (Bauckhage et al., 2018) for the shortest path problem and follows simply from the principle of assigning positions on the path to vertices; using k | V | binary variables, this formulation will find the longest path that visits exactly k of a graph's | V | vertices, if such a path exists. As a point of theoretical interest, we present a second formulation based on degree constraints that is more complicated, but reduces the dependence of the number of variables on k to logarithmic; specifically, it requires | V | + 2 | E | ⌊ log 2 ⁡ k ⌋ + 3 | E | binary variables to encode the longest path problem. We adapt these basic formulations for several variants of the standard longest path problem. Scaling factors for penalty terms and preprocessing time required to construct the Q matrix representing the problem are made explicit in the paper. [ABSTRACT FROM AUTHOR]