The goal of materialized view selection is to select views that optimally support a given workload, while complying with storage constraints. This paper presents the first approach for solving materialized view selection on a quantum annealer. It shows how instances of materialized view selection can be transformed into semantically equivalent QUBO problems that can be solved on quantum annealers. The solution translates into an optimal choice of candidate views. The paper concludes with an analysis of the asymptotic growth of the required number of qubits as a function of the problem dimensions, and points out future work directions.
The goal of materialized view selection is to select views that optimally support a given workload, while complying with storage constraints. This paper presents the first approach for solving materialized view selection on a quantum annealer. It shows how instances of materialized view selection can be transformed into semantically equivalent QUBO problems that can be solved on quantum annealers. The solution translates into an optimal choice of candidate views. The paper concludes with an analysis of the asymptotic growth of the required number of qubits as a function of the problem dimensions, and points out future work directions.
We show how to use quantum computing to optimize data allocation in distributed systems.Our problem model considers storage constraints (modeling limitations in storage capacity on each node), k-safety constraints (ensuring that a user-defined number of copies of each data partition is distributed in the system), and performance (calculating overheads due to the need for sending data for remote accesses over the network).Specifically, our approach leverages quantum annealers, providing high-quality solutions to instances of quadratic unconstrained binary optimization (QUBO) problems quickly.We show how to transform data allocation instances into equivalent QUBO instances.Also, we analyze the number of qubits needed to represent the resulting instances.More precisely, we determine the asymptotic number of required qubits as a function of the dimensions of the input problem.Our analysis takes into account different annealer topologies, ranging from fully connected qubits to sparse connection structures.Finally, we outline future work for this project.
Given a query plan, the goal of multiobjective query optimization [1] is to optimally map each operator in a plan to an implementation. Operator implementations differ by quality metrics such as cost and latency. In this context, query optimization becomes a multiobjective optimization problem. The optimal solution depends on user preferences and minimizes, for instance, a weighted sum over different cost metrics. We show how to transform instances of multiobjective query optimization, an NP-hard problem [1], into equivalent Quadratic Unconstrained Binary Optimization (QUBO) formulas that can be solved efficiently on quantum annealers.
Abstract One approach to solving planning problems is to compile them to other problems for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances of quadratic unconstrained binary optimization (QUBO) problem. Early quantum annealers are now available, though their constraints restrict the types of QUBOs they can take as input. Here, we introduce the planning community to the key steps in compiling planning problems to QA hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we describe preliminary results from running an early quantum annealer on a parametrized family of hard planning problems. The results show that different mappings can substantially affect performance, even when many features of the resulting instances are similar. We conclude with insights gained from this early study that suggest directions for future work.
Quantum annealers offer a promising hardware platform for solving combinatorial optimization problems, especially those formulated as Quadratic Unconstrained Binary Optimization (QUBO). In this work, we propose PDQUBO ( P erformance- D riven Q uadratic U nconstrained B inary O ptimization), a QUBO-based feature selection method, that is, directly executable on quantum annealers. Unlike prior QUBO-based feature selection approaches on quantum annealers, PDQUBO explicitly quantifies the performance impact of both individual features and feature pairs on recommender system models. This alignment between QUBO optimization objectives and model performance ensures that the solution direction is closely tied to recommendation quality, making it well-suited for practical deployment on quantum hardware. Moreover, by leveraging counterfactual analysis, PDQUBO is model-agnostic and evaluation-metric-independent, making it broadly applicable across diverse recommender architectures and assessment criteria. In addition, we investigate the instability of quantum annealing on real quantum devices with respect to varying problem sizes and problem difficulties. Extensive experiments on real-world datasets demonstrate that PDQUBO consistently outperforms prior QUBO-based feature selection methods on quantum annealers. Furthermore, we compare PDQUBO against classical feature selection baselines on click-through rate (CTR) prediction tasks, showing its strong performance and highlighting the potential of using quantum annealers for real-world feature selection applications. Our findings suggest that integrating quantum optimization with counterfactual analysis provides a promising direction for effective feature selection in recommender systems.
This paper explores the applications of quantum annealing (QA) and classical simulated annealing (SA) to a suite of combinatorial optimization problems in machine learning, namely feature selection, instance selection, and clustering. We formulate each task as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implement both quantum and classical solvers to compare their effectiveness. For feature selection, we propose several QUBO configurations that balance feature importance and redundancy, showing that quantum annealing (QA) produces solutions that are computationally more efficient. In instance selection, we propose a few novel heuristics for instance-level importance measures that extend existing methods. For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement, and demonstrate consistent improvements in cluster compactness and retrieval metrics. Our results suggest that QA can be a competitive and efficient tool for discrete machine learning optimization, even within the constraints of current quantum hardware.
Quantum annealers offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.