การคำนวณแบบคลาสสิกบนคอมพิวเตอร์ควอนตัม

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

การจำลองวงจรบูลีนด้วยวงจรควอนตัม

วงจรบูลีนประกอบด้วย Gate AND, OR, NOT, และ FANOUT เพื่อจำลองวงจรบูลีนด้วยวงจรควอนตัม เราจะเริ่มต้นด้วยการแสดงให้เห็นว่า Gate ทั้งสี่ตัวนั้นสามารถจำลองด้วย Gate ควอนตัมได้อย่างไร เมื่อทำเสร็จแล้ว การแปลงวงจรบูลีนที่กำหนดเป็นวงจรควอนตัมเป็นเรื่องง่ายแค่การจำลองทีละ Gate เราจะต้องการเพียง NOT Gate, controlled-NOT Gate, และ Toffoli Gate ในการทำสิ่งนี้ ซึ่งทั้งหมดเป็นการดำเนินการแบบ deterministic นอกเหนือจากเป็น unitary

Toffoli Gate

Toffoli Gate สามารถอธิบายได้อีกทางว่าเป็น controlled-controlled-NOT Gate ซึ่งมีการกระทำบนสถานะฐานมาตรฐานดังที่แสดงในภาพต่อไปนี้

โดยคำนึงว่าเราใช้แบบแผนการจัดเรียงของ Qiskit ซึ่ง Qubit ถูกจัดเรียงในลำดับนัยสำคัญที่เพิ่มขึ้นจากบนลงล่าง การแสดงแทนเมทริกซ์ของ Gate นี้มีดังนี้

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

อีกวิธีคิดเกี่ยวกับ Toffoli Gate คือโดยพื้นฐานแล้วมันเป็น query gate สำหรับฟังก์ชัน AND ในแง่ที่ว่ามันเป็นไปตามรูปแบบที่เราเห็นในบทเรียนก่อนหน้าสำหรับการใช้งาน unitary query gate ของฟังก์ชันใดๆ ที่มีอินพุตและเอาต์พุตเป็นสตริงไบนารี

Toffoli Gate ไม่ได้รวมอยู่ในชุด Gate ค่าเริ่มต้นที่พูดถึงก่อนหน้าในบทเรียน แต่เป็นไปได้ที่จะสร้าง Toffoli Gate จาก Gate $H,$ $T,$ $T^{\dagger},$ และ CNOT ดังนี้

การจำลอง Boolean Gate ด้วย Toffoli, controlled-NOT, และ NOT Gate

Toffoli Gate หนึ่งตัว ใช้ร่วมกับ NOT Gate สองสามตัว สามารถใช้งาน AND และ OR Gate ได้ และ FANOUT Gate สามารถใช้งานได้ง่ายโดยใช้ controlled-NOT Gate ดังที่ภาพต่อไปนี้แนะนำ

ในทั้งสามกรณี Qubit ที่ AND, OR, และ FANOUT Gate กระทำบนจะมาจากด้านซ้ายเป็นอินพุต และเรายังต้องการ Qubit workspace หนึ่งตัวที่เริ่มต้นในสถานะศูนย์สำหรับแต่ละตัว Qubit workspace เหล่านี้ปรากฏอยู่ในกล่องที่แสดงการใช้งาน Gate เพื่อแนะนำว่าเป็นของใหม่ และดังนั้นเป็นส่วนหนึ่งของต้นทุนของการใช้งานเหล่านี้

สำหรับ AND และ OR Gate เรายังมี Qubit สองตัวเหลืออยู่ นอกเหนือจาก Qubit เอาต์พุต ตัวอย่างเช่น ภายในกล่องในภาพที่แสดงการจำลองของ AND Gate Qubit สองตัวบนถูกปล่อยอยู่ในสถานะ $\vert a\rangle$ และ $\vert b\rangle$ Qubit เหล่านี้แสดงว่าอยู่ภายในกล่องเพราะไม่จำเป็นต้องใช้อีกต่อไปและไม่ได้เป็นส่วนหนึ่งของเอาต์พุต พวกมันสามารถถูกละเลยในตอนนี้ แม้ว่าเราจะหันมาสนใจพวกมันในไม่ช้า

Boolean Gate ที่เหลือคือ NOT Gate รวมอยู่ในชุด Gate ควอนตัมค่าเริ่มต้นของเรา ดังนั้นเราไม่จำเป็นต้องจำลองตัวนี้

การจำลอง Gate ต่อ Gate ของวงจรบูลีน

ทีนี้สมมติว่าเรามีวงจรบูลีนธรรมดาชื่อ $C$ ที่ประกอบด้วย AND, OR, NOT, และ FANOUT Gate และมีบิตอินพุต $n$ บิตและเอาต์พุต $m$ บิต กำหนด $t = \operatorname{size}(C)$ เป็นจำนวน Gate ใน $C$ และตั้งชื่อ $f$ ให้กับฟังก์ชันที่ $C$ คำนวณ ซึ่งมีรูปแบบ

$$f:\Sigma^n\rightarrow\Sigma^m$$

สำหรับ $\Sigma = \{0,1\}$

ทีนี้พิจารณาสิ่งที่เกิดขึ้นเมื่อเราไปทีละตัวผ่าน AND, OR, และ FANOUT Gate ของ $C$ แทนที่แต่ละตัวด้วยการจำลองที่สอดคล้องกันที่อธิบายข้างต้น รวมถึงการเพิ่ม Qubit workspace ที่จำเป็น ตั้งชื่อวงจรที่ได้ว่า $R$ และจัดเรียง Qubit ของ $R$ ให้บิตอินพุต $n$ บิตของ $C$ สอดคล้องกับ Qubit บนสุด $n$ ตัวของ $R$ และ Qubit workspace อยู่ด้านล่าง

ที่นี่ $k$ คือจำนวน Qubit workspace ที่จำเป็น ซึ่งหนึ่งตัวสำหรับแต่ละ AND, OR, และ FANOUT Gate ของ $C$ และ $g$ เป็นฟังก์ชันในรูปแบบ $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ ที่อธิบายสถานะของ Qubit ที่เหลืออยู่ที่สร้างโดยการจำลอง Gate หลังจากรัน $R$ ในภาพ Qubit ที่สอดคล้องกับเอาต์พุต $f(x)$ อยู่ด้านบนและ Qubit ที่เหลืออยู่ที่จัดเก็บ $g(x)$ อยู่ด้านล่าง เราสามารถบังคับให้เป็นเช่นนี้ได้ถ้าต้องการโดยจัดเรียง Qubit ใหม่โดยใช้ SWAP Gate ซึ่งสามารถใช้งานได้ด้วย controlled-NOT Gate สามตัวแบบนี้:

อย่างที่เราจะเห็นในส่วนถัดไป ไม่จำเป็นต้องจัดเรียง Qubit เอาต์พุตใหม่แบบนี้จริงๆ แต่ก็ง่ายพอที่จะทำถ้าเลือก

ฟังก์ชัน $g$ ที่อธิบายสถานะคลาสสิกของ Qubit ที่เหลืออยู่ถูกกำหนดโดยวงจร $C$ แต่จริงๆ แล้วเราไม่จำเป็นต้องกังวลมากนักเกี่ยวกับมัน เราไม่สนใจโดยเฉพาะว่า Qubit เหล่านี้อยู่ในสถานะอะไรเมื่อการคำนวณเสร็จสิ้น ตัวอักษร $g$ มาหลัง $f$ ดังนั้นเป็นชื่อที่สมเหตุสมผลสำหรับฟังก์ชันนี้ด้วยเหตุนั้น แต่มีเหตุผลที่ดีกว่าในการเลือกชื่อ $g$ มันย่อมาจาก garbage (ขยะ)

การเก็บกวาดขยะ

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

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

โชคดี ไม่ยากที่จะเก็บกวาดขยะ กุญแจสำคัญคือการใช้ข้อเท็จจริงที่ว่าเนื่องจาก $R$ เป็นวงจรควอนตัม เราสามารถรันมันย้อนกลับได้ โดยเพียงแทนที่แต่ละ Gate ด้วย inverse ของมันและใช้พวกมันในลำดับย้อนกลับ จึงได้วงจรควอนตัมสำหรับการดำเนินการ $R^{\dagger}$ Toffoli Gate, CNOT Gate, และ NOT Gate จริงๆ แล้วเป็น inverse ของตัวเอง ดังนั้นการรัน $R$ ย้อนกลับเป็นเรื่องของการใช้ Gate ในลำดับย้อนกลับเท่านั้น แต่โดยทั่วไปมากขึ้น วงจรควอนตัมใดๆ สามารถย้อนกลับได้ดังที่เพิ่งอธิบาย

โดยเฉพาะอย่างยิ่ง สิ่งที่เราสามารถทำได้คือเพิ่ม Qubit อีก $m$ ตัว (โดยระลึกว่าฟังก์ชัน $f$ มีบิตเอาต์พุต $m$ บิต) ใช้ CNOT Gate เพื่อคัดลอกเอาต์พุตของ $R$ ไปยัง Qubit เหล่านี้ และย้อนกลับ $R$ เพื่อเก็บกวาดขยะ ภาพต่อไปนี้แสดงวงจรที่ได้และอธิบายการกระทำบนสถานะฐานมาตรฐาน

ถ้าเราใส่กล่องล้อมรอบวงจรทั้งหมดและเรียกมันว่า $Q$ มันจะมีลักษณะดังนี้:

เมื่อ $C$ มี Gate $t$ ตัว วงจร $Q$ จะมี Gate $O(t)$ ตัว

ถ้าเราละเลย Qubit workspace $k$ ตัวเพิ่มเติม สิ่งที่เรามีคือวงจร $Q$ ที่ทำงานเหมือน query gate สำหรับฟังก์ชัน $f$ พอดี ถ้าเราแค่ต้องการคำนวณฟังก์ชัน $f$ บนสตริง $x$ บางตัว เราสามารถตั้งค่า $y = 0^m$ และค่าที่ได้ $f(x)$ จะปรากฏบน Qubit $m$ ตัวล่าง หรือเราสามารถป้อนสถานะที่แตกต่างออกไปให้กับ Qubit $m$ ตัวล่างถ้าต้องการ (อาจจะเพื่อใช้ประโยชน์จาก phase kickback เหมือนในอัลกอริทึมของ Deutsch หรือ Deutsch-Jozsa)

ซึ่งหมายความว่าสำหรับอัลกอริทึม query ใดๆ ถ้าเรามีวงจรบูลีนที่คำนวณฟังก์ชันอินพุต เราสามารถแทนที่แต่ละ query gate ด้วยการใช้งาน Circuit ของมัน และอัลกอริทึม query จะทำงานอย่างถูกต้อง

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

การใช้งานฟังก์ชันที่ invertible

การสร้างที่อธิบายไว้ช่วยให้เราจำลองวงจรบูลีนใดๆ ด้วยวงจรควอนตัมในลักษณะที่ปราศจากขยะ ถ้า $C$ เป็นวงจรบูลีนที่ใช้งานฟังก์ชัน $f:\Sigma^n \rightarrow \Sigma^m$ เราจะได้วงจรควอนตัม $Q$ ที่ดำเนินการดังนี้บนสถานะฐานมาตรฐาน

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

จำนวน $k$ บ่งบอกว่าต้องใช้ Qubit workspace ทั้งหมดกี่ตัว เพียงพอสำหรับวัตถุประสงค์ของคอร์สนี้ แต่เป็นไปได้ที่จะใช้ methodology นี้อีกก้าวหนึ่งเมื่อฟังก์ชัน $f$ เองเป็น invertible

เพื่อความแม่นยำ สมมติว่าฟังก์ชัน $f$ มีรูปแบบ $f:\Sigma^n \rightarrow \Sigma^n$ และสมมติด้วยว่ามีฟังก์ชัน $f^{-1}$ โดยที่ $f^{-1}(f(x)) = x$ สำหรับทุก $x\in\Sigma^n$ (ซึ่งมีอยู่เฉพาะตัวเสมอเมื่อมีอยู่) ซึ่งหมายความว่าการดำเนินการที่แปลง $\vert x \rangle$ เป็น $\vert f(x) \rangle$ สำหรับทุก $x\in\Sigma^n$ เป็น unitary ดังนั้นเราอาจหวังที่จะสร้างวงจรควอนตัมที่ใช้งานการดำเนินการ unitary ที่กำหนดโดย

$$U \vert x \rangle = \vert f(x) \rangle$$

สำหรับทุก $x\in\Sigma^n$

เพื่อความชัดเจน ความเป็นจริงที่ว่านี่เป็นการดำเนินการ unitary ขึ้นอยู่กับ $f$ ที่เป็น invertible มันไม่ใช่ unitary เมื่อ $f$ ไม่ใช่ invertible โดยไม่คำนึงถึง Qubit workspace $U$ แตกต่างจากการดำเนินการที่วงจร $Q$ ใช้งานเพราะเราไม่ได้เก็บสำเนาของอินพุตไว้และ XOR ไปยังสตริงที่ arbitrary เราแทนที่ $x$ ด้วย $f(x)$

คำถามคือ: เมื่อ $f$ เป็น invertible เราสามารถทำสิ่งนี้ได้หรือไม่?

คำตอบคือใช่ โดยต้องอนุญาตให้ใช้ Qubit workspace และนอกเหนือจากมีวงจรบูลีนที่คำนวณ $f$ เรายังต้องมีวงจรที่คำนวณ $f^{-1}$ ด้วย ดังนั้น นี่ไม่ใช่ทางลัดสำหรับการ invert ฟังก์ชันในเชิงการคำนวณเมื่อเราไม่รู้วิธีทำแล้ว! ภาพต่อไปนี้แสดงให้เห็นว่าสามารถทำได้อย่างไรโดยการประกอบวงจรควอนตัมสองตัว $Q_f$ และ $Q_{f^{-1}}$ ซึ่งได้มาแยกกันสำหรับฟังก์ชัน $f$ และ $f^{-1}$ ผ่านวิธีการที่อธิบายข้างต้น ร่วมกับ SWAP Gate $n$ ตัว โดยกำหนดให้ $k$ เป็นค่าสูงสุดของจำนวน Qubit workspace ที่ $Q_f$ และ $Q_{f^{-1}}$ ต้องการ