Prosedur estimasi fase

Selanjutnya, kita akan membahas prosedur estimasi fase, yaitu algoritma kuantum untuk menyelesaikan masalah estimasi fase.

Kita akan mulai dengan pemanasan presisi rendah, yang menjelaskan beberapa intuisi dasar di balik metode ini. Kemudian kita akan membahas transformasi Fourier kuantum, yang merupakan operasi kuantum penting yang digunakan dalam prosedur estimasi fase, beserta implementasi sirkuit kuantumnya. Setelah kita memiliki transformasi Fourier kuantum, kita akan mendeskripsikan prosedur estimasi fase secara umum dan menganalisis kinerjanya.

Pemanasan: memperkirakan fase dengan presisi rendah

Kita akan mulai dengan beberapa versi sederhana dari prosedur estimasi fase yang memberikan solusi presisi rendah untuk masalah estimasi fase. Ini berguna untuk menjelaskan intuisi di balik prosedur umum yang akan kita lihat sedikit kemudian dalam pelajaran ini.

Menggunakan phase kickback

Pendekatan sederhana untuk masalah estimasi fase, yang memungkinkan kita mempelajari sesuatu tentang nilai $\theta$ yang kita cari, didasarkan pada fenomena phase kick-back. Seperti yang akan kita lihat, ini pada dasarnya adalah versi satu-Qubit dari prosedur estimasi fase umum yang akan dibahas kemudian dalam pelajaran ini.

Sebagai bagian dari input untuk masalah estimasi fase, kita memiliki sirkuit kuantum uniter untuk operasi $U.$ Kita bisa menggunakan deskripsi sirkuit ini untuk membuat sirkuit untuk operasi controlled-$U$, yang bisa digambarkan seperti yang disarankan oleh gambar ini (dengan operasi $U,$ dilihat sebagai Gate kuantum, di sebelah kiri dan operasi controlled-$U$ di sebelah kanan).

Kita bisa membuat sirkuit kuantum untuk operasi controlled-$U$ dengan terlebih dahulu menambahkan control qubit ke sirkuit untuk $U,$ kemudian mengganti setiap Gate dalam sirkuit untuk $U$ dengan versi controlled dari Gate tersebut — sehingga satu control qubit baru kita secara efektif mengontrol setiap Gate tunggal dalam sirkuit untuk $U.$ Ini membutuhkan kita memiliki versi controlled dari setiap Gate dalam sirkuit kita, tapi kita selalu bisa membangun sirkuit untuk operasi controlled ini jika tidak termasuk dalam set Gate kita.

Sekarang perhatikan sirkuit berikut, di mana state input $\vert\psi\rangle$ dari semua qubit kecuali yang paling atas adalah vektor eigen state kuantum dari $U.$

Probabilitas hasil pengukuran untuk sirkuit ini bergantung pada nilai eigen dari $U$ yang bersesuaian dengan vektor eigen $\vert\psi\rangle.$ Mari kita analisis sirkuit secara rinci untuk menentukan tepatnya bagaimana.

State awal sirkuit adalah

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

dan Gate Hadamard pertama mentransformasi state ini menjadi

$$\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.$$

Selanjutnya, operasi controlled-$U$ dilakukan, yang menghasilkan state

$$\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 asumsi bahwa $\vert\psi\rangle$ adalah vektor eigen dari $U$ dengan nilai eigen $\lambda = e^{2\pi i\theta},$ kita bisa mengekspresikan state ini secara alternatif sebagai 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 mengamati fenomena phase kickback. Ini sedikit berbeda kali ini dibandingkan dengan algoritma Deutsch dan algoritma Deutsch-Jozsa karena kita tidak bekerja dengan query gate — tapi idenya serupa.

Akhirnya, Gate Hadamard kedua dilakukan. Setelah sedikit penyederhanaan, kita mendapatkan ekspresi ini untuk state ini.

$$\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)$$

Pengukuran oleh karena itu menghasilkan outcome $0$ dan $1$ dengan probabilitas ini:

$$\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 probabilitas untuk dua kemungkinan outcome, $0$ dan $1,$ sebagai fungsi dari $\theta.$

Secara alami, kedua probabilitas selalu berjumlah $1.$ Perhatikan bahwa ketika $\theta = 0,$ hasil pengukuran selalu $0,$ dan ketika $\theta = 1/2,$ hasil pengukuran selalu $1.$ Jadi, meskipun hasil pengukuran tidak mengungkapkan tepat apa itu $\theta,$ ia memang memberi kita beberapa informasi tentangnya — dan jika kita dijanjikan bahwa $\theta = 0$ atau $\theta = 1/2,$ kita bisa belajar dari sirkuit mana yang benar tanpa kesalahan.

Secara intuitif, kita bisa menganggap outcome pengukuran sirkuit sebagai tebakan untuk $\theta$ dengan "akurasi satu bit." Dengan kata lain, jika kita menulis $\theta$ dalam notasi biner dan membulatkannya ke satu bit, kita akan mendapatkan angka seperti ini:

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

Outcome pengukuran bisa dilihat sebagai tebakan untuk bit $a.$ Ketika $\theta$ bukan $0$ atau $1/2,$ ada probabilitas nonzero bahwa tebakannya salah — tapi probabilitas membuat kesalahan menjadi semakin kecil saat kita semakin mendekati $0$ atau $1/2.$

Wajar untuk bertanya peran apa yang dimainkan oleh dua Gate Hadamard dalam prosedur ini:

• Gate Hadamard pertama mengatur control qubit ke superposisi seragam dari $\vert 0\rangle$ dan $\vert 1\rangle,$ sehingga ketika phase kickback terjadi, itu terjadi untuk state $\vert 1\rangle$ dan bukan state $\vert 0\rangle,$ menciptakan perbedaan fase relatif yang mempengaruhi outcome pengukuran. Jika kita tidak melakukan ini dan phase kickback menghasilkan fase global, itu tidak akan berpengaruh pada probabilitas mendapatkan outcome pengukuran yang berbeda.

• Gate Hadamard kedua memungkinkan kita mempelajari sesuatu tentang angka $\theta$ melalui fenomena interferensi. Sebelum Gate Hadamard kedua, state qubit paling atas adalah

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

  dan jika kita mengukur state ini, kita akan mendapatkan $0$ dan $1$ masing-masing dengan probabilitas $1/2,$ tidak memberi tahu kita apa pun tentang $\theta.$ Namun dengan melakukan Gate Hadamard kedua, kita menyebabkan angka $\theta$ mempengaruhi probabilitas output.

Menggandakan fase

Sirkuit di atas menggunakan fenomena phase kickback untuk memperkirakan $\theta$ dengan akurasi satu bit. Satu bit akurasi mungkin sudah cukup dalam beberapa situasi — tapi untuk faktorisasi kita akan membutuhkan jauh lebih banyak akurasi dari itu. Pertanyaan wajarnya adalah, bagaimana kita bisa mempelajari lebih banyak tentang $\theta?$

Satu hal yang sangat sederhana yang bisa kita lakukan adalah mengganti operasi controlled-$U$ dalam sirkuit kita dengan dua salinan dari operasi ini, seperti dalam sirkuit ini:

Dua salinan operasi controlled-$U$ setara dengan operasi controlled-$U^2$. Jika $\vert\psi\rangle$ adalah vektor eigen dari $U$ dengan nilai eigen $\lambda = e^{2\pi i \theta},$ maka state ini juga merupakan vektor eigen dari $U^2,$ kali ini dengan nilai eigen $\lambda^2 = e^{2\pi i (2\theta)}.$

Jadi, jika kita menjalankan versi sirkuit ini, kita secara efektif melakukan komputasi yang sama seperti sebelumnya, kecuali bahwa angka $\theta$ diganti dengan $2\theta.$ Berikut adalah plot yang menggambarkan probabilitas output saat $\theta$ berkisar dari $0$ ke $1.$

Melakukan ini memang bisa memberi kita beberapa informasi tambahan tentang $\theta.$ Jika representasi biner dari $\theta$ adalah

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

maka menggandakan $\theta$ secara efektif menggeser titik biner satu posisi ke kanan:

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

Dan karena kita menyamakan $\theta = 1$ dengan $\theta = 0$ saat kita bergerak mengelilingi lingkaran satuan, kita melihat bahwa bit $a_1$ tidak berpengaruh pada probabilitas kita, dan kita secara efektif mendapatkan tebakan untuk bit kedua setelah titik biner jika kita membulatkan $\theta$ ke dua bit. Misalnya, jika kita tahu sebelumnya bahwa $\theta$ adalah $0$ atau $1/4,$ maka kita bisa sepenuhnya mempercayai outcome pengukuran untuk memberi tahu kita mana yang benar.

Namun belum jelas bagaimana estimasi ini harus didamaikan dengan apa yang kita pelajari dari sirkuit phase kickback asli (yang tidak digandakan) untuk memberi kita informasi paling akurat yang mungkin tentang $\theta.$ Jadi mari kita mundur sejenak dan mempertimbangkan cara untuk melanjutkan.

Estimasi fase dua qubit

Daripada mempertimbangkan dua opsi yang dijelaskan di atas secara terpisah, mari kita gabungkan keduanya menjadi satu sirkuit seperti ini.

Gate Hadamard setelah operasi controlled telah dihapus dan belum ada pengukuran di sini. Kita akan menambahkan lebih banyak ke sirkuit saat kita mempertimbangkan opsi kita untuk mempelajari sebanyak mungkin tentang $\theta.$

Jika kita menjalankan sirkuit ini ketika $\vert\psi\rangle$ adalah vektor eigen dari $U,$ state qubit bawah akan tetap $\vert\psi\rangle$ sepanjang seluruh sirkuit, dan fase akan "ditendang" ke state dua qubit atas. Mari kita analisis sirkuit dengan cermat, melalui gambar berikut.

Kita bisa menulis state $\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.$$

Ketika operasi controlled-$U$ pertama dilakukan, nilai eigen $\lambda = e^{2\pi i\theta}$ ditendang ke dalam fase ketika $a_0$ (qubit paling atas) sama dengan $1,$ tapi tidak ketika $0.$ Jadi, kita bisa mengekspresikan state 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 hal serupa, kecuali untuk $a_1$ daripada $a_0,$ dan dengan $\theta$ diganti dengan $2\theta.$ Kita bisa mengekspresikan state 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 string biner $a_1 a_0$ sebagai merepresentasikan bilangan bulat $x \in \{0,1,2,3\}$ dalam notasi biner, yaitu $x = 2 a_1 + a_0,$ kita bisa mengekspresikan state ini secara alternatif sebagai 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$$

Tujuan kita adalah mengekstrak informasi sebanyak mungkin tentang $\theta$ dari state ini.

Pada titik ini kita akan mempertimbangkan kasus khusus, di mana kita dijanjikan bahwa $\theta = \frac{y}{4}$ untuk beberapa bilangan bulat $y\in\{0,1,2,3\}.$ Dengan kata lain, kita memiliki $\theta\in \{0, 1/4, 1/2, 3/4\},$ sehingga kita bisa mengekspresikan angka ini secara tepat menggunakan notasi biner dengan dua bit, sebagai .$00,$ .$01,$ .$10,$ atau .$11.$ Secara umum, $\theta$ mungkin bukan salah satu dari empat nilai ini, tapi memikirkan kasus khusus ini akan membantu kita mengetahui cara paling efektif mengekstrak informasi tentang $\theta$ secara umum.

Pertama kita akan mendefinisikan vektor state dua qubit untuk setiap kemungkinan nilai $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$$

Setelah menyederhanakan eksponensial, kita bisa menuliskan vektor-vektor ini sebagai 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 ortogonal: jika kita memilih pasangan mana pun dari mereka dan menghitung produk dalamnya, kita mendapatkan $0.$ Masing-masing juga merupakan vektor satuan, sehingga $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ adalah basis ortonormal. Oleh karena itu kita tahu langsung bahwa ada pengukuran yang bisa membedakan mereka dengan sempurna — artinya, jika kita diberi salah satunya tapi tidak tahu yang mana, maka kita bisa mengetahui yang mana tanpa kesalahan.

Untuk melakukan diskriminasi seperti itu dengan sirkuit kuantum, kita pertama bisa mendefinisikan operasi uniter $V$ yang mentransformasi state basis standar menjadi empat state yang tercantum 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 menuliskan $V$ sebagai matriks $4\times 4,$ cukup dengan mengambil kolom-kolom $V$ sebagai state $\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 istimewa, dan kemungkinan besar beberapa pembaca pernah menemuinya sebelumnya: ini adalah matriks yang berkaitan dengan transformasi Fourier diskret berdimensi $4$. Mengingat fakta ini, mari kita sebut dengan nama $\mathrm{QFT}_4$ daripada $V.$ Nama $\mathrm{QFT}$ adalah singkatan dari quantum Fourier transform — yang pada dasarnya hanyalah transformasi Fourier diskret, dipandang sebagai operasi uniter. Kita akan membahas transformasi Fourier kuantum secara lebih rinci dan umum sebentar 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 bisa melakukan invers dari operasi ini untuk pergi ke arah lain, untuk mentransformasi state $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ menjadi state basis standar $\vert 0\rangle,\ldots,\vert 3\rangle.$ Jika kita melakukan ini, maka kita bisa mengukur untuk mengetahui nilai $y\in\{0,1,2,3\}$ mana yang mendeskripsikan $\theta$ sebagai $\theta = y/4.$ Berikut adalah diagram sirkuit kuantum yang melakukan ini.

Singkatnya, jika kita menjalankan sirkuit ini ketika $\theta = y/4$ untuk $y\in\{0,1,2,3\},$ state tepat sebelum pengukuran berlangsung akan menjadi $\vert \psi\rangle \vert y\rangle$ (untuk $y$ yang dikodekan sebagai string biner dua bit), sehingga pengukuran akan mengungkapkan nilai $y$ tanpa kesalahan.

Sirkuit ini dimotivasi oleh kasus khusus bahwa $\theta \in \{0,1/4,1/2,3/4\}$ — tapi kita bisa menjalankannya untuk pilihan $U$ dan $\vert \psi\rangle$ apa pun, dan karenanya nilai $\theta$ apa pun, yang kita inginkan. Berikut adalah plot probabilitas output yang dihasilkan sirkuit untuk pilihan $\theta$ yang sewenang-wenang.

Ini adalah peningkatan yang jelas dibandingkan varian satu qubit yang dijelaskan sebelumnya dalam pelajaran ini. Ini tidak sempurna — bisa memberi kita jawaban yang salah — tapi jawabannya sangat condong ke nilai-nilai $y$ di mana $y/4$ mendekati $\theta.$ Khususnya, outcome paling mungkin selalu sesuai dengan nilai $y/4$ yang paling dekat dengan $\theta$ (menyamakan $\theta = 0$ dan $\theta = 1$ seperti sebelumnya), dan dari plot terlihat bahwa nilai $x$ terdekat ini selalu muncul dengan probabilitas tepat di atas $40\%.$ Ketika $\theta$ tepat di tengah antara dua nilai tersebut, seperti $\theta = 0.375$ misalnya, dua nilai $y$ yang sama-sama dekat memiliki kemungkinan yang sama.

Bersiap untuk menggeneralisasi ke banyak qubit

Mengingat peningkatan yang baru saja kita peroleh dengan menggunakan dua control qubit daripada satu, bersamaan dengan invers dari transformasi Fourier kuantum berdimensi $4,$ wajar untuk mempertimbangkan menggeneralisasikannya lebih jauh — dengan menambahkan lebih banyak control qubit. Saat kita melakukan ini, kita mendapatkan prosedur estimasi fase umum. Kita akan melihat bagaimana ini bekerja sebentar lagi, tapi untuk mendeskripsikannya dengan tepat kita perlu membahas transformasi Fourier kuantum secara lebih umum, untuk melihat bagaimana ia didefinisikan untuk dimensi lain dan untuk melihat bagaimana kita bisa mengimplementasikannya (atau inversnya) dengan sirkuit kuantum.

Transformasi Fourier kuantum

Transformasi Fourier kuantum adalah operasi uniter yang bisa didefinisikan untuk sembarang dimensi bilangan bulat positif $N.$ Di bagian ini, kita akan melihat bagaimana operasi ini didefinisikan dan bagaimana operasi ini bisa diimplementasikan dengan Circuit kuantum pada $m$ qubit dengan biaya $O(m^2)$ ketika $N = 2^m.$

Matriks yang menggambarkan transformasi Fourier kuantum diturunkan dari operasi analog pada vektor $N$-dimensi yang dikenal sebagai transformasi Fourier diskrit. Operasi ini bisa dipahami dengan berbagai cara. Misalnya, kita bisa memikirkan transformasi Fourier diskrit dalam istilah matematis abstrak murni sebagai pemetaan linear. Atau kita bisa memikirkannya dalam istilah komputasi, di mana kita diberikan vektor $N$-dimensi berisi bilangan kompleks (menggunakan notasi biner untuk mengkodekan bagian riil dan imajiner dari entri, misalkan) dan tujuannya adalah menghitung vektor $N$-dimensi yang diperoleh dengan menerapkan transformasi Fourier diskrit. Fokus kita adalah pada cara ketiga, yaitu melihat transformasi ini sebagai operasi uniter yang bisa dilakukan pada sistem kuantum.

Ada algoritma efisien untuk menghitung transformasi Fourier diskrit pada vektor input tertentu yang dikenal sebagai transformasi Fourier cepat. Algoritma ini memiliki aplikasi dalam pemrosesan sinyal dan banyak area lainnya, dan dianggap oleh banyak orang sebagai salah satu algoritma terpenting yang pernah ditemukan. Ternyata, implementasi transformasi Fourier kuantum ketika $N$ adalah pangkat 2 yang akan kita pelajari didasarkan pada struktur dasar yang sama yang membuat transformasi Fourier cepat itu mungkin.

Definisi transformasi Fourier kuantum

Untuk mendefinisikan transformasi Fourier kuantum, pertama-tama kita akan mendefinisikan bilangan kompleks $\omega_N,$ untuk setiap bilangan bulat 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 bilangan pada lingkaran satuan kompleks yang kita peroleh jika kita mulai dari $1$ dan bergerak berlawanan arah jarum jam sebesar sudut $2\pi/N$ radian, atau sepersekian $1/N$ dari keliling lingkaran. Berikut 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 bisa mendefinisikan transformasi Fourier kuantum $N$-dimensi, yang digambarkan oleh matriks $N\times N$ yang baris dan kolomnya dikaitkan dengan state basis standar $\vert 0\rangle,\ldots,\vert N-1\rangle.$ Kita hanya akan membutuhkan operasi ini ketika $N = 2^m$ adalah pangkat $2$ untuk estimasi fase, tetapi operasi ini bisa didefinisikan untuk sembarang bilangan bulat 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 sudah dinyatakan, ini adalah matriks yang terkait dengan transformasi Fourier diskrit $N$-dimensi. Seringkali faktor depan $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 $N$ yang kecil.

$$\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, bahwa $\mathrm{QFT}_2$ adalah nama lain untuk operasi Hadamard.

Keunitaran

Mari kita verifikasi bahwa $\mathrm{QFT}_N$ adalah uniter, untuk sembarang pilihan $N.$ Salah satu cara melakukannya adalah dengan menunjukkan bahwa kolom-kolomnya membentuk basis ortonormal. Kita bisa mendefinisikan vektor yang sesuai dengan kolom nomor $y,$ mulai 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 kali dalam antara dua vektor ini memberikan ekspresi berikut:

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

Kita bisa mengevaluasi penjumlahan seperti ini menggunakan rumus berikut untuk jumlah $N$ suku pertama deret 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}$$

Secara spesifik, kita bisa menggunakan rumus ini ketika $\alpha = \omega_N^{y-z}.$ Ketika $y = z,$ kita punya $\alpha = 1,$ sehingga menggunakan rumus dan membagi dengan $N$ menghasilkan

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

Ketika $y\neq z,$ kita punya $\alpha \neq 1,$ sehingga rumus mengungkapkan 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 terjadi karena $\omega_N^N = e^{2\pi i} = 1,$ sehingga $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ membuat pembilang nol, sementara penyebutnya tidak nol karena $\omega_N^{y-z} \neq 1.$ Secara intuitif, apa yang kita lakukan adalah menjumlahkan sejumlah titik yang tersebar di sekeliling lingkaran satuan, dan titik-titik tersebut saling meniadakan dan menghasilkan $0$ ketika dijumlahkan.

Kita sudah menetapkan bahwa $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ adalah himpunan ortonormal,

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

yang mengungkapkan bahwa $\mathrm{QFT}_N$ adalah uniter.

Gate fase terkontrol

Untuk mengimplementasikan transformasi Fourier kuantum dengan Circuit kuantum, kita perlu menggunakan Gate fase terkontrol. Ingat bahwa operasi fase adalah operasi uniter qubit tunggal berbentuk

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

untuk sembarang bilangan riil $\alpha.$ Versi terkontrol dari Gate ini memiliki 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 terkontrol ini, sebenarnya tidak masalah qubit mana yang menjadi kontrol dan mana yang menjadi target karena dua kemungkinan itu setara. Kita bisa menggunakan simbol-simbol berikut untuk merepresentasikan Gate ini dalam diagram Circuit kuantum.

Untuk bentuk ketiga, label $\alpha$ juga terkadang ditempatkan di sisi garis kontrol atau di bawah kontrol bawah jika itu lebih mudah.

Untuk melakukan transformasi Fourier kuantum ketika $N = 2^m$ dan $m\geq 2,$ kita perlu melakukan operasi pada $m$ qubit yang aksinya pada state basis standar bisa dijelaskan sebagai

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

di mana $a$ adalah sebuah bit dan $y \in \{0,\ldots,2^{m-1} - 1\}$ adalah bilangan yang dikodekan dalam notasi biner sebagai string $m-1$ bit. Ini bisa dilakukan menggunakan Gate fase terkontrol dengan menggeneralisasi contoh berikut, di mana $m=5.$

Secara umum, untuk sembarang pilihan $m\geq 2,$ qubit paling atas yang sesuai dengan bit $a$ bisa dipandang sebagai kontrol, dengan Gate fase $P_{\alpha}$ berkisar dari $\alpha = \pi/2^{m-1}$ pada qubit yang sesuai dengan bit paling tidak signifikan dari $y$ hingga $\alpha = \frac{\pi}{2}$ pada qubit yang sesuai dengan bit paling signifikan dari $y.$ Gate fase terkontrol ini semuanya berkomutasi satu sama lain dan bisa dilakukan dalam urutan apa pun.

Implementasi Circuit dari QFT

Sekarang kita akan melihat bagaimana kita bisa mengimplementasikan transformasi Fourier kuantum dengan Circuit ketika dimensi $N = 2^m$ adalah pangkat $2.$ Sebenarnya ada beberapa cara untuk mengimplementasikan transformasi Fourier kuantum, tetapi ini adalah metode paling sederhana yang dikenal. Setelah kita tahu cara mengimplementasikan transformasi Fourier kuantum dengan Circuit kuantum, mudah untuk mengimplementasikan inversnya: kita bisa mengganti setiap Gate dengan inversnya (atau, secara setara, transposa konjugat) dan menerapkan Gate dalam urutan terbalik. Setiap sirkuit kuantum yang terdiri dari Gate uniter saja bisa diinverskan dengan cara ini.

Implementasinya bersifat rekursif, sehingga itulah cara paling alami untuk menjelaskannya. Kasus dasar adalah $m=1,$ di mana transformasi Fourier kuantum adalah operasi Hadamard.

Untuk melakukan transformasi Fourier kuantum pada $m$ qubit ketika $m \geq 2,$ kita bisa melakukan langkah-langkah berikut, yang aksinya akan kita jelaskan untuk state basis standar berbentuk $\vert x \rangle \vert a\rangle,$ di mana $x\in\{0,\ldots,2^{m-1} - 1\}$ adalah bilangan bulat yang dikodekan sebagai $m-1$ bit menggunakan notasi biner dan $a$ adalah satu bit.

1. Pertama terapkan transformasi Fourier kuantum $2^{m-1}$-dimensi ke $m-1$ qubit paling bawah/paling kiri untuk mendapatkan state 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 secara rekursif menerapkan metode yang dijelaskan untuk satu qubit lebih sedikit, menggunakan operasi Hadamard pada satu qubit sebagai kasus dasar.

2. Gunakan qubit paling atas/paling kanan sebagai kontrol untuk menyuntikkan fase $\omega_{2^m}^y$ untuk setiap state basis standar $\vert y\rangle$ dari $m-1$ qubit yang tersisa (seperti dijelaskan di atas) untuk mendapatkan state 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. Lakukan Gate Hadamard pada qubit paling atas/paling kanan untuk mendapatkan state 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 urutan qubit sehingga bit paling tidak signifikan menjadi bit paling signifikan, dengan semua qubit lainnya 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 dapatkan untuk $N = 32 = 2^5.$ Dalam diagram ini, qubit diberi nama yang sesuai dengan vektor basis standar $\vert x\rangle \vert a\rangle$ (untuk input) dan $\vert b\rangle \vert y\rangle$ (untuk output) agar lebih jelas.

Analisis

Rumus kunci yang perlu kita verifikasi bahwa Circuit yang baru saja dijelaskan 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)}.$$

Rumus ini berlaku untuk sembarang pilihan bilangan bulat $a,$ $b,$ $x,$ dan $y,$ tetapi kita hanya membutuhkannya untuk $a,b\in\{0,1\}$ dan $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Rumus ini bisa diperiksa dengan mengembangkan perkalian dalam eksponen di ruas 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 kesetaraan kedua memanfaatkan pengamatan bahwa

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

Transformasi Fourier kuantum $2^m$-dimensi didefinisikan sebagai 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 mendapatkan

$$\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 state basis standar $\vert x \rangle \vert a\rangle$ dan $\vert b \rangle \vert y \rangle$ sebagai pengkodean biner bilangan bulat dalam rentang $\{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 bahwa Circuit di atas mengimplementasikan operasi yang diperlukan. Jika metode untuk melakukan transformasi Fourier kuantum ini terlihat luar biasa, itu memang begitu: ini pada dasarnya adalah transformasi Fourier cepat dalam bentuk Circuit kuantum.

Akhirnya, mari kita hitung berapa banyak Gate yang digunakan dalam Circuit yang baru saja dijelaskan. Gate fase terkontrol tidak ada dalam set Gate standar yang kita bahas di pelajaran sebelumnya, tetapi untuk memulai kita akan mengabaikan ini dan menghitung masing-masingnya sebagai satu Gate.

Mari kita biarkan $s_m$ menunjukkan jumlah Gate yang kita butuhkan untuk setiap kemungkinan pilihan $m.$ Jika $m=1,$ transformasi Fourier kuantum hanyalah operasi Hadamard, jadi

$$s_1 = 1.$$

Jika $m\geq 2,$ maka dalam Circuit di atas kita butuh $s_{m-1}$ Gate untuk transformasi Fourier kuantum pada $m-1$ qubit, ditambah $m-1$ Gate fase terkontrol, ditambah Gate Hadamard, ditambah $m-1$ Gate swap, sehingga

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

Kita bisa mendapatkan ekspresi bentuk tertutup dengan menjumlahkan:

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

Kita sebenarnya tidak membutuhkan sebanyak Gate swap yang dijelaskan metode ini. Jika kita sedikit mengatur ulang Gate, kita bisa mendorong semua Gate swap ke kanan dan mengurangi jumlah Gate swap yang diperlukan menjadi $\lfloor m/2\rfloor.$ Secara asimtotik ini bukan peningkatan besar: kita masih mendapatkan Circuit berukuran $O(m^2)$ untuk melakukan $\mathrm{QFT}_{2^m}.$

Jika kita ingin mengimplementasikan transformasi Fourier kuantum hanya menggunakan Gate dari set Gate standar kita, kita perlu membangun atau mengaproksimasi setiap Gate fase terkontrol dengan Gate dari set kita. Jumlah yang diperlukan tergantung pada seberapa banyak akurasi yang kita butuhkan, tetapi sebagai fungsi dari $m$ total biaya tetap kuadratik.

Sebenarnya mungkin untuk mengaproksimasi transformasi Fourier kuantum cukup dekat dengan jumlah Gate sub-kuadratik dengan menggunakan fakta bahwa $P_{\alpha}$ sangat dekat dengan operasi identitas ketika $\alpha$ sangat kecil — yang berarti kita bisa saja meninggalkan sebagian besar Gate fase terkontrol tanpa mengalami terlalu banyak kerugian dalam hal akurasi.

Prosedur umum dan analisis

Sekarang kita akan memeriksa prosedur estimasi fase secara umum. Idenya adalah memperluas versi dua qubit dari estimasi fase yang kita pertimbangkan di atas dengan cara alami yang disarankan oleh diagram berikut.

Perhatikan bahwa, untuk setiap qubit kontrol baru yang ditambahkan di atas, kita menggandakan jumlah kali operasi uniter $U$ dilakukan. Ini ditunjukkan dalam diagram oleh pangkat pada $U$ untuk setiap operasi uniter terkontrol.

Cara paling langsung untuk mengimplementasikan operasi controlled-$U^k$ untuk beberapa pilihan $k$ adalah cukup dengan mengulang operasi controlled-$U$ sebanyak $k$ kali. Jika memang metodologi inilah yang digunakan, harus diakui bahwa penambahan qubit kontrol berkontribusi signifikan terhadap ukuran Circuit: jika kita memiliki $m$ qubit kontrol, seperti yang digambarkan diagram, total $2^m - 1$ salinan operasi controlled-$U$ diperlukan. Ini berarti biaya komputasi yang signifikan dikeluarkan seiring bertambahnya $m$ — tetapi seperti yang akan kita lihat, ini juga menghasilkan aproksimasi $\theta$ yang jauh lebih akurat.

Penting untuk dicatat, bagaimanapun, bahwa untuk beberapa pilihan $U$ mungkin saja membuat Circuit yang mengimplementasikan operasi $U^k$ untuk nilai $k$ yang besar dengan cara yang lebih efisien daripada sekadar mengulang $k$ kali Circuit untuk $U.$ Kita akan melihat contoh spesifik dari ini dalam konteks faktorisasi bilangan bulat nanti dalam pelajaran ini, di mana algoritma efisien untuk eksponensiasi modular yang dibahas dalam pelajaran sebelumnya datang menyelamatkan.

Sekarang mari kita analisis Circuit yang baru saja dijelaskan. State segera sebelum transformasi Fourier kuantum invers terlihat 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.$$

Kasus khusus

Sejalan dengan apa yang kita lakukan dalam kasus $m=2,$ pertama-tama kita akan mempertimbangkan kasus khusus bahwa $\theta = y/2^m$ untuk $y\in\{0,\ldots,2^m-1\}.$ Dalam kasus ini state sebelum transformasi Fourier kuantum invers bisa ditulis secara alternatif 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, ketika transformasi Fourier kuantum invers diterapkan, state menjadi

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

dan pengukuran mengungkapkan $y$ (dikodekan dalam biner).

Membatasi probabilitas

Untuk nilai $\theta$ lainnya, yaitu yang tidak berbentuk $y/2^m$ untuk bilangan bulat $y,$ hasil pengukuran tidak akan pasti, tetapi kita bisa membuktikan batas pada probabilitas untuk hasil yang berbeda. Ke depannya, mari kita pertimbangkan sembarang pilihan $\theta$ yang memenuhi $0\leq \theta < 1.$

Setelah transformasi Fourier kuantum invers dilakukan, state Circuit adalah ini:

$$\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, ketika pengukuran pada $m$ qubit teratas dilakukan, kita melihat setiap hasil $y$ dengan probabilitas

$$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 lebih memahami probabilitas-probabilitas ini, kita akan menggunakan rumus yang sama yang kita lihat sebelumnya, untuk jumlah bagian awal deret 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 bisa menyederhanakan penjumlahan yang muncul dalam rumus untuk $p_y$ dengan mengambil $\alpha = e^{2\pi i (\theta - y/2^m)}.$ Berikut yang kita dapatkan.

$$\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 kasus bahwa $\theta = y/2^m,$ kita menemukan bahwa $p_y = 1$ (seperti yang sudah kita ketahui dari mempertimbangkan kasus khusus ini), dan dalam kasus bahwa $\theta \neq y/2^m,$ kita menemukan bahwa

$$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 bisa mempelajari lebih banyak tentang probabilitas-probabilitas ini dengan memikirkan bagaimana panjang busur dan panjang tali busur pada lingkaran satuan saling berhubungan. Berikut adalah gambar yang mengilustrasikan hubungan yang kita butuhkan untuk sembarang bilangan riil $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr].$

Pertama, panjang tali busur (digambar biru) tidak mungkin lebih besar dari panjang busur (digambar ungu):

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

Menghubungkan panjang-panjang ini dari arah lain, kita melihat bahwa rasio panjang busur terhadap panjang tali busur paling besar ketika $\delta = \pm 1/2,$ dan dalam kasus ini rasionya adalah setengah keliling lingkaran dibagi diameter, yaitu $\pi/2.$ Dengan demikian, kita punya

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

dan sehingga

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

Analisis berdasarkan hubungan-hubungan ini mengungkapkan dua fakta berikut.

1. Misalkan $\theta$ adalah bilangan riil dan $y\in \{0,\ldots,2^m-1\}$ memenuhi

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

   Ini berarti bahwa $y/2^m$ adalah aproksimasi $m$-bit terbaik untuk $\theta,$ atau tepat berada di tengah antara $y/2^m$ dan $(y-1)/2^m$ atau $(y+1)/2^m,$ sehingga itu adalah salah satu dari dua aproksimasi terbaik untuk $\theta.$

   Kita akan membuktikan bahwa $p_y$ haruslah cukup besar dalam kasus ini. Berdasarkan asumsi yang kita pertimbangkan, berikut bahwa $\vert 2^m \theta - y \vert \leq 1/2,$ sehingga kita bisa menggunakan pengamatan kedua di atas yang menghubungkan panjang busur dan tali busur untuk menyimpulkan bahwa

   $$\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 bisa menggunakan pengamatan pertama tentang panjang busur dan tali busur untuk menyimpulkan bahwa

   $$\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.$$

   Memanfaatkan kedua ketidaksetaraan ini pada $p_y$ mengungkapkan

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

   Ini menjelaskan pengamatan kita bahwa hasil terbaik terjadi dengan probabilitas lebih dari $40\%$ dalam versi $m=2$ estimasi fase yang dibahas sebelumnya. Ini sebenarnya bukan 40%, melainkan $4/\pi^2,$ dan bahkan batas ini berlaku untuk setiap pilihan $m.$

2. Sekarang misalkan $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 berarti ada aproksimasi yang lebih baik $z/2^m$ untuk $\theta$ di antara $\theta$ dan $y/2^m.$

   Kali ini kita akan membuktikan bahwa $p_y$ tidak terlalu besar. Kita bisa mulai dengan pengamatan sederhana bahwa

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

   yang mengikuti dari fakta bahwa dua titik mana pun pada lingkaran satuan bisa berbeda dalam nilai absolut sebanyak-banyaknya $2.$

   Kita juga bisa menggunakan pengamatan kedua tentang panjang busur dan tali busur dari atas, kali ini bekerja dengan penyebut $p_y$ daripada pembilangnya, 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 ketidaksetaraan mengungkapkan

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

   Perhatikan bahwa, meskipun batas ini cukup baik untuk tujuan kita, ini cukup kasar — probabilitasnya biasanya jauh lebih rendah dari $1/4.$

Kesimpulan penting dari analisis ini adalah bahwa aproksimasi yang sangat dekat dengan $\theta$ kemungkinan besar akan terjadi — kita akan mendapatkan aproksimasi $m$-bit terbaik dengan probabilitas lebih dari $40\%$ — sedangkan aproksimasi yang meleset lebih dari $2^{-m}$ lebih kecil kemungkinannya terjadi, dengan probabilitas yang dibatasi di atas oleh $25\%.$

Mengingat jaminan-jaminan ini, mungkin untuk meningkatkan kepercayaan kita dengan mengulangi prosedur estimasi fase beberapa kali, untuk mengumpulkan bukti statistik tentang $\theta.$ Penting untuk dicatat bahwa state $\vert\psi\rangle$ dari kumpulan qubit bawah tidak berubah oleh prosedur estimasi fase, sehingga bisa digunakan untuk menjalankan prosedur sebanyak yang kita inginkan. Khususnya, setiap kali kita menjalankan Circuit, kita mendapatkan aproksimasi $m$-bit terbaik untuk $\theta$ dengan probabilitas lebih dari $40\%,$ sementara probabilitas untuk meleset lebih dari $2^{-m}$ dibatasi oleh $25\%.$ Jika kita menjalankan Circuit beberapa kali dan mengambil hasil yang paling sering muncul, oleh karena itu sangat mungkin bahwa hasil yang paling sering muncul tidak akan menjadi salah satu yang terjadi paling banyak $25\%$ dari waktu. Hasilnya, kita akan sangat mungkin mendapatkan aproksimasi $y/2^m$ yang dalam jarak $1/2^m$ dari nilai $\theta.$ Memang, kemungkinan kecil bahwa kita meleset lebih dari $1/2^m$ berkurang secara eksponensial seiring bertambahnya jumlah kali prosedur dijalankan.

Berikut adalah dua plot yang menunjukkan probabilitas untuk tiga nilai berturut-turut untuk $y$ ketika $m = 3$ dan $m=4$ sebagai fungsi dari $\theta.$ (Hanya tiga hasil yang ditampilkan untuk kejelasan. Probabilitas untuk hasil lainnya diperoleh dengan menggeser secara siklik fungsi dasar yang sama.)