A common way of solving satisfiability instances with quantum methods is to transform these instances into instances of QUBO. State-of-the-art transformations from MAX-3SAT to QUBO work by mapping clauses of a 3SAT formula associated with the MAX-3SAT instance to an instance of QUBO and combining the resulting QUBOs into a single QUBO instance representing the whole MAX-3SAT instance. As creating these transformations is currently done manually or via exhaustive search methods and is, therefore, algorithmically inefficient, we see potential for including search-based optimization. In this paper, we propose two methods of using evolutionary algorithms to create QUBO representations of MAX-3SAT problems automatically. We evaluate our created QUBOs on 500 and 1000-clause 3SAT formulae and find competitive performance to state-of-the-art baselines when using both classical and quantum annealing solvers.@en

In this paper, we present an open-source Python framework, called satqubolib. This framework aims to provide all necessary tools for solving (MAX)-3SAT problems on quantum hardware systems via Quadratic Unconstrained Binary Optimization (QUBO). Our framework solves two major issues when solving (MAX)-3SAT instances in the context of quantum computing. Firstly, a common way of solving satisfiability instances with quantum methods is, to transform these instances into instances of QUBO, as QUBO is the input format for quantum annealers and the Quantum Approximate Optimization Algorithm (QAOA) on quantum gate systems. Studies have shown, that the choice of this transformation can significantly impact the solution quality of quantum hardware systems. Thus, our framework provides thousands of usable QUBO transformations for satisfiability problems. Doing so also enables practitioners from any domain to immediately explore and use quantum techniques as a potential solver for their domain-specific problems, as long as they can be encoded as satisfiability problems. As a second contribution, we created a dataset of 6000 practically hard and satisfiable SAT instances that are also small enough to be solved with current quantum(-hybrid) methods. This dataset enables meaningful benchmarking of new quantum, quantum-hybrid, and classical methods for solving satisfiability problems.

@en

To solve 3sat instances on quantum annealers they need to be transformed to an instance of Quadratic Unconstrained Binary Optimization (QUBO). When there are multiple transformations available, the question arises whether different transformations lead to differences in the obtained solution quality. Thus, in this paper we conduct an empirical benchmark study, in which we compare four structurally different QUBO transformations for the 3sat problem with regards to the solution quality on D-Wave’s Advantage_system4.1. We show that the choice of QUBO transformation can significantly impact the number of correct solutions the quantum annealer returns. Furthermore, we show that the size of a QUBO instance (i.e., the dimension of the QUBO matrix) is not a sufficient predictor for solution quality, as larger QUBO instances may produce better results than smaller QUBO instances for the same problem. We also empirically show that the number of different quadratic values of a QUBO instance, combined with their range, can significantly impact the solution quality.

@en

One way of solving 3sat instances on a quantum computer is to transform the 3sat instances into instances of Quadratic Unconstrained Binary Optimizations (QUBOs), which can be used as an input for the QAOA algorithm on quantum gate systems or as an input for quantum annealers. This mapping is performed by a 3sat-to-QUBO transformation. Recently, it has been shown that the choice of the 3sat-to-QUBO transformation can significantly impact the solution quality of quantum annealing. It has been shown that the solution quality can vary up to an order of magnitude difference in the number of correct solutions received, depending solely on the 3sat-to-QUBO transformation. An open question is: what causes these differences in the solution quality when solving 3sat-instances with different 3sat-to-QUBO transformations? To be able to conduct meaningful studies that assess the reasons for the differences in the performance, a larger number of different 3sat-to-QUBO transformations would be needed. However, currently, there are only a few known 3sat-to-QUBO transformations, and all of them were created manually by experts, who used time and clever reasoning to create these transformations. In this paper, we will solve this problem by proposing an algorithmic method that is able to create thousands of new and different 3sat-to-QUBO transformations, and thus enables researchers to systematically study the reasons for the significant difference in the performance of different 3sat-to-QUBO transformations. Our algorithmic method is an exhaustive search procedure that exploits properties of (Formula presented.) dimensional pattern QUBOs, a concept which has been used implicitly in the creation of 3sat-to-QUBO transformations before, but was never described explicitly. We will thus also formally and explicitly introduce the concept of pattern QUBOs in this paper.

@en

In this work, we introduce a new workflow to solve portfolio optimization problems on annealing platforms. We combine a classical preprocessing step with a modified unconstrained binary optimization (QUBO) model and evaluate it using simulated annealing (classical computer), digital annealing (Fujitsu’s Digital Annealing Unit), and quantum annealing (D-Wave Advantage). Starting from Markowitz’s theory on portfolio optimization, our classical preprocessing step finds the most promising assets within a set of possible assets to choose from. We then modify existing QUBO models for portfolio optimization, such that there are no limitations on the number of assets that can be invested in. Furthermore, our QUBO model enables an investor to also place an arbitrary amount of money into each asset. We apply this modified QUBO to the set of promising asset candidates we generated previously via classical preprocessing. A solution to our QUBO model contains information about what percentage of the whole available capital should be invested into which asset. For the evaluation, we have used publicly available real-world data sets of stocks of the New York Stock Exchange as well as common ETFs. Finally, we have compared the respective annealing results with randomly generated portfolios by using the return, variance, and diversification of the created portfolios as measures. The results show that our QUBO formulation is capable of creating well-diversified portfolios that respect certain criteria given by an investor, such as maximizing return, minimizing risk, or sticking to a certain budget.@en