Representing a given problem as a QUBO problem implies the possibility of running it in a quantum computational environment (generic or specific). The well-known problem of looking for similar functions in biological structures, especially of proteins, is of great interest in the field of Bioinformatics. We give a QUBO formulation for CMO protein problem. Experimental results validate this approach as an alternative to classical methods via combinatorial optimization. For the accomplishment of such experiments, we use the qbsolv tool.
Representing a given problem as a QUBO problem implies the possibility of running it in a quantum computational environment (generic or specific). The well-known problem of looking for similar functions in biological structures, especially of proteins, is of great interest in the field of Bioinformatics. We give a QUBO formulation for CMO protein problem. Experimental results validate this approach as an alternative to classical methods via combinatorial optimization. For the accomplishment of such experiments, we use the qbsolv tool.
Protein folding is a fundamental biological process in which a linear chain of amino acids spontaneously adopts a unique three-dimensional structure essential for proper biological function, molecular recognition and transport of nutrients. Protein misfolding, on the other hand can lead to severe neurodegenerative disorders such as Alzheimer’s, Parkinson’s and cystic fibrosis. Traditional approaches to protein folding, such as knowledge-based and statistical methods, often face limitations in scalability and physical accuracy. To overcome these challenges, the problem has been reformulated as a combinatorial optimization problem classified as NP-hard. In this work, we implement the CVaR-VQE algorithm to solve a previously proposed QUBO formulation of lattice protein folding within a gate-based quantum computing framework. We demonstrate that, compared to the quantum annealing approach, this method significantly reduces qubit requirements and improves scalability, enabling more efficient and practical implementations on NISQ devices. Additionally, we benchmarked our results against classical optimization using IBM CPLEX, we observed that the proposed quantum approach yields high-quality solutions across multiple peptide instances.
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.
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.
With the development of quantum computing, the use of quantum algorithms to solve combinatorial optimization problems on quantum computers has become a major research focus. The Quadratic Unconstrained Binary Optimization (QUBO) model serves as a bridge between combinatorial optimization problems and quantum computers, and is a prerequisite for these studies. In combinatorial optimization problems, the Domination Problem (DP) is related to many practical issues in the real world, such as the fire station problem, social network theory, and so on. Additionally, the DP has numerous variants, such as independent DP, total DP, k-domination, and so forth. However, there is a scarcity of quantum computing research on these variant problems. A possible reason for this is the lack of research on QUBO modeling for these issues. This paper investigates the QUBO modeling methods for the classic DP and its variants. Compared to previous studies, the QUBO modeling method we propose for the classic DP can utilize fewer qubits. This will lower the barrier for solving DP on quantum computers. At the same time, for many variants of DP problems, we provide their QUBO modeling methods for the first time. Our work will accelerate the entry of DP into the quantum era.
The field of Combinatorial Optimization (CO) is one of the most important
areas in the general field of optimization, with important applications found
in every industry, including both the private and public sectors. It is also
one of the most active research areas pursued by the research communities of
Operations Research, Computer Science, and Analytics as they work to design and
test new methods for solving real world CO problems. In recent years, we have
discovered that a mathematical formulation known as QUBO, an acronym for a
Quadratic Unconstrained Binary Optimization problem, can embrace a large
variety of important CO problems found in industry and government. Through
special reformulation techniques that are easy to apply, the power of QUBO
solvers can be used to efficiently solve many important problems once they are
put into the QUBO framework. This two-step process of first re-casting an
original model into the form of a QUBO model and then solving it with
appropriate software enables the QUBO model to become a unifying framework for
combinatorial optimization. The alternative path that results for effectively
modeling and solving many important problems is a new development in the field
of combinatorial optimization. The materials provided in subsequent sections
illustrate the process of reformulating important optimization problems as QUBO
models through a series of explicit examples. Collectively these examples
highlight the application breadth of the QUBO model. We do not focus here on
modeling a given problem in the form classically adopted in the optimization
community. Rather, our examples disclose the methods that can be used to recast
a given problem, perhaps existing in a classical mathematical form, into an
equivalent QUBO model.
With the recent advancements in the field of combinatorial optimization, QUBO (quadratic unconstrained binary optimization) has become a topic of intense interest, as a problem format acceptable to several hardware heuristics such as quantum and digital annealers. Accordingly, transforming hard mathematical problems into QUBO problems is of particular importance. In this paper, we restate three problems in NP-complete and NP-hard classes as QUBO problems with proofs of equivalence. Our problems of interest are the numerical three-dimensional matching problem, the monochromatic triangle problem and the optimum facility location problem. Furthermore, we comment on the feasibility of these formulations on sophisticated QUBO solving platforms.