Algoritma kuantum: Algoritma kuantum variasi

nota

Takashi Imamichi (24 Mei 2024)

Muat turun pdf kuliah asal. Perlu diingat bahawa beberapa petikan kod mungkin sudah lapuk kerana ia adalah imej statik.

Anggaran masa QPU untuk menjalankan eksperimen ini ialah 9 minit (diuji pada pemproses Eagle).

(buku nota ini mungkin tidak dapat dinilai dalam masa yang dibenarkan pada Pelan Terbuka. Sila gunakan sumber pengkomputeran kuantum dengan bijak.)

1. Pengenalan

Tutorial ini memberikan gambaran keseluruhan tentang algoritma hibrid kuantum-klasikal, khususnya memfokuskan pada penyelesai eigennilai kuantum variasi (VQE) dan algoritma pengoptimuman anggaran kuantum (QAOA). Objektif utama algoritma-algoritma ini adalah untuk menangani masalah pengoptimuman dengan menggunakan Circuit kuantum dengan Gate kuantum berparameter.

Walaupun terdapat kemajuan dalam pengkomputeran kuantum, kehadiran hingar dalam peranti kuantum semasa menyukarkan pengekstrakan hasil yang bermakna daripada Circuit kuantum yang dalam. Untuk mengatasi cabaran ini, VQE dan QAOA menggunakan pendekatan hibrid kuantum-klasikal, yang melibatkan pelaksanaan berulang Circuit kuantum yang agak pendek menggunakan pengkomputeran kuantum dan pengoptimuman parameter Circuit kuantum berparameter sasaran menggunakan pengkomputeran klasikal.

QAOA berpotensi memberikan penyelesaian optimum kepada masalah sasaran pada skala utiliti, berkat penerapan pelbagai teknik mitigasi dan penindasan ralat. VQE mempunyai banyak aplikasi (seperti kimia kuantum) di mana ia kurang berskala. Tetapi terdapat beberapa pendekatan berkaitan eigennilai yang telah muncul untuk melengkapi dan menambah VQE, termasuk pendiagonalan subruang Krylov dan pendiagonalan kuantum berasaskan pensampelan (SQD). Memahami VQE adalah langkah pertama yang penting dalam memahami pelbagai algoritma hibrid klasikal-kuantum yang telah muncul.

Modul ini menerangkan konsep asas dan pelaksanaan VQE dan QAOA. Tutorial lanjutan akan meneroka topik dan teknik lanjutan untuk menskalakan algoritma-algoritma ini. Anda memerlukan pustaka berikut dalam persekitaran anda untuk menjalankan buku nota ini. Jika anda belum memasangnya lagi, anda boleh memasangnya dengan membuka ulasan dan menjalankan sel berikut.

# Added by doQumentation — required packages for this notebook
!pip install -q matplotlib numpy qiskit qiskit-ibm-runtime rustworkx scipy

# % pip install 'qiskit[visualization]' qiskit-ibm-runtime

2. Mengira eigennilai minimum bagi Hamiltonian mudah

Kita akan mulakan dengan menerapkan VQE pada kes yang sangat mudah, untuk melihat cara ia berfungsi. Kita akan mengira eigennilai minimum bagi matriks Pauli $Z$ dengan VQE. Kita akan mulakan dengan mengimport beberapa pakej umum.

import numpy as np
from qiskit.circuit import ParameterVector, QuantumCircuit
from qiskit.primitives import StatevectorEstimator, StatevectorSampler
from qiskit.quantum_info import SparsePauliOp
from scipy.optimize import minimize

Kita kini menentukan pengoperasi yang diminati dan melihatnya dalam bentuk matriks.

op = SparsePauliOp("Z")
op.to_matrix()

array([[ 1.+0.j,  0.+0.j],
       [ 0.+0.j, -1.+0.j]])

Mudah untuk mendapatkan eigennilai secara klasikal, jadi kita boleh semak kerja kita. Ini mungkin menjadi sukar apabila kita berskala ke arah utiliti. Di sini kita gunakan numpy.

# compute eigenvalues with numpy
result = np.linalg.eigh(op.to_matrix())
print("Eigenvalues:", result.eigenvalues)

Eigenvalues: [-1.  1.]

Untuk mendapatkan eigennilai menggunakan algoritma kuantum variasi, kita membina Circuit dengan Gate yang mengambil parameter variasi:

# define a variational form
param = ParameterVector("a", 3)
qc = QuantumCircuit(1, 1)
qc.u(param[0], param[1], param[2], 0)
qc_estimator = qc.copy()
qc.measure(0, 0)
qc.draw("mpl")

Jika kita ingin menganggarkan nilai jangkaan bagi pengoperasi (seperti $Z$), kita patut gunakan Estimator. Jika kita ingin melihat keadaan sistem, kita gunakan Sampler.

sampler = StatevectorSampler()
estimator = StatevectorEstimator()

Kita boleh mengira kiraan rentetan bit 0 dan 1 dengan nilai parameter rawak [1, 2, 3] menggunakan Sampler.

# compute counts of bitstrings with random parameter values by Sampler
result = sampler.run([(qc, [1, 2, 3])]).result()
counts = result[0].data.c.get_counts()
counts

{'0': 783, '1': 241}

Kita tahu bahawa kita boleh mengira nilai jangkaan Z dengan $\langle Z \rangle = p_0 - p_1$ dengan kebarangkalian $\{0: p_0, 1: p_1\}$.

# compute the expectation value of Z based on the counts
(counts.get("0", 0) - counts.get("1", 0)) / sum(counts.values())

0.529296875

Circuit ini berfungsi, tetapi nilai parameter yang dipilih tidak sepadan dengan keadaan bertenaga rendah (atau eigennilai rendah). Eigennilai yang diperoleh adalah jauh lebih tinggi daripada minimum. Hasilnya adalah serupa apabila menggunakan estimator.

Perlu diingat bahawa Estimator mengambil Circuit kuantum tanpa pengukuran.

result = estimator.run([(qc_estimator, op, [1, 2, 3])]).result()
result[0].data.evs

array(0.54030231)

Kita perlu mencari melalui parameter dan mencari yang menghasilkan eigennilai terendah. Kita membuat fungsi untuk menerima nilai parameter bagi bentuk variasi dan mengembalikan nilai jangkaan $\langle Z \rangle$.

# define a cost function to look for the minimum eigenvalue of Z
def cost(x):
    result = sampler.run([(qc, x)]).result()
    counts = result[0].data.c.get_counts()
    expval = (counts.get("0", 0) - counts.get("1", 0)) / sum(counts.values())
    # the following line shows the trajectory of the optimization
    print(expval, counts)
    return expval

Mari kita terapkan fungsi minimize SciPy untuk mencari eigennilai minimum Z.

# minimize the cost function with scipy's minimize
min_result = minimize(cost, [0, 0, 0], method="COBYLA", tol=1e-8)
min_result

1.0 {'0': 1024}
0.494140625 {'0': 765, '1': 259}
0.466796875 {'0': 751, '1': 273}
0.564453125 {'0': 801, '1': 223}
-0.4296875 {'1': 732, '0': 292}
-0.984375 {'1': 1016, '0': 8}
-0.8984375 {'1': 972, '0': 52}
-0.990234375 {'1': 1019, '0': 5}
-0.892578125 {'1': 969, '0': 55}
-0.986328125 {'1': 1017, '0': 7}
-0.861328125 {'1': 953, '0': 71}
-1.0 {'1': 1024}
-0.982421875 {'1': 1015, '0': 9}
-0.99609375 {'1': 1022, '0': 2}
-0.986328125 {'1': 1017, '0': 7}
-1.0 {'1': 1024}
-0.990234375 {'1': 1019, '0': 5}
-0.998046875 {'1': 1023, '0': 1}
-0.99609375 {'1': 1022, '0': 2}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-0.998046875 {'1': 1023, '0': 1}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-0.998046875 {'1': 1023, '0': 1}
-0.998046875 {'1': 1023, '0': 1}
-0.998046875 {'1': 1023, '0': 1}
-1.0 {'1': 1024}
-0.99609375 {'1': 1022, '0': 2}
-1.0 {'1': 1024}
-0.99609375 {'1': 1022, '0': 2}
-0.998046875 {'1': 1023, '0': 1}
-0.998046875 {'1': 1023, '0': 1}
-0.99609375 {'1': 1022, '0': 2}
-0.998046875 {'1': 1023, '0': 1}
-1.0 {'1': 1024}
-0.998046875 {'1': 1023, '0': 1}
-0.998046875 {'1': 1023, '0': 1}
-0.99609375 {'1': 1022, '0': 2}
-1.0 {'1': 1024}
-0.998046875 {'1': 1023, '0': 1}
-1.0 {'1': 1024}
-0.998046875 {'1': 1023, '0': 1}
-0.998046875 {'1': 1023, '0': 1}
-1.0 {'1': 1024}
-0.998046875 {'1': 1023, '0': 1}
-0.998046875 {'1': 1023, '0': 1}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-0.998046875 {'1': 1023, '0': 1}
-0.994140625 {'1': 1021, '0': 3}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}
-1.0 {'1': 1024}

message: Optimization terminated successfully.
 success: True
  status: 1
     fun: -1.0
       x: [ 3.182e+00  1.338e+00  1.664e-01]
    nfev: 63
   maxcv: 0.0

# check counts of bitstrings with the optimal parameters
result = sampler.run([(qc, min_result.x)]).result()
result[0].data.c.get_counts()

{'0': 1, '1': 1023}

2.1 Latihan

Kira eigennilai minimum bagi $Z \otimes Z$ dengan VQE.

z2 = SparsePauliOp("ZZ")
print(z2)
print(z2.to_matrix())

SparsePauliOp(['ZZ'],
              coeffs=[1.+0.j])
[[ 1.+0.j  0.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j -1.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j -1.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  0.+0.j  1.+0.j]]

# compute eigenvalues with numpy

# define a variational form
# qc = ...

# compute counts of bitstrings with a random parameter values by Sampler
# result = sampler.run(...)
# result

# compute the expectation value of ZZ based on the counts

# verify the expectation value of ZZ with Estimator

# define a cost function to look for the minimum eigenvalue of ZZ
# def cost(x):
#    expval = ...
#    return expval

# minimize the cost function with scipy's minimize
# min_result = minimize(cost, [...], method="COBYLA", tol=1e-8)
# min_result

# check counts of bitstrings with the optimal parameter values
# result = sampler.run(qc, min_result.x).result()
# result

Penyelesaian latihan

Kita menentukan pengoperasi yang diminati dan melihatnya dalam bentuk matriks.

z2 = SparsePauliOp("ZZ")
print(z2)
print(z2.to_matrix())

SparsePauliOp(['ZZ'],
              coeffs=[1.+0.j])
[[ 1.+0.j  0.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j -1.+0.j  0.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j -1.+0.j  0.+0.j]
 [ 0.+0.j  0.+0.j  0.+0.j  1.+0.j]]

Untuk mendapatkan eigennilai menggunakan algoritma kuantum variasi, kita membina Circuit dengan Gate yang mengambil parameter variasi:

# define a variational form
param = ParameterVector("a", 6)
qc = QuantumCircuit(2, 2)
qc.u(param[0], param[1], param[2], 0)
qc.u(param[3], param[4], param[5], 1)
qc_estimator = qc.copy()
qc.measure([0, 1], [0, 1])
qc.draw("mpl")

Jika kita ingin menganggarkan nilai jangkaan bagi pengoperasi (seperti $Z \otimes Z$), kita akan menggunakan Estimator. Jika kita ingin melihat keadaan sistem, kita gunakan Sampler.

sampler = StatevectorSampler()
estimator = StatevectorEstimator()

# compute counts of bitstrings with random parameter values by Sampler
result = sampler.run([(qc, [1, 2, 3, 4, 5, 6])]).result()
counts = result[0].data.c.get_counts()
counts

{'10': 661, '11': 203, '01': 47, '00': 113}

# compute the expectation value of ZZ based on the counts
(
    counts.get("00", 0)
    - counts.get("01", 0)
    - counts.get("10", 0)
    + counts.get("11", 0)
) / sum(counts.values())

-0.3828125

Circuit ini berfungsi, tetapi nilai parameter yang dipilih tidak sepadan dengan keadaan bertenaga rendah (atau eigennilai rendah). Eigennilai yang diperoleh adalah jauh lebih tinggi daripada minimum. Hasilnya adalah serupa apabila menggunakan estimator.

# verify the expectation value of ZZ with Estimator
result = estimator.run([(qc_estimator, z2, [1, 2, 3, 4, 5, 6])]).result()
result[0].data.evs

array(-0.35316516)

Kita perlu mencari melalui parameter dan mencari yang menghasilkan eigennilai terendah.

# define a cost function to look for the minimum eigenvalue of ZZ
def cost(x):
    result = sampler.run([(qc, x)]).result()
    counts = result[0].data.c.get_counts()
    expval = (
        counts.get("00", 0)
        - counts.get("01", 0)
        - counts.get("10", 0)
        + counts.get("11", 0)
    ) / sum(counts.values())
    print(expval, counts)
    return expval

# minimize the cost function with scipy's minimize
min_result = minimize(cost, [0, 0, 0, 0, 0, 0], method="COBYLA", tol=1e-8)
min_result

1.0 {'00': 1024}
0.578125 {'00': 808, '01': 216}
0.5234375 {'00': 780, '01': 244}
0.548828125 {'00': 793, '01': 231}
0.3515625 {'00': 637, '10': 164, '11': 55, '01': 168}
0.3359375 {'00': 638, '11': 46, '10': 174, '01': 166}
0.283203125 {'00': 602, '10': 181, '01': 186, '11': 55}
-0.087890625 {'01': 414, '00': 184, '10': 143, '11': 283}
0.236328125 {'10': 27, '11': 623, '01': 364, '00': 10}
-0.0625 {'11': 261, '01': 403, '00': 219, '10': 141}
0.248046875 {'01': 366, '11': 628, '00': 11, '10': 19}
-0.0625 {'10': 145, '11': 254, '01': 399, '00': 226}
0.228515625 {'01': 373, '11': 609, '00': 20, '10': 22}
0.0546875 {'11': 376, '10': 273, '01': 211, '00': 164}
-0.447265625 {'01': 731, '10': 10, '11': 267, '00': 16}
-0.71484375 {'01': 871, '11': 99, '00': 47, '10': 7}
-0.46484375 {'01': 741, '00': 253, '10': 9, '11': 21}
-0.87890625 {'01': 962, '00': 39, '11': 23}
-0.640625 {'00': 176, '01': 837, '11': 8, '10': 3}
-0.88671875 {'01': 966, '00': 41, '11': 17}
-0.994140625 {'01': 1021, '11': 3}
-0.91796875 {'01': 982, '11': 35, '00': 7}
-0.994140625 {'01': 1021, '11': 2, '00': 1}
-0.939453125 {'01': 993, '00': 31}
-0.990234375 {'01': 1019, '11': 5}
-0.90234375 {'01': 974, '00': 21, '11': 29}
-0.98046875 {'01': 1014, '11': 10}
-0.994140625 {'01': 1021, '00': 3}
-0.990234375 {'01': 1019, '11': 4, '00': 1}
-0.98828125 {'01': 1018, '11': 6}
-0.990234375 {'01': 1019, '11': 4, '00': 1}
-0.994140625 {'01': 1021, '11': 2, '00': 1}
-0.99609375 {'01': 1022, '11': 2}
-0.998046875 {'01': 1023, '00': 1}
-0.99609375 {'01': 1022, '00': 2}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '00': 1}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '00': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '00': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '00': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '00': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-0.99609375 {'01': 1022, '00': 1, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '00': 1}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-0.99609375 {'01': 1022, '11': 1, '00': 1}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '00': 1}
-0.994140625 {'01': 1021, '00': 3}
-0.998046875 {'01': 1023, '00': 1}
-0.99609375 {'01': 1022, '11': 2}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '00': 1}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-0.998046875 {'01': 1023, '11': 1}
-0.99609375 {'01': 1022, '11': 2}
-1.0 {'01': 1024}
-0.998046875 {'01': 1023, '11': 1}

message: Optimization terminated successfully.
 success: True
  status: 1
     fun: -0.998046875
       x: [ 3.167e+00  6.940e-01  1.033e+00 -2.894e-02  8.933e-01
            1.885e+00]
    nfev: 128
   maxcv: 0.0

message: Optimization terminated successfully.
 success: True
  status: 1
     fun: -0.99609375
       x: [ 3.098e+00 -5.402e-01  1.091e+00 -1.004e-02  3.615e-01
            6.913e-01]
    nfev: 115
   maxcv: 0.0

Kita mendapat eigennilai yang sangat hampir dengan minimum yang diberikan oleh numpy.

# check counts of bitstrings with the optimal parameters
result = sampler.run([(qc, min_result.x)]).result()
result[0].data.c.get_counts()

{'01': 1024}

3. Pengoptimuman Kuantum dengan corak Qiskit

Dalam panduan ini kita akan belajar tentang corak Qiskit dan pengoptimuman anggaran kuantum. Corak Qiskit ialah satu set langkah yang intuitif dan boleh diulang untuk melaksanakan aliran kerja pengkomputeran kuantum: Kita akan menggunakan corak ini dalam konteks pengoptimuman kombinatorial dan menunjukkan cara menyelesaikan masalah Max-Cut menggunakan Algoritma Pengoptimuman Anggaran Kuantum (QAOA), iaitu kaedah hibrid (kuantum-klasik) yang berulang.

Perlu diingat bahawa bahagian QAOA ini berdasarkan "Bahagian 1: QAOA skala kecil" daripada tutorial Quantum approximate optimization algorithm. Lihat tutorial itu untuk belajar cara menskalakan masalah ini.

3.1 Corak Qiskit (skala kecil) untuk pengoptimuman

Bahagian ini akan menggunakan masalah Max-Cut berskala kecil untuk menggambarkan langkah-langkah yang diperlukan bagi menyelesaikan masalah pengoptimuman menggunakan komputer kuantum. Masalah Max-Cut ialah masalah pengoptimuman yang sukar diselesaikan (lebih spesifik, ia merupakan masalah NP-susah) dengan pelbagai aplikasi dalam pengelompokan, sains rangkaian, dan fizik statistik. Tutorial ini mempertimbangkan satu graf dengan nod yang dihubungkan oleh tepi dan bertujuan memisahkan nod kepada dua set dengan "memotong" tepi, supaya bilangan tepi yang dipotong dimaksimumkan. Untuk memberikan konteks sebelum memetakan masalah ini kepada algoritma kuantum, kamu boleh memahami dengan lebih baik bagaimana masalah Max-Cut menjadi masalah pengoptimuman kombinatorial klasik dengan terlebih dahulu mempertimbangkan peminimuman fungsi $f(x)$

$$\min_{x\in \{0, 1\}^n}f(x),$$

di mana input $x$ ialah vektor yang komponennya sepadan dengan setiap nod dalam graf. Kemudian, hadkan setiap komponen ini supaya bernilai sama ada $0$ atau $1$ (yang mewakili sama ada ia termasuk atau tidak termasuk dalam potongan). Contoh skala kecil ini menggunakan graf dengan $n=5$ nod.

Kamu boleh menulis fungsi bagi sepasang nod $i,j$ yang menunjukkan sama ada tepi $(i,j)$ yang sepadan berada dalam potongan. Contohnya, fungsi $x_i + x_j - 2 x_i x_j$ bernilai 1 hanya jika salah satu daripada $x_i$ atau $x_j$ bernilai 1 (bermakna tepi itu berada dalam potongan) dan sifar sebaliknya. Masalah memaksimumkan tepi dalam potongan boleh diformulasikan sebagai

$$\max_{x\in \{0, 1\}^n} \sum_{(i,j)} x_i + x_j - 2 x_i x_j,$$

yang boleh ditulis semula sebagai peminimuman dalam bentuk

$$\min_{x\in \{0, 1\}^n} \sum_{(i,j)} 2 x_i x_j - x_i - x_j.$$

Minimum $f(x)$ dalam kes ini berlaku apabila bilangan tepi yang dilalui potongan adalah maksimum. Seperti yang dapat dilihat, tiada kaitan dengan pengkomputeran kuantum lagi. Kamu perlu merumuskan semula masalah ini kepada sesuatu yang dapat difahami oleh komputer kuantum. Mulakan masalah kamu dengan membina graf dengan $n=5$ nod.

import matplotlib
import matplotlib.pyplot as plt
import numpy as np
import rustworkx as rx
from rustworkx.visualization import mpl_draw

n = 5

graph = rx.PyGraph()
graph.add_nodes_from(range(1, n + 1))
edge_list = [
    (0, 1, 1.0),
    (0, 2, 1.0),
    (1, 2, 1.0),
    (1, 3, 1.0),
    (2, 4, 1.0),
    (3, 4, 1.0),
]
graph.add_edges_from(edge_list)
pos = rx.spring_layout(graph, seed=2)
mpl_draw(graph, node_size=600, pos=pos, with_labels=True, labels=str)

3.2 Langkah 1. Petakan input klasik kepada masalah kuantum

Langkah pertama dalam corak ini ialah memetakan masalah klasik (graf) kepada Circuit dan operator kuantum. Untuk melakukan ini, terdapat tiga langkah utama yang perlu diambil:

1. Gunakan satu siri reformulasi matematik untuk mewakili masalah ini menggunakan notasi masalah Pengoptimuman Binari Tidak Berkekangan Kuadratik (QUBO).
2. Tulis semula masalah pengoptimuman sebagai Hamiltonian yang keadaan asasnya sepadan dengan penyelesaian yang meminimumkan fungsi kos.
3. Bina Circuit kuantum yang akan menyediakan keadaan asas Hamiltonian ini melalui proses yang serupa dengan anil kuantum.

Nota: Dalam metodologi QAOA, kamu akhirnya mahu mempunyai operator (Hamiltonian) yang mewakili fungsi kos algoritma hibrid kita, serta Circuit berparameter (Ansatz) yang mewakili keadaan kuantum dengan calon penyelesaian kepada masalah. Kamu boleh mengambil sampel daripada keadaan calon ini dan kemudian menilainya menggunakan fungsi kos.

Graf → masalah pengoptimuman

Langkah pertama pemetaan ini adalah pertukaran notasi. Berikut menyatakan masalah dalam notasi QUBO:

$$\min_{x\in \{0, 1\}^n}x^T Q x,$$

di mana $Q$ ialah matriks $n\times n$ nombor nyata, $n$ sepadan dengan bilangan nod dalam graf kamu, $x$ ialah vektor pemboleh ubah binari yang diperkenalkan di atas, dan $x^T$ menunjukkan transpos vektor $x$.

Problem name: maxcut

Minimize
  2*x_1*x_2 + 2*x_1*x_3 + 2*x_2*x_3 + 2*x_2*x_4 + 2*x_3*x_5 + 2*x_4*x_5 - 2*x_1
  - 3*x_2 - 3*x_3 - 2*x_4 - 2*x_5

Subject to
  No constraints

  Binary variables (5)
    x_1 x_2 x_3 x_4 x_5

Masalah pengoptimuman → Hamiltonian

Kamu kemudian boleh merumuskan semula masalah QUBO sebagai Hamiltonian (di sini, matriks yang mewakili tenaga sistem):

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_iZ_i.$$

Langkah-langkah reformulasi daripada masalah QAOA kepada Hamiltonian

Untuk menunjukkan bagaimana masalah QAOA boleh ditulis semula dengan cara ini, mula-mula gantikan pemboleh ubah binari $x_i$ kepada satu set pemboleh ubah baharu $z_i\in\{-1, 1\}$ melalui

$$x_i = \frac{1-z_i}{2}.$$

Di sini kamu boleh nampak bahawa jika $x_i$ adalah $0$, maka $z_i$ mestilah $1$. Apabila $x_i$ digantikan dengan $z_i$ dalam masalah pengoptimuman ($x^TQx$), formulasi yang setara boleh diperoleh.

$$x^TQx=\sum_{ij}Q_{ij}x_ix_j \\ =\frac{1}{4}\sum_{ij}Q_{ij}(1-z_i)(1-z_j) \\=\frac{1}{4}\sum_{ij}Q_{ij}z_iz_j-\frac{1}{4}\sum_{ij}(Q_{ij}+Q_{ji})z_i + \frac{n^2}{4}.$$

Sekarang jika kita takrifkan $b_i=-\sum_{j}(Q_{ij}+Q_{ji})$, alih keluar faktor awalan, dan suku malar $n^2$, kita tiba kepada dua formulasi setara bagi masalah pengoptimuman yang sama.

$$min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Di sini, $b$ bergantung pada $Q$. Perlu diingat bahawa untuk memperoleh $z^TQz + b^Tz$ kita menggugurkan faktor 1/4 dan ofs malar $n^2$ yang tidak memainkan peranan dalam pengoptimuman.

Kini, untuk mendapatkan formulasi kuantum bagi masalah ini, naikkan taraf pemboleh ubah $z_i$ kepada matriks Pauli $Z$, seperti matriks $2\times 2$ dalam bentuk

$$Z_i = \begin{pmatrix}1 & 0 \\ 0 & -1\end{pmatrix}.$$

Apabila kamu menggantikan matriks-matriks ini dalam masalah pengoptimuman di atas, kamu mendapat Hamiltonian berikut

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_iZ_i.$$

Ingat juga bahawa matriks $Z$ ini dibenamkan dalam ruang pengiraan komputer kuantum, iaitu ruang Hilbert bersaiz $2^n\times 2^n$. Oleh itu, kamu harus memahami suku seperti $Z_iZ_j$ sebagai hasil darab tensor $Z_i\otimes Z_j$ yang dibenamkan dalam ruang Hilbert $2^n\times 2^n$. Contohnya, dalam masalah dengan lima pemboleh ubah keputusan, suku $Z_1Z_3$ difahami sebagai $I\otimes Z_3\otimes I\otimes Z_1\otimes I$ di mana $I$ ialah matriks identiti $2\times 2$.

Hamiltonian ini dipanggil Hamiltonian fungsi kos. Ia mempunyai sifat bahawa keadaan asasnya sepadan dengan penyelesaian yang meminimumkan fungsi kos $f(x)$. Oleh itu, untuk menyelesaikan masalah pengoptimuman kamu, kamu kini perlu menyediakan keadaan asas $H_C$ (atau keadaan dengan pertindihan tinggi dengannya) pada komputer kuantum. Kemudian, mengambil sampel daripada keadaan ini akan, dengan kebarangkalian yang tinggi, menghasilkan penyelesaian kepada $\min~f(x)$.

def build_max_cut_operator(graph: rx.PyGraph) -> tuple[SparsePauliOp, float]:
    sp_list = []
    constant = 0
    for s, t in graph.edge_list():
        w = graph.get_edge_data(s, t)
        sp_list.append(("ZZ", [s, t], w / 2))
        constant -= 1 / 2
    return SparsePauliOp.from_sparse_list(
        sp_list, num_qubits=graph.num_nodes()
    ), constant

cost_hamiltonian, constant = build_max_cut_operator(graph)
print("Cost Function Hamiltonian:", cost_hamiltonian)
print("Constant:", constant)

Cost Function Hamiltonian: SparsePauliOp(['IIIZZ', 'IIZIZ', 'IIZZI', 'IZIZI', 'ZIZII', 'ZZIII'],
              coeffs=[0.5+0.j, 0.5+0.j, 0.5+0.j, 0.5+0.j, 0.5+0.j, 0.5+0.j])
Constant: -3.0

Hamiltonian → Circuit kuantum

Hamiltonian $H_C$ mengandungi definisi kuantum masalah kamu. Kini kamu boleh membina Circuit kuantum yang akan membantu mengambil sampel penyelesaian yang baik daripada komputer kuantum. QAOA diilhamkan oleh anil kuantum dan menggunakan lapisan operator berselang-seli dalam Circuit kuantum.

Idea umumnya adalah bermula dalam keadaan asas sistem yang diketahui, $H^{\otimes n}|0\rangle$ di atas, dan kemudian mengarahkan sistem ke dalam keadaan asas operator kos yang diminati. Ini dilakukan dengan menggunakan operator $\exp\{-i\gamma_k H_C\}$ dan $\exp\{-i\beta_k H_m\}$ dengan sudut $\gamma_1,...,\gamma_p$ dan $\beta_1,...,\beta_p~$.

Circuit kuantum yang kamu jana adalah berparameter dengan $\gamma_i$ dan $\beta_i$, jadi kamu boleh mencuba nilai $\gamma_i$ dan $\beta_i$ yang berbeza dan mengambil sampel daripada keadaan yang terhasil. Dalam kes ini kita akan mencuba contoh dengan 1 lapisan QAOA yang mengandungi dua parameter: $\gamma_1$ dan $\beta_1$.

from qiskit.circuit.library import QAOAAnsatz

circuit = QAOAAnsatz(cost_operator=cost_hamiltonian, reps=1)
circuit.measure_all()
circuit.draw("mpl")

circuit.decompose(reps=3).draw("mpl", fold=-1)

circuit.parameters

ParameterView([ParameterVectorElement(β[0]), ParameterVectorElement(γ[0])])

3.3 Langkah 2. Optimumkan Circuit untuk pelaksanaan perkakasan kuantum

Circuit di atas mengandungi satu siri abstraksi yang berguna untuk berfikir tentang algoritma kuantum, tetapi tidak boleh dijalankan pada perkakasan. Untuk dapat dijalankan pada QPU, Circuit perlu melalui satu siri operasi yang membentuk langkah Transpiler atau pengoptimuman Circuit dalam corak.

Pustaka Qiskit menawarkan satu siri laluan Transpiler yang melayani pelbagai transformasi Circuit. Kamu perlu memastikan Circuit kamu dioptimumkan untuk tujuan kamu.

Transpiler mungkin melibatkan beberapa langkah, seperti:

• Pemetaan awal Qubit dalam Circuit (seperti pemboleh ubah keputusan) kepada Qubit fizikal pada peranti.
• Pengembangan arahan dalam Circuit kuantum kepada arahan asli perkakasan yang difahami oleh Backend.
• Penghalaan mana-mana Qubit dalam Circuit yang berinteraksi kepada Qubit fizikal yang bersebelahan antara satu sama lain.
• Penindasan ralat dengan menambah Gate satu Qubit untuk mengurangkan bunyi dengan penyahgandingan dinamik.

Maklumat lanjut tentang Transpiler boleh didapati dalam dokumentasi kami.

Kod berikut mengubah dan mengoptimumkan Circuit abstrak kepada format yang sedia untuk dilaksanakan pada salah satu peranti yang boleh diakses melalui awan menggunakan perkhidmatan Qiskit IBM® Runtime.

Perlu diingat bahawa kamu boleh menguji program kamu secara tempatan dengan "mod pengujian tempatan" sebelum menghantarnya ke komputer kuantum sebenar. Maklumat lanjut tentang mod pengujian tempatan boleh didapati dalam dokumentasi.

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Use a quantum device
service = QiskitRuntimeService()
backend = service.least_busy(min_num_qubits=127)
# backend = service.backend("ibm_kingston")

# You can test your programs locally with a fake backend (local testing mode)
# backend = FakeBrisbane()

print(backend)

# Create pass manager for transpilation
pm = generate_preset_pass_manager(optimization_level=3, backend=backend)

candidate_circuit = pm.run(circuit)
candidate_circuit.draw("mpl", fold=False, idle_wires=False)

service = QiskitRuntimeService(channel="ibm_quantum_platform")

<IBMBackend('ibm_strasbourg')>

3.4 Langkah 3. Laksanakan menggunakan primitif Qiskit

Dalam aliran kerja QAOA, parameter QAOA yang optimum ditemui dalam gelung pengoptimuman berulang, yang menjalankan satu siri penilaian Circuit dan menggunakan pengoptimum klasik untuk mencari parameter $\beta_k$ dan $\gamma_k$ yang optimum. Gelung pelaksanaan ini dilaksanakan melalui langkah-langkah berikut:

1. Takrifkan parameter awal
2. Wujudkan Session baharu yang mengandungi gelung pengoptimuman dan primitif yang digunakan untuk mengambil sampel Circuit
3. Setelah set parameter yang optimum ditemui, laksanakan Circuit sekali lagi untuk mendapatkan taburan akhir yang akan digunakan dalam langkah pasca-pemprosesan.

Takrifkan Circuit dengan parameter awal

Kita bermula dengan parameter yang dipilih secara rawak.

initial_gamma = np.pi
initial_beta = np.pi / 2
init_params = [initial_gamma, initial_beta]

Takrifkan Backend dan primitif pelaksanaan

Gunakan primitif Qiskit Runtime untuk berinteraksi dengan Backend IBM®. Dua primitif tersebut adalah Sampler dan Estimator, dan pilihan primitif bergantung pada jenis pengukuran yang ingin kamu jalankan pada komputer kuantum. Untuk peminimuman $H_C$, gunakan Estimator kerana pengukuran fungsi kos adalah sekadar nilai jangkaan $\langle H_C \rangle$.

Jalankan

Primitif menawarkan pelbagai mod pelaksanaan untuk menjadualkan beban kerja pada peranti kuantum, dan aliran kerja QAOA berjalan secara berulang dalam sebuah Session. Kamu boleh memasukkan fungsi kos berasaskan Sampler ke dalam rutin peminimuman SciPy untuk mencari parameter yang optimum.

def cost_func_estimator(params, ansatz, hamiltonian, estimator):
    # transform the observable defined on virtual qubits to
    # an observable defined on all physical qubits
    isa_hamiltonian = hamiltonian.apply_layout(ansatz.layout)

    pub = (ansatz, isa_hamiltonian, params)
    job = estimator.run([pub])

    results = job.result()[0]
    cost = results.data.evs

    objective_func_vals.append(cost)

    return cost

from qiskit_ibm_runtime import Session, EstimatorV2
from scipy.optimize import minimize

objective_func_vals = []  # Global variable
with Session(backend=backend) as session:
    # If using qiskit-ibm-runtime<0.24.0, change `mode=` to `session=`
    estimator = EstimatorV2(mode=session)
    estimator.options.default_shots = 1000

    # Set simple error suppression/mitigation options
    estimator.options.dynamical_decoupling.enable = True
    estimator.options.dynamical_decoupling.sequence_type = "XY4"
    estimator.options.twirling.enable_gates = True
    estimator.options.twirling.num_randomizations = "auto"

    result = minimize(
        cost_func_estimator,
        init_params,
        args=(candidate_circuit, cost_hamiltonian, estimator),
        method="COBYLA",
        tol=1e-2,
    )
    print(result)

message: Optimization terminated successfully.
 success: True
  status: 1
     fun: -0.6557925874481715
       x: [ 2.873e+00  9.414e-01]
    nfev: 21
   maxcv: 0.0

Pengoptimum berjaya mengurangkan kos dan menemui parameter yang lebih baik untuk Circuit.

plt.figure(figsize=(12, 6))
plt.plot(objective_func_vals)
plt.xlabel("Iteration")
plt.ylabel("Cost")
plt.show()

Setelah kamu menemui parameter optimum untuk Circuit, kamu boleh menetapkan parameter ini dan mengambil sampel taburan akhir yang diperoleh dengan parameter yang dioptimumkan. Di sinilah primitif Sampler harus digunakan kerana ia adalah taburan kebarangkalian pengukuran bitstring yang sepadan dengan potongan optimum pada graf.

Nota: Ini bermakna menyediakan keadaan kuantum $\psi$ dalam komputer dan kemudian mengukurnya. Pengukuran akan meruntuhkan keadaan ke dalam satu keadaan asas pengiraan — contohnya, 010101110000... — yang sepadan dengan calon penyelesaian $x$ kepada masalah pengoptimuman awal kita ($\max f(x)$ atau $\min f(x)$ bergantung pada tugasan).

optimized_circuit = candidate_circuit.assign_parameters(result.x)
optimized_circuit.draw("mpl", fold=False, idle_wires=False)

from qiskit_ibm_runtime import SamplerV2

# If using qiskit-ibm-runtime<0.24.0, change `mode=` to `backend=`
sampler = SamplerV2(mode=backend)

# Set simple error suppression/mitigation options
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XY4"
sampler.options.twirling.enable_gates = True
sampler.options.twirling.num_randomizations = "auto"

pub = (optimized_circuit,)
job = sampler.run([pub], shots=int(1e4))
counts_int = job.result()[0].data.meas.get_int_counts()
counts_bin = job.result()[0].data.meas.get_counts()
shots = sum(counts_int.values())
final_distribution_int = {key: val / shots for key, val in counts_int.items()}
final_distribution_bin = {key: val / shots for key, val in counts_bin.items()}
print(final_distribution_int)

{12: 0.0652, 31: 0.0089, 4: 0.0085, 13: 0.0731, 26: 0.0256, 28: 0.0246, 17: 0.0405, 25: 0.0591, 20: 0.031, 15: 0.0221, 8: 0.017, 21: 0.0371, 14: 0.0461, 16: 0.0229, 19: 0.0723, 23: 0.0199, 22: 0.0478, 18: 0.0708, 24: 0.0165, 6: 0.0525, 7: 0.0155, 5: 0.0245, 3: 0.0231, 29: 0.0121, 30: 0.0062, 10: 0.0363, 1: 0.0097, 9: 0.042, 27: 0.0094, 11: 0.0349, 0: 0.0129, 2: 0.0119}

3.5 Langkah 4. Proses selepas, kembalikan keputusan dalam format klasik

Langkah pasca-pemprosesan mentafsirkan output pensampelan untuk mengembalikan penyelesaian bagi masalah asal kamu. Dalam kes ini, kamu berminat dengan bitstring yang mempunyai kebarangkalian tertinggi kerana ia menentukan potongan optimum. Simetri dalam masalah ini membolehkan empat penyelesaian yang mungkin, dan proses pensampelan akan mengembalikan salah satu daripadanya dengan kebarangkalian yang sedikit lebih tinggi, tetapi kamu boleh lihat dalam taburan yang diplot di bawah bahawa empat daripada bitstring tersebut jauh lebih berkemungkinan berbanding yang lain.

# auxiliary functions to sample most likely bitstring
def to_bitstring(integer, num_bits):
    result = np.binary_repr(integer, width=num_bits)
    return [int(digit) for digit in result]

keys = list(final_distribution_int.keys())
values = list(final_distribution_int.values())
most_likely = keys[np.argmax(np.abs(values))]
most_likely_bitstring = to_bitstring(most_likely, len(graph))
most_likely_bitstring.reverse()

print("Result bitstring:", most_likely_bitstring)

Result bitstring: [1, 0, 1, 1, 0]

import matplotlib.pyplot as plt

matplotlib.rcParams.update({"font.size": 10})
final_bits = final_distribution_bin
values = np.abs(list(final_bits.values()))
top_4_values = sorted(values, reverse=True)[:4]
positions = []
for value in top_4_values:
    positions.append(np.where(values == value)[0])
fig = plt.figure(figsize=(11, 6))
ax = fig.add_subplot(1, 1, 1)
plt.xticks(rotation=45)
plt.title("Result Distribution")
plt.xlabel("Bitstrings (reversed)")
plt.ylabel("Probability")
ax.bar(list(final_bits.keys()), list(final_bits.values()), color="tab:grey")
for p in positions:
    ax.get_children()[p[0].item()].set_color("tab:purple")
plt.show()

Visualisasi potongan terbaik

Daripada bitstring optimum, kamu boleh menggambarkan potongan ini pada graf asal.

colors = ["tab:grey" if i == 0 else "tab:purple" for i in most_likely_bitstring]
mpl_draw(graph, node_size=600, pos=pos, with_labels=True, labels=str, node_color=colors)

Dan kira nilai potongan tersebut. Penyelesaian ini tidak optimum disebabkan oleh hingar (nilai potongan bagi penyelesaian optimum ialah 5).

from typing import Sequence

def evaluate_sample(x: Sequence[int], graph: rx.PyGraph) -> float:
    assert len(x) == len(
        list(graph.nodes())
    ), "The length of x must coincide with the number of nodes in the graph."
    return sum(
        x[u] * (1 - x[v]) + x[v] * (1 - x[u]) for u, v in list(graph.edge_list())
    )

cut_value = evaluate_sample(most_likely_bitstring, graph)
print("The value of the cut is:", cut_value)

The value of the cut is: 5

Ini menamatkan tutorial QAOA skala kecil. Kamu akan belajar cara menyesuaikan QAOA pada skala utiliti dalam "Bahagian 2: tingkatkan skalanya!" dalam tutorial Quantum approximate optimization algorithm.

# Check Qiskit version
import qiskit

qiskit.__version__

'2.0.2'