Masalah estimasi fase

Bagian pelajaran ini menjelaskan masalah estimasi fase. Kita akan mulai dengan diskusi singkat tentang teorema spektral dari aljabar linear, kemudian beralih ke pernyataan masalah estimasi fase itu sendiri.

Teorema spektral

Teorema spektral adalah fakta penting dari aljabar linear yang menyatakan bahwa matriks dari jenis tertentu, yang disebut matriks normal, dapat dinyatakan dengan cara yang sederhana dan berguna. Kita hanya akan membutuhkan teorema ini untuk matriks uniter dalam pelajaran ini, tetapi di masa mendatang dalam seri ini kita akan menerapkannya pada matriks Hermitian juga.

Matriks normal

Matriks persegi $M$ dengan entri bilangan kompleks dikatakan sebagai matriks normal jika ia komut dengan transpos konjugatnya: $M M^{\dagger} = M^{\dagger} M.$

Setiap matriks uniter $U$ adalah normal karena

$$U U^{\dagger} = \mathbb{I} = U^{\dagger} U.$$

Matriks Hermitian, yang merupakan matriks yang sama dengan transpos konjugatnya sendiri, adalah kelas penting lain dari matriks normal. Jika $H$ adalah matriks Hermitian, maka

$$H H^{\dagger} = H^2 = H^{\dagger} H,$$

sehingga $H$ adalah normal.

Tidak setiap matriks persegi adalah normal. Misalnya, matriks ini tidak normal:

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$

(Ini adalah contoh matriks yang sederhana namun luar biasa dan sering sangat berguna untuk dipertimbangkan.) Ini tidak normal karena

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$

sementara

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}.$$

Pernyataan teorema

Berikut adalah pernyataan teorema spektral.

Teorema

Teorema spektral: Misalkan $M$ adalah matriks kompleks $N\times N$ yang normal. Terdapat basis ortonormal dari vektor kompleks $N$-dimensi $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ bersama bilangan kompleks $\lambda_1,\ldots,\lambda_N$ sedemikian sehingga

$$M = \lambda_1 \vert \psi_1\rangle\langle \psi_1\vert + \cdots + \lambda_N \vert \psi_N\rangle\langle \psi_N\vert.$$

Ekspresi matriks dalam bentuk

$$M = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert \tag{1}$$

umumnya disebut sebagai dekomposisi spektral. Perhatikan bahwa jika $M$ adalah matriks normal yang dinyatakan dalam bentuk $(1),$ maka persamaan

$$M \vert \psi_j \rangle = \lambda_j \vert \psi_j \rangle$$

harus benar untuk setiap $j = 1,\ldots,N.$ Ini adalah konsekuensi dari fakta bahwa $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ adalah ortonormal:

$$M \vert \psi_j \rangle = \left(\sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\right)\vert \psi_j\rangle = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\psi_j \rangle = \lambda_j \vert\psi_j \rangle$$

Artinya, setiap bilangan $\lambda_j$ adalah eigenvalue dari $M$ dan $\vert\psi_j\rangle$ adalah eigenvector yang bersesuaian dengan eigenvalue tersebut.

• Contoh 1. Misalkan

  $$\mathbb{I} = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix},$$

  yang bersifat normal. Teorema menyiratkan bahwa $\mathbb{I}$ dapat ditulis dalam bentuk $(1)$ untuk beberapa pilihan $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ dan $\vert\psi_2\rangle.$ Ada beberapa pilihan yang berhasil, termasuk

  $$\lambda_1 = 1, \hspace{5pt} \lambda_2 = 1, \hspace{5pt} \vert\psi_1\rangle = \vert 0\rangle, \hspace{5pt} \vert\psi_2\rangle = \vert 1\rangle.$$

  Perhatikan bahwa teorema tidak mengatakan bahwa bilangan kompleks $\lambda_1,\ldots,\lambda_N$ berbeda — kita bisa memiliki bilangan kompleks yang sama berulang, yang diperlukan untuk contoh ini. Pilihan ini berhasil karena

  $$\mathbb{I} = \vert 0\rangle\langle 0\vert + \vert 1\rangle\langle 1\vert.$$

  Memang, kita bisa memilih $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ sebagai basis ortonormal manapun dan persamaan akan benar. Misalnya,

  $$\mathbb{I} = \vert +\rangle\langle +\vert + \vert -\rangle\langle -\vert.$$

• Contoh 2. Pertimbangkan operasi Hadamard.

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

  Ini adalah matriks uniter, sehingga bersifat normal. Teorema spektral menyiratkan bahwa $H$ dapat ditulis dalam bentuk $(1),$ dan khususnya kita memiliki

  $$H = \vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert$$

  di mana

  $$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle.$$

  Lebih eksplisit,

  $$\begin{aligned} \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle, \\[3mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle. \end{aligned}$$

  Kita bisa memeriksa bahwa dekomposisi ini benar dengan melakukan perhitungan yang diperlukan:

  $$\vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert = \begin{pmatrix} \frac{2 + \sqrt{2}}{4} & \frac{\sqrt{2}}{4}\\[2mm] \frac{\sqrt{2}}{4} & \frac{2 - \sqrt{2}}{4} \end{pmatrix} - \begin{pmatrix} \frac{2 - \sqrt{2}}{4} & -\frac{\sqrt{2}}{4}\\[2mm] -\frac{\sqrt{2}}{4} & \frac{2 + \sqrt{2}}{4} \end{pmatrix} = H.$$

Seperti yang diungkapkan contoh pertama di atas, bisa ada beberapa kebebasan dalam bagaimana eigenvector dipilih. Namun, tidak ada kebebasan sama sekali dalam bagaimana eigenvalue dipilih, kecuali untuk urutannya: bilangan kompleks $\lambda_1,\ldots,\lambda_N$ yang sama, yang dapat mencakup pengulangan bilangan kompleks yang sama, akan selalu muncul dalam persamaan $(1)$ untuk pilihan matriks $M$ tertentu.

Sekarang mari kita fokus pada matriks uniter. Misalkan kita memiliki bilangan kompleks $\lambda$ dan vektor non-nol $\vert\psi\rangle$ yang memenuhi persamaan

$$U\vert\psi\rangle = \lambda\vert\psi\rangle. \tag{2}$$

Artinya, $\lambda$ adalah eigenvalue dari $U$ dan $\vert\psi\rangle$ adalah eigenvector yang bersesuaian dengan eigenvalue ini.

Matriks uniter mempertahankan norma Euclidean, sehingga kita menyimpulkan hal berikut dari $(2).$

$$\bigl\| \vert\psi\rangle \bigr\| = \bigl\| U \vert\psi\rangle \bigr\| = \bigl\| \lambda \vert\psi\rangle \bigr\| = \vert \lambda \vert \bigl\| \vert\psi\rangle \bigr\|$$

Kondisi bahwa $\vert\psi\rangle$ adalah non-nol menyiratkan bahwa $\bigl\| \vert\psi\rangle \bigr\|\neq 0,$ sehingga kita bisa membatalkannya dari kedua sisi untuk mendapatkan

$$\vert \lambda \vert = 1.$$

Ini mengungkapkan bahwa eigenvalue dari matriks uniter harus selalu memiliki nilai absolut sama dengan satu, sehingga mereka berada pada lingkaran satuan.

$$\mathbb{T} = \{\alpha\in\mathbb{C} : \vert\alpha\vert = 1\}$$

(Simbol $\mathbb{T}$ adalah nama umum untuk lingkaran satuan kompleks. Nama $S^1$ juga umum.)

Pernyataan masalah estimasi fase

Dalam masalah estimasi fase, kita diberikan keadaan kuantum $\vert \psi\rangle$ dari $n$ qubit, bersama sirkuit kuantum uniter yang bertindak pada $n$ qubit. Kita dijanjikan bahwa $\vert \psi\rangle$ adalah eigenvector dari matriks uniter $U$ yang mendeskripsikan aksi sirkuit, dan tujuan kita adalah menghitung atau mendekati eigenvalue $\lambda$ yang bersesuaian dengan $\vert \psi\rangle.$ Lebih tepatnya, karena $\lambda$ berada pada lingkaran satuan kompleks, kita dapat menulis

$$\lambda = e^{2\pi i \theta}$$

untuk bilangan real unik $\theta$ yang memenuhi $0\leq\theta<1.$ Tujuan masalah adalah menghitung atau mendekati bilangan real $\theta$ ini.

Masalah estimasi fase

Input: Sirkuit kuantum uniter untuk operasi $U$ $n$-qubit bersama keadaan kuantum $n$-qubit $\vert\psi\rangle$
Janji: $\vert\psi\rangle$ adalah eigenvector dari $U$
Output: aproksimasi untuk bilangan $\theta\in[0,1)$ yang memenuhi $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Berikut adalah beberapa catatan tentang pernyataan masalah ini:

1. Masalah estimasi fase berbeda dari masalah lain yang sudah kita lihat sejauh ini dalam kursus karena inputnya mencakup keadaan kuantum. Biasanya kita fokus pada masalah yang memiliki input dan output klasik, tetapi tidak ada yang mencegah kita mempertimbangkan input keadaan kuantum seperti ini. Dalam hal relevansi praktisnya, masalah estimasi fase biasanya ditemui sebagai submasalah di dalam komputasi yang lebih besar, seperti yang akan kita lihat dalam konteks faktorisasi bilangan bulat nanti dalam pelajaran.

2. Pernyataan masalah estimasi fase di atas tidak spesifik tentang apa yang merupakan aproksimasi dari $\theta,$ tetapi kita dapat merumuskan pernyataan masalah yang lebih tepat tergantung pada kebutuhan dan minat kita. Dalam konteks faktorisasi bilangan bulat, kita akan menuntut aproksimasi yang sangat tepat untuk $\theta,$ tetapi dalam kasus lain kita mungkin puas dengan aproksimasi yang sangat kasar. Kita akan membahas segera bagaimana presisi yang kita butuhkan mempengaruhi biaya komputasi dari solusi.

3. Perhatikan bahwa saat kita bergerak dari $\theta = 0$ menuju $\theta = 1$ dalam masalah estimasi fase, kita mengelilingi seluruh lingkaran satuan, mulai dari $e^{2\pi i \cdot 0} = 1$ dan bergerak berlawanan arah jarum jam menuju $e^{2\pi i \cdot 1} = 1.$ Artinya, ketika kita mencapai $\theta = 1$ kita kembali ke tempat mulai di $\theta = 0.$ Jadi, saat kita mempertimbangkan akurasi aproksimasi, pilihan $\theta$ yang mendekati $1$ harus dianggap sebagai dekat dengan $0.$ Misalnya, aproksimasi $\theta = 0.999$ harus dianggap berada dalam $1/1000$ dari $\theta = 0.$