Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing

Nikhil Kowshik, Sayan Manna, Sudebkumar Prasant Pal · 2025

Read Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing by Nikhil Kowshik, Sayan Manna, Sudebkumar Prasant Pal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07200.txt.

Introduction

Nikhil Kowshik and 2 co-authors apply quantum algorithms to set balancing in a 2025 paper. Set balancing asks how to split items into two groups so that group traits match as closely as possible. The problem is NP-hard, meaning no fast exact method is known, and it shows up in clinical trial design and experiment scheduling.

The team maps the problem to an Ising model, a physics-style energy model, and builds cost formulas for two quantum methods, QAOA and QWOA. For QAOA they compare six mixer Hamiltonians, the parts that shuffle candidate solutions, using a scaled circuit method that beat standard layouts. A post-processing step based on Shannon entropy then evens out trait distributions across the groups. Results stress that mixer choice and circuit design matter as much as the headline algorithm.

Catalog record

CREATORNikhil Kowshik, Sayan Manna, Sudebkumar Prasant Pal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-07200

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing Nikhil Kowshik, Sayan Manna, Sudebkumar Prasant Pal Abstract We explore the application of variational quantum algorithms to the NP-hard set balancing problem, a critical challenge in clinical trial design and experimental scheduling. The problem is mapped to an Ising model, with tailored Quadratic Unconstrained Binary Optimization (QUBO) formulations and cost Hamiltonians expressed in Pauli-Z form. We implement both the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Walk Optimization Algorithm (QWOA), evaluating them in separate experimental settings. For QAOA, we perform a comparative analysis of six mixer Hamiltonians (X, XY, Full-SWAP, Ring-SWAP, Grover, and Warm-Started), employing scaled-exponential Pauli-string realizations of the mixer unitaries, which yield superior performance over conventional circuit decompositions. Additionally, we introduce a Shannon-entropy-based post-processing technique that refines solutions by maximizing feature-distribution uniformity across partitions. These results underscore the importance of mixer choice and circuit implementation in enhancing QAOA performance for combinatorial optimization. 1. Set Balancing: Introduction The problem of splitting a set into two subsets with almost identical properties or attributes but differing in only one of the attributes is a set balancing problem. It naturally emerges during the design of experiments [ 7 , 13 ] with respect to a collection of attributes. When designing studies pertaining to a group of attributes, it automatically comes to light. Every subject possesses a variety of binary traits or qualities. Being young or old, black or white, tall or small, etc., are examples of attributes. Treatment group ( T ) and control group ( C ) are the two subgroups into which individuals are divided. The goal is to ensure that, for each attribute, the percentage of subjects in ( T ) and ( C ) who share that characteristic is about equal. For example, there should be roughly the same percentage of young people, tall individuals, etc. in both groups. Consider splitting or partitioning a set S\subseteq U into two subsets, where one subset is “positive” in an attribute A and the other subset is “negative” on the same attribute A . Here, U is the universal set of all items. Let S_{i},1\leq i\leq m , be a collection {\cal S} of m arbitrary non-empty proper subsets of U . One way of partitioning the subset S is to use a bicoloring b of the universal set U , and to project that bicoloring b on S , thereby splitting S into two subsets, say S_{b} and S_{b}^{\prime} . Similarly, any subset S_{i}\in{\cal S} can also be partitioned into two sets S_{i_{b}} and S_{i_{b}}^{\prime} , for all 1\leq i\leq m . We consider the notion of balancing the set system or collection {\cal S} by a possible bicoloring b provided the cardinalities of S_{i_{b}} and S_{i_{b}}^{\prime} are more or less equal, for all 1\leq i\leq m . For an arbitrary set system {\cal S} , we may not have a perfectly balancing bicoloring b . This is closely related to the study of discrepancy theory , which investigates how evenly elements can be distributed across multiple sets [ 15 , 4 ] . In practice, one often seeks a coloring that minimizes the total imbalance either in the infinity metric or the Euclidean metric. We prefer the Euclidean metric, which enables us to directly invoke the QUBO optimization technique of quadratic objective function optimization, where implement Quantum Approximate Optimization Algorithm (QAOA) [ 5 ] and Quantum Walk Optimization Algorithm (QWOA) [ 3 , 11 ] . The following is an explanation of the set balancing problem for a universal set U of n subjects or elements. The number of subjects in the general population is n . The potential feature or attribute count is m . The subjects are described by A , an m\times n matrix with entries in \{0,1\} . Each row denotes a feature or a subset of U , whereas each column denotes a subject or an element of U . a_{ij}=\begin{cases}1,&\text{if subject }j\text{ has feature }i\\ 0,&\text{otherwise}\end{cases} The grouping of subjects is denoted by the vector b , which has n rows and 1 column. The values in b are either -1 or 1 , where b_{j}=1 indicates that subject j belongs to the treatment group T , and b_{j}=-1 indicates that subject j belongs to the control group C . The balancing of a feature is described by c=Ab , which is an n\times 1 vector. The numeric value of c_{i} is the imbalance in feature i . If c_{i}>0 , then there are more subjects with feature i in T , and if c_{i}<0 , then there are more subjects with feature i in C . 2. Hamiltonians, Ising Models, and QAOA Adiabatic quantum optimization [ 2 , 6 ] has long been studied as a paradigm for approximately solving NP-hard combinatorial optimization problems. The central idea relies on interpolating between two Hamiltonians: a cost Hamiltonian H_{C} , whose ground state encodes the solution to the optimization problem, and a mixer Hamiltonian H_{M} , whose role is to drive transitions between computational basis states. According to the Adiabatic Theorem [ 6 ] , if a system is initialized in the ground state of H_{M} and evolved slowly under a time-dependent Hamiltonian that interpolates between H_{M} and H_{C} , it will remain in its ground state throughout the process and finally encode the solution of the original problem in H_{C} . A classical Ising Hamiltonian, widely used to model optimization problems [ 10 ] , can be written as a quadratic polynomial over N binary spins s_{i}\in\{\pm 1\} : H(s_{1},\dots,s_{N})=-\sum_{i<j}J_{ij}s_{i}s_{j}-\sum_{i=1}^{N}h_{i}s_{i}, (3.1) where J_{ij} are pairwise interaction strengths and h_{i} are external fields. Its quantum analogue replaces spins with Pauli- Z operators, leading to the cost Hamiltonian H_{C}=H(\sigma_{1}^{z},\dots,\sigma_{N}^{z}), (3.2) and a standard choice of mixer Hamiltonian is H_{M}=-h_{0}\sum_{i=1}^{N}\sigma_{i}^{x}, (3.3) which drives transitions between computational basis states. The Quantum Approximate Optimization Algorithm (QAOA) [ 5 ] can be understood as a digitized, Trotterized version of adiabatic quantum evolution. Instead of continuously evolving under a time-dependent Hamiltonian, QAOA alternates between unitaries generated by H_{C} and H_{M} . Specifically, for a circuit with p layers, the QAOA ansatz is |\psi_{p}(\boldsymbol{\gamma},\boldsymbol{\beta})\rangle=\prod_{k=1}^{p}e^{-i\beta_{k}H_{M}}e^{-i\gamma_{k}H_{C}}|+\rangle^{\otimes N}, (1) where the parameters \boldsymbol{\gamma}=(\gamma_{1},\dots,\gamma_{p}) and \boldsymbol{\beta}=(\beta_{1},\dots,\beta_{p}) control the discretized evolution. The initial state |+\rangle^{\otimes N} , being the ground state of H_{M} , represents an equal superposition of all possible bitstrings, ensuring that all potential solutions are considered at the outset. QAOA thus provides a variational hybrid quantum-classical framework: the parameters (\boldsymbol{\gamma},\boldsymbol{\beta}) are optimized using a classical optimizer to minimize the expectation value of H_{C} . As the number of layers p increases, QAOA converges to the continuous-time adiabatic algorithm, though in practice small p often yields good approximations with polynomial resources. Variants and generalizations of QAOA extend the choice of mixer Hamiltonians and problem encodings, broadening its applicability to a wider class of optimization and constraint-satisfaction problems [ 9 ] . These components are schematically illustrated in Figure 1 . Figure 1 : Alternating layers of H_{C} (represented here as H_{P} )and H_{M} form the quantum circuit and are optimized by a classical optimizer. Source for image is [ 1 ] 3. Set Balancing : Problem Definition The Set Balancing problem is a

Read the complete text