content/ex2/ex2-vi.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bài 2 - Thuật toán Shor\n",
    "## BỐI CẢNH LỊCH SỬ\n",
    "\n",
    "Trong tính toán giải thuật, chúng ta thường quan tâm hiệu suất của thuật toán sẽ tăng theo mối quan hệ gì đối với độ lớn của khối lượng đầu vào. Lấy một ví dụ đơn giản đó là phép toán cộng. Độ phức tạp cho thuật toán của phép cộng luôn tăng tuyến tính theo độ lớn của 2 số hạng được cộng. Tuy nhiên, không phải bài toán nào cũng có giải thuật tối ưu. Có những bài toán mà thuật toán tối ưu nhất cho nó chỉ dừng lại ở mối quan hệ _số mũ_ đối với độ lớn của đầu vào. Khi mối quan hệ là số mũ, thì chỉ với độ lớn trung bình của khối lượng đầu vào cũng đủ để hạ gục bất kì chiếc máy tính nào trên thế giới hiện nay. Những bài toán gần như không có lời giải tối ưu này thường được dùng để tạo ra an toàn bảo mật trên hệ thống internet.\n",
    "\n",
    "Vào năm 1994, Peter Shor đã chỉ ra rằng bài toán phân tích một số thành thừa số nguyên tố có thể thực hiện một cách hiệu quả bằng máy tính lượng tử.[1] Đây thực sự là một phát hiện vĩ đại bởi lời giải tối ưu nhất cho bài toán này lúc bấy giờ chỉ dừng lại ở hàm số mũ. Tính bất khả thi của bài toán cũng chính là nên tảng bảo mật của hệ thống [mã hóa RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)). Việc phân tích một số nguyên cực lớn thành thừa số nguyên tố bằng máy tính cổ điển đòi hỏi hàng triệu qubits và cổng lượng tử; những mạch lượng tử này là quá lớn để có thể vận hành một cách hiệu quả trên nền tảng lượng tử hiện nay.\n",
    "\n",
    "Vậy, làm thế nào mà Lieven M.K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood và Isaac L. Chuang có thể phân tích 15 thành thừa số nguyên tố trên máy tính lượng tử vào năm 2001?[2]\n",
    "\n",
    "Cái khó trong việc xây dựng mạch lượng tử để áp dụng thuật toán Shor đó là tạo ra mạch để tính toán biểu thức $ay \\bmod N$. Mặc dù chúng ta có thể tạo ra những mạch này chỉ với một số lượng đa thức của số cổng lượng tử, chúng vẫn là quá lớn để có thể chạy trên máy tính lượng tử hiện nay. Mặc dù vậy, chúng ta vẫn có thể 'ăn gian' để tạo ra mạch lượng tử hiệu quả cho bài toán này nếu chúng ta biết trước thông tin về đặc tính của bài toán.\n",
    "\n",
    "Để vận hành được những mạch lượng tử này trên thiết bị, tác giả của bài báo trên đã tìm ra một mạch lượng tử đơn giản để tính toán $7y \\bmod 15$. Mạch lượng tử của họ đủ nhỏ để có thể chạy trên thiết bị. Sau khi kết thúc bài tập này, bạn sẽ tạo ra được một mạch lượng tử để tính toán $35y \\bmod N$ để áp dụng giải thuật Shor và nó có thể chạy được trên `ibmq_santiago`.\n",
    "\n",
    "Để hiểu hơn về bài tập này, bạn có thể tìm hiểu [Qiskit Textbook page on Shor's algorithm](https://qiskit.org/textbook/ch-algorithms/shor.html). Tuy nhiên, bạn vẫn có thể hoàn thành bài tập mà không cần phải đọc qua tài liệu ngoài nếu kiến thức của sách quá chi tiết.\n",
    "\n",
    "### Tài liệu tham khảo\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",
    "1. 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: Thuật Toán Shor\n",
    "\n",
    "Có một thuật toán được gọi là [ước lượng pha lượng tử (quantum phase estimation)](https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html) nó cho chúng ta biết pha của một cổng khi đưa vào một trạng thái nhất định. Ví dụ, đầu vào của thuật toán ước lượng pha có thể là trạng thái $|1\\rangle$ và cổng $Z$. Nếu cổng $Z$ tác động lên trạng thái $|1\\rangle$, chúng ta sẽ thu được trạng thái tương tự với một pha tổng quát $\\pi$ được thêm vào:\n",
    "\n",
    "$$\n",
    "Z|1\\rangle = -|1\\rangle = e^{i\\pi} |1\\rangle\n",
    "$$\n",
    "\n",
    "Và thuật toán ước lượng pha lượng tử có thể giải quyết vấn đề này cho chúng ta. Bạn có thêm xem thêm một ví dụ khác ở [đây](https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html#2.-Example:-T-gate-).\n",
    "\n",
    "Shor đã chỉ ra rằng nếu chúng ta thực hiện ước lượng pha trên một cổng, $U$, mà có hành vi $U|y\\rangle = |a y\\bmod N\\rangle$, chúng ta có thể nhanh chóng thu thập được những thông tin về thừa số nguyên tố của $N$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bài Tập\n",
    "\n",
    "Trong bài tập này, chúng ta sẽ phân tách số 35 thành các thừa số nguyên tố bằng cách sử dụng ước lượng pha trên một mạch triển khai $13y \\bmod 35$. Bài tập này là để tạo một mạch để làm điều này, và đủ nhỏ để có thể chạy được trên `ibmq_santiago`! Đây không phải là một nhiệm vụ đơn giản, vì thế điều đầu tiên chúng ta phải làm là gian lận. \n",
    "\n",
    "Một chi tiết của thuật toán Shor đó là mạch của chúng ta chỉ cần hoạt động trên các trạng thái mà chúng ta có thể đạt được thông qua việc áp dụng $U$ cho trạng thái bắt đầu $|1\\rangle$. I.e. Chúng ta có thể sử dụng bất kì mạch nào có hành vi: \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",
    "Vậy làm thế nào để chúng ta có thể làm điều này dễ dàng hơn cho chúng ta? Vì chúng ta chỉ cần biến đổi chính xác bốn trạng thái khác nhau, chúng ta có thể mã hóa chúng thành hai qubit. Đối với bài tập này, chúng ta sẽ chọn ánh xạ các trạng thái tính toán cơ sở của hệ 2 qubit thành các số như sau:\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",
    "Vì sao điều này là \"gian lận\"? Để tận dụng sự tối này, chúng ta cần biết tất cả trạng thái mà $U$ sẽ tác động vào, điều này có nghĩa chúng ta phải tính $ay \\bmod N$ cho đến khi chúng ta quay trở lại 1, và điều đó có nghĩa là chúng ta biết được chu kỳ của $a^x \\bmod N$ và từ đó tìm được các thừa số nguyên tố của $N$. Bất kỳ sự tối ưu nào như thế, trong đó chúng ta sử dụng thông tin cho chúng ta biết giá trị của $r$, rõ ràng sẽ không tăng quy mô lên tới các vấn đề mà máy tính cổ điển không thể giải quyết. \n",
    "\n",
    "Nhưng mục đích của bài tập này chỉ là để xác minh rằng thuật toán của Shor trên thực tế sẽ hoạt động như dự kiến,  và chúng tôi sẽ không lo lắng về việc chúng tôi đã gian lận để có được một mạch cho $U$.\n",
    "\n",
    "<div id='u-definition'></div>\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Bài Tập 2a:** Tạo một mạch ($U$) có thể thực hiện phép biến đổi:\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",
    "và được điều khiển bởi một qubit khác. Mạch sẽ hoạt động trên một thanh ghi mục tiêu hai qubit có tên 'target', và được điều khiển bởi một thanh ghi điều khiển một qubit có tên 'control'. Bạn nên gán mạch đã hoàn thành của mình vào biến '`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",
    "# Viết code của bạn ở giữa những dòng này - Bắt đầu\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Viết code của bạn ở giữa những dòng này - Kết thúc\n",
    "\n",
    "cu.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Và chạy ô bên dưới để kiểm tra kết quả:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Kiểm tra đáp án của bạn sử dụng code sau\n",
    "from qc_grader import grade_ex2a\n",
    "grade_ex2a(cu)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Chúc mừng! Bạn đã hoàn thành phần khó của bài tập. \n",
    "\n",
    "Chúng ta đọc kết quả của thuật toán ước lượng pha bằng cách đo các qubit, vì thế chúng ta cần đảm bảo rằng các thanh ghi 'counting'(bộ đếm) chứa đủ số lượng qubits để đọc ra $r$. Trong trường hợp này, $r = 4$, điều này có nghĩa chúng ta chỉ cần $\\log_2(4) = 2$ qubits (gian lận một lần nữa vì chúng ta đã biết trước $r$), những bởi vì Santiago có 5 qubit, và chúng ta chỉ sử dụng 2 qubit cho thanh ghi 'target', chúng ta sẽ dùng hết 3 qubits còn lại như là thanh ghi bộ đếm.\n",
    "\n",
    "Để thực hiện ước lượng pha trên $U$, chúng ta cần tạo ra một mạch thực hiện $U^{2^x}$ ($U$ được lặp lại $2^x$ lần) với mỗi qubit (với chỉ số $x$) trong thanh ghi của chúng ta với $n$ qubit đếm. Trong trường hợp của chúng ta điều này nghĩa là chúng ta cần ba mạch thực hiện:\n",
    "\n",
    "$$ U, \\; U^2, \\; \\text{and} \\; U^4 $$\n",
    "\n",
    "Vì thế bước tiếp theo là tạo ra một mạch thực hiện $U^2$ (i.e. một mạch tương đương với việc thực hiện $U$ hai lần).\n",
    "\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "\n",
    "**Bài Tập 2b:** Tạo một mạch ($U^2$) có thể thực hiện phép biến đổi:\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",
    "và được điều khiển bởi một qubit khác. Mạch sẽ hoạt động trên một thanh ghi mục tiêu hai qubit có tên 'target', và được điều khiển bởi một thanh ghi điều khiển một qubit có tên 'control'. Bạn nên gán mạch đã hoàn thành của mình vào biến '`cu2`'.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "c = QuantumRegister(1, 'control')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu2 = QuantumCircuit(c, t)\n",
    "\n",
    "# Viết code của bạn ở giữa những dòng này - Bắt đầu\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Viết code của bạn ở giữa những dòng này - Kết thúc\n",
    "\n",
    "cu2.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Và bạn có thể kiểm tra kết quả của bạn bên dưới"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Kiểm tra đáp án của bạn sử dụng code sau\n",
    "from qc_grader import grade_ex2b\n",
    "grade_ex2b(cu2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cuối cùng, chúng ta cần một mạch tương đương với việc thực hiện $U$ bốn lần (i.e. chúng ta cần mạch $U^4$).  \n",
    "\n",
    "<div class=\"alert alert-block alert-success\">\n",
    "    \n",
    "**Bài Tập 2c:** Tạo ra mạch ($U^4$) có thể thực hiện phép biến đổi:\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",
    "và được điều khiển bởi một qubit khác. Mạch sẽ hoạt động trên một thanh ghi mục tiêu hai qubit có tên 'target', và được điều khiển bởi một thanh ghi điều khiển một qubit có tên 'control'. Bạn nên gán mạch đã hoàn thành của mình vào biến 'cu4'. _Gợi ý: Giải pháp tốt nhất rất đơn giản._\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "c = QuantumRegister(1, 'control')\n",
    "t = QuantumRegister(2, 'target')\n",
    "cu4 = QuantumCircuit(c, t)\n",
    "\n",
    "# Viết code của bạn ở giữa những dòng này - Bắt đầu\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Viết code của bạn ở giữa những dòng này - Kết thúc\n",
    "\n",
    "cu4.draw('mpl')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bạn có thể kiểm tra kết quả của bạn sử dụng code sau"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Kiểm tra đáp án của bạn sử dụng code sau\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",
    "**Bài Tập 2 cuối:** Bây giờ chúng ta đã có mạch được điểu khiển $U$, $U^2$ and $U^4$, chúng ta có thể kết hợp nó thành một mạch thực hiện phần lượng tử của thuật toán Shor.\n",
    "\n",
    "Phần khởi tạo khá dễ: chúng ta cần đặt thanh ghi đếm vào trạng thái $|{+}{+}{+}\\rangle$ (ta có thể làm nó bằng cách sử dụng ba cổng H) và chúng ta cần thanh ghi mục tiêu ở trạng thái $|1\\rangle$ (mà chúng ta đã ánh xạ sang trạng thái tính toán cơ sở $|00\\rangle$, vì thế chúng ta sẽ không cần phải làm gì ở đây). Chúng tôi sẽ làm tất cả những thứ này cho bạn.\n",
    "\n",
    "Nhiệm vụ của bạn là tạo ra mạch thực hiện các phép điều khiển-$U$, sẽ được sử dụng giữa quá trình khởi tạo và phép biến đổi Fourier nghịch đảo lượng tử. Rõ ràng hơn, chúng tôi muốn một mạch:\n",
    "\n",
    "\n",
    "$$\n",
    "CU_{c_0 t}CU^2_{c_1 t}CU^4_{c_2 t}\n",
    "$$\n",
    "\n",
    "Trong đó $c_0$, $c_1$ và $c_2$ là ba qubit trong thanh ghi ‘counting’, $t$ là thanh ghi ‘target’, và $U$ như đã <a href=\"#u-definition\">được định nghĩa ở phần đầu của bài tập này</a>. Trong kí hiệu này, $CU_{a b}$ nghĩa là $CU$ được điều khiển bởi $a$ và tác động lên $b$. Một giải pháp dễ dàng cho việc này là kết hợp các mạch `cu`, `cu2` và `cu4` mà bạn đã tạo ra ở trên, nhưng rất có thể bạn sẽ tìm thấy được một mạch hiệu quả hơn và có cùng hành vi! \n",
    "    \n",
    "</div>\n",
    "<div class=\"alert alert-block alert-danger\">\n",
    "    \n",
    "Mạch của bạn chỉ được phép chứa [CNOTs](https://qiskit.org/documentation/stubs/qiskit.circuit.library.CXGate.html) và cổng U đơn qubit [U-gates](https://qiskit.org/documentation/stubs/qiskit.circuit.library.UGate.html). Điểm của bạn sẽ là số lượng cổng CNOT mà bạn sử dụng (càng it càng tốt), vì cổng nhiều qubit thường khó thực hiện trên phần cứng hơn nhiều so với cổng đơn qubit. Nếu bạn đang gặp khó khăn với yêu cầu này, chúng tôi đã bao gồm một dòng code bên cạnh bài nộp, nó sẽ chuyển đổi mạch của bạn sang dạng này, mặc dù bạn có thể làm tốt hơn bằng tay. \n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Code để kết hợp các giải pháp trước vào bài nộp cuối của bạn\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": [
    "# Kiểm tra kết quả của bạn sử dụng code sau\n",
    "from qc_grader import grade_ex2_final\n",
    "# Bỏ comment hai dòng dưới nếu bạn cần chuyển đổi mạch của mình sang cổng CNOT và cổng đơn qubit\n",
    "#from qiskit import transpile\n",
    "#cux = transpile(cux, basis_gates=['cx','u'])\n",
    "grade_ex2_final(cux)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Khi bạn đã hài lòng với mạch của mình, bạn có thể nộp nó bên dưới:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Nộp kết quả của bạn. Bạn có thể nộp nó vào bất cứ lúc nào.\n",
    "from qc_grader import submit_ex2_final\n",
    "submit_ex2_final(cux)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Xin chúc mừng! Bạn đã hoàn thành bài tập. Hãy đọc tiếp để xem mạch của bạn được sử dụng để phân tách số 35 thành các thừa số nguyên tố, và xem nó hoạt động như thế nào .\n",
    "\n",
    "## Dùng mạch của bạn để phân tách 35 thành các thừa số nguyên tố\n",
    "\n",
    "Đoạn code ở ô phía dưới sẽ nhận nội dung bài tập bạn gửi và sử dụng nó để tạo một mạch cung cấp cho chúng tôi  $\\tfrac{s}{r}$, trong đó $s$ là một số nguyên ngẫu nhiên trong khoảng $0$ và $r-1$, và $r$ là chu kỳ của hàm $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",
    "# Tạo mạch đối tượng\n",
    "cr = ClassicalRegister(3)\n",
    "shor_circuit = QuantumCircuit(cqr, tqr, cr)\n",
    "\n",
    "# Khởi tạo các qubits\n",
    "shor_circuit.h(cqr)\n",
    "\n",
    "# Thêm mạch của bạn\n",
    "shor_circuit = shor_circuit.compose(cux)\n",
    "\n",
    "# Thực hiện QFT đảo và tách kết quả\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": [
    "Hãy chuyển đổi mạch này và xem nó lớn như thế nào và nó sử dụng bao nhiêu CNOT: "
   ]
  },
  {
   "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\"circuit depth: {tqc.depth()}\")\n",
    "print(f\"circuit contains {tqc.count_ops()['cx']} CNOTs\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hãy xem chúng ta nhận được gì:"
   ]
  },
  {
   "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": [
    "Giả sử rằng mọi thứ đều hoạt động chính xác, chúng ta sẽ thấy xác suất đo các số $0$, $2$, $4$ và $8$ bằng nhau. Điều này xảy ra vì việc ước lượng pha cho chúng ta $2^n \\cdot \\tfrac{s}{r}$, trong đó $n$ là số lượng qubit trong thanh ghi bộ đếm của chúng ta (ở đây $n = 3$, $s$ là một số nguyên ngẫu nhiên trong khoảng $0$ và $r-1$, và $r$ là số chúng ta đang cố tính toán). Hãy chuyển chúng thành phân số cho chúng ta biết $s/r$ (đây là thứ mà chúng ta có thể dễ dàng tính toán theo cách cổ điển):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from fractions import Fraction\n",
    "n = 3  # n là số lượng qubit trong thanh ghi 'counting'\n",
    "# Lặp qua mỗi chuỗi đo lường\n",
    "for measurement in counts.keys():\n",
    "    # Chuyển đổi chuỗi nhị phân thành 'int'(số nguyên) và chia cho 2 ^ n \n",
    "    decimal = int(measurement, 2)/2**n\n",
    "    # Sử dụng thuật toán phân số liên tục(continued fractions) để chuyển đổi thành a / b \n",
    "    print(Fraction(decimal).limit_denominator())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Chúng ta có thể thấy mẫu số của một số kết quả sẽ cho chúng ta biết câu trả lời đúng $r = 4$. Chúng ta có thể kiểm tra $r=4$ nhanh chóng:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "13**4 % 35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vậy làm thế nào để ta có thể lấy được các thừa số nguyên tố từ điều này? Có khả năng cao là ước chung lớn nhất của $N$ và $a^{r/2}-1$ hoặc $a^{r/2}+1$ là thừa số nguyên tố của $N$, và ước chung lớn nhất là một thứ mà chúng ta có thể dễ dàng tính toán theo kiểu cổ điển."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from math import gcd # Ước chung lớn nhất\n",
    "for x in [-1, 1]:\n",
    "    print(f\"Guessed factor: {gcd(13**(4//2)+x, 35)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Chúng ta chỉ cần tìm một thừa số nguyên tố và có thể dùng nó để chia $N$ để tìm các thừa số khác. Nhưng trong trường hợp này, _cả_ $a^{r/2}-1$ hoặc $a^{r/2}+1$ đều cho ta thừa số của $35$. Chúng tôi có thể xác minh lại điều này là chính xác: :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "7*5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chạy trên `ibmq_santiago`\n",
    "\n",
    "Chúng tôi đã hứa rằng bài này sẽ chạy trên Santiago, vì vậy ở đây chúng tôi sẽ hướng dẫn bạn cách thực hiện điều đó. Trong ví dụ này, chúng tôi sẽ sử dụng thiết bị Santiago mô phỏng để thuận tiện, nhưng bạn có thể chuyển sang thiết bị thực nếu muốn: "
   ]
  },
  {
   "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",
    "## Bỏ comment đoạn code này để chạy trên máy thật\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",
    "# Bạn cần chuyển đổi cho Santiago\n",
    "tqc = transpile(shor_circuit, santiago, optimization_level=3)\n",
    "\n",
    "if not real_device:\n",
    "    tqc = assemble(tqc)\n",
    "\n",
    "# Chạy mạch và in ra counts\n",
    "counts = santiago.run(tqc).result().get_counts()\n",
    "plot_histogram(counts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nếu điểm của bạn đủ thấp, bạn sẽ thấy chúng ta có xác suất cao đo được $0$, $2$, $4$ hoặc $8$ như chúng ta đã thấy với việc mô phỏng hoàn hảo. Bạn sẽ thấy thêm một vài kết quả khác do sự không chính xác trong bộ xử lý và những thứ khác không mong muốn tương tác với qubit của chúng tôi.'Nhiễu' này này trở nên tồi tệ hơn khi mạch của chúng tôi dài hơn, vì thời gian tính toán lâu hơn đồng nghĩa với việc nhiều thời gian hơn cho các tương tác không mong muốn và nhiều cổng hơn đồng nghĩa với việc nhiều lỗi tiềm ẩn hơn. Đây là lý do tại sao chúng tôi cần gian lận để tạo ra mạch nhỏ nhất có thể. \n",
    "\n",
    "Trong tương lai gần, các hệ thống lượng tử của chúng tôi sẽ cải thiện và đủ để chúng tôi có thể bắt đầu sử dụng các kỹ thuật giảm thiểu lỗi nâng cao hơn để khắc phục những vấn đề này, điều này nghĩa là chúng tôi có thể chạy các mạch đủ lớn để chúng tôi có thể [thực hiện thuật toán của Shor mà không gian lận](https://arxiv.org/pdf/quant-ph/0205095.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Thông tin thêm\n",
    "\n",
    "**Tạo bởi:** Frank Harkins\n",
    "\n",
    "**Dịch bởi:** Bao Bach, Minh Dinh\n",
    "\n",
    "**Phiên bản:** 1.0.1"
   ]
  }
 ],
 "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.8.3"
  },
  "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
}