IEEE Access

A Quantum Approximate Optimization Algorithm for Resource Allocation in Database System

Jakub Kołota

Published Jan 1, 2026• 0 citations

Abstract

This paper presents a novel approach for partitioning database sessions into groups using the quantum MaxCut problem solved by the Quantum Approximate Optimization Algorithm (QAOA). Each session is represented as a node in a graph, with edges indicating the degree of resource contention between sessions. By defining a comprehensive resource demand function that accounts for CPU time, memory usage, and input/output operations, the problem is formulated as a graph partitioning task aimed at optimally distributing sessions to minimize overlap and enhance resource utilization. The paper outlines the implementation of the QAOA algorithm using Cirq, including the construction of the quantum circuit, the optimization of parameters, and the measurement of results. The results are visualized through graphs and heatmaps that illustrate the division of sessions and the reduction in resource contention. As its main contribution, the paper demonstrates the practical application of quantum algorithms to resource allocation in database systems, indicating a promising approach for improving system performance and mitigating resource conflicts.

DOI: 10.1109/access.2026.3665318

Related papers

A Quantum Approximate Optimization Algorithm on Conflict Graphs for Radio Resource Allocation

Marina Gavrilovskaia, Kwang‐Cheng Chen

Radio resource allocation is always a central and complex computational task in state-of-the-art wireless networks. Computationally efficient implementation of radio resource allocation is certainly desirable in wireless networks, and can be generalized to many resource allocation/management problems in C4ISR systems. Quantum optimization, an emerging quantum computation technology, suggests a new avenue toward (radio) resource allocation particularly potential to reduce computing latency in systems. Quantum approximation optimization algorithm (QAOA) was recently shown to possibly achieve resource allocation (RRA) in limited scope, while the generalization of QAOA for RRA remains an active research subject. Considering OFDMA resource allocation, this paper extends QAOA to multiple radio blocks by quantum state preparation, and takes the interference between adjacent radio resource units into account by introducing the conflict graphs to formulate quantum optimization. Computational experiments successfully verify proposed quantum optimization to RRA.

IEEE Military Communications Conference (MILCOM)Oct 6, 20251 citation

Edge-based quantum approximate optimization algorithm for MAX-CUT problem

Youngjin Seo, Jun Heo

Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.

Quantum Information ProcessingSep 23, 20251 citation

SOLVING THE MAX-CUT PROBLEM USING THE QASPA ALGORITHM

Д. О. САПОЖНИК

A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.

Bulletin of National Technical University KhPI Series System Analysis Control and Information TechnologiesDec 29, 20250 citations

Solving Correlation Clustering with the Quantum Approximate Optimisation Algorithm

Jordi R. Weggemans

The quantum approximation optimisation algorithm (QAOA) is one of the leading candidates for testing the applicability of gate-model quantum resources at solving optimisation problems on small-sized quantum hardware. A combinatorial problem that has been understudied with QAOA is correlation clustering: given a weighted (+1,-1) graph, where the edge weights indicate whether two nodes are similar (positive edge weight) or different (negative edge weight), the task in correlation clustering is to find a clustering that either maximises agreements, minimises disagreements or a combination of both. In this thesis, we design Hamiltonian formulations that encode correlation clustering problems such that they can be solved with QAOA. For all Hamiltonian formulations we propose circuit implementations and study their complexities. To benchmark the performances of a basic QAOA algorithm using these formulations, we use numerical simulations on complete graph data sets. For one of the formulations, which uses a multi-level approach naturally suitable to qudit systems, we investigate the performances of several optimisers and introduce heuristic strategies to further improve its performance. On all instances in our data-sets, which include complete as well as Erdős–Renyi graphs, the improved algorithm shows competitive performances for QAOA depth p ≥ 2. We also show that for this algorithm at p = 1 parameters exists such that it has a performance guarantee of 0.670 on 3-regular graphs.

Jan 1, 20201 citation

An exponentially more efficient optimization algorithm for noisy quantum computers

Marko J. Rančić

Quantum computers are devices which allow the solution of problems unsolvable to their classical counterparts. As an error-corrected quantum computer is still a decade away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm predominantly computes graph partitions with a maximal separation of edges (MaxCut), but can also be modified to calculate other properties of graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition a graphs 32 nodes on publicly available 5 qubit gate-based solid state quantum devices without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on solid state devices such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal quantum simulators. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with quantum simulators, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.

Oct 22, 20213 citations

Variational Quantum Algorithms for Combinatorial Optimization

Daniel F. Pérez-Ramírez

The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.

arXiv:2407.06421Jul 8, 20243 citations