Masalah anggaran fasa

Bahagian pelajaran ini menerangkan masalah anggaran fasa. Kita akan mulakan dengan perbincangan ringkas tentang teorem spektral daripada aljabar linear, kemudian beralih kepada pernyataan masalah anggaran fasa itu sendiri.

Teorem spektral

Teorem spektral adalah fakta penting daripada aljabar linear yang menyatakan bahawa matriks jenis tertentu, yang dipanggil matriks normal, boleh dinyatakan dengan cara yang mudah dan berguna. Kita hanya memerlukan teorem ini untuk matriks unitari dalam pelajaran ini, tetapi kemudian dalam siri ini kita akan menggunakannya untuk matriks Hermitian juga.

Matriks normal

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

Setiap matriks unitari $U$ adalah normal kerana

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

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

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

jadi $H$ adalah normal.

Tidak setiap matriks persegi adalah normal. Sebagai contoh, matriks ini bukan normal:

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

(Ini adalah contoh mudah tetapi hebat tentang matriks yang sering sangat berguna untuk dipertimbangkan.) Ia bukan normal kerana

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

manakala

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

Berikut adalah pernyataan teorem spektral.

Teorem

Teorem spektral: Biarkan $M$ adalah matriks kompleks normal $N\times N$. Terdapat asas ortonormal bagi vektor kompleks $N$-dimensi $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ bersama-sama dengan nombor kompleks $\lambda_1,\ldots,\lambda_N$ sedemikian rupa sehingga

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

Ungkapan sebuah matriks dalam bentuk

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

biasanya dipanggil penguraian spektral. Perhatikan bahawa jika $M$ adalah matriks normal yang dinyatakan dalam bentuk $(1)$, maka persamaan

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

mestilah benar untuk setiap $j = 1,\ldots,N$. Ini adalah akibat daripada fakta bahawa $\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$$

Iaitu, setiap nombor $\lambda_j$ adalah nilai eigen bagi $M$ dan $\vert\psi_j\rangle$ adalah vektor eigen yang berkaitan dengan nilai eigen tersebut.

• Contoh 1. Biarkan

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

  yang merupakan normal. Teorem ini menyiratkan bahawa $\mathbb{I}$ boleh ditulis dalam bentuk $(1)$ untuk sesetengah pilihan $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ dan $\vert\psi_2\rangle.$ Terdapat pelbagai pilihan yang berfungsi, 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 bahawa teorem ini tidak mengatakan bahawa nombor kompleks $\lambda_1,\ldots,\lambda_N$ adalah berbeza — kita boleh mempunyai nombor kompleks yang sama berulang, yang diperlukan untuk contoh ini. Pilihan-pilihan ini berfungsi kerana

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

  Malah, kita boleh memilih $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ sebagai mana-mana asas ortonormal dan persamaan akan benar. Sebagai contoh,

  $$\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 unitari, jadi ia adalah normal. Teorem spektral menyiratkan bahawa $H$ boleh ditulis dalam bentuk $(1)$, dan khususnya kita ada

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

  Dengan 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 boleh menyemak bahawa penguraian ini betul dengan melakukan pengiraan 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 didedahkan oleh contoh pertama di atas, terdapat sedikit kebebasan dalam bagaimana vektor eigen dipilih. Namun, tiada kebebasan sama sekali dalam bagaimana nilai eigen dipilih, kecuali untuk pengurutannya: nombor kompleks yang sama $\lambda_1,\ldots,\lambda_N$, yang boleh merangkumi pengulangan nombor kompleks yang sama, akan sentiasa muncul dalam persamaan $(1)$ untuk pilihan matriks $M$ yang diberikan.

Sekarang mari kita fokus kepada matriks unitari. Andaikan kita mempunyai nombor kompleks $\lambda$ dan vektor bukan sifar $\vert\psi\rangle$ yang memenuhi persamaan

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

Iaitu, $\lambda$ adalah nilai eigen bagi $U$ dan $\vert\psi\rangle$ adalah vektor eigen yang berkaitan dengan nilai eigen ini.

Matriks unitari memelihara norma Euclidean, dan oleh itu kita menyimpulkan perkara berikut daripada $(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\|$$

Syarat bahawa $\vert\psi\rangle$ adalah bukan sifar menyiratkan bahawa $\bigl\| \vert\psi\rangle \bigr\|\neq 0$, jadi kita boleh membatalkannya dari kedua-dua belah untuk memperoleh

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

Ini mendedahkan bahawa nilai eigen bagi matriks unitari mestilah sentiasa mempunyai nilai mutlak yang sama dengan satu, jadi ia terletak pada bulatan unit.

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

(Simbol $\mathbb{T}$ adalah nama lazim untuk bulatan unit kompleks. Nama $S^1$ juga lazim.)

Pernyataan masalah anggaran fasa

Dalam masalah anggaran fasa, kita diberi keadaan kuantum $\vert \psi\rangle$ bagi $n$ Qubit, bersama-sama dengan litar kuantum unitari yang bertindak ke atas $n$ Qubit. Kita dijanjikan bahawa $\vert \psi\rangle$ adalah vektor eigen bagi matriks unitari $U$ yang menggambarkan tindakan litar, dan matlamat kita adalah untuk mengira atau menganggarkan nilai eigen $\lambda$ yang berkaitan dengan $\vert \psi\rangle.$ Lebih tepat lagi, kerana $\lambda$ terletak pada bulatan unit kompleks, kita boleh menulis

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

untuk nombor nyata unik $\theta$ yang memenuhi $0\leq\theta<1$. Matlamat masalah ini adalah untuk mengira atau menganggarkan nombor nyata $\theta$ ini.

Masalah anggaran fasa

Input: Litar kuantum unitari untuk operasi $U$ bagi $n$-Qubit bersama-sama dengan keadaan kuantum $n$-Qubit $\vert\psi\rangle$
Janji: $\vert\psi\rangle$ adalah vektor eigen bagi $U$
Output: penghampiran kepada nombor $\theta\in[0,1)$ yang memenuhi $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Berikut adalah beberapa catatan mengenai pernyataan masalah ini:

1. Masalah anggaran fasa berbeza daripada masalah lain yang telah kita lihat setakat ini dalam kursus kerana input merangkumi keadaan kuantum. Biasanya kita fokus kepada masalah yang mempunyai input dan output klasik, tetapi tiada yang menghalang kita daripada mempertimbangkan input keadaan kuantum seperti ini. Dari segi relevansi praktikalnya, masalah anggaran fasa biasanya ditemui sebagai submasalah dalam pengiraan yang lebih besar, seperti yang akan kita lihat dalam konteks pemfaktoran integer kemudian dalam pelajaran ini.

2. Pernyataan masalah anggaran fasa di atas tidak khusus tentang apa yang merupakan penghampiran kepada $\theta$, tetapi kita boleh merumuskan pernyataan masalah yang lebih tepat bergantung kepada keperluan dan minat kita. Dalam konteks pemfaktoran integer, kita akan memerlukan penghampiran yang sangat tepat kepada $\theta$, tetapi dalam kes lain kita mungkin berpuas hati dengan penghampiran yang sangat kasar. Kita akan bincangkan tidak lama lagi bagaimana ketepatan yang kita perlukan mempengaruhi kos pengiraan sesuatu penyelesaian.

3. Perhatikan bahawa apabila kita bergerak dari $\theta = 0$ ke arah $\theta = 1$ dalam masalah anggaran fasa, kita mengelilingi seluruh bulatan unit, bermula dari $e^{2\pi i \cdot 0} = 1$ dan bergerak lawan jam ke arah $e^{2\pi i \cdot 1} = 1$. Iaitu, apabila kita mencapai $\theta = 1$ kita kembali ke tempat asal pada $\theta = 0$. Jadi, apabila kita mempertimbangkan ketepatan penghampiran, pilihan $\theta$ yang hampir kepada $1$ harus dianggap sebagai hampir kepada $0$. Sebagai contoh, penghampiran $\theta = 0.999$ harus dianggap sebagai berada dalam jarak $1/1000$ daripada $\theta = 0$.