Algoritme kuantum untuk sistem persamaan linear (HHL09): Langkah 1 - Kebingungan mengenai penggunaan algoritma estimasi fase

Saya telah mencoba untuk mendapatkan kepala saya di sekitar kertas algoritma Quantum terkenal (?) Untuk sistem linear persamaan (Harrow, Hassidim & Lloyd, 2009) (lebih dikenal sebagai kertas algoritma HHL09 ) untuk beberapa waktu, sekarang.

Pada halaman pertama, mereka berkata :

Kami membuat sketsa di sini ide dasar dari algoritma kami dan kemudian membahasnya secara lebih rinci di bagian selanjutnya. Diberikan Hermitian matriks A , dan vektor satuan → b , misalkan kita ingin menemukan → x memuaskan A → x = → b . (Kami membahas pertanyaan efisiensi kemudian serta bagaimana asumsi yang telah kami buat tentang A dan → b dapat dilonggarkan.) Pertama, algoritma ini merepresentasikan → b sebagai keadaan kuantum | b ⟩ = Σ N $N\times N$$A$$\vec{b}$$\vec{x}$$A\vec{x} = \vec{b}$$A$$\vec{b}$$\vec{b}$. Selanjutnya, kami menggunakan teknik simulasi Hamiltonian [3, 4] untuk menerapkan eiAtto| bi⟩untuk superposisi yang berbeda kalit. Kemampuan untuk membuat eksponensialA iniditerjemahkan, melalui teknik estimasi fase yang terkenal [5-7] ke dalam kemampuan untuk membusuk| b⟩ di eigenbasis dariAdan untuk menemukan yang sesuai nilai eigen λjSecara informal, keadaan sistem setelah tahap ini dekatΣ j $|b\rangle = \sum_{i=1}^{N}b_i|i\rangle$$e^{iAt}$$|b_i\rangle$$t$$A$$|b\rangle$$A$$\lambda_j$, di manaujadalah dasar vektor eigen dari Adan| b⟩=Σ j = N j = 1 βj| uj⟩.$\sum_{j=1}^{j=N} \beta_j |u_j\rangle|\lambda_j\rangle$$u_j$$A$$|b\rangle = \sum_{j=1}^{j=N} \beta_j|u_j\rangle$

Sejauh ini bagus. Sebagaimana dijelaskan dalam Nielsen & Chuang dalam bab " Transformasi kuantum Fourier dan aplikasinya ", algoritma estimasi fase digunakan untuk memperkirakan in e i 2 π φ yang merupakan nilai eigen yang sesuai dengan vektor eigen | u ⟩ dari operator kesatuan U .$\varphi$$e^{i2\pi \varphi}$$|u\rangle$$U$

Inilah bagian yang relevan dari Nielsen & Chuang:

Algoritma estimasi fase menggunakan dua register. Register pertama berisi qubit awalnya di negara | 0 ⟩ . Bagaimana kita memilih t tergantung pada dua hal: jumlah digit akurasi yang ingin kita miliki dalam estimasi untuk φ , dan dengan probabilitas apa kita ingin prosedur estimasi fase berhasil. Ketergantungan t pada jumlah ini muncul secara alami dari analisis berikut.$t$$|0\rangle$$t$$\varphi$$t$

Register kedua dimulai di negara dan berisi sebanyak qubit seperti yang diperlukan untuk menyimpan | u ⟩ . Estimasi fase dilakukan dalam dua tahap. Pertama, kami menerapkan sirkuit yang ditunjukkan pada Gambar 5.2. Sirkuit dimulai dengan menerapkan transformasi Hadamard ke register pertama, diikuti oleh aplikasi operasi- U yang terkontrol pada register kedua, dengan U dinaikkan menjadi kekuatan dua berturut-turut. Keadaan akhir dari register pertama dengan mudah terlihat:$|u\rangle$$|u\rangle$$U$$U$

$$\frac{1}{2^{t/2}}\left(|0\rangle+\text{exp}(2\pi i 2^{t-1}\varphi)|1\rangle)(|0\rangle+\text{exp}(2\pi i 2^{t-2}\varphi)|1\rangle)...(|0\rangle+\text{exp}(2\pi i 2^{0}\varphi)|1\rangle\right)= \frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}\text{exp}(2\pi i \varphi k)|k\rangle$$

Tahap kedua estimasi fase adalah untuk menerapkan transformasi Fourier invers kuantum pada register pertama. Ini diperoleh dengan membalikkan sirkuit untuk transformasi quantum Fourier pada bagian sebelumnya (Latihan 5.5) dan dapat dilakukan dalam langkah . Tahap ketiga dan terakhir dari estimasi fase adalah membaca keadaan register pertama dengan melakukan pengukuran dalam dasar komputasi. Kami akan menunjukkan bahwa ini memberikan perkiraan φ yang cukup baik . Skema algoritma secara keseluruhan ditunjukkan pada Gambar 5.3.$\Theta (t^2)$$\varphi$

Untuk mempertajam intuisi kita mengapa estimasi fase bekerja, anggap dapat dinyatakan dengan tepat int bit, karena φ = 0. φ 1 . . . φ t . Kemudian negara (5.20) yang dihasilkan dari tahap pertama estimasi fase dapat ditulis ulang$\varphi$$\varphi = 0.\varphi_1 ... \varphi_t$

$$\frac{1}{2^{t/2}}(|0\rangle + \exp(2\pi i 0.\varphi_t|1\rangle)(|0\rangle + \exp(2\pi i 0.\varphi_{t-1}\varphi_t|1\rangle)...(|0\rangle + \exp(2\pi i 0.\varphi_1...\varphi_t|1\rangle)$$

Tahap kedua dari estimasi fase adalah untuk menerapkan transformasi Fourier kuantum terbalik. Tetapi membandingkan persamaan sebelumnya dengan bentuk produk untuk transformasi Fourier, Persamaan (5.4), kita melihat bahwa keadaan keluaran dari tahap kedua adalah keadaan produk . Pengukuran dalam basis komputasi, oleh karena itu, memberi kita φ tepat!$|\varphi_1 ...\varphi_t\rangle$$\varphi$

$\varphi$$U$$|u\rangle$

$$\frac{1}{2^{t/2}}\sum_{j = 0}^{2^t-1}\exp(2\pi i \varphi j)|j\rangle |u\rangle \to |\tilde \varphi \rangle |u\rangle$$

^$\dagger$

Langkah 1 (Estimasi Fase):

$A$$A$$e^{iAt}$$A$

$U=e^{iAt}$$|u_j\rangle$$U$$N\times N$$N$$A$$\lambda_j$$e^{iAt}$$e^{i \lambda_j t}$$U$$e^{2\pi i \varphi} \equiv e^{ i \lambda_j t}$$\varphi = \frac{\lambda_j t}{2\pi}$$|b\rangle$$U$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$|u_j\rangle$$U$$|u\rangle \otimes (|0\rangle)^{\otimes t}$$|u\rangle \otimes |\tilde\varphi\rangle$$|u_j\rangle \otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$$\lambda_j$$|u_j\rangle$$A$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

Pertanyaan:

$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde\lambda_j\rangle$$\sum_{j=1}^{j=N}\beta_j|u_j\rangle\otimes |\tilde{\frac{\lambda_j t}{2\pi}}\rangle$

$\frac{t}{2\pi}$

Sunting: Bagian 2 telah diminta di sini untuk membuat pertanyaan individual lebih fokus.

^{Saya juga memiliki beberapa kebingungan mengenai Langkah 2 dan Langkah 3 dari algoritma HHL09 juga, tetapi saya memutuskan untuk mempostingnya sebagai utas pertanyaan terpisah, karena yang ini menjadi terlalu panjang. Saya akan menambahkan tautan ke utas pertanyaan itu, pada postingan ini, setelah dibuat.}

$\dagger$

Tergantung pada makalahnya tapi saya melihat 2 pendekatan:

1. $t$$t = t_0 = 2\pi$

2. $\tilde \lambda$$\lambda$$\frac{t}{2\pi}$$\tilde \lambda$$\frac{\lambda t}{2\pi}$

Berikut ini beberapa tautan:

1. $t$$2\pi$

2. $t$$t_0$$2\pi$

3. $t = 2\pi$

4. $t_0 = 2\pi$

$\frac{t}{2\pi}$

$U$$e^{-i\lambda t}$$\lambda t/(2\pi)$$A$$\lambda$

$U$$e^{-i\lambda t}$$A$$\lambda\rangle$

$|\tilde\lambda\rangle$