content/ex2/ex2-id.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Latihan 2 - Algoritma Shor's\n",
    "## Latar belakang sejarah\n",
    "\n",
    "Didalam komputasi, kita sering mengukur peforma dari algoritma dengan bagaimana algoritma tersebut berkembang dengan masukkan yang diberikan. Sebagai contoh, penjumlahan memiliki algoritma yang berkembang secara linear dengan ukuran angka yang kita tambahkan. Ada beberapa masalah didalam komputasi yang dimana memiliki algoritma yang kita harus berkembang secara _eksponensial_ dengan ukuran masukkan yang diberikan, dan dimana masukkan yang memiliki ukuran yang terlalu besar untuk diselesaikan oleh komputer diseluruh dunia. Kita sangat yakin,sebagian dari keamanan internet bergantung pada masalah komputasi yang tidak dapat di pecahkan.\n",
    "\n",
    "PAda tahun 1994, Peter Shor menunjukan bahwa sangatlah mungkin untuk memfaktorisasi angka menjadi angka prima secara efektif di komputer kuantum.[1] Yang merupakan berita besar, sebagai algoritma klasikal yang kita ketahui yang dimana algoritma tersebut dapat berkembang secara eksponensial. Dan sebagai kenyataannya, [Enkripsi RSA](https://id.wikipedia.org/wiki/RSA) bergantung pada pemfaktoran angka yang besar sehingga menjadi tidak mungkin untuk dipecahkan. Untuk memfaktorisasi angka integer yang sangat besar pada komputer klasik diperlukan jutaan qubit dan gerbang, dan sirkuit ini terlalu besar untuk dieksekusi oleh kuantum komputer pada saat ini.\n",
    "\n",
    "Jadi bagaimana Lieven M.K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood and Isaac L. Chuang berhasil memfaktorkan 15 di kuantum komputer pada tahun 2001?! [2]\n",
    "\n",
    "Kesulitan dalam membuat sirkuit untuk algoritma Shor’s adalah membuat sirkuit yang dapat menghitung $ay \\bmod N$ secara terkontrol. Ketika kita tahu bagaimana membuat sirkuit ini dengan gerbang secara polinomial, yang masih terlalu besar untuk komputer saat ini. Beruntung, jika kita telah mengetahui sebagian dari informasi dari pada awal masalah, kemudia kita dapat 'mencurangi' dan membuat sirkuit yang lebih efisien.\n",
    "\n",
    "Untuk menjalakan sirkuit di perakgkat keras yang ada pada saat itu, penulis jurnal diatas mendapatkan sirkuit yang simpel yang dapat mengeksekusi $7y \\bmod 15$. Yang dimana membuat sirkuit tersebut cukup kecil untuk dijalankan di perangkat keras mereka. Pada akhir dari latihan ini, anda akan membuat sirkuit untuk $35y \\bmod N$ yang dapat digunakan di algoritma Shor’s dan dapat dijalankan di `ibmq_santiago`.\n",
    "\n",
    "Jika anda ingin megrti apa yang terjadi didalam latihan ini, anda dapat membaca [buku cetak Qiskit halaman algoritma Shor’s](https://qiskit.org/textbook/ch-algorithms/shor.html), jika ini terlalu susah bagi anda, anda dapat menyelesaikan latihan ini tanpa membaca.\n",
    "\n",
    "### Referensi\n",
    "1. Shor, Peter W. \"Algorithms for quantum computation: discrete logarithms and factoring.\" Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994.\n",
    "2. Vandersypen, Lieven MK, et al. \"Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance.\" Nature 414.6866 (2001): 883-887."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## tl;dr: Algoritma Shor's\n",
    "\n",
    "Ada satu algoritma disebut [_quantum phase estimation_](https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html) yang dimana memberitahukan gelombang yang di berikan dari gerbang untuk setiap keadaan kuantum. Sebagai contoh, masukan untuk algoritma estimasi gelombang dapat menjadi keadaan kuantum $|1\\rangle$ dan gerbang $Z$. Jika gerbang $Z$ bereaksi pada keadaan $|1\\rangle$, kita mendapatkan keadaan yang sama dengan pertambahaan gelombang global sebesar $\\pi$:\n",
    "\n",
    "$$\n",
    "Z|1\\rangle = -|1\\rangle = e^{i\\pi} |1\\rangle\n",
    "$$\n",
    "\n",
    "dan *quantum phase estimation* dapat menghasilkan untuk kita. Anda dapat melihat contoh lain [disini](https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html#2.-Example:-T-gate-).\n",
    "\n",
    "Shor menunjukan bhawa kita melakukan estimasi gelombang dengan gerbang, $U$, yang memiliki sifat $U|y\\rangle = |a y\\bmod N\\rangle$, kita dapat mendapatkan beberapa informasi faktor dari $N$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2## Masalah\n",
    "\n",
    "Didalam latihan ini, kita akan memfaktorisasi 25 dengan menggunakan estimasi gelombang dengan sirkuit yang mengimplentasikan $13y \\bmod 35$. Didalam latihan ini membuat sirkuit dan cukup kecil untuk dijalankan di `ibmq_santiago`! Ini berupakan tugas yang mudah, jadi pertama sekali kita membuat contekan.\n",
    "\n",
    "Detil dari algoritma Shor’s adalah sirkuit kita haruslah berkerja pada keadaan yang kita capai dengan mengaplikasikan $U$ untuk memulai keadaan $|1\\rangle$. Contoh kita dapat menggunakan sirkuit apapun yang memiliki sifat: \n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U|1\\rangle &= |13\\rangle \\\\\n",
    "UU|1\\rangle &= |29\\rangle \\\\\n",
    "UUU|1\\rangle &= |27\\rangle \\\\\n",
    "UUUU|1\\rangle &= |1\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Jadi bagaimana kita membuat menjadi lebih mudah untuk kita ? Sejak kita hanya memerlukan untuk mentransformasi 4 keadaan berbeda secara benar. Untuk latihan ini, kita akan memilih untuk memetakan 2 qubit keadaan komputasional basis ke angka seperti:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "|1\\rangle &\\rightarrow |00\\rangle \\\\\n",
    "|13\\rangle &\\rightarrow |01\\rangle \\\\\n",
    "|29\\rangle &\\rightarrow |10\\rangle \\\\\n",
    "|27\\rangle &\\rightarrow |11\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Kenapa ini “menyontek”? Karena, untuk menggunakan optimisasi ini, kita perlu tahu semua keadaan $U$ yang akan terefek, yang dimana kita harus menghitung $ay \\bmod N$ sampai kita mendapatkan 1 kembali, dan artinya kita mengetahui periode dari $a^x \\bmod N$ dan artinya kita mendapatkan faktor dari $N$. Semua optimisasi seperti ini, yang dimana kita gunakan dapat memberitahukan nilai dari $r$, yang pastinnya tidak akan menskalakan permasalahan yang tidak dapat komputer klasik pecahkan. \n",
    "\n",
    "Tapi kegunaan dari latihan ini hanyalah memverifikasi bahwa algoritma Shor’s dapat berkerja sesuai harapan, dan kita tidak akan mengkhawatirkan fakta bahwa kita mencurangi untuk mendapatkan sirkuit untuk $U$.\n",
    "\n",
    "<div id='u-definition'></div>\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Latihan 2a:** Membuat sebuah sirkuit ($U$) yang dapat memlakukan transformasi:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U|00\\rangle &= |01\\rangle \\\\\n",
    "U|01\\rangle &= |10\\rangle \\\\\n",
    "U|10\\rangle &= |11\\rangle \\\\\n",
    "U|11\\rangle &= |00\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "dan jika di kontrol oleh qubit lainnya. Sirkuit tersebut akan berkerja pada 2 qubit target register yang bernama 'target', dan akan dikontrol oleh sebuah qubit register yang bernama 'kontrol'. Anda harus memberikan sirkuit yang anda selesaikan ke variabel '`cu`'.\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from qiskit import QuantumCircuit\n",
    "from qiskit import QuantumRegister, QuantumCircuit\n",
    "c = QuantumRegister(1, 'control')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu = QuantumCircuit(c, t, name=\"Controlled 13^x mod 35\")\n",
    "\n",
    "# TULIS KODE ANDA DIANTARA BARIS INI - MULAI\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# TULIS KODE ANDA DIANTARA BARIS INI - AKHIR\n",
    "\n",
    "cu.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dan jalankan sel dibawah untuk mengecek jawaban anda:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Cek jawaban anda menggunakan kode dibawah\n",
    "from qc_grader import grade_ex2a\n",
    "grade_ex2a(cu)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Selamat! Anda telah menyelesaikan bagian tersulit. \n",
    "\n",
    "Kita membaca keluaran dari algoritma estimasi gelombang dengan mengukur qubit, jadi kita wajib memastikan register 'penghitung' cukup dapat untuk membaca $r$. Pada kasus kita, $r = 4$, yang dimana kita hanya memerlukan $\\log_2(4) = 2$ qubit (menyontek lagi karena kita tahu $r$ sebelumnya), tapi sejak Santiago memiliki 5 qubit, dan kita hanya menggunakan 2 qubit sebagai register 'target', kita akan menggunakan sisa 3 qubit menjadi register penghitung.\n",
    "\n",
    "Membuat estimasi gelombang pada $U$, kita perlu membuat sirkuit yang dapat melakukan $U^{2^x}$ ($U$ berulang $2^x$ kali) untuk setiap qubit (dengan index $x$) di dalam register $n$ qubit penghitung. Didalam kasus ini artinya kita perlu 3 sirkuit yang mengimplementasikan:\n",
    "\n",
    "$$ U, \\; U^2, \\; \\text{and} \\; U^4 $$\n",
    "\n",
    "Jadi tahap selanjutnya adalah membuat sirkuit yang dapat melakukan $U^2$ (yang sama dengan sirkuit yang mengaplikasikan $U$ secara dua kali).\n",
    "\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Latihan 2b:** Membuat sirkuit ($U^2$) yang melakukan transformasi:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U|00\\rangle &= |10\\rangle \\\\\n",
    "U|01\\rangle &= |11\\rangle \\\\\n",
    "U|10\\rangle &= |00\\rangle \\\\\n",
    "U|11\\rangle &= |01\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "dan di kontrol oleh qubit lain. Sirkuit tersebut akan berkerja pada 2 qubit target register yang bernama 'target', dan akan dikontrol oleh sebuah qubit register yang bernama 'kontrol'. Anda harus memberikan sirkuit yang anda selesaikan ke variabel '`cu2`'.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "c = QuantumRegister(1, 'kontrol')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu2 = QuantumCircuit(c, t)\n",
    "\n",
    "# TULIS KODE ANDA DIANTARA BARIS INI - MULAI\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# TULIS KODE ANDA DIANTARA BARIS INI - AKHIR\n",
    "\n",
    "cu2.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dan jalankan sel dibawah untuk mengecek jawaban anda:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Cek jawaban anda menggunakan code dibawah\n",
    "from qc_grader import grade_ex2b\n",
    "grade_ex2b(cu2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Akhirnya, kita juga perlu sirkuit yang dapat mengaplikasikan $U$ 4 kali (kita memerlukan sirkuit $U^4$).  \n",
    "\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "    \n",
    "**Latihan 2c:** Membuat sirkuit ($U^4$) yang dapat melakukan transformasi:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "U|00\\rangle &= |00\\rangle \\\\\n",
    "U|01\\rangle &= |01\\rangle \\\\\n",
    "U|10\\rangle &= |10\\rangle \\\\\n",
    "U|11\\rangle &= |11\\rangle \\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "dan di kontrol oleh qubit lain. Sirkuit tersebut akan berkerja pada 2 qubit target register yang bernama 'target', dan akan dikontrol oleh sebuah qubit register yang bernama 'kontrol'. Anda harus memberikan sirkuit yang anda selesaikan ke variabel '`cu4`'. _Petunjuk: Solusi terbaik adalah paling simpel._\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "c = QuantumRegister(1, 'kontrol')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu4 = QuantumCircuit(c, t)\n",
    "\n",
    "# TULIS CODE ANDA DIANTARA BARIS INI - MULAI\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# TULIS KODE ANDA DIANTARA BARIS INI - AKHIR\n",
    "\n",
    "cu4.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anda dapat mengecek jawaban anda mengunakan kode dibawah: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Cek jawaban anda mengunakan kode berikut ini\n",
    "from qc_grader import grade_ex2c\n",
    "grade_ex2c(cu4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Latihan 2 final:** Sekarang kita harus mengkontrol $U$, $U^2$ dan $U^4$, kita dapat mengabungkan semua menjadi sirkuit yang menjalakn bagian kuantum dari algoritma Shor's.\n",
    "\n",
    "Bagian initialisasi merupakan bagian mudah: kita perlu menaruh register penghitung ke keadaan $|{+}{+}{+}\\rangle$ (yang kita dapat lakukan dengan menggunakan 3 gerbang-H) dan kita memerlukan register target menjadi keadaan $|1\\rangle$ (yang dimana kita memetakan basis komputasioanal keadaan $|00\\rangle$, sehingga kita tidak perlu membuat apapun disini). Kita akan lakuakan ini semua untuk anda.\n",
    "\n",
    "Tugas _anda_ adalah membuat sirkuit yang menjalakan $U$-terkontrol, yang akan digunakan diantara initialisasi dan inverse transformasi Fourier kuantum . Secara formal, kita ingin sirkuit:\n",
    "\n",
    "\n",
    "$$\n",
    "CU_{c_0 t}CU^2_{c_1 t}CU^4_{c_2 t}\n",
    "$$\n",
    "\n",
    "Dimana $c_0$, $c_1$ dan $c_2$ adalah tiga qubit di register 'penghitung', $t$ adalah register ‘target’ , and $U$ adalah <a href=\"#u-definition\">telah terdefinisi di bagian pertama latihan</a>. di dalam notasi ini, $CU_{a b}$ berarti $CU$ yang dikontrol oleh $a$ dan beraksi oleh $b$. Solusi termudah adalah mengabungkan semua sirkuit `cu`, `cu2` dan `cu4` yang anda buat, tapi anda akan mendapatkan sirkuit lebih efisien yang memiliki sifat yang sama!\n",
    "    \n",
    "</div>\n",
    "<div class=\"alert alert-block alert-danger\">\n",
    "    \n",
    "Sirkuit anda hanya boleh mengandung [CNOT](https://qiskit.org/documentation/stubs/qiskit.circuit.library.CXGate.html) dan qubit tunggal [gerbang U](https://qiskit.org/documentation/stubs/qiskit.circuit.library.UGate.html). Nilai anda akan berasalah dari gerbang CNOT (semakin sedikit semakin bagus), karna gerbang multi qubit biasanya lebih sulit di jalankan di perangkat keras. Jika anda kesusahan untuk persyaratan yang ada, kami telah memasukan satu baris dekat pengumpulan yang akan mengkonversi sirkuit anda kedalam format yang ada, meskipun lebih disarankan anda lakukan menggunkan dengan tangan.\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Kode untuk mengabungkan solusi sebelumnya ke pengumpulan terakhir anda\n",
    "cqr = QuantumRegister(3, 'control')\n",
    "tqr = QuantumRegister(2, 'target')\n",
    "cux = QuantumCircuit(cqr, tqr)\n",
    "solutions = [cu, cu2, cu4]\n",
    "for i in range(3):\n",
    "    cux = cux.compose(solutions[i], [cqr[i], tqr[0], tqr[1]])\n",
    "cux.draw('mpl')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Cek jawaban anda dengan kode dibawah ini\n",
    "from qc_grader import grade_ex2_final\n",
    "# tutup komentar dibawah jika anda pingin mengkonversi sirkuit anda menjadi CNOT dan gerbang qubit tunggal.\n",
    "#from qiskit import transpile\n",
    "#cux = transpile(cux, basis_gates=['cx','u'])\n",
    "grade_ex2_final(cux)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jika anda sudah senang dengan sirkuit anda, anda dapat kumpul dibawah:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Kumpul jawaban anda. Anda dapat mengumpulkan kapan pun.\n",
    "from qc_grader import submit_ex2_final\n",
    "submit_ex2_final(cux)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Selamat! Anda telah menyelesaikan latihan ini. Lanjutkan membaca untuk melihat sirkuit anda digunakan untuk memfaktorkan angka 35, dan melihat bagaimana cara melakukannya.\n",
    "\n",
    "## Mengunakan sirkuit anda untuk memfaktorkan 35\n",
    "\n",
    "Sel kode dibawah akan mengambil submisi anda dari latihan dan menggunakannya untuk membuat sirkuit yag memberikan $\\tfrac{s}{r}$, dimana $s$ adalah angka bilangan bulat acak diantara $0$ dan $r-1$, dan $r$ merupakan periode dari fungsi $f(x) = 13^x \\bmod 35$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from qiskit.circuit.library import QFT\n",
    "from qiskit import ClassicalRegister\n",
    "# Membuat objek sikuit\n",
    "cr = ClassicalRegister(3)\n",
    "shor_circuit = QuantumCircuit(cqr, tqr, cr)\n",
    "\n",
    "# Menginitialisasi qubit\n",
    "shor_circuit.h(cqr)\n",
    "\n",
    "# Tambah sirkuit anda\n",
    "shor_circuit = shor_circuit.compose(cux)\n",
    "\n",
    "# Lakukan inverse QFT dan mengekstrak keluarannya\n",
    "shor_circuit.append(QFT(3, inverse=True), cqr)\n",
    "shor_circuit.measure(cqr, cr)\n",
    "shor_circuit.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mari kita trasnpile sirkuit dan lihat seberapa besar sirkuit tersebut, dan berapa banyak CNOT yang digunakan:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from qiskit import Aer, transpile\n",
    "from qiskit.visualization import plot_histogram\n",
    "qasm_sim = Aer.get_backend('aer_simulator')\n",
    "tqc = transpile(shor_circuit, basis_gates=['u', 'cx'], optimization_level=3)\n",
    "print(f\"kedalaman sirkuit: {tqc.depth()}\")\n",
    "print(f\"sirkuit mengandung {tqc.count_ops()['cx']} CNOT\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dan mari kita lihat apa yang kita dapat:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "counts = qasm_sim.run(tqc).result().get_counts()\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Asumsi semua berkerja dengan benar, kita seharusnya dapat melihat probabilitas yang sama dari pengukuran angka $0$, $2$, $4$ dan $8$. Ini disebabkan karena estimasi gelombang memberikan kita $2^n \\cdot \\tfrac{s}{r}$, dimana $n$ adalah jumlah qubit didalam register penghitung kita (disini $n = 3$, $s$ merupakan angka bulat acak $0$ dan $r-1$, dan $r$ merupakan angka yang kita ingin hitung). Mari kita konversi semua menjadi pecahan yang memberi tahu kita $s/r$ (yang dimana kita dapat hitung secara mudah):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from fractions import Fraction\n",
    "n = 3  #n merupakan jumlah dari register 'penghitung'\n",
    "# Ulang setiap hasil pengukuran string\n",
    "for measurement in counts.keys():\n",
    "    # Konversi string binari ke 'int', dan bagi dengan 2^n\n",
    "    decimal = int(measurement, 2)/2**n\n",
    "    # Gunakan algoritma pecahan berkelanjutan untuk mengkonversi dari a/b\n",
    "    print(Fraction(decimal).limit_denominator())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kita dapat melihat penyebut dari beberapa hasil yang ada akan memberikan kita jawaban yang benar $r = 4$. kita dapat memverifikasi $r=4$ secara cepat:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "13**4 % 35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jadi bagaimana kita dapat faktor dari ini? Dimana adanya probalitas tinggi yang dimana merupakan faktor persekutuan terbesar dari $N$ dan antara $a^{r/2}-1$ atau $a^{r/2}+1$ adalah faktor dari $N$, dan faktor persekutuan terbesar yang kita dapat hitung secara klasikal secara mudah."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from math import gcd # faktor persekutuan terbesar\n",
    "for x in [-1, 1]:\n",
    "    print(f\"faktor yangn ditebak: {gcd(13**(4//2)+x, 35)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kita hanya perlu mencari satu faktor, dan dapat gunakan untuk membagi $N$ untuk mendapatkan faktor lainnya. Tetapi untuk kasusu ini, _kedua_ $a^{r/2}-1$ atau $a^{r/2}+1$ memberikan kita faktor $35$ f. Kita dapat memverifikasi lagi:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "7*5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Jalakan di `ibmq_santiago`\n",
    "\n",
    "Kami berjanji ini dapat berjalan di Santiago, jadi kami akan menunjukan bagaimana anda melakukannya. Didalam contoh ini kita akan menggunakan simulasi dari perangkat Santiago untuk kemudahan, tapi anda pdat mengantikan dengan perangkat asli jika anda mau:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from qiskit.test.mock import FakeSantiago\n",
    "from qiskit import assemble\n",
    "from qiskit.visualization import plot_histogram\n",
    "santiago = FakeSantiago()\n",
    "real_device = False\n",
    "\n",
    "## tutup komentar dibawah untuk menjalankan kode di perangkat asli\n",
    "#from qiskit import IBMQ\n",
    "#IBMQ.load_account()\n",
    "#provider = IBMQ.get_provider(hub='ibm-q', group='open', project='main')\n",
    "#santiago = provider.get_backend('ibmq_santiago')\n",
    "#real_device = True\n",
    "\n",
    "# Kita perlu transpile untuk Santiago\n",
    "tqc = transpile(shor_circuit, santiago, optimization_level=3)\n",
    "\n",
    "if not real_device:\n",
    "    tqc = assemble(tqc)\n",
    "\n",
    "# Jalankan sirkuit dan mencetak jumlah\n",
    "counts = santiago.run(tqc).result().get_counts()\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jika nilai anda cukup rendah, anda akan melihat kita mendapatkan probabilitas dari pengukuran $0$, $2$, $4$ atau $8$ seperti di simulasi. Anda akan melihat adanya hasil extra karena inakurasi dari prosesor dan interaksi asing pada qubit kita. `'noise'` ini akan semakin parah jika semakin panjang sirkuit yang kita miliki, semakin panjang waktu komputasi berarti semankin banyak potensi error yang ada. Karena itu kita wajib untuk curang untuk membuat sirkuit sekecil mungkin.\n",
    "\n",
    "Pada masa depan, kuantum sistem kita akan cukup berkembang yang kita capat memulai menggunakan teknik mitigasi error lebih canggih untuk mengatasi permasalahan ini, yang dimana akan berarti kita dapat menjalankan sirkuit yang cukup besar untuk [mengerjakan algoritma Shor's tanpa mencurangi](https://arxiv.org/pdf/quant-ph/0205095.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Additional information\n",
    "\n",
    "**Created by:** Frank Harkins\n",
    "\n",
    "**Indonesia Translate by:** Felix Montalfu\n",
    "\n",
    "**Version:** 1.0.0"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  },
  "nbdime-conflicts": {
   "local_diff": [
    {
     "diff": [
      {
       "diff": [
        {
         "key": 0,
         "length": 1,
         "op": "removerange"
        }
       ],
       "key": "version",
       "op": "patch"
      }
     ],
     "key": "language_info",
     "op": "patch"
    }
   ],
   "remote_diff": [
    {
     "diff": [
      {
       "diff": [
        {
         "diff": [
          {
           "key": 4,
           "op": "addrange",
           "valuelist": "8"
          },
          {
           "key": 4,
           "length": 1,
           "op": "removerange"
          }
         ],
         "key": 0,
         "op": "patch"
        }
       ],
       "key": "version",
       "op": "patch"
      }
     ],
     "key": "language_info",
     "op": "patch"
    }
   ]
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}