ปัญหาการประมาณเฟส

ส่วนนี้ของบทเรียนอธิบาย ปัญหาการประมาณเฟส เราจะเริ่มต้นด้วยการพูดถึงสั้นๆ เกี่ยวกับ spectral theorem จากพีชคณิตเชิงเส้น จากนั้นจะดำเนินไปสู่การระบุปัญหาการประมาณเฟส

ทฤษฎีบทสเปกตรัม

Spectral theorem เป็นข้อเท็จจริงสำคัญจากพีชคณิตเชิงเส้นที่ระบุว่า matrix ประเภทหนึ่ง ที่เรียกว่า normal matrix สามารถแสดงในรูปแบบที่เรียบง่ายและมีประโยชน์ ในบทเรียนนี้ เราจะใช้ theorem นี้กับ unitary matrix เท่านั้น แต่ต่อไปในซีรีส์นี้เราจะนำไปใช้กับ Hermitian matrix ด้วย

Normal matrix

square matrix $M$ ที่มีสมาชิกเป็นจำนวนเชิงซ้อนเรียกว่า normal matrix หากมัน commute กับ conjugate transpose ของมัน: $M M^{\dagger} = M^{\dagger} M.$

unitary matrix $U$ ทุกตัวเป็น normal เพราะ

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

Hermitian matrix ซึ่งเป็น matrix ที่เท่ากับ conjugate transpose ของมันเอง เป็นอีกกลุ่มสำคัญของ normal matrix หาก $H$ เป็น Hermitian matrix แล้ว

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

ดังนั้น $H$ เป็น normal

ไม่ใช่ทุก square matrix ที่เป็น normal ตัวอย่างเช่น matrix นี้ไม่ใช่ normal:

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

(นี่เป็นตัวอย่างที่เรียบง่ายแต่ยอดเยี่ยมของ matrix ที่มักมีประโยชน์มากในการพิจารณา) มันไม่ใช่ normal เพราะ

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

ในขณะที่

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

การระบุ Theorem

ต่อไปนี้คือการระบุ spectral theorem

Theorem

Spectral theorem: ให้ $M$ เป็น normal matrix เชิงซ้อนขนาด $N\times N$ มี basis orthonormal ของเวกเตอร์เชิงซ้อน $N$ มิติ $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ พร้อมกับจำนวนเชิงซ้อน $\lambda_1,\ldots,\lambda_N$ เพื่อให้

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

การแสดง matrix ในรูปแบบ

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

มักเรียกว่า spectral decomposition สังเกตว่าหาก $M$ เป็น normal matrix ที่แสดงในรูปแบบ $(1)$ แล้วสมการ

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

ต้องเป็นความจริงสำหรับทุก $j = 1,\ldots,N$ นี่เป็นผลจากข้อเท็จจริงที่ว่า $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ เป็น 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$$

นั่นคือ แต่ละจำนวน $\lambda_j$ คือ eigenvalue ของ $M$ และ $\vert\psi_j\rangle$ คือ eigenvector ที่สอดคล้องกับ eigenvalue นั้น

• ตัวอย่างที่ 1. ให้

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

  ซึ่งเป็น normal Theorem บอกว่า $\mathbb{I}$ สามารถเขียนในรูปแบบ $(1)$ สำหรับการเลือก $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ และ $\vert\psi_2\rangle$ บางอย่าง มีหลายการเลือกที่ทำงานได้ รวมถึง

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

  สังเกตว่า theorem ไม่ได้บอกว่าจำนวนเชิงซ้อน $\lambda_1,\ldots,\lambda_N$ แตกต่างกัน — เราสามารถมีจำนวนเชิงซ้อนเดิมซ้ำได้ ซึ่งจำเป็นสำหรับตัวอย่างนี้ การเลือกเหล่านี้ทำงานได้เพราะ

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

  อันที่จริง เราสามารถเลือก $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ เป็น ทุก basis orthonormal และ สมการจะเป็นความจริง ตัวอย่างเช่น

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

• ตัวอย่างที่ 2. พิจารณาการดำเนินการ Hadamard

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

  นี่คือ unitary matrix ดังนั้นมันเป็น normal Spectral theorem บอกว่า $H$ สามารถเขียนใน รูปแบบ $(1)$, และโดยเฉพาะอย่างยิ่งเรามี

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

  ที่

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

  อย่างชัดเจนยิ่งขึ้น

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

  เราสามารถตรวจสอบว่า decomposition นี้ถูกต้องโดยการทำการคำนวณที่ต้องการ:

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

ดังที่ตัวอย่างแรกข้างต้นแสดงให้เห็น อาจมีอิสระในการเลือก eigenvector อย่างไรก็ตาม ไม่มีอิสระเลยในวิธีเลือก eigenvalue ยกเว้นลำดับของพวกมัน: จำนวนเชิงซ้อน $N$ ตัวเดิม $\lambda_1,\ldots,\lambda_N$, ซึ่งอาจมีการซ้ำของจำนวนเชิงซ้อนเดิม จะปรากฏในสมการ $(1)$ เสมอสำหรับ matrix $M$ ที่กำหนด

ตอนนี้ลองมุ่งเน้นไปที่ unitary matrix สมมติว่าเรามีจำนวนเชิงซ้อน $\lambda$ และเวกเตอร์ที่ไม่ใช่ศูนย์ $\vert\psi\rangle$ ที่ตอบสนองสมการ

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

กล่าวคือ $\lambda$ คือ eigenvalue ของ $U$ และ $\vert\psi\rangle$ คือ eigenvector ที่สอดคล้องกับ eigenvalue นี้

Unitary matrix รักษา Euclidean norm ดังนั้นเราสรุปได้ดังต่อไปนี้จาก $(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\|$$

เงื่อนไขที่ $\vert\psi\rangle$ ไม่ใช่ศูนย์บอกว่า $\bigl\| \vert\psi\rangle \bigr\|\neq 0$, ดังนั้นเราจึงหารทั้งสองข้างด้วยค่านี้ได้ และจะได้

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

สิ่งนี้แสดงว่า eigenvalue ของ unitary matrix ต้องมีค่าสัมบูรณ์เท่ากับหนึ่งเสมอ ดังนั้นพวกมันอยู่บน unit circle

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

(สัญลักษณ์ $\mathbb{T}$ เป็นชื่อที่ใช้กันทั่วไปสำหรับ complex unit circle ชื่อ $S^1$ ก็ใช้กันทั่วไปเช่นกัน)

การระบุปัญหาการประมาณเฟส

ใน ปัญหาการประมาณเฟส เราได้รับสถานะควอนตัม $\vert \psi\rangle$ ของ $n$ Qubit พร้อมกับ unitary quantum circuit ที่ทำงานบน $n$ Qubit เรา ถูกสัญญา ว่า $\vert \psi\rangle$ เป็น eigenvector ของ unitary matrix $U$ ที่อธิบายการกระทำของ circuit และเป้าหมายของเราคือการคำนวณหรือประมาณ eigenvalue $\lambda$ ที่ $\vert \psi\rangle$ สอดคล้องด้วย อย่างแม่นยำยิ่งขึ้น เพราะ $\lambda$ อยู่บน complex unit circle เราสามารถเขียนได้เป็น

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

สำหรับจำนวนจริงเพียงค่าเดียว $\theta$ ที่สอดคล้องกับ $0\leq\theta<1$ เป้าหมายของปัญหาคือการคำนวณหรือประมาณจำนวนจริง $\theta$ นี้

ปัญหาการประมาณเฟส

อินพุต: quantum circuit ของ unitary สำหรับการดำเนินการ $U$ บน $n$ Qubit พร้อมกับสถานะควอนตัม $n$ Qubit $\vert\psi\rangle$
คำสัญญา: $\vert\psi\rangle$ เป็น eigenvector ของ $U$
เอาต์พุต: การประมาณของจำนวน $\theta\in[0,1)$ ที่สอดคล้องกับ $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

ต่อไปนี้คือข้อสังเกตบางประการเกี่ยวกับการระบุปัญหานี้:

1. ปัญหาการประมาณเฟสแตกต่างจากปัญหาอื่นๆ ที่เราเห็นในคอร์สนี้จนถึงตอนนี้ ตรงที่อินพุตรวมถึงสถานะควอนตัม โดยทั่วไปเราเน้นปัญหาที่มีอินพุตและเอาต์พุตแบบ classical แต่ไม่มีอะไรป้องกันเราจากการพิจารณาอินพุตสถานะควอนตัมเช่นนี้ ในแง่ของความเกี่ยวข้องในทางปฏิบัติ ปัญหาการประมาณเฟสมักพบเป็น ปัญหาย่อย ภายในการคำนวณที่ใหญ่กว่า อย่างที่เราจะเห็นในบริบทของการแยกตัวประกอบจำนวนเต็มในภายหลังในบทเรียน

2. การระบุปัญหาการประมาณเฟสข้างต้นไม่ได้ระบุว่าอะไรถือเป็นการประมาณ $\theta$ แต่เราสามารถกำหนดการระบุปัญหาที่แม่นยำยิ่งขึ้นขึ้นอยู่กับความต้องการและความสนใจของเรา ในบริบทของการแยกตัวประกอบจำนวนเต็ม เราจะต้องการการประมาณ $\theta$ ที่แม่นยำมาก แต่ในกรณีอื่นๆ เราอาจพอใจกับการประมาณที่หยาบมาก เราจะพูดถึงในไม่ช้าว่าความแม่นยำที่เราต้องการส่งผลต่อต้นทุนการคำนวณของวิธีแก้ปัญหาอย่างไร

3. สังเกตว่าเมื่อเราเดินทางจาก $\theta = 0$ ไปสู่ $\theta = 1$ ในปัญหาการประมาณเฟส เราวนรอบ unit circle จนครบ โดยเริ่มต้นจาก $e^{2\pi i \cdot 0} = 1$ และเคลื่อนที่ทวนเข็มนาฬิกาไปสู่ $e^{2\pi i \cdot 1} = 1$ กล่าวคือ เมื่อเราถึง $\theta = 1$ เราอยู่ที่จุดเริ่มต้นเดิมที่ $\theta = 0$ ดังนั้น เมื่อเราพิจารณาความถูกต้องของการประมาณ ค่า $\theta$ ที่ใกล้ $1$ ควรถือว่าอยู่ใกล้ $0$ ตัวอย่างเช่น การประมาณ $\theta = 0.999$ ควรถือว่าอยู่ภายใน $1/1000$ ของ $\theta = 0$