Optimizasyon problemlerinin kuantum hesaplama ile çözümü
Solution of optimization problems using quantum computing
Yazar: SABRİ GÜNDÜZ
Danışman: PROF. DR. İHSAN YILMAZ
Çanakkale Onsekiz Mart Üniversitesi / Lisansüstü Eğitim Enstitüsü / Matematik Ana Bilim Dalı
Derece: Doktora, 2024
Konu: Matematik = Mathematics

Özet:
Bu çalışmada, ilk önce bir optimizasyon problemi kuantum optimizasyon yöntemlerinden olan kuantum tavlama yöntemiyle çözülmektedir, ardından Uyarlamalı Grover Arama algoritması yüksek boyuta uyarlanmış ve bu algoritmanın optimizasyon problemlerini çözme becerisi incelenmiştir.
Çalışmanın birinci kısmında Avrupa basketbolunun fantezi basketbol platformlarından olan Euroleague Fantasy Challenge'da (EFC) ideal takım oluşturma (10 oyuncu ve 1 baş antrenör) ve oyuncu dizilişi belirlemeyi içeren bir optimizasyon problemi ele alınmaktadır. Takım oluşturmada EFC'nin bazı oyuncu seçimi kriterlerine ilaveten PTM değerinin en yüksek olması istenmektedir. Bunun için öncelikle problem, ikili tam sayılı programlama (BIP) formatında modellenmektedir; ardından, açık kaynaklı Python kütüphanesi PyQUBO ile Kuadratik Kısıtsız İkili Optimizasyon (Quadratic Unconstrained Binary Optimization -QUBO) formatına çevrilmektedir. İdeal oyuncu listesi ve bir baş antrenör, D-Wave firmasının Leap Hybrid (kuantum-klasik) cihazı ile belirlenerek takım oluşturulmaktadır. Daha sonra bu oyuncu listesini temel alarak en yüksek PTM değerine sahip ideal diziliş belirlenmesi amacıyla BIP modeli oluşturulmaktadır. Ardından bu model aynı işlemlerden geçirilerek hem hibrit hem de pür kuantum tavlayıcı ile çözülmektedir. Sonuç olarak, iki yöntemin de aynı oyuncu dizilişini önerdiği bulunmuştur.
Çalışmanın ikinci kısmında Uyarlamalı Grover Arama (Grover Adaptive Search- GAS) algoritması yüksek boyuta taşınmıştır. Yüksek boyuttaki bu GAS algoritmasının verimliliği, QUBO ve Yüksek Dereceden İkili Optimizasyon (Higher-Order Unconstrained Binary Optimization-HUBO) formatında optimizasyon problemleriyle test edilmiştir. Araştırmanın sonucunda Yüksek boyuttaki GAS algoritmasının daha az kuantum kaynak (küdit) kullanarak optimizasyon problemlerini çözebildiği elde edilmiştir.

Abstract:
This study, first, solves an optimization problem through quantum annealing method, which is one of the quantum optimization methods, and secondly, adapts the Grover Adaptive Search Algorithm into high dimension and examines the ability of this algorithm to solve optimization problems.
The first part of this study addresses an optimization problem that involves building the ideal team (10 players and 1 head coach) in the Euroleague Fantasy Challenge (EFC), one of the fantasy basketball platforms of European basketball, and determining the lineup. To determine the lineup, this study meets some of the EFC's player selection criteria and seeks to have the highest PTM value. To do so, the problem is first converted into in binary integer programming (BIP) format, and then converted to Quadratic Unconstrained Binary Optimization (QUBO) format via the open source Python library, PyQUBO. The ideal players and one head coach are selected using the D-Wave's Leap Hybrid (quantum- classical) device to build the team. Based on this, the BIP model is created to identify the ideal lineup with the highest PTM value. Then, the same operations are performed on this model through both Hybrid and Pure quantum annealers. The results show that both methods yield the same player lineup.
The second part of this study adapts the Grover Adaptive Search (GAS) to high dimension. The efficiency of this high-dimensional GAS algorithm is tested using optimization problems in QUBO and Higher-Order Unconstrained Binary Optimization (HUBO) format. The results significantly indicate that this algorithm achieves to solve optimization problems using less quantum sources (qudits).