## JEPIN
(Jurnal Edukasi dan Penelitian Informatika)
ISSN(e): 2548-9364 / ISSN(p) : 2460-0741
No. 2 Agustus 2021

## Analisis Metode Quantum untuk Optimalisasi Algoritma Best First Search
Rafiqa Dewi #1 , Muhammad Ridwan Lubis *2
# Manajemen Informatika, AMIK Tunas Bangsa Pematangsiantar Jl. Sudirman Blok A no. 1/2/3 Pematangsiantar
1 rafiqa@amiktunasbangsa.ac.id
* Komputerisasi Komputer, AMIK Tunas Bangsa Pematangsiantar Jl. Sudirman Blok A no. 1/2/3 Pematangsiantar
2 ridwanlubis@amiktunasbangsa.ac.id
Abstrak — Pada penelitian ini, penulis mengusulkan metode quantum  untuk  menggantikan  perhitungan  klasik  pada algoritma  Best  First  Search,  yang  bertujuan  untuk meningkatkan algoritma BFS dalam mencari solusi terbaik, dengan membuatnya bekerja lebih cepat. Penulis menggantikan  setiap  informasi  yang  disimpan  dalam  bit  ke dalam  bentuk  qubit.  Penulis  telah  melakukan  percobaan terhadap  2 3 solusi  dengan  3  qubit.  Setelah  menerapkan pendekatan  qubit  ini  pada  perhitungan  BFS  klasik  maka diperoleh hasil akhir berupa perolehan solusi terbaik dengan percepatan yang signifikan. Dimana perhitungan BFS Klasik melakukan  8  kali  perhitungan  sementara  BFS  Quantum melakukannya hanya dengan 1 kali perhitungan saja.
Kata  kunci — Quantum,  Searching,  Best  First  Search, Optimasi, Algoritma

## I. P ENDAHULUAN
Algoritma Best First Search merupakan algoritma yang dipakai  untuk  mendukung  pola  penalaran  dalam  sistem pakar, dalam melakukan panduan pencarian ke arah node yang tepat dimana solusi dari masalah berada. Pendekatan yang dilakukan yaitu pencarian solusi terbaik berdasarkan pengetahuan  yang  dimiliki  sehingga  penelusuran  yang dilakukan  dapat  ditentukan  mulai  dari  mana  dan bagaimana  menggunakan  proses  terbaik  untuk  pencarian solusi[1].
Sedangkan pada algoritma quantum, langkah penyelesaian  masalah  dan  instruksi  diimplementasikan pada komputer quantum. Algoritma quantum memanfaatkan  fitur-fitur  dasar  dari  komputasi  quantum seperti quantum superposition atau quantum entanglement. Menurut  penelitian  yang  telah  dilakukan,  penggunaan fitur-fitur ini telah mampu mengoptimasi pemrosesan data, terutama pengolahan data besar[2].
Pada  penelitian  ini,  penulis  akan  menerapkan perhitungan  kuantum  pada  algoritma  Best  First  Search klasik/konvensional  untuk  memperoleh  hasil  pencarian yang lebih cepat.

## II. LANDASAN TEORI
Teori  kuantum  adalah  di  antara  revolusi  konseptual yang  paling  signifikan  abad  ke ‐ 20.  Pemahaman  akan teori ‐ teori  ini  menyebabkan  kemajuan  besar  teknologi abad ini. Pada abad ke ‐ 21 ini, kita berharap dapat melihat teori ‐ teori  ini  bersatu  untuk  membentuk  sebuah  kekuatan yang lebih kuat untuk kemajuan: teori kuantum informasi. Para  ilmuwan  memprediksi  bahwa  sekitar  2030  ada kemungkinan  komputer  sudah  tidak  memiliki  transistor dan  chip.  Bayangkan  sebuah  komputer  yang  jauh  lebih cepat  daripada  komputer  silikon  umum  klasik  saat  ini. Komputer  tersebut  boleh  jadi  adalah  sebuah  komputer kuantum.
Secara  teoritis  komputer  kuantum  dapat  beroperasi tanpa  konsumsi  energi  yang  besar  dan  miliar  kali  lebih cepat  dari  komputer  saat  ini.  Komputer  kuantum diprediksi  akan  mengungguli  komputer  klasik  dalam tugas-tugas tertentu, seperti memfaktorkan bilangan  besar dan  mencari  basis  data.  Konstruksi  komputer  yang operasinya  didasarkan  pada  prinsip-prinsip  mekanika kuantum  tampak  sangat  menantang.  Pendekatan solid state menawarkan  potensi  untuk  menjawab  tantangan  ini dengan  membuat  nanomaterial  baru  yang  sesuai  untuk pemrosesan informasi kuantum (QIP)[3] .
Kuantum  komputer  juga  dapat  diimpementasikan pada  pekerjaan  klastering  atau  pengelompokan  data.  Jika representasi spasial dari data memungkinkan pengelompokan  yang  bermakna  menggunakan  informasi geometris,  pengelompokan  kuantum/Quantum  Clustering (QC) akan melakukan pekerjaan itu[4].

## A. Komputer Quantum
Komputer  quantum  memiliki  fungsi  kerja  yang  mirip dengan  komputer  klasik,  namun  terbentuk  dan  memiliki cara  kerja  yang  berbeda.  Komputer  klasik  memiliki memori  yang  tersusun  atas  bit-bit.  Tiap  bit  ini  tersusun atas  0  dan  1.  Komputer  qunatum  terdiri  dari  sekumpulan qubits.  Sebuah  qubit  bisa  merepresentasikan  nilai  satu
atau nol, atau berada pada quantum superposition dari dua state tersebut. Sepasang qubit akan mampu berada pada 4 state  quantum  superposition,  dan  tiga  qubit  pada  4  state quantum  superposition.  Secara  umum  sebuah  komputer kuantum  dengan  n  qubit  akan  bisa  berada  pada  2^n  state berbeda  dalam  waktu  yang  sama.  Sedangkan  pada komputer biasa hanya 1 state dari tiap 2^n state itu dalam satu waktu.
Pada  penelitian  yang ditulis oleh Rahmat M.Sidik, dkk (2020)  disimpulkan  bahwa  transformasi  Bravyi-Kitaev cenderung lebih efektif dan efisien ketika mensimulasikan molekul  terlebih  jika  molekul  yang  disimulasikan memiliki jumlah orbital yang banyak[5].
Pada  penelitian  selanjutnya  disebutkan  bahwa  secara eksplisit  gagasan  akselerator  kuantum  yang  berisi tumpukan penuh lapisan akselerator. Tumpukan seperti itu dimulai  pada  tingkat  tertinggi  yang  menggambarkan aplikasi target akselerator. Lapisan berikutnya mengabstraksi logika kuantum yang menguraikan algoritma yang akan dieksekusi pada akselerator kuantum [6].
Komputer  kuantum,  jika  direalisasikan  sepenuhnya, menjanjikan teknologi revolusioner. Akibatnya, komputasi  kuantum  telah  menjadi  salah  satu  bidang penelitian terpanas dalam beberapa tahun terakhir. Zaman kuantum  tampaknya  akan  tiba  lebih  cepat  daripada  nanti karena  mesin  berukuran  kecil  hingga  menengah  yang berguna  secara  komersial  telah  dibuat.  Namun,  komputer kuantum  skala  penuh,  dan  algoritma  skala  penuh  yang akan  mereka  lakukan,  tetap  di  luar  jangkauan  untuk  saat ini. Saat ini tidak pasti bagaimana komputer pertama akan dibangun.  Banyak  teknologi  berbeda  bersaing  untuk menjadi komputer kuantum skalabel pertama[7].

## B. Qubits
Qubit  adalah  versi  kuantum  dari  bit  klasik.  Sama seperti  bit,  qubit  memiliki  dua  status  dan  dapat  mewakili informasi  dalam format biner. Namun, qubit bisa eksis di kedua  negara  pada  saat  yang  sama  karena  superposisi. Informasi  yang  terkandung  dalam  satu  qubit  dapat dijelaskan  oleh  dua  bilangan  kompleks  dan  biasanya ditulis sebagai:[7]
α |0 ⟩ + β |1 ⟩

## C. Superposisi
Teori  komputasi  kuantum  sangat  terinspirasi  oleh fenomena partikel pada mekanika kuantum. Fenomena ini disebut  dengan superposisi  dimana sebuah partikel  dalam mekanika kuantum dapat memiliki dua keadaan sekaligus. Superposisi dari sebuah pertikel ini jika ditransformasikan kedalam komputasi  dapat  berupa bit dimana nilai dari  bit hanya  terdiri  dari  0  atau  1  akan  tetapi  dalam  komputasi kuantum  nilai  bit  dapat  berupa  0  atau  1  atau  kombinasi dari kedua nilai[8].

## D. Pendekatan Metode Kuantum untuk Klasifikasi
Komputer  kuantum  sekarang  dapat  menganalisis  data input  di  ruang fitur  ini.  Berdasarkan  ini,  kami  membahas dua pendekatan untuk  membangun model kuantum untuk klasifikasi.  Pada  pendekatan  pertama,  perangkat  kuantum memperkirakan  produk  dalam  dari  keadaan  kuantum untuk  menghitung  kernel  yang  tidak  dapat  dipecahkan secara klasik. Kernel  dapat  dimasukkan ke dalam metode kernel  klasik  seperti  mesin  vektor  dukungan.  Dalam pendekatan kedua, kami menggunakan rangkaian kuantum variasi sebagai model linier yang mengklasifikasikan data secara eksplisit dalam ruang Hilbert[9].

## E. Pendekatan Metode Quantum untuk Pencarian Data
Secara  tradisional,  heuristik  digunakan  untuk  memilih di antara kemungkinan jalur pohon, idealnya menghasilkan  urutan  optimal  dari  tindakan  yang dihasilkan  dari  pohon  pencarian  diperluas  yang  tidak seragam.  Pada  pandangan  pertama,  operasi  seperti  itu tampaknya  tidak  mungkin  dilakukan  kuantum  secara mekanis[10].
Algoritma  pencarian  pohon  tradisional  menyediakan cetak biru untuk pemodelan perilaku pemecahan masalah. Berbagai  spektrum  masalah  dapat  dirumuskan  dalam istilah  dari  pencarian  pohon.  Komputasi  kuantum, khususnya algoritma Grover, telah membangkitkan sangat menarik  karena  memungkinkan  percepatan  kuadrat diperoleh dalam pencarian Prosedur[11].

## F. Best First Search
Metode  Best  First  Search  biasanya  digunakan  dalam pencarian  ruang  pencarian  dinamis  dengan  informasi heuristik  yang  memungkinkan  metode  untuk  menemukan keadaan  tujuan  atau  solusi  dengan  menghasilkan  hanya sebagian  kecil  dari  ruang  pencarian.  Pencarian ini  efisien karena  selalu  mempertimbangkan  node  atau  state  yang paling  menjanjikan  untuk  ekspansi  atau  eksploitasi. Dengan mentransfer metodologi terbaik-pertama ke dalam lingkungan  paralel,  tugas  memecahkan  masalah  saat  ini ditangani lebih efisien[12].

## III. M ETODE P ENELITIAN
Pada  algoritma  BFS  klasik  kita  akan  menemukan bahwa  pencarian  solusi  terbaik  pertama  dapat  diperoleh dengan  melakukan  identifikasi  solusi  yang  tersedia.  Ada banyak  masalah  di  komputer  klasik  sains  yang  dapat dirumuskan  kembali  sebagai  pencarian  daftar  untuk elemen  unik  yang  cocok  dengan  beberapa  kondisi  yang telah  ditentukan.  Jika  tidak  ada  pengetahuan  tambahan tentang  kondisi  pencarian  C  tersedia,  algoritma  klasik terbaik  adalah  pencarian  brute-force  yaitu  elemen  secara berurutan  diuji  terhadap  C  dan  segera  setelah  elemen cocok  dengan  kondisi,  algoritma  berakhir.  Untuk  daftar elemen  N,  ini  membutuhkan  rata-rata  perbandingan  N/2. Dengan  memanfaatkan  paralelisme  dan  interferensi kuantum,  Grover  menemukan  algoritma  kuantum  yang dapat  menemukan  elemen  yang  cocok  hanya  dalam langkah O(√N)[13].

## IV. H ASIL DAN P EMBAHASAN

## A. Pencarian data dengan Best First Search
Seperti  komputer  reguler  (komputer  klasik)  bekerja dengan  bits,  yang  kita  ekspresikan  dengan  0  atau  1. Demikian  juga  untuk  mengekspresikan  teks,  angka,  foto, audio  atau video dengan bilangan biner 0 atau 1 tersebut. Contohnya  angka  4 → 100,  “hello” → 11010…01111, dan lain sebagainya[14].
Sedangkan  komputer  kuantum  bekerja  tidak  seperti halnya  komputer  klasik.  Komputer  kuantum  bekerja dengan qubits. Qubits hampir sama cara kerjanya dengan bits,  namun  perbedaannya  adalah  bahwa  pada  qubits memungkinkan  nilai  biner  untuk  mengekspresikan  teks, angka, dan sebagainya tersebut dengan nilai 0 dan 1 pada saat yang bersamaan.
Pada bidang ilmu kuantum mekanik terdapat fenomena bahwa  sebuah  partikel  memiliki  dua  keadaan  pada  saat yang  bersamaan,  menjadikannya  sangat  unik  dan  inilah yang menjadi dasar ilmu kuantum[15].
Penulis  akan  mengemukakan  sebuah  contoh  sederhana sebuah  masalah  yang  akan  diselesaikan  dengan  kuantum. Bukan hanya dengan satu qubit namun juga memungkinkan  untuk  bekerja  dengan  dua  atau  lebih qubits. Contohnya, jika terdapat dua buah bits yaitu bit A bernilai  1  dan  bit  B  bernilai  0  seperti  yang  terlihat  pada Gambar 1.

## Gambar. 1 Kondisi Qubit 1
Maka  qubits  dapat  digambarkan  sebagai  berikut (Gambar 2) pada saat yang bersamaan.

## Gambar. 2 Kondisi Qubit 2
Sebuah komputer kuantum adalah kumpulan dari qubits yang didesain  untuk  berinteraksi  antara satu  dengan yang lainnya  agar  dapat  dilakukan  pekerjaan  komputasi. Melihat  dari  cara  kerja  komputer  klasik  dengan  bit  dan komputer    kuantum  dengan  qubits  maka  dapat  dikatakan bahwa  komputer  kuantum  bekerja  jauh  lebih  cepat dibanding komputer klasik.

## B. Implementasi  Quantum  Searching  pada  algoritma Best First Search
Perhitungan  komputer  kuantum  dapat  digambarkan dengan  menyelesaikan  sebuah  permasalahan  optimasi sebuah  agen  travel  yang  akan  mengangkut  tiga  orang penumpang dari  satu  lokasi  ke lokasi  lainnya dengan dua buah taksi yang tersedia yang dapat dilihat pada Gambar 3.
Untuk  mendapatkan  solusi  optimal  dari  permasalahan di  atas  kita  akan  mencoba  untuk  menghitungnya  dengan perhitungan  komputer  klasik  terlebih  dahulu.  Yaitu dengan  menyimpan  informasi  dari  solusi  yang  mungkin
dengan  menggunakan  3  bits  yang  dapat  dilihat  pada Gambar 4.
Gambar. 3 Permasalahan optimasi sebuah agen travel

## Gambar. 4 Perhitungan dengan Tiga Bits
Ini  adalah  kemungkinan  yang  pertama,  yaitu  Alisha menumpang di  taksi  0, Banna menumpang di  taksi  0 dan Chayla menumpang di taksi 1. Lalu kita akan menampung kemungkinan ini dengan Tabel 1.
TABEL I C ONTOH P ERHITUNGAN DENGAN Q UANTUM A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 0
Dari tabel di atas maka diperoleh solusi yang mungkin: 8 atau 2*2*2=2 3
Selanjutnya  kita  akan  memberi  skor  dengan  formula berikut:
Skor=Jumlah pasangan berteman berbagi taksi yang sama – Jumlah pasangan bermusuhan berbagi taksi yang sama.
Pada  komputer  klasik  untuk  menghitung  3  bits  pada kasus ini yaitu terdapat 3 orang dan 2 taksi dengan kondisi syarat  yang  telah  ditentukan,  maka  model  matematika untuk  mendapatkan jumlah solusi  yang ditemukan adalah
1 0 ϕ ϕ Alisha Banna Chayla Taksi 0 Taksi 1 Kondisinya: Goal: Alisha        Banna Alisha        Chayla
Banna        Chayla Maksimum : Jumlah pasangan yang berteman berbagi taksi yang sama Minimum : Jumlah pasangan yang bermusuhan berbagi taksi yang sama A B           C 0 0 1
2*2*2=2 3 → 8  solusi.  Maka  jika  terdapat  kasus  lain dengan  4  orang  dan  2  taksi,  maka  model  matematika untuk  mendapatkan jumlah solusi  yang ditemukan adalah 2*2*2*2=2 4 → 16 solusi. Demikian juga dengan n orang dan  2  taksi,  model  matematikanya  adalah  2 n .  Lalu  kita akan  mencoba  dengan  100  orang  dan  2  taksi,  dimana model  matematikanya  adalah  2 100 ≈  10 30 .  Perhitungan dengan tiga Qubit dapat dilihat pada Gambar 5 dan Tabel 2.
Gambar. 5 Contoh Perhitungan dengan Tiga Qubit
TABEL II P ERHITUNGAN DENGAN T IGA Q UBIT A B C Proses Skor
0 0 0 1-2 -1 0 0 1 1-0 1 0 1 0 0-1 -1 0 1 1 0-1 -1 1 0 0 0-1 -1 1 0 1 0-1 -1 1 1 0 1-0 1 1 1
1 1-2 -1
Maka  kita  mendapatkan  solusi  terbaik  yaitu  (lihat Gambar 6): 001 dan 110
dan

## Gambar. 6 Solusi Terbaik Perhitungan dengan Tiga Qubit
Maka pada komputer quantum perhitungan 3 qubits nya adalah:
Gambar. 7 Kondisi pada komputer quantum perhitungan 3 qubits
Dimana  1  qubit  akan  dihitung  seperti  berikut  (Gambar 8):

## Gambar. 8 Proses perhitungan 1 qubit
Dan berikut ini (Gambar 9) adalah perhitungan untuk 2 qubits:

## Gambar. 9 Perhitungan dengan Dua Qubit
Model matematikanya adalah 2qu=2 2
Dan  berikut  ini  adalah  perhitungan  untuk  3  qubits (Gambar 10):

## Gambar. 10 Perhitungan dengan Tiga Qubit
Maka model matematikanya adalah 3qu=2 3

## V. K ESIMPULAN
Untuk  menyelesaikan  proses  pencarian  dengan  3  bits dengan menggunakan perhitungan BFS klasik dibutuhkan bentangan sebanyak 8 bar sehingga mendapatkan hasil 2 3 . Sedangkan  untuk  menyelesaikan  3  bits  pada  perhitungan BFS  kuantum  kita  hanya  perlu  membentangkan  1  bar untuk menampung 3 qubits yang setara dengan= 2 3 solusi. Maka  dengan  ini,  perhitungan  BFS  kuantum  dapat langsung  melakukan  pencarian  terhadap  2 3 solusi  yang terbentang dalam satu  kali iterasi, sedangkan perhitungan BFS  klasik  harus  melakukannya  sebanyak  8  iterasi.
0 0 0
A      B       C
Maka Skor → 1-2=-1
0         0         1
A B         C 1          1         0 A B C ϕ     ϕ       ϕ
A B C
Ф A 0 1 50% 50%
Ф    Ф    Ф A     B     C 12,5% 12,5% 12,5% 12,5% 0     1     0 0     1     1 1     0     0 1     0     1 0     0     1 0     0     0 1     1     0 1     1 1 12,5% 12,5% 12,5% 12,5% Ф      Ф A      B 0       0 0       1
1       0 1       1 25% 25% 25% 25%
Sampai  ditahap  ini,  perbandingan  kecepatan  antara  BFS klasik dengan BFS kuantum  adalah 8:1.
Maka  jika  ingin  menyelesaikan  proses  pencarian  yang lebih  besar  yakni  misalnya  100  qubits  atau  10 100 dengan perhitungan BFS Kuantum adalah dengan membentangkan  100  buah  qubits  dalam  satu  bar  untuk mendapatkan solusi terbaiknya.

## R EFERENSI
[1] H.  Angriani  and  Y.  Saharaeni,  “Implementasi  Algoritma  Best First Search Dalam Sistem Pakar Pertolongan Pertama Pada Bayi dan Anak,” Inspir.  J.  Teknol.  Inf.  dan  Komun. ,  vol.  10,  no.  2,  p.
116, 2020, doi: 10.35585/inspir.v10i2.2575.
[2] R.  A.  Dzakiy,  “Optimasi  Komputasi  menggunakan  Algoritma Quantum  Grover  dan  Keunggulannya  dalam  Pemecahan Permasalahan Pencarian,” 2017.
[3] M.  Kapp,  “Florida  State  University  Libraries,” Elder  Law  Rev. , vol. 1, 2002.
[4] D.  Horn  and  A.  Gottlieb,  “The  method  of  quantum  clustering,” Adv.  Neural  Inf.  Process.  Syst. ,  no.  April,  2002,  doi: 10.7551/mitpress/1120.003.0103.
[5] M.  S.  A.  Rahmat  and  P.  Nurwantoro,  “Kajian  Komputasi Algoritma  Kuantum  Quantum  V  ariational  Eigensolver  untuk Simulasi Molekul H2,” J. Fis. Indones. , vol. 24, no. 1, p. 17, 2020, doi: 10.22146/jfi.v24i1.52011.
[6] K. Bertels et al. , “Quantum Computer Architecture Toward Full- Stack Quantum Accelerators,” IEEE Trans. Quantum Eng. , vol. 1, pp. 1–17, 2021, doi: 10.1109/tqe.2020.2981074.
[7] S.  Resch  and  U.  R.  Karpuzcu,  “Quantum  Computing:  An Overview  Across  the  System  Stack,”  2019,  [Online].  Available: http://arxiv.org/abs/1905.07240.
[8] L.  M.  Gultom,  “Klasifikasi  Data  Dengan  Quantum  Perceptron,”
Teknovasi , vol. 4, no. 1, pp. 1–9, 2017.
[9] M.  Schuld  and  N.  Killoran,  “Quantum  Machine  Learning  in Feature Hilbert Spaces,” Phys. Rev. Lett. , vol. 122, no. 4, p. 40504, Feb. 2019, doi: 10.1103/PhysRevLett.122.040504.
[10]  A.  Sequeira,  L.  P.  Santos,  and  L.  S.  Barbosa,  “Generalised Quantum  Tree  Search,”  pp.  39–40,  2021,  doi:  10.1109/q- se52541.2021.00015.
[11]  L.  Tarrataca  and  A.  Wichert,  “Tree  search  and  quantum computation,” Quantum Inf. Process. , vol. 10, no. 4, pp. 475–500, 2011, doi: 10.1007/s11128-010-0212-z.
[12]  D. Whitlock, P. Dey, and R. Hyatt, “A Parallel Best-First Search,” in Proceedings of the 1988 ACM Sixteenth Annual Conference on Computer Science , 1988, p. 735, doi: 10.1145/322609.323190.
[13]  A.  Grover,  “Perhitungan  Analitik  Algoritma  Grover,”  no.  1,  pp.
1–5.
[14]  T. Peng, A. W. Harrow, M. Ozols, and X. Wu, “Simulating Large Quantum  Circuits  on  a  Small  Quantum  Computer,” Phys.  Rev. Lett. ,  vol.  125,  no.  15,  p.  150504,  Oct.  2020,  doi:
10.1103/PhysRevLett.125.150504.
[15]  M. Saw, “Prospek komputer kuantum di masa depan.”