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 litar 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 litar kuantum bersatu untuk operasi $U.$ Kita boleh menggunakan huraian litar ini untuk mencipta litar bagi operasi controlled-$U$, yang boleh digambarkan seperti yang dicadangkan oleh rajah ini (dengan operasi $U,$ dilihat sebagai get kuantum, di sebelah kiri dan operasi controlled-$U$ di sebelah kanan).

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

Sekarang pertimbangkan litar 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 litar ini bergantung pada eigenvalue bagi $U$ yang sepadan dengan eigenvector $\vert\psi\rangle.$ Mari kita analisis litar secara terperinci untuk menentukan bagaimana tepatnya.

Keadaan awal litar adalah

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

dan get 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 get pertanyaan — tetapi ideanya adalah serupa.

Akhirnya, get 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 litar mana satu yang betul tanpa ralat.

Secara intuitif, kita boleh menganggap keputusan pengukuran litar 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 get Hadamard dalam prosedur ini:

• get 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.

• get Hadamard kedua membolehkan kita mempelajari sesuatu tentang nombor $\theta$ melalui fenomena interferens. Sebelum get 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 get Hadamard kedua, kita menyebabkan nombor $\theta$ mempengaruhi kebarangkalian output.

Menggandakan fasa

litar 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 litar kita dengan dua salinan operasi ini, seperti dalam litar 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 litar 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 litar 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 litar seperti ini.

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

Jika kita menjalankan litar ini apabila $\vert\psi\rangle$ adalah eigenvector bagi $U,$ keadaan qubit bawah akan kekal sebagai $\vert\psi\rangle$ sepanjang keseluruhan litar, dan fasa akan "ditendang" ke dalam keadaan dua qubit atas. Mari kita analisis litar 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.$$

get 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 litar 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 litar kuantum yang melakukan ini.

Untuk merumuskan, jika kita menjalankan litar 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.

litar 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 litar 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 litar 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 litar 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.

get fasa terkawal

Untuk mengimplementasikan transformasi Fourier kuantum dengan litar kuantum, kita perlu menggunakan get 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 get 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 get 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 get ini dalam gambar rajah litar 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 get 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 get 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 get fasa terkawal ini bolak-balik antara satu sama lain dan boleh dilaksanakan dalam sebarang urutan.

Implementasi litar bagi QFT

Sekarang kita akan melihat bagaimana kita boleh mengimplementasikan transformasi Fourier kuantum dengan litar 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 litar kuantum, adalah mudah untuk mengimplementasikan songsangannya: kita boleh menggantikan setiap get dengan songsangannya (atau, secara setara, konjugat transpose) dan menggunakan get dalam urutan terbalik. Setiap litar kuantum yang terdiri daripada get 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 get 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 litar 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 litar 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 litar 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 litar kuantum.

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

Katakan $s_m$ menandakan bilangan get 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 litar di atas kita memerlukan $s_{m-1}$ get untuk transformasi Fourier kuantum pada $m-1$ qubit, ditambah $m-1$ get fasa terkawal, ditambah satu get Hadamard, ditambah $m-1$ get 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 get swap seperti yang dihuraikan kaedah ini. Jika kita menyusun semula get sedikit, kita boleh menolak semua get swap ke kanan dan mengurangkan bilangan get swap yang diperlukan kepada $\lfloor m/2\rfloor.$ Secara asimptotik ini bukan peningkatan besar: kita masih mendapat litar bersaiz $O(m^2)$ untuk melaksanakan $\mathrm{QFT}_{2^m}.$

Jika kita ingin mengimplementasikan transformasi Fourier kuantum menggunakan hanya get daripada set get standard kita, kita perlu sama ada membina atau menganggar setiap get fasa terkawal dengan get 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 get sub-kuadratik dengan menggunakan fakta bahawa $P_{\alpha}$ sangat hampir dengan operasi identiti apabila $\alpha$ sangat kecil — yang bermakna kita boleh meninggalkan kebanyakan get 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 litar: 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 litar yang melaksanakan operasi $U^k$ bagi nilai $k$ yang besar dengan cara yang lebih cekap daripada sekadar mengulangi litar 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 litar 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 litar 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 litar, 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 litar 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.)