ขั้นตอนการประมาณเฟส

ต่อไปเราจะพูดถึง ขั้นตอนการประมาณเฟส ซึ่งเป็นอัลกอริทึมควอนตัมสำหรับแก้ปัญหาการประมาณเฟส

เราจะเริ่มต้นด้วยการอุ่นเครื่องแบบความแม่นยำต่ำ ซึ่งจะช่วยอธิบายสัญชาตญาณพื้นฐานเบื้องหลังวิธีนี้ จากนั้นเราจะพูดถึง การแปลงฟูริเยร์ควอนตัม ซึ่งเป็นการดำเนินการควอนตัมที่สำคัญที่ใช้ในขั้นตอนการประมาณเฟส พร้อมกับการนำไปใช้งานด้วย Circuit ควอนตัม เมื่อเรามีการแปลงฟูริเยร์ควอนตัมแล้ว เราจะอธิบายขั้นตอนการประมาณเฟสในเชิงทั่วไปและวิเคราะห์ประสิทธิภาพของมัน

อุ่นเครื่อง: ประมาณเฟสด้วยความแม่นยำต่ำ

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

การใช้ phase kickback

วิธีที่ง่ายในการแก้ปัญหาการประมาณเฟส ซึ่งช่วยให้เราเรียนรู้บางอย่างเกี่ยวกับค่า $\theta$ ที่เราต้องการ อาศัยปรากฏการณ์ phase kick-back ดังที่เราจะเห็น นี่คือเวอร์ชัน single-qubit ของขั้นตอนการประมาณเฟสทั่วไปที่จะพูดถึงในภายหลัง

ในฐานะส่วนหนึ่งของอินพุตสำหรับปัญหาการประมาณเฟส เรามี Circuit ควอนตัมแบบ unitary สำหรับการดำเนินการ $U$. เราสามารถใช้คำอธิบาย Circuit นี้เพื่อสร้าง Circuit สำหรับการดำเนินการ controlled-$U$ ซึ่งสามารถแสดงได้ตามที่รูปนี้บอก (โดยมีการดำเนินการ $U$, มองเป็น Gate ควอนตัม อยู่ทางซ้าย และการดำเนินการ controlled-$U$ อยู่ทางขวา)

เราสามารถสร้าง Circuit ควอนตัมสำหรับการดำเนินการ controlled-$U$ โดยการเพิ่ม control qubit ให้กับ Circuit สำหรับ $U$ ก่อน แล้วแทนที่ทุก Gate ใน Circuit สำหรับ $U$ ด้วยเวอร์ชัน controlled ของ Gate นั้น — ดังนั้น control qubit ใหม่หนึ่งตัวของเราจึงควบคุม Gate ทุกตัวใน Circuit สำหรับ $U$ สิ่งนี้ต้องการให้เรามีเวอร์ชัน controlled ของทุก Gate ใน Circuit ของเรา แต่เราสามารถสร้าง Circuit สำหรับการดำเนินการ controlled เหล่านี้ได้เสมอในกรณีที่ไม่ได้รวมอยู่ใน gate set ของเรา

ลองพิจารณา Circuit ต่อไปนี้ โดยที่สถานะอินพุต $\vert\psi\rangle$ ของ qubit ทั้งหมดยกเว้น qubit บนสุดคือสถานะควอนตัมที่เป็น eigenvector ของ $U$

ความน่าจะเป็นของผลการวัดสำหรับ Circuit นี้ขึ้นอยู่กับ eigenvalue ของ $U$ ที่สอดคล้องกับ eigenvector $\vert\psi\rangle$ มาวิเคราะห์ Circuit อย่างละเอียดเพื่อหาว่ามันเป็นอย่างไรกันแน่

สถานะเริ่มต้นของ Circuit คือ

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

และ Hadamard Gate แรกแปลงสถานะนี้เป็น

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

ต่อไป การดำเนินการ controlled-$U$ จะถูกดำเนินการ ส่งผลให้ได้สถานะ

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

โดยใช้สมมติฐานที่ว่า $\vert\psi\rangle$ เป็น eigenvector ของ $U$ ที่มี eigenvalue $\lambda = e^{2\pi i\theta}$, เราสามารถแสดงสถานะนี้ได้อีกแบบดังต่อไปนี้

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

ที่นี่เราสังเกตเห็นปรากฏการณ์ phase kickback มันแตกต่างจากครั้งก่อนที่เราเห็นในอัลกอริทึมของ Deutsch และ Deutsch-Jozsa เล็กน้อย เพราะเราไม่ได้ทำงานกับ query gate — แต่ความคิดก็คล้ายกัน

สุดท้าย Hadamard Gate ที่สองจะถูกดำเนินการ หลังจากการลดรูปเล็กน้อย เราได้นิพจน์สำหรับสถานะนี้

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

ดังนั้นการวัดจะให้ผลลัพธ์ $0$ และ $1$ ด้วยความน่าจะเป็นเหล่านี้:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

นี่คือกราฟแสดงความน่าจะเป็นสำหรับผลลัพธ์ที่เป็นไปได้สองแบบ คือ $0$ และ $1,$ ในฐานะฟังก์ชันของ $\theta$

ตามธรรมชาติ ความน่าจะเป็นทั้งสองรวมกันได้เสมอเท่ากับ $1$ สังเกตว่าเมื่อ $\theta = 0$, ผลการวัดจะเป็น $0$ เสมอ และเมื่อ $\theta = 1/2$, ผลการวัดจะเป็น $1$ เสมอ ดังนั้น แม้ว่าผลการวัดจะไม่เปิดเผยว่า $\theta$ คืออะไรกันแน่ แต่ก็ให้ข้อมูลบางอย่างเกี่ยวกับมัน — และหากเราได้รับการรับรองว่า $\theta = 0$ หรือ $\theta = 1/2$ เราสามารถเรียนรู้จาก Circuit ว่าค่าใดถูกต้องโดยไม่ผิดพลาด

พูดตามสัญชาตญาณ เราสามารถคิดว่าผลการวัดของ Circuit เป็นการเดา $\theta$ ด้วย "ความแม่นยำหนึ่งบิต" กล่าวอีกนัยหนึ่ง ถ้าเราเขียน $\theta$ ในรูปเลขฐานสองและปัดเศษให้เหลือหนึ่งบิต เราจะได้ตัวเลขแบบนี้:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

ผลการวัดสามารถมองได้ว่าเป็นการเดาบิต $a$ เมื่อ $\theta$ ไม่ใช่ทั้ง $0$ หรือ $1/2$ มีความน่าจะเป็นที่ไม่ใช่ศูนย์ที่การเดาจะผิด — แต่ ความน่าจะเป็นของการเกิดข้อผิดพลาดจะลดลงเรื่อย ๆ เมื่อเราเข้าใกล้ $0$ หรือ $1/2$ มากขึ้น

เป็นเรื่องธรรมชาติที่จะถามว่า Hadamard Gate ทั้งสองมีบทบาทอะไรในขั้นตอนนี้:

• Hadamard Gate แรกตั้ง control qubit ให้อยู่ในซูเปอร์โพซิชันสม่ำเสมอของ $\vert 0\rangle$ และ $\vert 1\rangle$, เพื่อที่เมื่อ phase kickback เกิดขึ้น มันจะเกิดขึ้นกับสถานะ $\vert 1\rangle$ และไม่ใช่สถานะ $\vert 0\rangle$ ทำให้เกิดความแตกต่างของเฟส สัมพัทธ์ ที่ส่งผลต่อความน่าจะเป็นของผลการวัด หากเราไม่ทำเช่นนี้และ phase kickback สร้าง global phase มันจะไม่มีผลต่อความน่าจะเป็นของการได้ผลการวัดที่แตกต่างกัน

• Hadamard Gate ที่สองช่วยให้เราเรียนรู้บางอย่างเกี่ยวกับตัวเลข $\theta$ ผ่านปรากฏการณ์ interference ก่อน Hadamard Gate ที่สอง สถานะของ qubit บนสุดคือ

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  และหากเราวัดสถานะนี้ เราจะได้ $0$ และ $1$ แต่ละอย่างด้วยความน่าจะเป็น $1/2$ ไม่บอกเราอะไรเกี่ยวกับ $\theta$ เลย แต่โดยการดำเนินการ Hadamard Gate ที่สอง เราทำให้ตัวเลข $\theta$ ส่งผลต่อความน่าจะเป็นของเอาต์พุต

การเพิ่มเฟสเป็นสองเท่า

Circuit ด้านบนใช้ปรากฏการณ์ phase kickback เพื่อประมาณ $\theta$ ด้วยความแม่นยำหนึ่งบิต ความแม่นยำหนึ่งบิตอาจเพียงพอในบางสถานการณ์ — แต่สำหรับการแยกตัวประกอบเราจะต้องการความแม่นยำมากกว่านั้นมาก คำถามที่เป็นธรรมชาติคือ เราจะเรียนรู้เพิ่มเติมเกี่ยวกับ $\theta$ ได้อย่างไร?

สิ่งที่ง่ายมากที่เราสามารถทำได้คือแทนที่การดำเนินการ controlled-$U$ ใน Circuit ของเราด้วย สองสำเนา ของการดำเนินการนี้ เหมือนใน Circuit นี้:

การดำเนินการ controlled-$U$ สองครั้งเทียบเท่ากับการดำเนินการ controlled-$U^2$ ครั้งเดียว ถ้า $\vert\psi\rangle$ เป็น eigenvector ของ $U$ ที่มี eigenvalue $\lambda = e^{2\pi i \theta}$, สถานะนี้ก็เป็น eigenvector ของ $U^2$ ด้วย คราวนี้มี eigenvalue $\lambda^2 = e^{2\pi i (2\theta)}$

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

การทำเช่นนี้สามารถให้ข้อมูลเพิ่มเติมเกี่ยวกับ $\theta$ ได้จริง ๆ ถ้าการแสดงในระบบฐานสองของ $\theta$ คือ

$$\theta = 0.a_1 a_2 a_3\cdots$$

การเพิ่ม $\theta$ เป็นสองเท่าจะเลื่อนจุดฐานสองไปทางขวาหนึ่งตำแหน่ง:

$$2\theta = a_1. a_2 a_3\cdots$$

และเนื่องจากเราถือว่า $\theta = 1$ เท่ากับ $\theta = 0$ เมื่อเราวนรอบวงกลมหน่วย เราจะเห็นว่าบิต $a_1$ ไม่มีอิทธิพลต่อความน่าจะเป็นของเรา และเราก็แค่กำลังเดา บิตที่สอง หลังจากจุดฐานสองถ้าเราปัดเศษ $\theta$ ให้เหลือสองบิต ตัวอย่างเช่น ถ้าเรารู้ล่วงหน้าว่า $\theta$ เป็น $0$ หรือ $1/4$ เราก็สามารถเชื่อถือผลการวัดอย่างสมบูรณ์เพื่อบอกเราว่าเป็นค่าใด

อย่างไรก็ตาม ยังไม่ชัดเจนว่าการประมาณนี้ควรได้รับการปรับให้สอดคล้องกับสิ่งที่เราเรียนรู้จาก Circuit phase kickback ดั้งเดิม (ที่ไม่ได้เพิ่มสองเท่า) เพื่อให้ได้ข้อมูลที่แม่นยำที่สุดเท่าที่เป็นไปได้เกี่ยวกับ $\theta$ ดังนั้นมาถอยกลับมาและพิจารณาวิธีดำเนินการต่อ

การประมาณเฟสด้วยสอง Qubit

แทนที่จะพิจารณาสองตัวเลือกที่อธิบายไว้ข้างต้นแยกกัน มารวมเข้าด้วยกันเป็น Circuit เดียวดังนี้

Hadamard Gate หลังจากการดำเนินการ controlled ถูกลบออกแล้วและยังไม่มีการวัดที่นี่ เราจะเพิ่มเติมสิ่งต่าง ๆ ลงใน Circuit เมื่อเราพิจารณาตัวเลือกของเราสำหรับการเรียนรู้มากที่สุดเท่าที่เป็นไปได้เกี่ยวกับ $\theta$

ถ้าเราเรียกใช้ Circuit นี้เมื่อ $\vert\psi\rangle$ เป็น eigenvector ของ $U$ สถานะของ qubit ล่างจะคงเป็น $\vert\psi\rangle$ ตลอด Circuit ทั้งหมด และเฟสจะถูก "kick" เข้าไปในสถานะของ qubit สองตัวบนสุด มาวิเคราะห์ Circuit อย่างละเอียดโดยใช้รูปต่อไปนี้

เราสามารถเขียนสถานะ $\vert\pi_1\rangle$ ดังนี้:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

เมื่อการดำเนินการ controlled-$U$ ครั้งแรกดำเนินการ eigenvalue $\lambda = e^{2\pi i\theta}$ จะถูก kick เข้าไปในเฟสเมื่อ $a_0$ (qubit บนสุด) เท่ากับ $1$ แต่ไม่ใช่เมื่อมันเป็น $0$ ดังนั้น เราสามารถแสดงสถานะที่ได้ดังนี้:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

controlled-$U$ Gate ที่สองและสามทำสิ่งที่คล้ายกัน ยกเว้นสำหรับ $a_1$ แทนที่จะเป็น $a_0$ และ $\theta$ แทนที่ด้วย $2\theta$ เราสามารถแสดงสถานะที่ได้ดังนี้:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

ถ้าเราคิดถึงสตริงฐานสอง $a_1 a_0$ ว่าแทนจำนวนเต็ม $x \in \{0,1,2,3\}$ ในรูปฐานสอง ซึ่งคือ $x = 2 a_1 + a_0$ เราสามารถแสดงสถานะนี้ได้อีกแบบดังนี้

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

เป้าหมายของเราคือดึงข้อมูลเกี่ยวกับ $\theta$ ให้ได้มากที่สุดจากสถานะนี้

ณ จุดนี้เราจะพิจารณากรณีพิเศษ ที่เราได้รับการรับรองว่า $\theta = \frac{y}{4}$ สำหรับจำนวนเต็ม $y\in\{0,1,2,3\}$ กล่าวอีกนัยหนึ่ง เรามี $\theta\in \{0, 1/4, 1/2, 3/4\}$ ดังนั้นเราสามารถแสดงตัวเลขนี้ได้อย่างแม่นยำโดยใช้รูปฐานสองด้วยสองบิต คือ .$00,$ .$01,$ .$10,$ หรือ .$11$ โดยทั่วไป $\theta$ อาจไม่ใช่หนึ่งในสี่ค่านี้ แต่การคิดถึงกรณีพิเศษนี้จะช่วยให้เราหาวิธีที่มีประสิทธิภาพสูงสุดในการดึงข้อมูลเกี่ยวกับ $\theta$ ในเชิงทั่วไป

ก่อนอื่นเราจะกำหนดเวกเตอร์สถานะสอง qubit สำหรับแต่ละค่า $y \in \{0, 1, 2, 3\}$ ที่เป็นไปได้

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

หลังจากลดรูปเลขชี้กำลัง เราสามารถเขียนเวกเตอร์เหล่านี้ดังนี้

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

เวกเตอร์เหล่านี้มีความตั้งฉากกัน: ถ้าเราเลือกคู่ใดก็ตามและคำนวณ inner product จะได้ $0$ แต่ละอันก็เป็น unit vector ด้วย ดังนั้น $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ จึงเป็น orthonormal basis ดังนั้นเราทราบทันทีว่ามีการวัดที่สามารถแยกแยะพวกมันได้อย่างสมบูรณ์แบบ — หมายความว่าถ้าเราได้รับหนึ่งในนั้นแต่ไม่รู้ว่าอันไหน เราก็สามารถหาว่ามันคืออันใดโดยไม่ผิดพลาด

เพื่อทำการแยกแยะดังกล่าวด้วย Circuit ควอนตัม เราสามารถกำหนดการดำเนินการ unitary $V$ ที่แปลง standard basis states ไปเป็นสี่สถานะที่แสดงไว้ข้างต้นก่อน

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

เพื่อเขียน $V$ เป็นเมทริกซ์ $4\times 4$ เราแค่นำคอลัมน์ของ $V$ มาเป็นสถานะ $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$

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

นี่เป็นเมทริกซ์พิเศษ และผู้อ่านบางคนอาจเคยพบมาก่อน: มันคือเมทริกซ์ที่เกี่ยวข้องกับ discrete Fourier transform มิติ $4$ ด้วยเหตุนี้ มาเรียกมันด้วยชื่อ $\mathrm{QFT}_4$ แทนที่จะเป็น $V$ ชื่อ $\mathrm{QFT}$ ย่อมาจาก quantum Fourier transform — ซึ่งก็คือ discrete Fourier transform มองในฐานะการดำเนินการ unitary เราจะพูดถึง quantum Fourier transform ในรายละเอียดและเชิงทั่วไปมากขึ้นในไม่ช้า

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

เราสามารถดำเนินการ inverse ของการดำเนินการนี้เพื่อไปทางตรงกันข้าม แปลงสถานะ $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ ไปเป็น standard basis states $\vert 0\rangle,\ldots,\vert 3\rangle$ ถ้าเราทำเช่นนี้ เราก็สามารถวัดเพื่อเรียนรู้ว่าค่า $y\in\{0,1,2,3\}$ ใดที่อธิบาย $\theta$ เป็น $\theta = y/4$ นี่คือแผนภาพของ Circuit ควอนตัมที่ทำสิ่งนี้

โดยสรุป ถ้าเราเรียกใช้ Circuit นี้เมื่อ $\theta = y/4$ สำหรับ $y\in\{0,1,2,3\}$, สถานะทันทีก่อนการวัดจะเป็น $\vert \psi\rangle \vert y\rangle$ (สำหรับ $y$ ที่เข้ารหัสเป็นสตริงฐานสองสองบิต) ดังนั้นการวัดจะเปิดเผยค่า $y$ โดยไม่ผิดพลาด

Circuit นี้มีแรงบันดาลใจจากกรณีพิเศษที่ $\theta \in \{0,1/4,1/2,3/4\}$ — แต่เราสามารถเรียกใช้มันสำหรับทุกตัวเลือกของ $U$ และ $\vert \psi\rangle$ และด้วยเหตุนี้ทุกค่าของ $\theta$ ที่เราต้องการ นี่คือกราฟแสดงความน่าจะเป็นของเอาต์พุตที่ Circuit ให้สำหรับทุกตัวเลือกของ $\theta$

นี่เป็นการปรับปรุงที่ชัดเจนเหนือรูปแบบ single-qubit ที่อธิบายไว้ก่อนหน้าในบทเรียน ไม่สมบูรณ์แบบ — อาจให้คำตอบที่ผิด — แต่คำตอบมักเอนเอียงมากไปทางค่า $y$ ที่ $y/4$ ใกล้เคียงกับ $\theta$ โดยเฉพาะอย่างยิ่ง ผลลัพธ์ที่น่าจะเป็นมากที่สุดจะสอดคล้องกับค่าที่ใกล้ที่สุดของ $y/4$ กับ $\theta$ เสมอ (ถือว่า $\theta = 0$ กับ $\theta = 1$ เป็นค่าเดียวกันเหมือนก่อนหน้า) และจากกราฟดูเหมือนว่าค่าที่ใกล้ที่สุดสำหรับ $x$ นี้ปรากฏด้วยความน่าจะเป็นสูงกว่า $40\%$ เพียงเล็กน้อยเสมอ เมื่อ $\theta$ อยู่กึ่งกลางพอดีระหว่างสองค่าดังกล่าว เช่น $\theta = 0.375$ สองค่า $y$ ที่ใกล้เท่ากันมีความน่าจะเป็นเท่ากัน

เตรียมการสำหรับการขยายไปสู่หลาย qubit

เมื่อเห็นการปรับปรุงที่เราได้รับโดยใช้ control qubit สองตัวแทนที่จะเป็นหนึ่ง ร่วมกับ inverse ของ quantum Fourier transform มิติ $4$ มันเป็นเรื่องธรรมชาติที่จะพิจารณาการขยายต่อไป — โดยเพิ่ม control qubit มากขึ้น เมื่อเราทำเช่นนี้ เราจะได้ ขั้นตอนการประมาณเฟส ทั่วไป เราจะเห็นว่ามันทำงานอย่างไรในไม่ช้า แต่เพื่ออธิบายอย่างแม่นยำ เราต้องพูดถึง quantum Fourier transform ในเชิงทั่วไปมากขึ้น เพื่อดูว่ามันถูกกำหนดสำหรับมิติอื่น ๆ อย่างไร และเราสามารถนำไปใช้ (หรือ inverse ของมัน) กับ Circuit ควอนตัมได้อย่างไร

การแปลงฟูริเยร์ควอนตัม

quantum Fourier transform คือการดำเนินการ unitary ที่สามารถกำหนดได้สำหรับจำนวนเต็มบวก $N$ ใด ๆ ในหัวข้อนี้ เราจะดูว่าการดำเนินการนี้ถูกกำหนดอย่างไร และสามารถนำไปใช้กับ Circuit ควอนตัมบน $m$ qubit ด้วยต้นทุน $O(m^2)$ ได้อย่างไรเมื่อ $N = 2^m$

เมทริกซ์ที่อธิบาย quantum Fourier transform มาจากการดำเนินการแบบคล้ายกันบนเวกเตอร์มิติ $N$ ที่รู้จักกันในชื่อ discrete Fourier transform การดำเนินการนี้สามารถคิดได้หลายแบบ ตัวอย่างเช่น เราสามารถคิดถึง discrete Fourier transform ในเชิงคณิตศาสตร์นามธรรมล้วน ๆ ในฐานะ linear mapping หรือเราสามารถคิดถึงมันในเชิงการคำนวณ ที่เราได้รับเวกเตอร์มิติ $N$ ของจำนวนเชิงซ้อน (โดยใช้เลขฐานสองในการเข้ารหัสส่วนจริงและส่วนจินตภาพของ entry สมมติว่า) และเป้าหมายคือคำนวณเวกเตอร์มิติ $N$ ที่ได้จากการใช้ discrete Fourier transform โฟกัสของเราจะอยู่ที่วิธีที่สาม ซึ่งคือการมองการแปลงนี้ในฐานะการดำเนินการ unitary ที่สามารถดำเนินการบนระบบควอนตัมได้

มีอัลกอริทึมที่มีประสิทธิภาพสำหรับการคำนวณ discrete Fourier transform บนเวกเตอร์อินพุตที่กำหนดที่รู้จักกันในชื่อ fast Fourier transform มันมีการใช้งานในการประมวลผลสัญญาณและหลายพื้นที่อื่น ๆ และถูกมองโดยหลายคนว่าเป็นหนึ่งในอัลกอริทึมที่สำคัญที่สุดที่เคยค้นพบ ปรากฏว่าการนำ quantum Fourier transform ไปใช้เมื่อ $N$ เป็นกำลังของ 2 ที่เราจะศึกษานั้นอิงจากโครงสร้างพื้นฐานเดียวกันกับที่ทำให้ fast Fourier transform เป็นไปได้

นิยามของ quantum Fourier transform

เพื่อนิยาม quantum Fourier transform เราจะกำหนดจำนวนเชิงซ้อน $\omega_N$ ก่อน สำหรับแต่ละจำนวนเต็มบวก $N$ ดังนี้:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

นี่คือตัวเลขบนวงกลมหน่วยเชิงซ้อนที่เราได้ถ้าเราเริ่มที่ $1$ และเคลื่อนทวนเข็มนาฬิกาด้วยมุม $2\pi/N$ เรเดียน หรือเศษ $1/N$ ของเส้นรอบวง นี่คือตัวอย่างบางส่วน:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

ตอนนี้เราสามารถนิยาม quantum Fourier transform มิติ $N$ ซึ่งอธิบายโดยเมทริกซ์ $N\times N$ ที่แถวและคอลัมน์เกี่ยวข้องกับ standard basis states $\vert 0\rangle,\ldots,\vert N-1\rangle$ เราต้องการการดำเนินการนี้เฉพาะเมื่อ $N = 2^m$ เป็นกำลังของ $2$ สำหรับการประมาณเฟส แต่การดำเนินการนี้สามารถนิยามได้สำหรับจำนวนเต็มบวก $N$ ใด ๆ

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

ดังที่กล่าวไว้แล้ว นี่คือเมทริกซ์ที่เกี่ยวข้องกับ discrete Fourier transform มิติ $N$ บ่อยครั้งไม่รวมตัวประกอบนำ $1/\sqrt{N}$ ไว้ในนิยามของเมทริกซ์นี้ แต่เราต้องรวมไว้เพื่อให้ได้เมทริกซ์ unitary

นี่คือ quantum Fourier transform เขียนเป็นเมทริกซ์ สำหรับค่า $N$ เล็กบางค่า

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

สังเกตโดยเฉพาะว่า $\mathrm{QFT}_2$ เป็นชื่ออีกชื่อสำหรับการดำเนินการ Hadamard

ความเป็น Unitary

มาตรวจสอบว่า $\mathrm{QFT}_N$ เป็น unitary สำหรับทุกตัวเลือกของ $N$ วิธีหนึ่งในการทำเช่นนี้คือแสดงว่าคอลัมน์ของมันก่อให้เกิด orthonormal basis เราสามารถกำหนดเวกเตอร์ที่สอดคล้องกับคอลัมน์ที่ $y$ เริ่มจาก $y = 0$ ไปถึง $y = N-1$ ดังนี้:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

การนำ inner product ระหว่างเวกเตอร์สองตัวใด ๆ เหล่านี้ให้นิพจน์นี้:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

เราสามารถประเมินผลรวมแบบนี้ได้โดยใช้สูตรต่อไปนี้สำหรับผลรวมของ $N$ พจน์แรกของอนุกรมเรขาคณิต

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

โดยเฉพาะอย่างยิ่ง เราสามารถใช้สูตรนี้เมื่อ $\alpha = \omega_N^{y-z}$ เมื่อ $y = z$ เรามี $\alpha = 1$ ดังนั้นการใช้สูตรและหารด้วย $N$ ให้

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

เมื่อ $y\neq z$ เรามี $\alpha \neq 1$ ดังนั้นสูตรจะเปิดเผยสิ่งนี้:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

สิ่งนี้เกิดขึ้นเพราะ $\omega_N^N = e^{2\pi i} = 1$ ดังนั้น $\omega_N^{N(y-z)} = 1^{y-z} = 1$ ทำให้ตัวเศษเป็นศูนย์ ในขณะที่ตัวส่วนไม่ใช่ศูนย์เพราะ $\omega_N^{y-z} \neq 1$ พูดตามสัญชาตญาณ สิ่งที่เราทำคือรวมจุดหลายจุดที่กระจายอยู่รอบ ๆ วงกลมหน่วย และพวกมันหักล้างกันและเหลือ $0$ เมื่อรวมกัน

เราจึงแสดงให้เห็นแล้วว่า $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ เป็นชุด orthonormal

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

ซึ่งเปิดเผยว่า $\mathrm{QFT}_N$ เป็น unitary

Gate เฟสแบบควบคุม

เพื่อนำ quantum Fourier transform ไปใช้กับ Circuit ควอนตัม เราจะต้องใช้ controlled-phase gates ระลึกว่า phase operation คือการดำเนินการ unitary single-qubit ในรูปแบบ

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

สำหรับจำนวนจริง $\alpha$ ใด ๆ เวอร์ชัน controlled ของ Gate นี้มีเมทริกซ์ดังต่อไปนี้:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

สำหรับ controlled gate นี้ จริง ๆ ไม่สำคัญว่า qubit ไหนเป็น control และ qubit ไหนเป็น target เพราะสองความเป็นไปได้นั้นเทียบเท่ากัน เราสามารถใช้สัญลักษณ์ใด ๆ ต่อไปนี้เพื่อแสดง Gate นี้ในแผนภาพ Circuit ควอนตัม

สำหรับรูปแบบที่สาม ป้ายกำกับ $\alpha$ ยังบางครั้งวางไว้ที่ด้านข้างของเส้น control หรือใต้ตัว control ล่างเมื่อสะดวก

เพื่อดำเนินการ quantum Fourier transform เมื่อ $N = 2^m$ และ $m\geq 2$ เราต้องดำเนินการ operation บน $m$ qubit ที่การกระทำบน standard basis states สามารถอธิบายได้ว่า

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

โดยที่ $a$ คือบิต และ $y \in \{0,\ldots,2^{m-1} - 1\}$ คือตัวเลขที่เข้ารหัสในรูปฐานสองเป็นสตริง $m-1$ บิต สิ่งนี้สามารถทำได้โดยใช้ controlled-phase gates โดยการขยายตัวอย่างต่อไปนี้ สำหรับ $m=5$

โดยทั่วไป สำหรับตัวเลือก $m\geq 2$ ใด ๆ qubit บนสุดที่สอดคล้องกับบิต $a$ สามารถมองเป็น control โดยมี phase gates $P_{\alpha}$ ตั้งแต่ $\alpha = \pi/2^{m-1}$ บน qubit ที่สอดคล้องกับบิตนัยสำคัญน้อยที่สุดของ $y$ ไปถึง $\alpha = \frac{\pi}{2}$ บน qubit ที่สอดคล้องกับบิตนัยสำคัญมากที่สุดของ $y$ controlled-phase gates เหล่านี้ commute ซึ่งกันและกันและสามารถดำเนินการในลำดับใด ๆ ก็ได้

Circuit ที่นำ QFT ไปใช้

ตอนนี้เราจะดูว่าเราสามารถนำ quantum Fourier transform ไปใช้กับ Circuit ได้อย่างไรเมื่อมิติ $N = 2^m$ เป็นกำลังของ $2$ จริง ๆ มีหลายวิธีในการนำ quantum Fourier transform ไปใช้ แต่นี่น่าจะเป็นวิธีที่ง่ายที่สุดที่รู้จัก เมื่อเรารู้วิธีนำ quantum Fourier transform ไปใช้กับ Circuit ควอนตัม ก็ง่ายที่จะนำ inverse ของมันไปใช้: เราสามารถแทนที่แต่ละ Gate ด้วย inverse ของมัน (หรืออีกนัยหนึ่งคือ conjugate transpose) และใช้ gate ในลำดับย้อนกลับ ทุก Circuit ควอนตัมที่ประกอบด้วย unitary gates ล้วน ๆ สามารถกลับด้านได้ด้วยวิธีนี้

การนำไปใช้นั้นมีลักษณะเป็น recursive ดังนั้นนั่นคือวิธีที่เป็นธรรมชาติที่สุดในการอธิบาย กรณีฐานคือ $m=1$ ซึ่งในกรณีนี้ quantum Fourier transform คือการดำเนินการ Hadamard

เพื่อดำเนินการ quantum Fourier transform บน $m$ qubit เมื่อ $m \geq 2$ เราสามารถดำเนินการตามขั้นตอนต่อไปนี้ ซึ่งการกระทำของมันเราจะอธิบายสำหรับ standard basis states ในรูปแบบ $\vert x \rangle \vert a\rangle$ โดยที่ $x\in\{0,\ldots,2^{m-1} - 1\}$ เป็นจำนวนเต็มที่เข้ารหัสเป็น $m-1$ บิตโดยใช้รูปฐานสอง และ $a$ คือบิตเดี่ยว

1. ดำเนิน quantum Fourier transform มิติ $2^{m-1}$ บน $m-1$ qubit ล่าง/ซ้ายสุดก่อน เพื่อให้ได้ สถานะนี้:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   สิ่งนี้ทำได้โดยการใช้วิธีที่กำลังอธิบายแบบ recursive สำหรับหนึ่ง qubit น้อยกว่า โดยใช้การดำเนินการ Hadamard บน qubit เดี่ยวเป็นกรณีฐาน

2. ใช้ qubit บน/ขวาสุดเป็น control เพื่อฉีดเฟส $\omega_{2^m}^y$ สำหรับแต่ละ standard basis state $\vert y\rangle$ ของ $m-1$ qubit ที่เหลือ (ตามที่อธิบายไว้ข้างต้น) เพื่อให้ได้สถานะนี้:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. ดำเนิน Hadamard gate บน qubit บน/ขวาสุดเพื่อให้ได้สถานะนี้:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. สลับลำดับของ qubit เพื่อให้บิตนัยสำคัญน้อยที่สุดกลายเป็นบิตนัยสำคัญมากที่สุด โดยบิตอื่น ๆ ทั้งหมดเลื่อนขึ้น/ขวา:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

ตัวอย่างเช่น นี่คือ Circuit ที่เราได้สำหรับ $N = 32 = 2^5$ ในแผนภาพนี้ qubit ได้รับชื่อที่สอดคล้องกับ standard basis vectors $\vert x\rangle \vert a\rangle$ (สำหรับอินพุต) และ $\vert b\rangle \vert y\rangle$ (สำหรับเอาต์พุต) เพื่อความชัดเจน

การวิเคราะห์

สูตรสำคัญที่เราต้องการเพื่อตรวจสอบว่า Circuit ที่อธิบายไว้นั้นนำ quantum Fourier transform มิติ $2^m$ ไปใช้คือ:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

สูตรนี้ใช้ได้กับทุกตัวเลือกของจำนวนเต็ม $a,$ $b,$ $x,$ และ $y,$ แต่เราจะต้องการมันเฉพาะสำหรับ $a,b\in\{0,1\}$ และ $x,y\in\{0,\ldots,2^{m-1}-1\}$ มันสามารถตรวจสอบได้โดยการขยายผลคูณในเลขชี้กำลังทางขวามือ

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

โดยที่ความเท่าเทียมที่สองใช้การสังเกตว่า

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

quantum Fourier transform มิติ $2^m$ ถูกกำหนดดังต่อไปนี้สำหรับทุก $u\in\{0,\ldots,2^m - 1\}$

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

ถ้าเราเขียน $u$ และ $v$ เป็น

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

สำหรับ $a,b\in\{0,1\}$ และ $x,y\in\{0,\ldots,2^{m-1} - 1\}$, เราได้

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

สุดท้าย โดยการคิดถึง standard basis states $\vert x \rangle \vert a\rangle$ และ $\vert b \rangle \vert y \rangle$ ในฐานะการเข้ารหัสฐานสองของจำนวนเต็มในช่วง $\{0,\ldots,2^m-1\}$,

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

เราเห็นว่า Circuit ด้านบนนำการดำเนินการที่ต้องการมาใช้ ถ้าวิธีการนำ quantum Fourier transform ไปใช้นี้ดูน่าทึ่ง ก็เพราะมันเป็นเช่นนั้นจริง ๆ: มันคือ fast Fourier transform ในรูปแบบของ Circuit ควอนตัม

สุดท้าย มาลองนับจำนวน gate ที่ใช้ใน Circuit ที่อธิบายไว้ controlled-phase gates ไม่ได้อยู่ใน gate set มาตรฐานที่เราพูดถึงในบทเรียนก่อน แต่ในตอนเริ่มต้นเราจะเพิกเฉยสิ่งนี้และนับแต่ละ gate เป็นหนึ่ง gate

ให้ $s_m$ แทนจำนวน gate ที่เราต้องการสำหรับแต่ละตัวเลือกของ $m$ ที่เป็นไปได้ ถ้า $m=1$, quantum Fourier transform ก็แค่การดำเนินการ Hadamard ดังนั้น

$$s_1 = 1.$$

ถ้า $m\geq 2$, ใน Circuit ด้านบนเราต้องการ $s_{m-1}$ gate สำหรับ quantum Fourier transform บน $m-1$ qubit บวก $m-1$ controlled-phase gates บวก Hadamard gate บวก $m-1$ swap gates ดังนั้น

$$s_m = s_{m-1} + (2m - 1).$$

เราสามารถหานิพจน์รูปปิดได้โดยการหาผลรวม:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

เราไม่จำเป็นต้องใช้ swap gates มากเท่าที่วิธีอธิบายไว้ ถ้าเราจัดเรียง gate ใหม่เล็กน้อย เราสามารถผลัก swap gates ทั้งหมดไปทางขวาและลดจำนวน swap gates ที่ต้องการเหลือ $\lfloor m/2\rfloor$ ในเชิง asymptotic นี่ไม่ใช่การปรับปรุงที่สำคัญ: เรายังคงได้ Circuit ที่มีขนาด $O(m^2)$ สำหรับการดำเนินการ $\mathrm{QFT}_{2^m}$

ถ้าเราต้องการนำ quantum Fourier transform ไปใช้โดยใช้เฉพาะ gate จาก gate set มาตรฐานของเรา เราต้องสร้างหรือประมาณ controlled-phase gates แต่ละตัวด้วย gate จากชุดของเรา จำนวนที่ต้องการขึ้นอยู่กับความแม่นยำที่เราต้องการ แต่ในฐานะฟังก์ชันของ $m$ ต้นทุนรวมยังคงเป็น quadratic

จริง ๆ เป็นไปได้ที่จะประมาณ quantum Fourier transform อย่างใกล้เคียงด้วยจำนวน gate ที่น้อยกว่า quadratic โดยใช้ความจริงที่ว่า $P_{\alpha}$ ใกล้เคียงกับ identity operation มากเมื่อ $\alpha$ เล็กมาก — ซึ่งหมายความว่าเราสามารถเพิกเฉย controlled-phase gates ส่วนใหญ่ได้โดยไม่สูญเสียความแม่นยำมากเกินไป

ขั้นตอนทั่วไปและการวิเคราะห์

ตอนนี้เราจะตรวจสอบขั้นตอนการประมาณเฟสในเชิงทั่วไป แนวคิดคือการขยายเวอร์ชันสอง qubit ของการประมาณเฟสที่เราพิจารณาข้างต้นในแบบธรรมชาติที่แผนภาพต่อไปนี้บอก

สังเกตว่า สำหรับแต่ละ control qubit ใหม่ที่เพิ่มเข้ามาด้านบน เรา เพิ่มสองเท่า จำนวนครั้งที่การดำเนินการ unitary $U$ ถูกดำเนินการ สิ่งนี้ถูกระบุในแผนภาพโดยเลขชี้กำลังบน $U$ สำหรับแต่ละการดำเนินการ controlled-unitary

วิธีที่ตรงไปตรงมาที่สุดในการนำการดำเนินการ controlled-$U^k$ ไปใช้สำหรับตัวเลือก $k$ บางค่าคือการทำซ้ำการดำเนินการ controlled-$U$ $k$ ครั้ง หากนี่คือระเบียบวิธีที่ใช้จริง ๆ ต้องตระหนักว่าการเพิ่ม control qubit มีส่วนทำให้ขนาดของ Circuit เพิ่มขึ้นอย่างมาก: ถ้าเรามี $m$ control qubit ตามที่แผนภาพแสดง จำเป็นต้องใช้ controlled-$U$ รวมทั้งหมด $2^m - 1$ สำเนา ซึ่งหมายความว่ามีต้นทุนการคำนวณที่สำคัญเกิดขึ้นเมื่อ $m$ เพิ่มขึ้น — แต่ดังที่เราจะเห็น มันยังนำไปสู่การประมาณ $\theta$ ที่แม่นยำมากขึ้นอย่างมีนัยสำคัญด้วย

อย่างไรก็ตาม สำคัญที่ต้องสังเกตว่า สำหรับตัวเลือก $U$ บางอย่าง อาจเป็นไปได้ที่จะสร้าง Circuit ที่นำการดำเนินการ $U^k$ สำหรับค่าขนาดใหญ่ของ $k$ ไปใช้ด้วยวิธีที่มีประสิทธิภาพมากกว่าการทำซ้ำ Circuit สำหรับ $U$ $k$ ครั้ง เราจะเห็นตัวอย่างเฉพาะของสิ่งนี้ในบริบทของการแยกตัวประกอบจำนวนเต็มในภายหลังของบทเรียน ที่อัลกอริทึมที่มีประสิทธิภาพสำหรับ modular exponentiation ที่พูดถึงในบทเรียนก่อนหน้าเข้ามาช่วยเหลือ

ตอนนี้มาวิเคราะห์ Circuit ที่อธิบายไว้ สถานะทันทีก่อน inverse quantum Fourier transform มีลักษณะดังนี้:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

กรณีพิเศษ

ในแนวทางคล้ายกับที่เราทำในกรณี $m=2$ เราจะพิจารณากรณีพิเศษก่อนที่ $\theta = y/2^m$ สำหรับ $y\in\{0,\ldots,2^m-1\}$ ในกรณีนี้ สถานะก่อน inverse quantum Fourier transform สามารถเขียนได้อีกแบบดังนี้:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

ดังนั้น เมื่อใช้ inverse quantum Fourier transform สถานะจะกลายเป็น

$$\vert\psi\rangle \vert y\rangle$$

และการวัดจะเปิดเผย $y$ (เข้ารหัสในฐานสอง)

การหา bound ของความน่าจะเป็น

สำหรับค่า $\theta$ อื่น ๆ หมายถึงค่าที่ไม่อยู่ในรูป $y/2^m$ สำหรับจำนวนเต็ม $y$ ผลการวัดจะไม่แน่นอน แต่เราสามารถพิสูจน์ bound บนความน่าจะเป็นสำหรับผลลัพธ์ต่าง ๆ ได้ ต่อจากนี้ มาพิจารณาตัวเลือก $\theta$ ใด ๆ ที่ตรงตาม $0\leq \theta < 1$

หลังจากดำเนิน inverse quantum Fourier transform สถานะของ Circuit คือ:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

ดังนั้น เมื่อดำเนินการวัดบน $m$ qubit บนสุด เราจะเห็นผลลัพธ์ $y$ แต่ละอันด้วยความน่าจะเป็น

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

เพื่อเข้าใจความน่าจะเป็นเหล่านี้ให้ดีขึ้น เราจะใช้สูตรเดิมที่เราเห็นก่อนหน้า สำหรับผลรวมของส่วนแรกของอนุกรมเรขาคณิต

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

เราสามารถลดรูปผลรวมที่ปรากฏในสูตรสำหรับ $p_y$ โดยใช้ $\alpha = e^{2\pi i (\theta - y/2^m)}$ นี่คือสิ่งที่เราได้

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

ดังนั้น ในกรณีที่ $\theta = y/2^m$ เราพบว่า $p_y = 1$ (ดังที่เราทราบอยู่แล้วจากการพิจารณากรณีพิเศษนี้) และในกรณีที่ $\theta \neq y/2^m$ เราพบว่า

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

เราสามารถเรียนรู้เพิ่มเติมเกี่ยวกับความน่าจะเป็นเหล่านี้โดยการคิดถึงความสัมพันธ์ระหว่างความยาวส่วนโค้งและความยาวคอร์ดบนวงกลมหน่วย นี่คือรูปที่แสดงความสัมพันธ์ที่เราต้องการสำหรับจำนวนจริง $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$ ใด ๆ

ก่อนอื่น ความยาวคอร์ด (วาดเป็นสีน้ำเงิน) ไม่สามารถมากกว่าความยาวส่วนโค้ง (วาดเป็นสีม่วง) ได้:

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

เมื่อเชื่อมโยงความยาวเหล่านี้ในทิศทางอื่น เราเห็นว่าอัตราส่วนของความยาวส่วนโค้งต่อความยาวคอร์ดมีค่ามากที่สุดเมื่อ $\delta = \pm 1/2$ และในกรณีนี้อัตราส่วนคือครึ่งหนึ่งของเส้นรอบวงของวงกลมหารด้วยเส้นผ่านศูนย์กลาง ซึ่งคือ $\pi/2$ ดังนั้น เรามี

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

และดังนั้น

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

การวิเคราะห์ที่อิงจากความสัมพันธ์เหล่านี้เปิดเผยข้อเท็จจริงสองอย่างต่อไปนี้

1. สมมติว่า $\theta$ เป็นจำนวนจริงและ $y\in \{0,\ldots,2^m-1\}$ ตรงตาม

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   ซึ่งหมายความว่า $y/2^m$ เป็นการประมาณ $m$-bit ที่ดีที่สุดของ $\theta$ หรืออยู่กึ่งกลางพอดีระหว่าง $y/2^m$ กับ $(y-1)/2^m$ หรือ $(y+1)/2^m$ ดังนั้นมันคือหนึ่งในสองการประมาณที่ดีที่สุดของ $\theta$

   เราจะพิสูจน์ว่า $p_y$ ต้องค่อนข้างใหญ่ในกรณีนี้ จากสมมติฐานที่เราพิจารณา ตามมาว่า $\vert 2^m \theta - y \vert \leq 1/2$ ดังนั้นเราสามารถใช้การสังเกตที่สองด้านบนเกี่ยวกับความสัมพันธ์ส่วนโค้งและคอร์ดเพื่อสรุปว่า

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   เราสามารถใช้การสังเกตแรกเกี่ยวกับความสัมพันธ์ส่วนโค้งและคอร์ดเพื่อสรุปว่า

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   การนำสองอสมการนี้ไปใช้กับ $p_y$ เปิดเผยว่า

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   สิ่งนี้อธิบายการสังเกตของเราว่าผลลัพธ์ที่ดีที่สุดเกิดขึ้นด้วยความน่าจะเป็นมากกว่า $40\%$ ในเวอร์ชัน $m=2$ ของการประมาณเฟสที่พูดถึงก่อนหน้า จริง ๆ ไม่ใช่ $40\%$ แต่คือ $4/\pi^2$ และในความเป็นจริง bound นี้ใช้ได้กับทุกตัวเลือกของ $m$

2. สมมติว่า $y\in \{0,\ldots,2^m-1\}$ ตรงตาม

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   ซึ่งหมายความว่ามีค่าประมาณ $z/2^m$ ของ $\theta$ ที่ดีกว่า อยู่ระหว่าง $\theta$ กับ $y/2^m$

   คราวนี้เราจะพิสูจน์ว่า $p_y$ ไม่สามารถใหญ่เกินไป เราสามารถเริ่มจากการสังเกตง่าย ๆ ว่า

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   ซึ่งตามมาจากความจริงที่ว่าสองจุดบนวงกลมหน่วยสามารถต่างกันในค่าสัมบูรณ์ได้มากที่สุด $2$

   เราสามารถใช้การสังเกตที่สองเกี่ยวกับความสัมพันธ์ส่วนโค้งและคอร์ดจากด้านบน คราวนี้ทำงานกับตัวส่วนของ $p_y$ แทนที่จะเป็นตัวเศษ เพื่อสรุปว่า

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   การนำสองอสมการมารวมกันเปิดเผยว่า

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   โปรดสังเกตว่า แม้ bound นี้เพียงพอสำหรับจุดประสงค์ของเรา แต่มันค่อนข้าง crude — ความน่าจะเป็นมักต่ำกว่า $1/4$ มาก

ข้อสรุปสำคัญจากการวิเคราะห์นี้คือการประมาณที่ใกล้เคียง $\theta$ มากมีแนวโน้มที่จะเกิดขึ้น — เราจะได้การประมาณ $m$-bit ที่ดีที่สุดด้วยความน่าจะเป็นมากกว่า $40\%$ — ในขณะที่การประมาณที่ต่างออกไปมากกว่า $2^{-m}$ มีแนวโน้มที่จะเกิดขึ้นน้อยกว่า โดยมีความน่าจะเป็นที่มีขอบเขตบนอยู่ที่ $25\%$

เมื่อมีการรับประกันเหล่านี้ เป็นไปได้ที่จะเพิ่มความเชื่อมั่นของเราโดยการทำซ้ำขั้นตอนการประมาณเฟสหลายครั้ง เพื่อรวบรวมหลักฐานทางสถิติเกี่ยวกับ $\theta$ สำคัญที่ต้องสังเกตว่าสถานะ $\vert\psi\rangle$ ของ qubit กลุ่มล่างไม่เปลี่ยนแปลงจากขั้นตอนการประมาณเฟส ดังนั้นจึงสามารถใช้เรียกขั้นตอนนี้ได้กี่ครั้งก็ได้ โดยเฉพาะอย่างยิ่ง แต่ละครั้งที่เราเรียกใช้ Circuit เราจะได้การประมาณ $m$-bit ที่ดีที่สุดของ $\theta$ ด้วยความน่าจะเป็นมากกว่า $40\%$ ในขณะที่ความน่าจะเป็นที่จะต่างออกไปมากกว่า $2^{-m}$ มีขอบเขตอยู่ที่ $25\%$ ถ้าเราเรียกใช้ Circuit หลายครั้งและนำผลลัพธ์ที่ปรากฏบ่อยที่สุดจากการเรียกใช้ มันจึงมีแนวโน้มอย่างมากว่าผลลัพธ์ที่ปรากฏบ่อยที่สุดจะไม่ใช่ผลลัพธ์ที่เกิดขึ้นได้มากที่สุด $25\%$ ของเวลา ด้วยเหตุนี้ เราจะมีแนวโน้มสูงที่จะได้การประมาณ $y/2^m$ ที่อยู่ภายใน $1/2^m$ จากค่า $\theta$ แท้จริงแล้ว โอกาสที่ไม่น่าจะเป็นที่เราจะต่างออกไปมากกว่า $1/2^m$ ลดลงแบบ exponential ตามจำนวนครั้งที่เรียกใช้ขั้นตอน

นี่คือกราฟสองกราฟที่แสดงความน่าจะเป็นสำหรับสามค่าต่อเนื่องของ $y$ เมื่อ $m = 3$ และ $m=4$ ในฐานะฟังก์ชันของ $\theta$ (แสดงเฉพาะสามผลลัพธ์เพื่อความชัดเจน ความน่าจะเป็นสำหรับผลลัพธ์อื่น ๆ ได้จากการเลื่อน cyclic ของฟังก์ชันพื้นฐานเดิม)