Prosedur anggaran fasa

Seterusnya, kita akan bincangkan prosedur anggaran fasa, iaitu satu algoritma kuantum untuk menyelesaikan masalah anggaran fasa.

Kita akan mulakan dengan pemanasan ketepatan rendah, yang menerangkan beberapa intuisi asas di sebalik kaedah ini. Kemudian kita akan bincangkan transformasi Fourier kuantum, iaitu operasi kuantum penting yang digunakan dalam prosedur anggaran fasa, serta implementasi Circuit kuantumnya. Setelah kita memahami transformasi Fourier kuantum, kita akan huraikan prosedur anggaran fasa secara penuh dan menganalisis prestasinya.

Pemanasan: menganggar fasa dengan ketepatan rendah

Kita akan mulakan dengan beberapa versi mudah prosedur anggaran fasa yang memberikan penyelesaian ketepatan rendah kepada masalah anggaran fasa. Ini berguna untuk menerangkan intuisi di sebalik prosedur umum yang akan kita lihat sebentar lagi dalam pelajaran ini.

Menggunakan fasa kickback

Pendekatan mudah kepada masalah anggaran fasa, yang membolehkan kita mempelajari sesuatu tentang nilai $\theta$ yang kita cari, adalah berdasarkan fenomena phase kick-back. Seperti yang akan kita lihat, ini pada dasarnya adalah versi satu-Qubit prosedur anggaran fasa umum yang akan dibincangkan kemudian dalam pelajaran ini.

Sebagai sebahagian daripada input kepada masalah anggaran fasa, kita mempunyai Circuit kuantum bersatu untuk operasi $U.$ Kita boleh menggunakan huraian Circuit ini untuk mencipta Circuit bagi operasi controlled-$U$, yang boleh digambarkan seperti yang dicadangkan oleh rajah ini (dengan operasi $U,$ dilihat sebagai Gate kuantum, di sebelah kiri dan operasi controlled-$U$ di sebelah kanan).

Kita boleh mencipta Circuit kuantum untuk operasi controlled-$U$ dengan terlebih dahulu menambah Qubit kawalan pada Circuit untuk $U,$ kemudian menggantikan setiap Gate dalam Circuit untuk $U$ dengan versi dikawal bagi Gate tersebut — jadi satu Qubit kawalan baru kita secara efektif mengawal setiap Gate tunggal dalam Circuit untuk $U.$ Ini memerlukan kita mempunyai versi dikawal bagi setiap Gate dalam Circuit kita, tetapi kita sentiasa boleh membina Circuit untuk operasi terkawal ini sekiranya ia tidak disertakan dalam set Gate kita.

Sekarang pertimbangkan Circuit berikut, di mana keadaan input $\vert\psi\rangle$ bagi semua Qubit kecuali yang paling atas adalah vektor eigenvector keadaan kuantum bagi $U.$

Kebarangkalian keputusan pengukuran untuk Circuit ini bergantung pada eigenvalue bagi $U$ yang sepadan dengan eigenvector $\vert\psi\rangle.$ Mari kita analisis Circuit secara terperinci untuk menentukan bagaimana tepatnya.

Keadaan awal Circuit adalah

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

dan Gate Hadamard pertama mengubah keadaan ini kepada

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

Seterusnya, operasi controlled-$U$ dilaksanakan, yang menghasilkan keadaan

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

Menggunakan andaian bahawa $\vert\psi\rangle$ adalah eigenvector bagi $U$ dengan eigenvalue $\lambda = e^{2\pi i\theta},$ kita boleh mengungkapkan keadaan ini secara alternatif seperti berikut.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

Di sini kita memerhati fenomena phase kickback. Ia sedikit berbeza kali ini berbanding dengan algoritma Deutsch dan algoritma Deutsch-Jozsa kerana kita tidak bekerja dengan Gate pertanyaan — tetapi ideanya adalah serupa.

Akhirnya, Gate Hadamard kedua dilaksanakan. Selepas sedikit penyederhanaan, kita memperoleh ungkapan ini untuk keadaan tersebut.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

Oleh itu, pengukuran menghasilkan keputusan $0$ dan $1$ dengan kebarangkalian berikut:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

Berikut adalah plot kebarangkalian untuk dua keputusan yang mungkin, $0$ dan $1,$ sebagai fungsi $\theta.$

Secara semula jadi, kedua-dua kebarangkalian sentiasa berjumlah $1.$ Perhatikan bahawa apabila $\theta = 0,$ keputusan pengukuran sentiasa $0,$ dan apabila $\theta = 1/2,$ keputusan pengukuran sentiasa $1.$ Jadi, walaupun keputusan pengukuran tidak mendedahkan nilai tepat $\theta,$ ia memberikan kita sedikit maklumat tentangnya — dan jika kita dijanjikan bahawa sama ada $\theta = 0$ atau $\theta = 1/2,$ kita boleh mengetahui dari Circuit mana satu yang betul tanpa ralat.

Secara intuitif, kita boleh menganggap keputusan pengukuran Circuit sebagai tekaan untuk $\theta$ dengan "satu bit ketepatan." Dengan kata lain, jika kita menulis $\theta$ dalam notasi binari dan membulatkannya kepada satu bit, kita akan mempunyai nombor seperti ini:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

Keputusan pengukuran boleh dilihat sebagai tekaan untuk bit $a.$ Apabila $\theta$ bukan $0$ mahupun $1/2,$ terdapat kebarangkalian bukan sifar bahawa tekaan akan salah — tetapi kebarangkalian membuat ralat semakin kecil apabila kita semakin hampir kepada $0$ atau $1/2.$

Adalah wajar untuk bertanya apakah peranan dua Gate Hadamard dalam prosedur ini:

• Gate Hadamard pertama menetapkan Qubit kawalan kepada superposisi seragam $\vert 0\rangle$ dan $\vert 1\rangle,$ supaya apabila phase kickback berlaku, ia berlaku untuk keadaan $\vert 1\rangle$ dan bukan keadaan $\vert 0\rangle$, mewujudkan perbezaan fasa relatif yang mempengaruhi keputusan pengukuran. Jika kita tidak melakukan ini dan phase kickback menghasilkan fasa global, ia tidak akan memberi kesan pada kebarangkalian mendapat keputusan pengukuran yang berbeza.

• Gate Hadamard kedua membolehkan kita mempelajari sesuatu tentang nombor $\theta$ melalui fenomena interferens. Sebelum Gate Hadamard kedua, keadaan Qubit atas adalah

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  dan jika kita mengukur keadaan ini, kita akan memperoleh $0$ dan $1$ masing-masing dengan kebarangkalian $1/2,$ yang tidak memberitahu kita apa-apa tentang $\theta.$ Namun dengan melaksanakan Gate Hadamard kedua, kita menyebabkan nombor $\theta$ mempengaruhi kebarangkalian output.

Menggandakan fasa

Circuit di atas menggunakan fenomena phase kickback untuk menganggar $\theta$ dengan ketepatan satu bit. Satu bit ketepatan mungkin cukup dalam sesetengah situasi — tetapi untuk pemfaktoran kita akan memerlukan jauh lebih banyak ketepatan daripada itu. Soalan yang wajar adalah, bagaimana kita boleh mempelajari lebih lanjut tentang $\theta?$

Satu perkara yang sangat mudah yang boleh kita lakukan adalah menggantikan operasi controlled-$U$ dalam Circuit kita dengan dua salinan operasi ini, seperti dalam Circuit ini:

Dua salinan operasi controlled-$U$ bersamaan dengan operasi controlled-$U^2$. Jika $\vert\psi\rangle$ adalah eigenvector bagi $U$ dengan eigenvalue $\lambda = e^{2\pi i \theta},$ maka keadaan ini juga merupakan eigenvector bagi $U^2,$ kali ini dengan eigenvalue $\lambda^2 = e^{2\pi i (2\theta)}.$

Jadi, jika kita menjalankan versi Circuit ini, kita pada dasarnya menjalankan pengiraan yang sama seperti sebelumnya, kecuali nombor $\theta$ digantikan dengan $2\theta.$ Berikut adalah plot yang menggambarkan kebarangkalian output apabila $\theta$ berkisar dari $0$ ke $1.$

Melakukan ini memang boleh memberikan kita beberapa maklumat tambahan tentang $\theta.$ Jika perwakilan binari $\theta$ adalah

$$\theta = 0.a_1 a_2 a_3\cdots$$

maka menggandakan $\theta$ secara efektif menggeser titik binari satu kedudukan ke kanan:

$$2\theta = a_1. a_2 a_3\cdots$$

Dan kerana kita menyamakan $\theta = 1$ dengan $\theta = 0$ semasa kita bergerak di sekitar bulatan unit, kita nampak bahawa bit $a_1$ tidak mempengaruhi kebarangkalian kita, dan kita pada dasarnya memperoleh tekaan untuk bit kedua selepas titik binari jika kita membulatkan $\theta$ kepada dua bit. Sebagai contoh, jika kita mengetahui lebih awal bahawa $\theta$ adalah sama ada $0$ atau $1/4,$ maka kita boleh sepenuhnya mempercayai keputusan pengukuran untuk memberitahu kita mana satu.

Namun tidak jelas, bagaimana anggaran ini harus diselaraskan dengan apa yang kita pelajari dari Circuit phase kickback asal (yang tidak digandakan) untuk memberikan maklumat paling tepat yang mungkin tentang $\theta.$ Jadi mari kita ambil langkah ke belakang dan fikirkan cara untuk meneruskan.

Anggaran fasa dua-Qubit

Daripada mempertimbangkan dua pilihan yang dihuraikan di atas secara berasingan, mari kita gabungkan keduanya dalam satu Circuit seperti ini.

Gate Hadamard selepas operasi terkawal telah dibuang dan tiada pengukuran di sini lagi. Kita akan menambah lagi pada Circuit apabila kita mempertimbangkan pilihan kita untuk mempelajari sebanyak mungkin tentang $\theta.$

Jika kita menjalankan Circuit ini apabila $\vert\psi\rangle$ adalah eigenvector bagi $U,$ keadaan Qubit bawah akan kekal sebagai $\vert\psi\rangle$ sepanjang keseluruhan Circuit, dan fasa akan "ditendang" ke dalam keadaan dua Qubit atas. Mari kita analisis Circuit dengan teliti, melalui rajah berikut.

Kita boleh menulis keadaan $\vert\pi_1\rangle$ seperti ini:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

Apabila operasi controlled-$U$ pertama dilaksanakan, eigenvalue $\lambda = e^{2\pi i\theta}$ ditendang ke dalam fasa apabila $a_0$ (Qubit atas) bersamaan $1,$ tetapi tidak apabila ia $0.$ Jadi, kita boleh mengungkapkan keadaan yang dihasilkan seperti ini:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

Gate controlled-$U$ kedua dan ketiga melakukan sesuatu yang serupa, kecuali untuk $a_1$ dan bukan $a_0,$ dan dengan $\theta$ digantikan oleh $2\theta.$ Kita boleh mengungkapkan keadaan yang dihasilkan seperti ini:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

Jika kita menganggap rentetan binari $a_1 a_0$ sebagai mewakili integer $x \in \{0,1,2,3\}$ dalam notasi binari, iaitu $x = 2 a_1 + a_0,$ kita boleh mengungkapkan keadaan ini secara alternatif seperti berikut.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

Matlamat kita adalah untuk mengekstrak sebanyak mungkin maklumat tentang $\theta$ daripada keadaan ini.

Pada ketika ini kita akan mempertimbangkan kes khas, di mana kita dijanjikan bahawa $\theta = \frac{y}{4}$ untuk sesetengah integer $y\in\{0,1,2,3\}.$ Dengan kata lain, kita mempunyai $\theta\in \{0, 1/4, 1/2, 3/4\},$ jadi kita boleh mengungkapkan nombor ini dengan tepat menggunakan notasi binari dengan dua bit, sebagai .$00,$ .$01,$ .$10,$ atau .$11.$ Secara umum, $\theta$ mungkin bukan salah satu daripada empat nilai ini, tetapi memikirkan kes khas ini akan membantu kita mengetahui cara paling berkesan untuk mengekstrak maklumat tentang $\theta$ secara umum.

Pertama kita akan mendefinisikan vektor keadaan dua-Qubit untuk setiap nilai yang mungkin $y \in \{0, 1, 2, 3\}.$

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

Selepas menyederhanakan eksponen, kita boleh menulis vektor-vektor ini seperti berikut.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

Vektor-vektor ini adalah ortogon: jika kita memilih mana-mana pasangan daripada mereka dan mengira hasil darab dalam mereka, kita mendapat $0.$ Setiap satunya juga merupakan vektor unit, jadi $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ adalah asas ortonormal. Oleh itu kita tahu serta-merta bahawa terdapat pengukuran yang boleh membezakan mereka dengan sempurna — bermakna, jika kita diberi salah satu daripadanya tetapi kita tidak tahu yang mana, maka kita boleh mengetahui yang mana tanpa ralat.

Untuk melaksanakan perbezaan sedemikian dengan Circuit kuantum, kita boleh terlebih dahulu mendefinisikan operasi uniter $V$ yang mengubah keadaan asas standard menjadi empat keadaan yang disenaraikan di atas.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

Untuk menulis $V$ sebagai matriks $4\times 4,$ ia hanyalah perkara mengambil lajur $V$ sebagai keadaan $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle.$

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Ini adalah matriks khas, dan berkemungkinan sesetengah pembaca pernah menemuinya sebelum ini: ia adalah matriks yang berkaitan dengan transformasi Fourier diskret $4$-dimensi. Memandangkan fakta ini, mari kita panggil ia dengan nama $\mathrm{QFT}_4$ dan bukan $V.$ Nama $\mathrm{QFT}$ adalah singkatan bagi transformasi Fourier kuantum — yang pada dasarnya hanyalah transformasi Fourier diskret, dilihat sebagai operasi uniter. Kita akan bincangkan transformasi Fourier kuantum dengan lebih terperinci dan keumuman tidak lama lagi.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Kita boleh melaksanakan songsangan operasi ini untuk pergi ke arah lain, untuk mengubah keadaan $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ menjadi keadaan asas standard $\vert 0\rangle,\ldots,\vert 3\rangle.$ Jika kita melakukan ini, maka kita boleh mengukur untuk mengetahui nilai $y\in\{0,1,2,3\}$ yang menghuraikan $\theta$ sebagai $\theta = y/4.$ Berikut adalah gambar rajah Circuit kuantum yang melakukan ini.

Untuk merumuskan, jika kita menjalankan Circuit ini apabila $\theta = y/4$ untuk $y\in\{0,1,2,3\},$ keadaan sejurus sebelum pengukuran berlaku akan menjadi $\vert \psi\rangle \vert y\rangle$ (untuk $y$ dikodkan sebagai rentetan binari dua-bit), jadi pengukuran akan mendedahkan nilai $y$ tanpa ralat.

Circuit ini dimotivasikan oleh kes khas bahawa $\theta \in \{0,1/4,1/2,3/4\}$ — tetapi kita boleh menjalankannya untuk mana-mana pilihan $U$ dan $\vert \psi\rangle,$ dan oleh itu mana-mana nilai $\theta,$ yang kita inginkan. Berikut adalah plot kebarangkalian output yang dihasilkan Circuit untuk pilihan $\theta$ yang sewenang-wenangnya.

Ini adalah peningkatan yang jelas berbanding varian satu-Qubit yang dihuraikan lebih awal dalam pelajaran ini. Ia tidak sempurna — ia boleh memberikan jawapan yang salah — tetapi jawapan sangat condong ke arah nilai $y$ yang $y/4$ hampir dengan $\theta.$ Khususnya, keputusan paling mungkin sentiasa sepadan dengan nilai $y/4$ yang paling hampir dengan $\theta$ (menyamakan $\theta = 0$ dan $\theta = 1$ seperti sebelumnya), dan dari plot ia kelihatan bahawa nilai terdekat untuk $x$ ini sentiasa muncul dengan kebarangkalian sedikit di atas $40\%.$ Apabila $\theta$ tepat di antara dua nilai sedemikian, seperti $\theta = 0.375$ sebagai contoh, dua nilai $y$ yang sama-sama hampir adalah sama-sama mungkin.

Bersedia untuk menggeneralisasi kepada banyak Qubit

Memandangkan peningkatan yang baru kita perolehi dengan menggunakan dua Qubit kawalan berbanding satu, bersama dengan songsangan transformasi Fourier kuantum $4$-dimensi, adalah wajar untuk mempertimbangkan generalisasinya lebih lanjut — dengan menambah lebih banyak Qubit kawalan. Apabila kita melakukan ini, kita memperoleh prosedur anggaran fasa umum. Kita akan melihat bagaimana ini berfungsi tidak lama lagi, tetapi untuk menerangkannya dengan tepat kita perlu membincangkan transformasi Fourier kuantum dengan lebih keumuman, untuk melihat bagaimana ia ditakrifkan untuk dimensi lain dan bagaimana kita boleh mengimplementasikannya (atau songsangannya) dengan Circuit kuantum.

Transformasi Fourier kuantum

Transformasi Fourier kuantum adalah operasi uniter yang boleh ditakrifkan untuk sebarang dimensi positif integer $N.$ Dalam bahagian ini, kita akan melihat bagaimana operasi ini ditakrifkan dan bagaimana ia boleh diimplementasikan dengan Circuit kuantum pada $m$ Qubit dengan kos $O(m^2)$ apabila $N = 2^m.$

Matriks yang menghuraikan transformasi Fourier kuantum diterbitkan daripada operasi analog pada vektor $N$-dimensi yang dikenali sebagai transformasi Fourier diskret. Operasi ini boleh difikirkan dengan cara yang berbeza. Sebagai contoh, kita boleh memikirkan transformasi Fourier diskret dalam istilah abstrak dan matematik semata-mata sebagai pemetaan linear. Atau kita boleh memikirkannya dalam istilah pengkomputeran, di mana kita diberi vektor kompleks $N$-dimensi (menggunakan notasi binari untuk mengodkan bahagian nyata dan khayalan entri, katakanlah) dan matlamatnya adalah untuk mengira vektor $N$-dimensi yang diperoleh dengan menggunakan transformasi Fourier diskret. Fokus kita akan pada cara ketiga, iaitu melihat transformasi ini sebagai operasi uniter yang boleh dilaksanakan pada sistem kuantum.

Terdapat algoritma cekap untuk mengira transformasi Fourier diskret pada vektor input yang diberikan yang dikenali sebagai transformasi Fourier pantas. Ia mempunyai aplikasi dalam pemprosesan isyarat dan banyak bidang lain, dan dianggap oleh ramai sebagai salah satu algoritma terpenting yang pernah ditemui. Ternyata, implementasi transformasi Fourier kuantum apabila $N$ adalah kuasa 2 yang akan kita pelajari adalah berdasarkan tepat pada struktur asas yang sama yang menjadikan transformasi Fourier pantas mungkin.

Definisi transformasi Fourier kuantum

Untuk mendefinisikan transformasi Fourier kuantum, kita akan terlebih dahulu mendefinisikan nombor kompleks $\omega_N,$ untuk setiap integer positif $N,$ seperti ini:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

Ini adalah nombor pada bulatan unit kompleks yang kita perolehi jika kita bermula pada $1$ dan bergerak mengikut arah lawan jam pada sudut $2\pi/N$ radian, atau pecahan $1/N$ lilitan bulatan. Berikut adalah beberapa contoh:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

Sekarang kita boleh mendefinisikan transformasi Fourier kuantum $N$-dimensi, yang dihuraikan oleh matriks $N\times N$ yang baris dan lajurnya dikaitkan dengan keadaan asas standard $\vert 0\rangle,\ldots,\vert N-1\rangle.$ Kita hanya akan memerlukan operasi ini untuk apabila $N = 2^m$ adalah kuasa $2$ untuk anggaran fasa, tetapi operasi ini boleh ditakrifkan untuk sebarang integer positif $N.$

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

Seperti yang telah dinyatakan, ini adalah matriks yang berkaitan dengan transformasi Fourier diskret $N$-dimensi. Selalunya faktor pendahulu $1/\sqrt{N}$ tidak disertakan dalam definisi matriks ini, tetapi kita perlu menyertakannya untuk mendapatkan matriks uniter.

Berikut adalah transformasi Fourier kuantum, ditulis sebagai matriks, untuk beberapa nilai kecil $N.$

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

Perhatikan, khususnya, bahawa $\mathrm{QFT}_2$ adalah nama lain untuk operasi Hadamard.

Keuniterian

Mari kita semak bahawa $\mathrm{QFT}_N$ adalah uniter, untuk sebarang pilihan $N.$ Salah satu cara untuk melakukan ini adalah dengan menunjukkan bahawa lajur-lajurnya membentuk asas ortonormal. Kita boleh mendefinisikan vektor yang sepadan dengan lajur nombor $y,$ bermula dari $y = 0$ hingga $y = N-1,$ seperti ini:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

Mengambil hasil darab dalam antara mana-mana dua vektor ini memberikan kita ungkapan ini:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

Kita boleh menilai jumlah seperti ini menggunakan formula berikut untuk jumlah $N$ sebutan pertama siri geometri.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Khususnya, kita boleh menggunakan formula ini apabila $\alpha = \omega_N^{y-z}.$ Apabila $y = z,$ kita mempunyai $\alpha = 1,$ jadi menggunakan formula dan membahagi dengan $N$ memberikan

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

Apabila $y\neq z,$ kita mempunyai $\alpha \neq 1,$ jadi formula mendedahkan ini:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

Ini berlaku kerana $\omega_N^N = e^{2\pi i} = 1,$ jadi $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ menjadikan pengangka sifar, manakala penyebut bukan sifar kerana $\omega_N^{y-z} \neq 1.$ Secara intuitif, apa yang kita lakukan adalah menjumlahkan sekumpulan titik yang diedarkan di sekitar bulatan unit, dan mereka saling menghapuskan dan meninggalkan $0$ apabila dijumlahkan.

Dengan itu kita telah membuktikan bahawa $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ adalah set ortonormal,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

yang mendedahkan bahawa $\mathrm{QFT}_N$ adalah uniter.

Gate fasa terkawal

Untuk mengimplementasikan transformasi Fourier kuantum dengan Circuit kuantum, kita perlu menggunakan Gate fasa terkawal. Ingat bahawa operasi fasa adalah operasi uniter satu-Qubit berbentuk

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

untuk sebarang nombor nyata $\alpha.$ Versi terkawal Gate ini mempunyai matriks berikut:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

Untuk Gate terkawal ini, sebenarnya tidak kira Qubit mana yang menjadi kawalan dan mana yang menjadi sasaran kerana kedua-dua kemungkinan adalah setara. Kita boleh menggunakan mana-mana simbol berikut untuk mewakili Gate ini dalam gambar rajah Circuit kuantum.

Untuk bentuk ketiga, label $\alpha$ juga kadangkala diletakkan di sisi garis kawalan atau di bawah kawalan bawah apabila itu lebih sesuai.

Untuk melaksanakan transformasi Fourier kuantum apabila $N = 2^m$ dan $m\geq 2,$ kita perlu melaksanakan operasi pada $m$ Qubit yang tindakannya pada keadaan asas standard boleh dihuraikan sebagai

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

di mana $a$ adalah bit dan $y \in \{0,\ldots,2^{m-1} - 1\}$ adalah nombor yang dikodkan dalam notasi binari sebagai rentetan $m-1$ bit. Ini boleh dilakukan menggunakan Gate fasa terkawal dengan menggeneralisasi contoh berikut, untuk $m=5.$

Secara umum, untuk pilihan sewenang-wenang $m\geq 2,$ Qubit atas yang sepadan dengan bit $a$ boleh dilihat sebagai kawalan, dengan Gate fasa $P_{\alpha}$ berkisar dari $\alpha = \pi/2^{m-1}$ pada Qubit yang sepadan dengan bit paling tidak signifikan bagi $y$ ke $\alpha = \frac{\pi}{2}$ pada Qubit yang sepadan dengan bit paling signifikan bagi $y.$ Semua Gate fasa terkawal ini bolak-balik antara satu sama lain dan boleh dilaksanakan dalam sebarang urutan.

Implementasi Circuit bagi QFT

Sekarang kita akan melihat bagaimana kita boleh mengimplementasikan transformasi Fourier kuantum dengan Circuit apabila dimensi $N = 2^m$ adalah kuasa $2.$ Sebenarnya, terdapat pelbagai cara untuk mengimplementasikan transformasi Fourier kuantum, tetapi ini boleh dibilang kaedah paling mudah yang diketahui. Setelah kita mengetahui cara mengimplementasikan transformasi Fourier kuantum dengan Circuit kuantum, adalah mudah untuk mengimplementasikan songsangannya: kita boleh menggantikan setiap Gate dengan songsangannya (atau, secara setara, konjugat transpose) dan menggunakan Gate dalam urutan terbalik. Setiap Circuit kuantum yang terdiri daripada Gate uniter sahaja boleh disongsangkan dengan cara ini.

Implementasi ini bersifat rekursif, jadi itulah cara paling semula jadi untuk menerangkannya. Kes asas adalah $m=1,$ dalam kes ini transformasi Fourier kuantum adalah operasi Hadamard.

Untuk melaksanakan transformasi Fourier kuantum pada $m$ Qubit apabila $m \geq 2,$ kita boleh melaksanakan langkah-langkah berikut, yang tindakannya akan kita huraikan untuk keadaan asas standard berbentuk $\vert x \rangle \vert a\rangle,$ di mana $x\in\{0,\ldots,2^{m-1} - 1\}$ adalah integer yang dikodkan sebagai $m-1$ bit menggunakan notasi binari dan $a$ adalah satu bit.

1. Pertama terapkan transformasi Fourier kuantum $2^{m-1}$-dimensi kepada $m-1$ Qubit bawah/paling kiri untuk mendapatkan keadaan ini:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   Ini dilakukan dengan menerapkan secara rekursif kaedah yang dihuraikan untuk satu Qubit lebih sedikit, menggunakan operasi Hadamard pada satu Qubit sebagai kes asas.

2. Gunakan Qubit atas/paling kanan sebagai kawalan untuk menyuntik fasa $\omega_{2^m}^y$ untuk setiap keadaan asas standard $\vert y\rangle$ bagi $m-1$ Qubit yang tinggal (seperti yang dihuraikan di atas) untuk mendapatkan keadaan ini:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. Laksanakan Gate Hadamard pada Qubit atas/paling kanan untuk mendapatkan keadaan ini:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. Permutasikan susunan Qubit supaya bit paling tidak signifikan menjadi bit paling signifikan, dengan semua yang lain digeser ke atas/kanan:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

Sebagai contoh, berikut adalah Circuit yang kita perolehi untuk $N = 32 = 2^5.$ Dalam gambar rajah ini, Qubit diberi nama yang sepadan dengan vektor asas standard $\vert x\rangle \vert a\rangle$ (untuk input) dan $\vert b\rangle \vert y\rangle$ (untuk output) untuk kejelasan.

Analisis

Formula utama yang kita perlukan untuk mengesahkan bahawa Circuit yang baru dihuraikan mengimplementasikan transformasi Fourier kuantum $2^m$-dimensi adalah ini:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

Formula ini berfungsi untuk sebarang pilihan integer $a,$ $b,$ $x,$ dan $y,$ tetapi kita hanya memerlukannya untuk $a,b\in\{0,1\}$ dan $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Ia boleh disemak dengan mengembangkan hasil darab dalam eksponen pada bahagian kanan,

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

di mana kesamaan kedua menggunakan pemerhatian bahawa

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

Transformasi Fourier kuantum $2^m$-dimensi ditakrifkan seperti berikut untuk setiap $u\in\{0,\ldots,2^m - 1\}.$

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

Jika kita menulis $u$ dan $v$ sebagai

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

untuk $a,b\in\{0,1\}$ dan $x,y\in\{0,\ldots,2^{m-1} - 1\},$ kita memperoleh

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

Akhirnya, dengan memikirkan keadaan asas standard $\vert x \rangle \vert a\rangle$ dan $\vert b \rangle \vert y \rangle$ sebagai pengekodan binari integer dalam julat $\{0,\ldots,2^m-1\},$

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

kita melihat bahawa Circuit di atas mengimplementasikan operasi yang diperlukan. Jika kaedah untuk melaksanakan transformasi Fourier kuantum ini kelihatan luar biasa, itu kerana ia memang begitu: ia pada dasarnya adalah transformasi Fourier pantas dalam bentuk Circuit kuantum.

Akhirnya, mari kita kira berapa banyak Gate yang digunakan dalam Circuit yang baru dihuraikan. Gate fasa terkawal tidak berada dalam set Gate standard yang kita bincangkan dalam pelajaran sebelumnya, tetapi untuk memulakan kita akan mengabaikan ini dan mengira setiap satunya sebagai satu Gate.

Katakan $s_m$ menandakan bilangan Gate yang kita perlukan untuk setiap pilihan $m$ yang mungkin. Jika $m=1,$ transformasi Fourier kuantum hanyalah operasi Hadamard, jadi

$$s_1 = 1.$$

Jika $m\geq 2,$ maka dalam Circuit di atas kita memerlukan $s_{m-1}$ Gate untuk transformasi Fourier kuantum pada $m-1$ Qubit, ditambah $m-1$ Gate fasa terkawal, ditambah satu Gate Hadamard, ditambah $m-1$ Gate swap, jadi

$$s_m = s_{m-1} + (2m - 1).$$

Kita boleh mendapatkan ungkapan bentuk tertutup dengan menjumlahkan:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

Kita sebenarnya tidak memerlukan sebanyak Gate swap seperti yang dihuraikan kaedah ini. Jika kita menyusun semula Gate sedikit, kita boleh menolak semua Gate swap ke kanan dan mengurangkan bilangan Gate swap yang diperlukan kepada $\lfloor m/2\rfloor.$ Secara asimptotik ini bukan peningkatan besar: kita masih mendapat Circuit bersaiz $O(m^2)$ untuk melaksanakan $\mathrm{QFT}_{2^m}.$

Jika kita ingin mengimplementasikan transformasi Fourier kuantum menggunakan hanya Gate daripada set Gate standard kita, kita perlu sama ada membina atau menganggar setiap Gate fasa terkawal dengan Gate dari set kita. Bilangan yang diperlukan bergantung pada berapa banyak ketepatan yang kita perlukan, tetapi sebagai fungsi $m$ jumlah kos kekal kuadratik.

Malah, adalah mungkin untuk menganggar transformasi Fourier kuantum dengan sangat tepat menggunakan bilangan Gate sub-kuadratik dengan menggunakan fakta bahawa $P_{\alpha}$ sangat hampir dengan operasi identiti apabila $\alpha$ sangat kecil — yang bermakna kita boleh meninggalkan kebanyakan Gate fasa terkawal tanpa mengalami terlalu banyak kehilangan dari segi ketepatan.

Prosedur umum dan analisis

Sekarang kita akan meneliti prosedur anggaran fasa secara umum. Ideanya adalah untuk memperluaskan versi dua-Qubit bagi anggaran fasa yang kita pertimbangkan di atas, mengikut cara yang dicadangkan oleh rajah berikut.

Perhatikan bahawa, bagi setiap Qubit kawalan baru yang ditambah di bahagian atas, kita menggandakan bilangan kali operasi uniter $U$ dilaksanakan. Ini ditunjukkan dalam rajah melalui kuasa pada $U$ bagi setiap operasi uniter terkawal.

Cara paling mudah untuk melaksanakan operasi $U^k$ terkawal bagi sesuatu pilihan $k$ ialah dengan hanya mengulangi operasi $U$ terkawal sebanyak $k$ kali. Jika inilah metodologi yang digunakan, perlu diakui bahawa penambahan Qubit kawalan menyumbang secara ketara kepada saiz Circuit: jika kita mempunyai $m$ Qubit kawalan, seperti yang digambarkan dalam rajah, sejumlah $2^m - 1$ salinan operasi $U$ terkawal diperlukan. Ini bermakna kos pengiraan yang besar ditanggung apabila $m$ meningkat — tetapi seperti yang akan kita lihat, ia juga menghasilkan penghampiran $\theta$ yang jauh lebih tepat.

Namun penting untuk diingat bahawa bagi sesetengah pilihan $U$, mungkin terdapat cara untuk mencipta Circuit yang melaksanakan operasi $U^k$ bagi nilai $k$ yang besar dengan cara yang lebih cekap daripada sekadar mengulangi Circuit untuk $U$ sebanyak $k$ kali. Kita akan melihat contoh khusus ini dalam konteks pemfaktoran integer kemudian dalam pelajaran ini, di mana algoritma cekap untuk pemangkinan modular yang dibincangkan dalam pelajaran sebelumnya datang menyelamatkan.

Sekarang mari kita analisis Circuit yang baru diterangkan. Keadaan sejurus sebelum jelmaan Fourier kuantum songsang kelihatan seperti ini:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

Kes khas

Selaras dengan apa yang kita lakukan dalam kes $m=2$, kita akan mempertimbangkan dahulu kes khas di mana $\theta = y/2^m$ untuk $y\in\{0,\ldots,2^m-1\}.$ Dalam kes ini, keadaan sebelum jelmaan Fourier kuantum songsang boleh ditulis semula seperti ini:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

Jadi, apabila jelmaan Fourier kuantum songsang digunakan, keadaan menjadi

$$\vert\psi\rangle \vert y\rangle$$

dan pengukuran mendedahkan $y$ (dikodkan dalam perduaan).

Membatasi kebarangkalian

Bagi nilai $\theta$ yang lain, iaitu yang tidak berbentuk $y/2^m$ untuk integer $y$, hasil pengukuran tidak akan pasti, tetapi kita boleh membuktikan batas ke atas kebarangkalian bagi hasil yang berbeza. Seterusnya, mari kita pertimbangkan pilihan $\theta$ sembarangan yang memenuhi $0\leq \theta < 1.$

Setelah jelmaan Fourier kuantum songsang dilaksanakan, keadaan Circuit adalah:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

Jadi, apabila pengukuran ke atas $m$ Qubit teratas dilakukan, kita melihat setiap hasil $y$ dengan kebarangkalian

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

Untuk memahami kebarangkalian ini dengan lebih baik, kita akan menggunakan formula yang sama seperti sebelum ini, untuk jumlah bahagian awal siri geometri.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Kita boleh memudahkan jumlah yang muncul dalam formula untuk $p_y$ dengan mengambil $\alpha = e^{2\pi i (\theta - y/2^m)}.$ Inilah yang kita perolehi.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

Jadi, dalam kes $\theta = y/2^m$, kita dapati $p_y = 1$ (seperti yang sudah kita ketahui daripada kes khas ini), dan dalam kes $\theta \neq y/2^m$, kita dapati bahawa

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

Kita boleh mengetahui lebih lanjut tentang kebarangkalian ini dengan memikirkan hubungan antara panjang lengkok dan panjang perentas pada bulatan unit. Berikut adalah rajah yang menggambarkan hubungan yang diperlukan untuk sebarang nombor nyata $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr].$

Pertama, panjang perentas (dilukis dalam biru) tidak mungkin lebih besar daripada panjang lengkok (dilukis dalam ungu):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

Menghubungkan panjang-panjang ini dari arah sebaliknya, kita lihat bahawa nisbah panjang lengkok kepada panjang perentas adalah paling besar apabila $\delta = \pm 1/2$, dan dalam kes ini nisbahnya ialah separuh lilitan bulatan dibahagikan dengan diameter, iaitu $\pi/2.$ Oleh itu, kita mempunyai

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

dan oleh itu

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

Analisis berdasarkan hubungan ini mendedahkan dua fakta berikut.

1. Andaikan $\theta$ adalah nombor nyata dan $y\in \{0,\ldots,2^m-1\}$ memenuhi

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   Ini bermakna $y/2^m$ sama ada merupakan penghampiran $m$-bit terbaik kepada $\theta$, atau ia berada tepat di tengah-tengah antara $y/2^m$ dengan sama ada $(y-1)/2^m$ atau $(y+1)/2^m$, jadi ia adalah salah satu daripada dua penghampiran terbaik kepada $\theta.$

   Kita akan buktikan bahawa $p_y$ mestilah agak besar dalam kes ini. Berdasarkan andaian yang kita pertimbangkan, ia mengikut bahawa $\vert 2^m \theta - y \vert \leq 1/2,$ jadi kita boleh menggunakan pemerhatian kedua di atas tentang panjang lengkok dan perentas untuk menyimpulkan bahawa

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Kita juga boleh menggunakan pemerhatian pertama tentang panjang lengkok dan perentas untuk menyimpulkan bahawa

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Menggunakan kedua-dua ketaksamaan ini pada $p_y$ mendedahkan

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   Ini menjelaskan pemerhatian kita bahawa hasil terbaik berlaku dengan kebarangkalian lebih daripada $40\%$ dalam versi $m=2$ bagi anggaran fasa yang dibincangkan sebelum ini. Bukan benar-benar $40\%$, ia adalah $4/\pi^2$, dan sebenarnya batas ini berlaku untuk setiap pilihan $m.$

2. Sekarang andaikan $y\in \{0,\ldots,2^m-1\}$ memenuhi

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   Ini bermakna terdapat penghampiran yang lebih baik $z/2^m$ kepada $\theta$ di antara $\theta$ dan $y/2^m.$

   Kali ini kita akan buktikan bahawa $p_y$ tidak boleh terlalu besar. Kita boleh mulakan dengan pemerhatian mudah bahawa

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   yang terhasil daripada fakta bahawa mana-mana dua titik pada bulatan unit boleh berbeza dalam nilai mutlak sebanyak-banyaknya $2.$

   Kita juga boleh menggunakan pemerhatian kedua tentang panjang lengkok dan perentas dari atas, kali ini bekerja dengan penyebut $p_y$ dan bukannya pengangka, untuk menyimpulkan

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   Menggabungkan kedua-dua ketaksamaan mendedahkan

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   Perlu diingat bahawa walaupun batas ini cukup baik untuk tujuan kita, ia agak kasar — kebarangkalian biasanya jauh lebih rendah daripada $1/4.$

Kesimpulan penting daripada analisis ini ialah penghampiran yang sangat dekat kepada $\theta$ cenderung berlaku — kita akan mendapat penghampiran $m$-bit terbaik dengan kebarangkalian lebih daripada $40\%$ — manakala penghampiran yang tersasar lebih daripada $2^{-m}$ kurang cenderung berlaku, dengan kebarangkalian dibatasi oleh $25\%.$

Memandangkan jaminan ini, adalah mungkin untuk meningkatkan keyakinan kita dengan mengulangi prosedur anggaran fasa beberapa kali, untuk mengumpul bukti statistik tentang $\theta.$ Penting untuk diingat bahawa keadaan $\vert\psi\rangle$ bagi koleksi Qubit bahagian bawah tidak berubah melalui prosedur anggaran fasa, jadi ia boleh digunakan untuk menjalankan prosedur sebanyak yang kita suka. Khususnya, setiap kali kita menjalankan Circuit, kita mendapat penghampiran $m$-bit terbaik kepada $\theta$ dengan kebarangkalian lebih daripada $40\%$, manakala kebarangkalian tersasar lebih daripada $2^{-m}$ dibatasi oleh $25\%.$ Jika kita menjalankan Circuit beberapa kali dan mengambil hasil yang paling kerap muncul, maka sangat berkemungkinan hasil yang paling kerap muncul bukanlah hasil yang berlaku paling banyak $25\%$ daripada masa. Akibatnya, kita akan sangat berkemungkinan memperolehi penghampiran $y/2^m$ yang berada dalam jarak $1/2^m$ daripada nilai $\theta.$ Sememangnya, peluang kecil bahawa kita tersasar lebih daripada $1/2^m$ berkurangan secara eksponen dengan bilangan kali prosedur dijalankan.

Berikut adalah dua plot yang menunjukkan kebarangkalian bagi tiga nilai berturutan $y$ apabila $m = 3$ dan $m=4$ sebagai fungsi $\theta.$ (Hanya tiga hasil ditunjukkan untuk kejelasan. Kebarangkalian untuk hasil lain diperoleh dengan menggeser secara berkitar fungsi pendasar yang sama.)