Pushing the Limits of Quantum Computing: Variational Algorithms for Solving NP-Hard Problems - Austin Wenxuan Li; Lilis Stianingsih; Ana Utami Zainal (Ambidextrous Journal of Innovation Efficiency and Technology in Organization, 2026)
This study explores the application of variational quantum algorithms to solve NP-hard combinatorial optimization problems, focusing specifically on the MaxBisection problem. The research introduces an enhanced hybrid quantum-classical framework, HTAAC-QSDP, which combines problem-informed ansatz design with semidefinite programming (SDP) relaxation and iterative optimization. Simulation results across multiple graph instances show that the proposed method achieves approximation ratios consistently above 0.95, approaching classical SDP benchmarks. Experiments also demonstrate the sensitivity of performance to key hyperparameters such as circuit depth, rotation scaling, and learning rate. Additionally, hardware implementation on IBM quantum devices reveals the model’s resilience under noise, provided that initialization and optimization strategies are carefully tuned. The findings suggest that variational quantum approaches can provide high-quality approximations for complex NP-hard problems, even in the noisy intermediate-scale quantum (NISQ) era. The results lay the groundwork for scalable quantum optimization frameworks and support the advancement of quantum advantage in real-world applications.