การค้นหาแบบไม่มีโครงสร้าง

สรุปภาพรวม

เราจะเริ่มด้วยคำอธิบายของปัญหาที่อัลกอริทึม Grover แก้ ตามธรรมเนียม ให้ $\Sigma = \{0,1\}$ แทน binary alphabet ตลอดการพูดถึงนี้

สมมติว่า

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

คือฟังก์ชันจาก binary strings ความยาว $n$ ไปยัง bits เราจะสมมติว่าสามารถคำนวณฟังก์ชันนี้ได้อย่างมีประสิทธิภาพ แต่นอกจากนั้นมันเป็นฟังก์ชันใด ๆ ก็ได้ และเราไม่สามารถพึ่งพาให้มันมีโครงสร้างพิเศษหรือ implementation เฉพาะที่ตรงกับความต้องการของเรา

สิ่งที่อัลกอริทึม Grover ทำคือค้นหา string $x\in\Sigma^n$ ที่ $f(x) = 1$ เราจะเรียก strings เหล่านี้ว่า solutions ของปัญหาการค้นหา ถ้ามี solutions หลายตัว ตัวใดตัวหนึ่งก็ถือว่าเป็น output ที่ถูกต้อง และถ้าไม่มี solutions เลย คำตอบที่ถูกต้องต้องรายงานว่าไม่มี solutions

งานนี้เรียกว่าปัญหา unstructured search เพราะเราไม่สามารถพึ่งพาให้ $f$ มีโครงสร้างใดเป็นพิเศษที่ทำให้ง่ายขึ้น เราไม่ได้ค้นหาในลิสต์ที่เรียงลำดับ หรือใน data structure ที่ออกแบบมาโดยเฉพาะเพื่ออำนวยความสะดวกในการค้นหา พูดง่าย ๆ คือเรากำลังงมเข็มในมหาสมุทร

โดยสัญชาตญาณ เราอาจจินตนาการว่ามี Boolean circuit ที่ซับซ้อนมากที่คำนวณ $f$ และเราสามารถรัน circuit นี้บน input string ที่เลือกได้ง่ายๆ แต่เพราะ circuit ซับซ้อนเกินไป เราไม่มีทางทำความเข้าใจ circuit ด้วยการตรวจดูมัน (นอกจากความสามารถในการประเมินมันบน input strings ที่เลือก)

วิธีหนึ่งในการทำงานค้นหานี้แบบคลาสสิกคือไล่ตรวจ strings ทั้งหมด $x\in\Sigma^n$ โดยประเมิน $f$ กับแต่ละตัวเพื่อตรวจสอบว่ามันเป็น solution หรือไม่ ต่อจากนี้ให้เขียน

$$N = 2^n$$

เพื่อความสะดวก มี $N$ strings ใน $\Sigma^n$ ดังนั้นการ iterate ผ่านทั้งหมดต้องการการประเมิน $f$ จำนวน $N$ ครั้ง ภายใต้สมมติฐานที่ว่าเราจำกัดอยู่กับการประเมิน $f$ บน inputs ที่เลือก นี่คือสิ่งที่ดีที่สุดที่ทำได้ด้วย deterministic algorithm ถ้าต้องการรับประกันความสำเร็จ ด้วย probabilistic algorithm เราอาจหวังจะประหยัดเวลาโดยสุ่มเลือก input strings ให้กับ $f$ แต่เราก็ยังต้องการการประเมิน $O(N)$ ครั้งถ้าต้องการให้วิธีนี้สำเร็จด้วยความน่าจะเป็นสูง

อัลกอริทึม Grover แก้ปัญหาการค้นหานี้ด้วยความน่าจะเป็นสูงโดยประเมิน $f$ เพียง $O(\sqrt{N})$ ครั้ง เพื่อให้ชัดเจน การประเมินฟังก์ชันเหล่านี้ต้องเกิดขึ้น ใน superposition คล้ายกับ query algorithms ที่พูดถึงใน บทเรียน Quantum query algorithms รวมถึงอัลกอริทึม Deutsch, อัลกอริทึม Deutsch-Jozsa, และอัลกอริทึม Simon ต่างจากอัลกอริทึมเหล่านั้น อัลกอริทึม Grover ใช้แนวทาง iterative: มันประเมิน $f$ บน superpositions ของ input strings และแทรกการดำเนินการอื่น ๆ ระหว่างการประเมินเหล่านั้น ซึ่งมีผลสร้าง interference patterns ที่นำไปสู่ solution ด้วยความน่าจะเป็นสูง (ถ้ามี) หลังจาก $O(\sqrt{N})$ iterations

การระบุปัญหาอย่างเป็นทางการ

เราจะทำให้ปัญหาที่อัลกอริทึม Grover แก้เป็นทางการโดยใช้ query model ของการคำนวณ นั่นคือ เราจะสมมติว่าเราสามารถเข้าถึงฟังก์ชัน $f:\Sigma^n\rightarrow\Sigma$ ผ่าน query gate ที่กำหนดในแบบปกติ:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

สำหรับทุก $x\in\Sigma^n$ และ $a\in\Sigma$ นี่คือการกระทำของ $U_f$ บน standard basis states และการกระทำโดยทั่วไปถูกกำหนดโดยความเป็นเชิงเส้น

ดังที่พูดถึงในบทเรียน พื้นฐานอัลกอริทึมควอนตัม ถ้าเรามี Boolean circuit สำหรับการคำนวณ $f$ เราสามารถแปลง Boolean circuit นั้นให้เป็น quantum circuit ที่ implement $U_f$ ได้ (โดยใช้ workspace qubits บางส่วนที่เริ่มและสิ้นสุดการคำนวณในสถานะ $\vert 0\rangle$) ดังนั้น แม้เราจะใช้ query model เพื่อทำให้ปัญหาที่อัลกอริทึม Grover แก้เป็นทางการ มันไม่ได้จำกัดอยู่กับ model นี้; เราสามารถรันอัลกอริทึม Grover บนฟังก์ชัน $f$ ใด ๆ ที่เรามี Boolean circuit

นี่คือการระบุปัญหาอย่างแม่นยำ ซึ่งตั้งชื่อว่า Search เพราะเรากำลังค้นหา solution หมายถึง string $x$ ที่ทำให้ $f$ ประเมินได้เป็น $1$

Search

Input: ฟังก์ชัน $f:\Sigma^n\rightarrow\Sigma$
Output: string $x\in\Sigma^n$ ที่ตรงตามเงื่อนไข $f(x) = 1$ หรือ "no solution" ถ้าไม่มี string $x$ ดังกล่าว

สังเกตว่านี่ ไม่ใช่ promise problem — ฟังก์ชัน $f$ จะเป็นฟังก์ชันใด ๆ ก็ได้ อย่างไรก็ตาม จะเป็นประโยชน์ที่จะพิจารณา promise variant ของปัญหาต่อไปนี้ ซึ่งรับประกันว่ามี solution อยู่พอดีหนึ่งตัว ปัญหานี้ปรากฏเป็นตัวอย่างของ promise problem ในบทเรียน Quantum query algorithms

Unique search

Input: ฟังก์ชันในรูปแบบ $f:\Sigma^n \rightarrow \Sigma$
Promise: มี string $z\in\Sigma^n$ พอดีหนึ่งตัวที่ $f(z) = 1$ โดย $f(x) = 0$ สำหรับทุก string $x\neq z$
Output: string $z$

ยังสังเกตด้วยว่าปัญหา Or ที่กล่าวถึงในบทเรียนเดียวกันมีความสัมพันธ์อย่างใกล้ชิดกับ Search สำหรับปัญหานั้น เป้าหมายคือแค่ตรวจสอบว่า solution มีอยู่หรือไม่ ต่างจากการหา solution จริง ๆ