Ang problemang phase estimation

Ipinapaliwanag ng seksyong ito ng aralin ang problemang phase estimation. Magsisimula tayo sa maikling talakayan ng spectral theorem mula sa linear algebra, tapos lilipat tayo sa pagsasaad ng problemang phase estimation mismo.

Spectral theorem

Ang spectral theorem ay isang mahalagang katotohanan mula sa linear algebra na nagsasaad na ang mga matrix ng isang tiyak na uri, na tinatawag na normal matrices, ay maaaring ipahayag sa isang simple at kapaki-pakinabang na paraan. Kakailanganin lang natin ang theorem na ito para sa mga unitary matrix sa araling ito, ngunit sa susunod na bahagi ng seryeng ito ay ilalapat din natin ito sa mga Hermitian matrix.

Mga normal matrix

Ang isang square matrix $M$ na may mga complex number na entry ay tinatawag na normal matrix kung ito ay commute sa kanyang conjugate transpose: $M M^{\dagger} = M^{\dagger} M.$

Ang bawat unitary matrix $U$ ay normal dahil

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

Ang mga Hermitian matrix, na mga matrix na katumbas ng kanilang sariling conjugate transpose, ay isa pang mahalagang klase ng mga normal matrix. Kung ang $H$ ay isang Hermitian matrix, kung gayon

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

kaya normal ang $H$.

Hindi lahat ng square matrix ay normal. Halimbawa, hindi normal ang matrix na ito:

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

(Ito ay isang simple ngunit napakagandang halimbawa ng matrix na madalas na napakatulong isaalang-alang.) Hindi ito normal dahil

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

habang

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

Pahayag ng theorem

Narito ang isang pahayag ng spectral theorem.

Theorem

Spectral theorem: Hayaan ang $M$ na maging isang normal na $N\times N$ complex matrix. May umiiral na orthonormal basis ng $N$-dimensional complex vectors na $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ kasama ang mga complex number na $\lambda_1,\ldots,\lambda_N$ na nagpapatunay na

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

Ang pagpapahayag ng matrix sa anyong

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

ay karaniwang tinatawag na spectral decomposition. Pansinin na kung ang $M$ ay isang normal matrix na naipahayag sa anyong $(1),$ kung gayon ang ekwasyon

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

ay dapat na totoo para sa bawat $j = 1,\ldots,N.$ Ito ay bunga ng katotohanan na ang $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ ay orthonormal:

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

Ibig sabihin, ang bawat numero na $\lambda_j$ ay isang eigenvalue ng $M$ at ang $\vert\psi_j\rangle$ ay isang eigenvector na naaayon sa eigenvalue na iyon.

• Halimbawa 1. Hayaan

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

  na normal. Ipinahihiwatig ng theorem na ang $\mathbb{I}$ ay maaaring isulat sa anyong $(1)$ para sa ilang pagpili ng $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ at $\vert\psi_2\rangle.$ Mayroong maraming pagpili na gumagana, kasama na ang

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

  Pansinin na hindi sinasabi ng theorem na ang mga complex number na $\lambda_1,\ldots,\lambda_N$ ay natatangi — maaari tayong magkaroon ng parehong complex number na paulit-ulit, na kinakailangan para sa halimbawang ito. Gumagana ang mga pagpiling ito dahil

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

  Sa katunayan, maaari nating piliin ang $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ na maging anumang orthonormal basis at magiging totoo ang ekwasyon. Halimbawa,

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

• Halimbawa 2. Isaalang-alang ang isang Hadamard operation.

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

  Ito ay isang unitary matrix, kaya ito ay normal. Ipinahihiwatig ng spectral theorem na ang $H$ ay maaaring isulat sa anyong $(1),$ at partikular na mayroon tayong

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

  kung saan

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

  Mas malinaw,

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

  Maaari nating suriin na tama ang decomposition na ito sa pamamagitan ng pagsasagawa ng mga kinakailangang kalkulasyon:

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

Tulad ng ipinapakita ng unang halimbawa sa itaas, maaaring may kalayaan sa kung paano pinipili ang mga eigenvector. Walang kalayaan, gayunpaman, sa kung paano pinipili ang mga eigenvalue, maliban sa kanilang pagkakasunod-sunod: ang parehong $N$ complex number na $\lambda_1,\ldots,\lambda_N,$ na maaaring magsama ng mga paulit-ulit na parehong complex number, ay laging lilitaw sa ekwasyong $(1)$ para sa isang ibinigay na pagpili ng matrix na $M.$

Ngayon, tumuon tayo sa mga unitary matrix. Ipagpalagay na mayroon tayong complex number na $\lambda$ at isang hindi-zero na vector na $\vert\psi\rangle$ na nagpapatunay sa ekwasyon

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

Ibig sabihin, ang $\lambda$ ay isang eigenvalue ng $U$ at ang $\vert\psi\rangle$ ay isang eigenvector na naaayon sa eigenvalue na ito.

Pinapanatili ng mga unitary matrix ang Euclidean norm, kaya naman nakukuha natin ang sumusunod mula sa $(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\|$$

Ang kondisyon na ang $\vert\psi\rangle$ ay hindi-zero ay nangangahulugang $\bigl\| \vert\psi\rangle \bigr\|\neq 0,$ kaya maaari nating kanselahin ito mula sa magkabilang panig upang makuha

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

Ibinubunyag nito na ang mga eigenvalue ng mga unitary matrix ay palaging may absolute value na katumbas ng isa, kaya nasa unit circle sila.

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

(Ang simbolong $\mathbb{T}$ ay isang karaniwang pangalan para sa complex unit circle. Karaniwang ginagamit din ang pangalang $S^1$.)

Pahayag ng problemang phase estimation

Sa problemang phase estimation, binibigyan tayo ng quantum state na $\vert \psi\rangle$ ng $n$ qubits, kasama ang isang unitary quantum circuit na kumikilos sa $n$ qubits. Ipinangako na ang $\vert \psi\rangle$ ay isang eigenvector ng unitary matrix na $U$ na naglalarawan sa aksyon ng circuit, at ang ating layunin ay kalkulahin o tantiyahin ang eigenvalue na $\lambda$ na naaayon sa $\vert \psi\rangle$. Mas tiyak, dahil ang $\lambda$ ay nasa complex unit circle, maaari nating isulat

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

para sa isang natatanging real number na $\theta$ na nagpapatunay ng $0\leq\theta<1.$ Ang layunin ng problema ay kalkulahin o tantiyahin ang real number na $\theta$ na ito.

Problemang phase estimation

Input: Isang unitary quantum circuit para sa isang $n$-qubit operation na $U$ kasama ang isang $n$-qubit quantum state na $\vert\psi\rangle$
Pangako: Ang $\vert\psi\rangle$ ay isang eigenvector ng $U$
Output: isang pagtatantya sa numero na $\theta\in[0,1)$ na nagpapatunay ng $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Narito ang ilang mga puna tungkol sa pahayag ng problemang ito:

1. Ang problemang phase estimation ay naiiba sa iba pang mga problema na nakita natin sa kurso dahil ang input ay nagsasama ng quantum state. Karaniwan ay nakatutok tayo sa mga problemang may classical na input at output, ngunit walang pumipigil sa atin na isaalang-alang ang mga quantum state input tulad nito. Sa mga tuntunin ng praktikal na kaugnayan, ang problemang phase estimation ay karaniwang nararatagpuan bilang isang subproblem sa loob ng isang mas malaking computation, tulad ng makikita natin sa konteksto ng integer factorization sa susunod na bahagi ng aralin.

2. Ang pahayag ng problemang phase estimation sa itaas ay hindi tiyak tungkol sa kung ano ang bumubuo ng pagtatantya ng $\theta,$ ngunit maaari tayong bumuo ng mas tumpak na mga pahayag ng problema depende sa ating mga pangangailangan at interes. Sa konteksto ng integer factorization, mangangailangan tayo ng napaka-tumpak na pagtatantya ng $\theta,$ ngunit sa ibang mga kaso maaaring masaya na tayo sa isang magaspang na pagtatantya. Tatalakayin natin sa ilang sandali kung paano nakakaapekto ang katumpakang kailangan natin sa computational cost ng isang solusyon.

3. Pansinin na habang tumatahak tayo mula sa $\theta = 0$ patungo sa $\theta = 1$ sa problemang phase estimation, umiikot tayo nang buo sa unit circle, simula sa $e^{2\pi i \cdot 0} = 1$ at gumagalaw counter-clockwise patungo sa $e^{2\pi i \cdot 1} = 1.$ Ibig sabihin, kapag naabot natin ang $\theta = 1$ ay nandoon na tayo uli sa $\theta = 0.$ Kaya, habang isinasaalang-alang natin ang katumpakan ng mga pagtatantya, ang mga pagpili ng $\theta$ malapit sa $1$ ay dapat ituring na malapit sa $0.$ Halimbawa, ang pagtatantya na $\theta = 0.999$ ay dapat ituring na nasa loob ng $1/1000$ ng $\theta = 0.$