Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing

• URL: http://arxiv.org/abs/2509.07200v1
• Date: Mon, 08 Sep 2025 20:31:30 GMT
• Title: Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing
• Authors: Nikhil Kowshik, Sayan Manna, Sudebkumar Prasant Pal,
• Abstract summary: We explore the application of variational quantum algorithms to the NP-hard set balancing problem.<n>The problem is mapped to an Ising model, with tailored Quadratic Unconstrained Binary Optimization (QUBO) formulations and cost Hamiltonians expressed in Pauli-Z form.<n>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.<n>We introduce a Shannon-entropy-based post
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Optimization-based Unfolding in High-Energy Physics [0.0]
  In High-Energy Physics, unfolding is the process of reconstructing true distributions of physical observables from detector-distorted measurements.<n>We develop a framework to tackle this problem using both classical and quantum-compatible methods.
  arXiv  Detail & Related papers  (2026-02-26T09:11:34Z)
• Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
  This paper investigates the performance of the emerging non-variational Quantum Walk-based optimisation algorithm (NV-QWOA) for solving small instances of the Quadratic Assignment Problem (QAP)<n>Performance is evaluated using two metrics: the number of objective function evaluations and the number of algorithm iterations required to consistently reach optimal or near optimal solutions across QAP instances with 5 to 10 facilities.<n>Our findings highlight the practical utility of quantum walks for complex quantum problems and establish a foundation for future quantum optimisation algorithms.
  arXiv  Detail & Related papers  (2026-01-03T07:50:03Z)
• A Lyapunov Framework for Quantum Algorithm Design in Combinatorial Optimization with Approximation Ratio Guarantees [15.259020859762556]
  We develop a framework aiming at designing quantum algorithms for optimization problems.<n>We provide theoretical guarantees on their approximation ratios.<n>We apply our framework to Max-Cut problem, implementing it as an adaptive variational quantum algorithm.
  arXiv  Detail & Related papers  (2025-12-25T15:38:24Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  We introduce a comprehensive benchmarking framework designed to evaluate quantum optimization techniques against well-established NP-hard problems.<n>Our framework focuses on key problem classes, including the Multi-Dimensional Knapsack Problem (MDKP), Maximum Independent Set (MIS), Quadratic Assignment Problem (QAP), and Market Share Problem (MSP)
  arXiv  Detail & Related papers  (2025-03-15T13:02:22Z)
• Bias-field digitized counterdiabatic quantum optimization [39.58317527488534]
  We call this protocol bias-field digitizeddiabatic quantum optimization (BF-DCQO) Our purely quantum approach eliminates the dependency on classical variational quantum algorithms. It achieves scaling improvements in ground state success probabilities, increasing by up to two orders of magnitude.
  arXiv  Detail & Related papers  (2024-05-22T18:11:42Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
  We propose an approach to solving constrained optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width.
  arXiv  Detail & Related papers  (2023-10-06T19:09:55Z)
• Benchmarking Metaheuristic-Integrated QAOA against Quantum Annealing [0.0]
  The study provides insights into the strengths and limitations of both Quantum Annealing and metaheuristic-integrated QAOA across different problem domains. The findings suggest that the hybrid approach can leverage classical optimization strategies to enhance the solution quality and convergence speed of QAOA.
  arXiv  Detail & Related papers  (2023-09-28T18:55:22Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• A self-consistent field approach for the variational quantum eigensolver: orbital optimization goes adaptive [52.77024349608834]
  We present a self consistent field approach (SCF) within the Adaptive Derivative-Assembled Problem-Assembled Ansatz Variational Eigensolver (ADAPTVQE) This framework is used for efficient quantum simulations of chemical systems on nearterm quantum computers.
  arXiv  Detail & Related papers  (2022-12-21T23:15:17Z)
• Mixer-Phaser Ans\"atze for Quantum Optimization with Hard Constraints [1.011960004698409]
  We introduce parametrized circuit ans"atze and present the results of a numerical study comparing their performance with a standard Quantum Alternating Operator Ansatz approach. The ans"atze are inspired by mixing and phase separation in the QAOA, and also motivated by compilation considerations with the aim of running on near-term superconducting quantum processors.
  arXiv  Detail & Related papers  (2021-07-13T04:50:56Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.