Abstract

Introduction. This abstract summarizes the core ideas presented in [2]. The join order (JO) optimization problem is an NP-hard combinatorial challenge in query optimization. It aims to find the most efficient sequence for joining multiple relations. Dynamic programming (DP) provides optimal solutions for small queries but becomes impractical for larger ones due to its exponential complexity. Heuristic methods balance between quality and efficiency. The JO problem has recently been explored with Quantum Computing, which relies on the Quadratic Unconstrained Binary Optimization (QUBO)[4]. Background. Finding efficient QUBO-based solutions for the JO problem while ensuring their validity on quantum annealers requires representing constraints on optimization variables using techniques like penalty terms and qubit chaining. However, these methods limit problem size and degrade performance. To address these challenges and handle larger JO problems, recent work [1] explored digital annealing—classical hardware inspired by quantum processing units (QPUs). While promising, this approach relies entirely on classical hardware and lacks quantum advantages. Recently, hybrid approaches have emerged to take advantage of both quantum and classical computation. These methods use classical algorithms to preprocess the problem description and constraints and then iteratively generate QUBO instances natively implementable on quantum annealers. D-Wave introduced Constrained Quadratic Models (CQM)[2], a hybrid solver that simplifies programming variables, objectives, and constraints. Main Approaches. We employ CQM [3] and …

Date

September 5, 2025

Authors

Hanwen Liu, Pranshi Saxena, Federico Spedalieri, Ibrahim Sabek

Journal

Proc. 1st Workshop Quantum Data and Machine Learning