Impact of a Warm-Start Strategy on Quantum Approximate Optimization Algorithm (QAOA) Performance While Solving The Single Machine Scheduling Problem

Creative Commons License

Çağlar Gençosman B., Özmutlu S.

ARCENG VII. INTERNATIONAL SCIENTIFIC RESEARCH CONGRESS, İstanbul, Türkiye, 27 - 28 Haziran 2026, cilt.1, ss.220-228, (Tam Metin Bildiri)

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 1
  • Basıldığı Şehir: İstanbul
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.220-228
  • Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
  • Bursa Uludağ Üniversitesi Adresli: Evet

Özet

In search of a faster alternative solution, researchers began applying quantum computing to solve NP-hard scheduling problems. The Single Machine Weighted Tardiness Problem (SMWTP) is an important NP-hard problem in the scheduling literature and is well-suited to quantum computing solutions. Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm that can be used to solve SMWTP. However, computational times might be important in the application of QAOA, since the number of qubits required to solve a problem increases with problem size. This study proposes a warm-start strategy to reduce solution time and improve solution quality in quantum computing. The SMWTP is first modeled as a mathematical program, then converted to a Quadratic Binary Optimization (QUBO) format to be solved by quantum methods. Then, the QUBO is expressed as an Ising Hamiltonian. Instead of initializing the circuit in a uniform superposition, the initial quantum state is encoded from a classical solution obtained using a warm-start heuristic, chosen as WSPT in this study. The QAOA circuit is executed by alternately applying the cost and mixing Hamiltonians, followed by measurement and subsequent classical evaluation of the weighted tardiness values. Test instances, in which algorithm parameters—such as penalty values and circuit depth—are systematically varied for comprehensive experimentation, are run to demonstrate the algorithm’s performance. Analyses reveal that warm-start initialization yields a lower average optimality gap and a higher number of optimal solutions compared to the no-warm-start strategy, confirming that initializing from the WSPT heuristic solution guides the quantum state toward higher-quality regions of the solution space.