โมเดล query ของการคำนวณ

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

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

ประเด็นสำคัญคืออินพุตถูกป้อนให้กับการคำนวณ โดยปกติในรูปของสตริงไบนารี โดยไม่มีส่วนใดที่ซ่อนไว้

คำอธิบายของโมเดล

ใน โมเดล query ของการคำนวณ อินพุตทั้งหมดไม่ได้ถูกป้อนให้กับการคำนวณเหมือนในโมเดลมาตรฐานที่แนะนำข้างต้น แต่อินพุตถูกทำให้พร้อมใช้งานในรูปแบบของ ฟังก์ชัน ซึ่งการคำนวณเข้าถึงโดยการทำ query อีกทางหนึ่ง เราอาจมองการคำนวณในโมเดล query ว่ามี random access ไปยังบิต (หรือส่วนของบิต) ของอินพุต

เรามักอ้างถึงอินพุตว่าถูกให้มาโดย oracle หรือ black box ในบริบทของโมเดล query ทั้งสองคำแนะนำว่าคำอธิบายสมบูรณ์ของอินพุตถูกซ่อนจากการคำนวณ โดยวิธีเดียวในการเข้าถึงมันคือการถามคำถาม เหมือนกับว่าเราปรึกษา Oracle ที่ Delphi เกี่ยวกับอินพุต: เธอจะไม่บอกทุกอย่างที่รู้ เธอตอบเฉพาะคำถามที่เจาะจง คำว่า black box สมเหตุสมผลโดยเฉพาะเมื่อเราคิดเกี่ยวกับอินพุตที่แสดงด้วยฟังก์ชัน เราไม่สามารถมองเข้าไปในฟังก์ชันและเข้าใจวิธีการทำงานของมัน เราสามารถประเมินมันบนอาร์กิวเมนต์ที่เราเลือกเท่านั้น

เราจะทำงานเฉพาะกับสตริงไบนารีในบทเรียนนี้ แทนที่จะเป็นสตริงที่มีสัญลักษณ์ต่างกัน ดังนั้นเขียน $\Sigma = \{0,1\}$ ต่อไปเพื่ออ้างถึงอักษรไบนารีเพื่อความสะดวก เราจะคิดเกี่ยวกับปัญหาการคำนวณที่แตกต่างกัน พร้อมตัวอย่างง่ายๆ ที่อธิบายในไม่ช้า แต่สำหรับทั้งหมดอินพุตจะถูกแทนด้วยฟังก์ชันในรูปแบบ

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

สำหรับจำนวนเต็มบวก $n$ และ $m$ สองตัว แน่นอน เราสามารถเลือกชื่ออื่นแทน $f$ ได้ แต่เราจะใช้ $f$ ตลอดบทเรียน

การบอกว่าการคำนวณทำ query หมายความว่าสตริง $x \in \Sigma^n$ บางตัวถูกเลือก จากนั้นสตริง $f(x)\in\Sigma^m$ ถูกทำให้พร้อมใช้งานสำหรับการคำนวณโดย oracle วิธีที่แม่นยำที่สิ่งนี้ทำงานสำหรับอัลกอริทึมควอนตัมจะกล่าวถึงในไม่ช้า เราต้องแน่ใจว่าสิ่งนี้เป็นไปได้ด้วยการดำเนินการควอนตัม unitary ที่อนุญาตให้ทำ query ใน superposition ได้ แต่สำหรับตอนนี้เราสามารถคิดเกี่ยวกับมันโดยสัญชาตญาณในระดับสูง

สุดท้าย วิธีที่เราวัดประสิทธิภาพของอัลกอริทึม query นั้นง่าย: เราจะนับ จำนวน query ที่พวกมันต้องการ สิ่งนี้เกี่ยวข้องกับเวลาที่จำเป็นในการดำเนินการคำนวณ แต่ไม่เหมือนกันทีเดียวเพราะเราละเลยเวลาสำหรับการดำเนินการอื่นๆ นอกเหนือจาก query และยังถือว่าแต่ละ query มีต้นทุนหน่วย เราสามารถคำนึงถึงการดำเนินการนอกเหนือจาก query ได้ถ้าต้องการ (และบางครั้งก็ทำเช่นนั้น) แต่การจำกัดความสนใจไว้ที่แค่จำนวน query ช่วยให้สิ่งต่างๆ เรียบง่าย

ตัวอย่างของปัญหา query

นี่คือตัวอย่างง่ายๆ สักสองสามอย่างของปัญหา query

• OR. ฟังก์ชันอินพุตมีรูปแบบ $f:\Sigma^n \rightarrow \Sigma$ (ดังนั้น $m=1$ สำหรับปัญหานี้) งานคือการแสดงผลลัพธ์ $1$ ถ้ามีสตริง $x\in\Sigma^n$ ที่ $f(x) = 1$ และแสดง $0$ ถ้าไม่มีสตริงดังกล่าว ถ้าคิดเกี่ยวกับฟังก์ชัน $f$ ว่าแทนลำดับของบิต $2^n$ บิตที่เราเข้าถึงแบบ random access ปัญหาคือการคำนวณ OR ของบิตเหล่านี้

• Parity. ฟังก์ชันอินพุตมีรูปแบบ $f:\Sigma^n \rightarrow \Sigma$ อีกครั้ง งานคือการกำหนดว่าจำนวนสตริง $x\in\Sigma^n$ ที่ $f(x) = 1$ เป็น คู่ หรือ คี่ เพื่อความแม่นยำ เอาต์พุตที่ต้องการคือ $0$ ถ้าเซต $\{x\in\Sigma^n : f(x) = 1\}$ มีจำนวนคู่ และ $1$ ถ้ามีจำนวนคี่ ถ้าคิดเกี่ยวกับฟังก์ชัน $f$ ว่าแทนลำดับของบิต $2^n$ บิตที่เราเข้าถึงแบบ random access ปัญหาคือการคำนวณ parity (หรือ exclusive-OR) ของบิตเหล่านี้

• Minimum. ฟังก์ชันอินพุตมีรูปแบบ $f:\Sigma^n \rightarrow \Sigma^m$ สำหรับการเลือกจำนวนเต็มบวก $n$ และ $m$ ใดๆ เอาต์พุตที่ต้องการคือสตริง $y \in \{f(x) : x\in\Sigma^n\}$ ที่มาก่อนในลำดับ lexicographic (นั่นคือ dictionary) ของ $\Sigma^m$ ถ้าคิดเกี่ยวกับฟังก์ชัน $f$ ว่าแทนลำดับของจำนวนเต็ม $2^n$ ตัวที่เข้ารหัสเป็นสตริงความยาว $m$ ในสัญกรณ์ไบนารีที่เราเข้าถึงแบบ random access ปัญหาคือการคำนวณค่าต่ำสุดของจำนวนเต็มเหล่านี้

เรายังพิจารณาปัญหา query ที่เรามี promise บนอินพุตด้วย ความหมายคือเราได้รับการรับประกันบางอย่างเกี่ยวกับอินพุต และเราไม่ต้องรับผิดชอบว่าจะเกิดอะไรขึ้นเมื่อการรับประกันนี้ไม่เป็นที่พอใจ วิธีอื่นในการอธิบายปัญหาประเภทนี้คือบอกว่าอินพุตบางตัว (ตัวที่ promise ไม่ถูกตอบสนอง) ถูกพิจารณาว่าเป็นอินพุต "don't care" ไม่มีข้อกำหนดใดๆ เลยที่วางบนอัลกอริทึมเมื่อได้รับอินพุต "don't care"

นี่คือตัวอย่างหนึ่งของปัญหาที่มี promise:

• Unique search. ฟังก์ชันอินพุตมีรูปแบบ $f:\Sigma^n \rightarrow \Sigma$ และเรา promised ว่ามีสตริงเดียว $z\in\Sigma^n$ ที่ $f(z) = 1$ โดยที่ $f(x) = 0$ สำหรับสตริงทั้งหมด $x\neq z$ งานคือการหาสตริงเดียวนี้ $z$

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

ในทางกลับกัน ปัญหา query บางอย่างไม่ "เป็นธรรมชาติ" แบบนี้เลย จริงๆ แล้ว ในการศึกษาโมเดล query บางครั้งเราคิดปัญหาที่ซับซ้อนและประดิษฐ์ขึ้นมากที่ยากที่จะจินตนาการว่าใครจะต้องการแก้จริงๆ นั่นไม่ได้หมายความว่าปัญหาไม่น่าสนใจ! สิ่งที่อาจดูประดิษฐ์หรือไม่เป็นธรรมชาติในตอนแรกสามารถให้เบาะแสที่ไม่คาดคิดหรือสร้างแรงบันดาลใจให้เกิดความคิดใหม่ๆ อัลกอริทึมควอนตัมของ Shor สำหรับการแยกตัวประกอบ ซึ่งได้รับแรงบันดาลใจจากอัลกอริทึมของ Simon เป็นตัวอย่างที่ดี ยังเป็นส่วนสำคัญของการศึกษาโมเดล query ที่จะมองหาขอบเขต ซึ่งสามารถให้ความกระจ่างเกี่ยวกับทั้งข้อได้เปรียบที่มีศักยภาพและข้อจำกัดของควอนตัมคอมพิวติ้ง

Query Gate

เมื่อเราอธิบายการคำนวณด้วยวงจร query จะทำโดย Gate พิเศษที่เรียกว่า query gate

วิธีที่ง่ายที่สุดในการนิยาม query gate สำหรับวงจรบูลีนคลาสสิกคือการอนุญาตให้พวกมันคำนวณฟังก์ชันอินพุต $f$ โดยตรง ดังที่ภาพต่อไปนี้แนะนำ

เมื่อมีการสร้างวงจรบูลีนสำหรับปัญหา query ฟังก์ชันอินพุต $f$ ถูกเข้าถึงผ่าน Gate เหล่านี้ และจำนวน query ที่วงจรทำเป็นเพียงจำนวน query gate ที่ปรากฏในวงจร สายอินพุตของวงจรบูลีนเองถูกเริ่มต้นด้วยค่าตายตัว ซึ่งควรพิจารณาเป็นส่วนหนึ่งของอัลกอริทึม (แทนที่จะเป็นอินพุตสำหรับปัญหา)

ตัวอย่างเช่น นี่คือวงจรบูลีนที่มี classical query gate ที่แก้ปัญหา parity ที่อธิบายข้างต้นสำหรับฟังก์ชันในรูปแบบ $f:\Sigma\rightarrow\Sigma$:

อัลกอริทึมนี้ทำ query สองครั้งเพราะมี query gate สองตัว วิธีการทำงานคือฟังก์ชัน $f$ ถูก query บนอินพุตที่เป็นไปได้สองตัว คือ $0$ และ $1$ และผลลัพธ์ถูกนำไปใช้ในวงจรบูลีนที่คำนวณ XOR (วงจรเฉพาะนี้ปรากฏเป็นตัวอย่างของวงจรบูลีนในบทเรียน Quantum circuits ของคอร์ส Basics of quantum information)

สำหรับวงจรควอนตัม คำจำกัดความของ query gate นี้ไม่ได้ผล เพราะ Gate เหล่านี้จะเป็น non-unitary สำหรับการเลือกฟังก์ชัน $f$ บางตัว ดังนั้น สิ่งที่เราทำแทนคือนิยาม unitary query gate ที่ดำเนินการดังที่ภาพนี้แนะนำบนสถานะฐานมาตรฐาน:

ที่นี่ เราสมมติว่า $x\in\Sigma^n$ และ $y\in\Sigma^m$ เป็นสตริงที่ arbitrary สัญกรณ์ $y\oplus f(x)$ หมายถึง bitwise exclusive-OR ของสตริงสองตัว ซึ่งมีความยาว $m$ ในกรณีนี้ ตัวอย่างเช่น $001 \oplus 101 = 100$

โดยสัญชาตญาณ สิ่งที่ Gate $U_f$ ทำ (สำหรับฟังก์ชัน $f$ ที่เลือก) คือสะท้อนสตริงอินพุต $x$ ด้านบนและ XOR ค่าฟังก์ชัน $f(x)$ ไปยังสตริงอินพุต $y$ ด้านล่าง ซึ่งเป็นการดำเนินการ unitary สำหรับทุกการเลือกของฟังก์ชัน $f$ จริงๆ แล้ว มันเป็นการดำเนินการแบบ deterministic และเป็น inverse ของตัวเอง ซึ่งหมายความว่าในฐานะเมทริกซ์ $U_f$ เป็น permutation matrix เสมอ ซึ่งหมายถึงเมทริกซ์ที่มี $1$ เดียวในแต่ละแถวและแต่ละคอลัมน์ โดยรายการอื่นทั้งหมดเป็น $0$ การคูณ permutation matrix กับเวกเตอร์เพียงแค่สับเปลี่ยนรายการของเวกเตอร์ (จึงเป็นที่มาของคำว่า permutation matrix) และดังนั้นไม่เปลี่ยนค่า Euclidean norm ของเวกเตอร์นั้น ซึ่งเผยให้เห็นว่า permutation matrix เป็น unitary เสมอ

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

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