QAOA: optimizasyon problemlerine kuantum yaklaşım

Bir ağı iki gruba en iyi şekilde bölmek gibi optimizasyon problemlerini kuantum devresine çeviren QAOA algoritmasını MaxCut örneğiyle öğren ve açılarını Qiskit’le bul.

Optimizasyon ve MaxCut

Lojistikte rota planlamak, finansta portföy seçmek, bir ağı en iyi şekilde bölmek: hepsi çok sayıda seçenek arasından en iyisini bulma problemidir. Seçenek sayısı problemle birlikte üstel büyüdüğü için birçoğu klasik bilgisayarlarda da zordur.

MaxCut bunların en bilinen örneğidir: bir grafın düğümlerini iki gruba ayır, iki ucu farklı gruplarda olan kenar sayısını en büyük yap. Her düğüme bir kübit verilir; 0 bir grubu, 1 diğer grubu gösterir. İki düğüm ve aralarında tek bir kenar varsa en iyi kesimler 01 ve 10’dur.

Maliyet ve karıştırıcı katmanlar

Her kenar, Qiskit kursunda gördüğün ZZ gözlemlenebiliriyle puanlanır: iki bit farklıysa ZZ = −1, aynıysa +1. Bu yüzden ZZ’yi küçültmek kenarı kesmek demektir. QAOA, bütün kesimlerin eşit süperpozisyonuyla başlar ve iki katmanı sırayla uygular.

Maliyet katmanı her kenar için γ açılı bir rzz kapısıdır ve iyi kesimlerin fazını kaydırır. Karıştırıcı katman her kübite β açılı bir rx kapısıdır ve bu fazları girişimle olasılığa çevirir. γ ve β’yı klasik bir optimizasyon seçer; tıpkı VQE’deki gibi.

import numpy as np
from qiskit import QuantumCircuit
from qiskit.circuit import Parameter
from qiskit.quantum_info import Statevector

gamma, beta = Parameter('gamma'), Parameter('beta')
qc = QuantumCircuit(2)
qc.h([0, 1])                 # bütün kesimlerin eşit süperpozisyonu
qc.rzz(2 * gamma, 0, 1)      # maliyet katmanı: kenar için ZZ
qc.rx(2 * beta, [0, 1])      # karıştırıcı katman

best = (0, 0, 0)
for g in np.linspace(0, np.pi, 25):
    for b in np.linspace(0, np.pi, 25):
        p = Statevector(qc.assign_parameters({gamma: g, beta: b})).probabilities_dict()
        cut = p.get('01', 0) + p.get('10', 0)
        if cut > best[0]:
            best = (cut, g, b)
print(best)   # yaklaşık (1.0, 0.785, 1.178): γ = π/4, β = 3π/8

Katman sayısı ve gerçek problemler

Tek kenarlı bu küçük örnekte tek bir katman (p = 1) en iyi kesimi %100 olasılıkla bulur. Büyük graflarda tek katman genellikle yetmez; katman sayısı p arttıkça QAOA en iyi cevaba yaklaşır, ama devre de uzar ve gürültü artar.

QAOA 2014’te önerildi ve bugünkü cihazlarda en çok denenen optimizasyon algoritmasıdır. Yine de büyük, gerçek problemlerde en iyi klasik yöntemleri geçtiği henüz gösterilmedi; bu, aktif bir araştırma konusudur.

Kendin dene

Bu devre iki düğümlü grafın iki en iyi kesimini, 01 ve 10’u, eşit olasılıkla verir; iyi ayarlanmış bir QAOA’nın varmak istediği sonuç budur. q1’deki X kapısını kaldır: sonuçlar 00 ve 11 olur, yani düğümler hep aynı gruba düşer ve kenar hiç kesilmez.

Tarayıcıda dene (kurulum yok)

Akılda kalsın

MaxCut’ta her düğüm bir kübittir; kesilen her kenar için ZZ = −1 olur.
QAOA eşit süperpozisyonla başlar, maliyet (rzz) ve karıştırıcı (rx) katmanlarını sırayla uygular.
γ ve β açılarını klasik bir optimizasyon seçer; katman sayısı arttıkça sonuç iyileşir.
Büyük problemlerde klasik yöntemlere karşı üstünlüğü henüz kanıtlanmadı.

Kendini sına

İki düğüm ve aralarında bir kenar olan grafta en iyi kesimler hangileridir?

00 ve 11
01 ve 10
Yalnızca 11

Cevabı göster

01 ve 10. Kenarın kesilmesi için iki düğüm farklı gruplarda olmalı: 01 ya da 10.

← VQE: bir molekülün en düşük enerjisini bulmak · Kuantum yürüyüşleri: rastgele yürüyüşün kuantum hâli →