Increasing efficiency of combinatorial optimization problems on quantum annealers using classical computers
Başlık çevirisi mevcut değil.
- Tez No: 667955
- Danışmanlar: DR. ÖĞR. ÜYESİ DİDEM UNAT ERTEN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 68
Özet
Google'ın kuantum bilgisayarların klasik bilgisayarlara göre üstünlüğü iddiası, kuantum hesaplama tarihinde büyük bir kilometre taşıdır. İddialara rağmen, kuantum bilgisayarların pratik uygulanabilirliği, düşük kuantum bit sayısı ve yüksek gürültü oranları nedeniyle tartışmalı olmaya devam etmekte. Kuantum hesaplamanın alternatif modeli, yalnızca belirli bir formatta bir optimizasyon problemini çözebilen kuantum tavlamadır. Kuantum tavlama, bu tür cihazların ölçeğinin binlerce kübite kadar çıkması nedeniyle aktif olarak araştırılmaktadır. Bu nispeten yüksek kübit sayısı, kuantum tavlayıcıların daha büyük boyutlardaki sorunları çözmesini sağlar, bu nedenle onları gerçek hayat senaryolarında kullanılabilir hale getirir. Çözülmüş optimizasyon probleminin spesifik formatı, aynı zamanda ikinci dereceden kısıtlanmamış ikili optimizasyon (QUBO) olarak da temsil edilebilen Ising formülasyonu olarak adlandırılır. QUBO, karşılık gelen önyargı ağırlıklarına ve kübitler arasındaki kuadratik ağırlıklara sahip bir kübit kümesinden oluşur. Bu tez, iki farklı kombinatoryal optimizasyon probleminin QUBO formülasyo- nunda ağırlık optimizasyonu için iki şema sunmaktadır. Her iki şema, QUBO'ları çözen bir tavlama cihazı ile arayüzlenen QUBO ağırlıklarını yeniden tanımlayan klasik bir bilgisayarı içerir. İlk kombinatoryal problem, önyargıların görevlerin hesap- lama maliyetlerini temsil ettiği ve ikinci dereceden terimlerin görevler arasındaki iletişimi modellediği görev atama problemidir. İkinci problem, önyargıların kuantum kapılarının aslına uygunluğunu temsil ettiği, ikinci dereceden terimlerin kübit hareketi modellediği devre haritalama problemidir. Ağırlık optimizasyon algoritması (WOA) olarak adlandırılan ilk yaklaşım, kuantum kapılarını fiziksel kübit topolojisine eşlemenin uygunluğundan sorumlu kübit önyargıları ile kübit hareketinden sorumlu ikinci dereceden terimler arasında istenen bir oranı arar. Oranın istenebilirliği, hem kübit hareketinden hem de haritalamadan kaynaklanan toplam aslına uygunluk ile tanımlanır. WOA'nın kuantum devre haritalaması için kuantum tavlama iş akışına eklenmesi, tüm sorunlu örneklerin %72,9'unda kübit hareketinin azalmasına neden oldu. Ayrıca, eşlenen devrenin toplam doğruluğunu IBM Vigo cihazında %39 ve IBM QX2'de %107 oranında artırmaya izin verdi. Deneyler, D-Wave kuantum tavlama yazılım yığınından tabu arama QUBO çözücüsünde gerçekleştirilmiştir. Karınca kolonisi ağırlık optimize edicisinin sonuçları, bir kuantum tavlama cihazının bulunmaması nedeniyle sınırlıdır.
Özet (Çeviri)
Google's claim of quantum supremacy is a big milestone in the history of quantum computing. Despite the claim, the practical applicability of quantum computers remains questionable due to the low number of quantum bits and high noise rates. An alternative model of quantum computing is quantum annealing, which is capable of solving only an optimization problem in a specific format. Quantum annealing is being actively researched due to the fact that the scale of such devices has increased up to thousands of qubits. This relatively high number of qubits enables quantum annealers to solve problems of larger sizes, hence makes them usable in real-life scenarios. The specific format of the solved optimization problem is called an Ising formulation, which can also be represented as quadratic unconstrained binary optimization (QUBO). The QUBO consists of a set of qubits with corresponding bias weights and the quadratic weights between the qubits. This thesis presents two schemes for weight optimization in the QUBO formulation of two different combinatorial optimization problems. Both schemes involve a classical computer redefining the QUBO weights that is interfaced with an annealing device, which solves the QUBOs. The first combinatorial problem is the task assignment problem, in which the biases represent the computational costs of tasks and quadratic terms model communication between tasks. The second problem is the circuit mapping problem, where the biases represent the fidelity of quantum gates, while the quadratic terms model qubit movement. The first approach named weight optimization algorithm (WOA) searches for a desirable ratio between the qubit biases responsible for fidelity of mapping quantum gates to physical qubit topology and the quadratic terms responsible for qubit movement. The desirability of the ratio is defined by the total fidelity resulting from both qubit movement and mapping. The second presented model uses ant colony optimization (ACO) to update the quadratic terms of the QUBO that solves the task assignment problem. However, this model can be generalized to any combinatorial optimization problem solvable by the ACO. Efficient updates of the weights based on the answers from previous QUBOs are expected to guide the reformulated QUBOs towards the optimum of the objective function. At the same time, this algorithm would allow utilizing the stochasticity of quantum annealers for better exploration of the solution space and their speed for faster generation of candidate solutions. The introduction of the WOA into the quantum annealing workflow for quantum circuit mapping resulted in reduced qubit movement in 72.9% of all problem samples. Moreover, it allowed to increase the total fidelity of the mapped circuit by 39% on the IBM Vigo device and 107% on IBM QX2. The experiments have been performed on the tabu search QUBO solver from the D-Wave quantum annealing software stack. The results for the ant colony weight optimizer are limited due to the unavailability of a quantum annealing device.
Benzer Tezler
- Kaynak kısıtlı proje programlama problemlerinin çözümü için yeni yöntem ve algoritmalar
New methods and algorithms for solving the resource-constrained project scheduling problem
İHSAN UĞUR
- Investigation of solution methodologies for the proposed combinatorial scheduling models
Önerilen kombinatoryel çizelgeleme modelleri için çözüm yöntemlerinin araştırılması
ŞEYDA TOPALOĞLU
Doktora
İngilizce
2003
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. İREM ÖZKARAHAN
- Konteyner yükleme problemleri için tabu arama ve pekiştirmeli öğrenme tabanlı bir hibrit yaklaşım
A hybrid approach based on tabu search and reinforcement learning for container loading problems
CANAN HAZAL AKARSU
Doktora
Türkçe
2024
Endüstri ve Endüstri Mühendisliğiİstanbul Üniversitesi-CerrahpaşaEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TARIK KÜÇÜKDENİZ
- The bees algorithm theory, improvements and applications
Arı algorithmsı teori, geliştirmeler ve uygulamalar
EBUBEKİR KOÇ
Doktora
İngilizce
2010
Endüstri ve Endüstri MühendisliğiCardiff University (Prifysgol Caerdydd)Endüstri Mühendisliği Ana Bilim Dalı
PROF. DR. DUC TRUONG PHAM
- Büyük ölçekli havayolu ekip eşleme problemlerinin çözümü için bir kolon türetme stratejisi
A column generation strategy for large scale airline crew pairing problems
BAHADIR ZEREN
Doktora
Türkçe
2017
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM OZKOL