การวัดต้นทุนการคำนวณ

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

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

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

การเข้ารหัสและความยาวอินพุต

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

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

ตัวเลข	การเข้ารหัสแบบไบนารี	ความยาว
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

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

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

ตัวเลข	การเข้ารหัสแบบ Unary	การเข้ารหัสแบบ Lexicographic
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(ในตารางนี้ สัญลักษณ์ $\varepsilon$ แทน สตริงว่าง ซึ่งไม่มีสัญลักษณ์ใดเลยและมีความยาวเท่ากับศูนย์ เพื่อหลีกเลี่ยงความสับสน เราใช้สัญลักษณ์พิเศษอย่าง $\varepsilon$ แทนสตริงว่างแทนที่จะเขียนว่างเปล่าจริงๆ)

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

ตัวอย่างเช่น จำนวนบิตที่ต้องใช้เพื่อแสดงจำนวนเต็มไม่เป็นลบ $N$ ในสัญกรณ์ไบนารี ซึ่งบางครั้งเขียนว่า $\operatorname{lg}(N)$ ได้จากสูตรต่อไปนี้

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

สมมติว่าเราใช้สัญกรณ์ไบนารีในการเข้ารหัสอินพุตสำหรับปัญหาการแยกตัวประกอบจำนวนเต็ม ความยาวอินพุต สำหรับตัวเลข $N$ จึงเท่ากับ $\operatorname{lg}(N)$ โปรดสังเกตว่าความยาว (หรือขนาด) ของอินพุต $N$ ไม่ใช่ $N$ เอง เมื่อ $N$ มีขนาดใหญ่ เราไม่จำเป็นต้องใช้บิตเท่านี้ในการแสดง $N$ ในสัญกรณ์ไบนารี

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

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

ตัวอย่างเช่น การคำนวณที่ง่ายมากอย่างหนึ่งคือการแปลงระหว่างการแทนค่าแบบไบนารีของจำนวนเต็มไม่เป็นลบและการเข้ารหัสแบบ lexicographic (ซึ่งเราไม่ได้อธิบายรายละเอียด แต่สามารถอนุมานได้จากตารางข้างต้น) ด้วยเหตุนี้ ต้นทุนการคำนวณของการแยกตัวประกอบจำนวนเต็มจะไม่ต่างกันมากนักหากเราตัดสินใจเปลี่ยนจากการเข้ารหัสใดในสองแบบนี้ไปใช้อีกแบบสำหรับอินพุต $N$ ในทางกลับกัน การเข้ารหัสจำนวนเต็มไม่เป็นลบในสัญกรณ์ unary ทำให้จำนวนสัญลักษณ์ที่ต้องการเพิ่มขึ้นแบบ exponential และเราจะไม่ถือว่ามันเป็นรูปแบบการเข้ารหัสที่ "สมเหตุสมผล" ด้วยเหตุนี้

การดำเนินการพื้นฐาน

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

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

ชุด Gate สากล

สำหรับโมเดลการคำนวณแบบวงจร โดยทั่วไปแต่ละ Gate ถูกมองว่าเป็นการดำเนินการพื้นฐาน สิ่งนี้นำไปสู่คำถามว่า Gate ตัวไหนบ้างที่เราอนุญาตในวงจรของเรา มุ่งเน้นที่วงจรควอนตัมก่อน เราได้เห็น Gate หลายตัวในซีรีส์นี้ รวมถึง Gate $X,$ $Y,$ $Z,$ $H,$ $S,$ และ $T$ Gate แบบ swap Gate ที่มีการควบคุม (รวมถึง controlled-NOT, Toffoli, และ Fredkin Gate) รวมถึง Gate ที่แทนการวัดในฐานมาตรฐาน ในบริบทของเกม CHSH เราได้เห็น Gate rotation เพิ่มเติมอีกสองสามตัว

เรายังได้พูดถึง query gate ในบริบทของโมเดล query และยังเห็นว่าการดำเนินการ unitary $U$ ใดๆ ที่กระทำบน Qubit จำนวนเท่าใดก็ได้ สามารถมองเป็น Gate ได้หากเราต้องการ แต่เราจะละเว้นทั้งสองตัวเลือกนี้เพื่อความชัดเจน เราจะไม่ทำงานในโมเดล query (แม้ว่าการใช้งาน query gate โดยใช้การดำเนินการพื้นฐานจะกล่าวถึงในภายหลังในบทเรียน) และการมอง Gate unitary ที่ arbitrary ซึ่งอาจกระทำบน Qubit หลายล้านตัว ว่าเป็นการดำเนินการพื้นฐานนั้นไม่ได้นำไปสู่แนวคิดต้นทุนการคำนวณที่มีความหมายหรือสมจริง

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

นี่คือตัวเลือกมาตรฐานหนึ่ง ซึ่งเราจะใช้เป็นชุด Gate ค่าเริ่มต้น สำหรับวงจรควอนตัม:

• Single-qubit unitary Gate จากรายการนี้: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ และ $T^{\dagger}$
• Controlled-NOT Gate
• การวัดในฐานมาตรฐานแบบ Single-qubit

ทางเลือกที่พบบ่อยอีกอย่างคือการมอง Toffoli, Hadamard, และ Gate $S$ ว่าเป็นพื้นฐาน นอกเหนือจากการวัดในฐานมาตรฐาน บางครั้ง single-qubit Gate ทั้งหมดถูกมองว่าเป็นพื้นฐาน แม้ว่าสิ่งนี้จะนำไปสู่โมเดลที่มีพลังงานที่ไม่สมจริงเมื่อไม่ได้คำนึงถึงความแม่นยำในการดำเนินการ Gate อย่างถูกต้อง

Unitary Gate ในชุดค่าเริ่มต้นของเราเป็นสิ่งที่เรียกว่าชุด Gate สากล ซึ่งหมายความว่าเราสามารถประมาณการดำเนินการ unitary ใดๆ บน Qubit จำนวนเท่าใดก็ได้ด้วยความแม่นยำระดับใดก็ได้ โดยใช้วงจรที่ประกอบด้วย Gate เหล่านี้เท่านั้น เพื่อความชัดเจน คำจำกัดความของความสากลไม่ได้กำหนดข้อกำหนดใดๆ เกี่ยวกับต้นทุนของการประมาณดังกล่าว หมายถึงจำนวน Gate จากชุดของเราที่เราต้องการ แท้จริงแล้ว การโต้แย้งที่ค่อนข้างง่ายตามแนวคิดทางคณิตศาสตร์ของ measure เผยให้เห็นว่าการดำเนินการ unitary ส่วนใหญ่ต้องมีต้นทุนสูงมาก การพิสูจน์ความสากลของชุด quantum gate ไม่ใช่เรื่องง่ายและจะไม่ถูกครอบคลุมในคอร์สนี้

สำหรับวงจรบูลีน เราจะใช้ Gate AND, OR, NOT, และ FANOUT เป็นตัวแทนการดำเนินการพื้นฐาน จริงๆ แล้วเราไม่จำเป็นต้องมีทั้ง Gate AND และ Gate OR เราสามารถใช้ กฎของ De Morgan เพื่อแปลงจากกฎหนึ่งไปอีกกฎหนึ่งโดยวาง NOT Gate บนสายอินพุต/เอาต์พุตทั้งสาม แต่ก็ยังเป็นทั้งเรื่องปกติและสะดวกที่จะอนุญาตให้มีทั้ง Gate AND และ Gate OR Gate AND, OR, NOT, และ FANOUT เป็นชุดสากลสำหรับการคำนวณแบบ deterministic หมายความว่าฟังก์ชันใดๆ จากบิตอินพุตจำนวนตายตัวไปยังบิตเอาต์พุตจำนวนตายตัวสามารถใช้ Gate เหล่านี้ได้

หลักการของการวัดที่ล่าช้า

Gate การวัดในฐานมาตรฐานสามารถปรากฏในวงจรควอนตัมได้ แต่บางครั้งก็สะดวกที่จะเลื่อนออกไปจนถึงตอนท้าย สิ่งนี้ช่วยให้เรามองการคำนวณควอนตัมว่าประกอบด้วยส่วน unitary (แทนการคำนวณเอง) ตามด้วยขั้นตอนการอ่านค่าอย่างง่ายที่ Qubit ถูกวัดและผลลัพธ์ถูกส่งออก สามารถทำได้เสมอ โดยต้องเพิ่ม Qubit เพิ่มเติมหนึ่งตัวสำหรับการวัดในฐานมาตรฐานแต่ละครั้ง ในภาพต่อไปนี้ วงจรด้านขวาแสดงให้เห็นว่าสามารถทำสิ่งนี้ได้อย่างไรสำหรับ Gate ด้านซ้าย

โดยเฉพาะอย่างยิ่ง บิตคลาสสิกในวงจรด้านซ้ายถูกแทนที่ด้วย Qubit ด้านขวา (เริ่มต้นในสถานะ $\vert 0\rangle$) และการวัดในฐานมาตรฐานถูกแทนที่ด้วย controlled-NOT Gate ตามด้วยการวัดในฐานมาตรฐานบน Qubit ล่าง ประเด็นคือการวัดในฐานมาตรฐานในวงจรด้านขวาสามารถถูกผลักไปยังปลายวงจรได้ หากบิตคลาสสิกในวงจรด้านซ้ายถูกใช้เป็นบิต control ในภายหลัง เราสามารถใช้ Qubit ล่างในวงจรด้านขวาเป็น control แทน และผลรวมโดยรวมจะเหมือนกัน (เราสมมติว่าบิตคลาสสิกในวงจรด้านซ้ายไม่ถูกเขียนทับหลังการวัดโดยการวัดอื่น แต่ถ้าเกิดขึ้นเราสามารถใช้บิตคลาสสิกใหม่แทนที่จะเขียนทับบิตที่ใช้สำหรับการวัดก่อนหน้า)

ขนาดและความลึกของวงจร

ขนาดวงจร

จำนวน Gate ทั้งหมดในวงจรเรียกว่า ขนาด ของวงจรนั้น ดังนั้น สมมติว่า Gate ในวงจรของเราแทนการดำเนินการพื้นฐาน ขนาดของวงจรแสดงถึงจำนวนการดำเนินการพื้นฐานที่ต้องการ หรือพูดอีกนัยหนึ่งคือ ต้นทุนการคำนวณ เราเขียน $\operatorname{size}(C)$ เพื่ออ้างถึงขนาดของวงจร $C$ ที่กำหนด

ตัวอย่างเช่น พิจารณาวงจรบูลีนต่อไปนี้สำหรับการคำนวณ XOR ของบิตสองบิต

ขนาดของวงจรนี้คือ 7 เพราะมี Gate ทั้งหมด 7 ตัว (การดำเนินการ Fanout ไม่ได้นับเป็น Gate เสมอไป แต่สำหรับบทเรียนนี้เราจะนับว่าเป็น Gate)

เวลา ต้นทุน และความลึกของวงจร

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

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

แต่สังเกตว่าขนาดของวงจรไม่จำเป็นต้องสอดคล้องโดยตรงกับระยะเวลาที่ใช้ในการรัน ในวงจรบูลีนสำหรับการคำนวณ XOR ของบิตสองบิต ตัวอย่างเช่น Gate FANOUT สองตัวสามารถดำเนินการพร้อมกันได้ เช่นเดียวกับ Gate NOT สองตัว รวมถึง Gate AND สองตัว วิธีอื่นในการวัดประสิทธิภาพของวงจร ซึ่งคำนึงถึงความเป็นไปได้ของ การทำงานขนาน นี้ คือ ความลึก นี่คือจำนวนขั้นต่ำของ ชั้น Gate ที่จำเป็นภายในวงจร โดย Gate ภายในแต่ละชั้นทำงานบนสายที่แตกต่างกัน เทียบเท่ากัน ความลึกของวงจรคือจำนวน Gate สูงสุดที่พบในเส้นทางใดๆ จากสายอินพุตไปยังสายเอาต์พุต สำหรับวงจรข้างต้น ความลึกคือ 4

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

การกำหนดต้นทุนให้กับ Gate ต่างๆ

หมายเหตุสุดท้ายเกี่ยวกับขนาดวงจรและต้นทุนการคำนวณคือสามารถกำหนดต้นทุนที่แตกต่างกันให้กับ Gate แทนที่จะมองว่า Gate ทุกตัวมีส่วนร่วมเท่ากันต่อต้นทุนรวม

ตัวอย่างเช่น ดังที่กล่าวไปแล้ว Gate FANOUT มักถูกมองว่าฟรีสำหรับวงจรบูลีน หมายความว่าเราอาจเลือกให้ Gate FANOUT มีต้นทุนเป็นศูนย์ ตัวอย่างอื่น เมื่อเราทำงานในโมเดล query และนับจำนวน query ที่วงจรทำต่ออินพุตฟังก์ชัน (ในรูปของ black box) เราก็กำหนดต้นทุนหน่วยให้กับ query gate อย่างมีประสิทธิผลและต้นทุนเป็นศูนย์ให้กับ Gate อื่นๆ เช่น Hadamard Gate ตัวอย่างสุดท้ายคือเราบางครั้งกำหนดต้นทุนที่แตกต่างกันให้กับ Gate ขึ้นอยู่กับความยากในการนำไปใช้งาน ซึ่งอาจแตกต่างกันขึ้นอยู่กับฮาร์ดแวร์ที่พิจารณา

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

ต้นทุนในฐานะฟังก์ชันของความยาวอินพุต

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

ครอบครัวของวงจร

อินพุตสำหรับปัญหาการคำนวณที่กำหนดสามารถแปรผันในความยาว และอาจมีขนาดใหญ่โตมหาศาลได้ แต่ละวงจร อีกทางหนึ่ง มีจำนวน Gate และสายตายตัว ด้วยเหตุนี้ เมื่อเราคิดเกี่ยวกับอัลกอริทึมในแง่ของวงจร โดยทั่วไปเราต้องการ ครอบครัว ของวงจรที่มีขนาดใหญ่โตมหาศาลเพื่อแทนอัลกอริทึม ครอบครัวของวงจรหมายถึงลำดับของวงจรที่เติบโตขึ้นในขนาด ช่วยให้รองรับอินพุตที่ใหญ่ขึ้นเรื่อยๆ ได้

ตัวอย่างเช่น ลองนึกภาพว่าเรามีอัลกอริทึมคลาสสิกสำหรับการแยกตัวประกอบจำนวนเต็ม เช่นอัลกอริทึมที่ factorint ใช้ เหมือนกับอัลกอริทึมคลาสสิกทุกตัว อัลกอริทึมนี้สามารถใช้วงจรบูลีนได้ แต่ต้องใช้วงจรแยกต่างหากสำหรับความยาวอินพุตแต่ละอย่าง หากเราดูวงจรที่ได้สำหรับความยาวอินพุตต่างๆ เราจะเห็นว่าขนาดของวงจรเติบโตขึ้นตามความยาวอินพุต สะท้อนความจริงที่ว่าการแยกตัวประกอบจำนวนเต็ม 4 บิตนั้นง่ายกว่ามากและต้องการการดำเนินการพื้นฐานน้อยกว่าการแยกตัวประกอบจำนวนเต็ม 1024 บิตมาก

สิ่งนี้นำเราไปแสดงต้นทุนการคำนวณของอัลกอริทึมโดยฟังก์ชัน $t$ ที่กำหนดให้ $t(n)$ เป็นจำนวน Gate ในวงจรที่ใช้งานอัลกอริทึมสำหรับอินพุต $n$ บิต ในแง่ที่เป็นทางการมากขึ้น อัลกอริทึมในโมเดลวงจรบูลีนอธิบายด้วยลำดับของวงจร $\{C_1, C_2, C_3,\ldots\},$ โดยที่ $C_n$ แก้ปัญหาใดก็ตามที่เราพูดถึงสำหรับอินพุต $n$-บิต (หรือโดยทั่วไปมากขึ้น สำหรับอินพุตที่ขนาดถูก parameterize ในทางใดทางหนึ่งโดย $n$) และฟังก์ชัน $t$ ที่แทนต้นทุนของอัลกอริทึมนี้ถูกกำหนดเป็น

$$t(n) = \operatorname{size}(C_n).$$

สำหรับวงจรควอนตัม สถานการณ์คล้ายกัน โดยต้องการวงจรที่ใหญ่ขึ้นเรื่อยๆ เพื่อรองรับสตริงอินพุตที่ยาวขึ้นเรื่อยๆ

ตัวอย่าง: การบวกจำนวนเต็ม

เพื่ออธิบายเพิ่มเติม ลองใช้เวลาสักครู่พิจารณาปัญหาการบวกจำนวนเต็ม ซึ่งง่ายกว่าการแยกตัวประกอบจำนวนเต็มหรือแม้แต่การหา GCD มาก

การบวกจำนวนเต็ม

อินพุต: จำนวนเต็ม $N$ และ $M$
เอาต์พุต: $N+M$

เราอาจออกแบบวงจรบูลีนสำหรับแก้ปัญหานี้อย่างไร?

เพื่อความง่าย ขอจำกัดความสนใจไว้ที่กรณีที่ $N$ และ $M$ ทั้งคู่เป็นจำนวนเต็มไม่เป็นลบที่แสดงด้วยสตริง $n$-บิตในสัญกรณ์ไบนารี เราจะอนุญาตให้มีศูนย์นำหน้าจำนวนเท่าใดก็ได้ในการเข้ารหัสเหล่านี้ ดังนั้น

$$0\leq N,M\leq 2^n - 1.$$

เอาต์พุตจะเป็นสตริงไบนารี $(n+1)$-บิต แทนค่าผลรวม ซึ่งเป็นจำนวนบิตสูงสุดที่เราต้องการเพื่อแสดงผลลัพธ์

เราเริ่มต้นด้วยอัลกอริทึม ซึ่งเป็น อัลกอริทึมมาตรฐาน สำหรับการบวกในรูปไบนารี ซึ่งเป็นอนาล็อกฐาน $2$ ของวิธีที่สอนการบวกในโรงเรียนประถมทั่วโลก อัลกอริทึมนี้สามารถใช้วงจรบูลีนได้ดังนี้

เริ่มจากบิตที่มีนัยสำคัญน้อยที่สุด เราสามารถคำนวณ XOR ของมันเพื่อหาบิตที่มีนัยสำคัญน้อยที่สุดสำหรับผลรวม จากนั้นเราคำนวณบิต carry ซึ่งเป็น AND ของบิตที่มีนัยสำคัญน้อยที่สุดสองบิตของ $N$ และ $M$ บางครั้งการดำเนินการสองอย่างนี้รวมกันเรียกว่า half adder

โดยใช้วงจร XOR ที่เราได้เห็นมาสองสามครั้งร่วมกับ AND Gate และ FANOUT Gate สองตัว เราสามารถสร้าง half adder ด้วย 10 Gate ถ้าด้วยเหตุผลบางอย่างเราเปลี่ยนใจและตัดสินใจรวม XOR Gate ไว้ในชุดการดำเนินการพื้นฐานของเรา เราจะต้องใช้ AND Gate 1 ตัว, XOR Gate 1 ตัว, และ FANOUT Gate 2 ตัวเพื่อสร้าง half adder

ไปที่บิตที่มีนัยสำคัญมากกว่า เราสามารถใช้ขั้นตอนที่คล้ายกัน แต่คราวนี้รวม carry bit จากตำแหน่งก่อนหน้าแต่ละตำแหน่งในการคำนวณด้วย โดยต่อ half adder สองตัวเข้าด้วยกันและนำ OR ของ carry bit ที่ผลิตออกมา เราสามารถสร้างสิ่งที่เรียกว่า full adder

สิ่งนี้ต้องการ Gate ทั้งหมด 21 ตัว: AND Gate 2 ตัว, XOR Gate 2 ตัว (แต่ละตัวต้องใช้ Gate 7 ตัวในการใช้งาน), OR Gate 1 ตัว, และ FANOUT Gate 4 ตัว

สุดท้าย โดยต่อ full adder เข้าด้วยกัน เราได้วงจรบูลีนสำหรับการบวกจำนวนเต็มไม่เป็นลบ ตัวอย่างเช่น วงจรต่อไปนี้คำนวณผลรวมของจำนวนเต็ม 4 บิตสองตัว

โดยทั่วไป สิ่งนี้ต้องการ

$$21 (n-1) + 10 = 21 n - 11$$

Gate ถ้าเราตัดสินใจรวม XOR Gate ไว้ในชุดการดำเนินการพื้นฐาน เราจะต้องใช้ AND Gate $2n-1$ ตัว, XOR Gate $2n-1$ ตัว, OR Gate $n-1$ ตัว, และ FANOUT Gate $4n-2$ ตัว รวมทั้งหมด $9n-5$ Gate ถ้านอกจากนี้เราตัดสินใจไม่นับ FANOUT Gate ก็จะเป็น $5n-3$ Gate

สัญกรณ์ Asymptotic

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

ในอีกแง่หนึ่ง ถ้าเราทำการวิเคราะห์ในระดับรายละเอียดนี้สำหรับการคำนวณทั้งหมดที่เราสนใจ รวมถึงงานที่ซับซ้อนกว่าการบวกมาก เราจะจมอยู่กับรายละเอียดอย่างรวดเร็ว เพื่อให้สิ่งต่างๆ จัดการได้ และเพื่อตั้งใจระงับรายละเอียดที่สำคัญรองลงมา โดยทั่วไปเราใช้ สัญกรณ์ Big-O เมื่อวิเคราะห์อัลกอริทึม ผ่านสัญกรณ์นี้เราสามารถแสดง ลำดับ ที่ฟังก์ชันเติบโต

อย่างเป็นทางการ ถ้าเรามีสองฟังก์ชัน $g(n)$ และ $h(n)$ เราเขียนว่า $g(n) = O(h(n))$ ถ้ามีจำนวนจริงบวก $c > 0$ และจำนวนเต็มบวก $n_0$ โดยที่

$$g(n) \leq c\cdot h(n)$$

สำหรับทุก $n \geq n_0.$ โดยทั่วไป $h(n)$ ถูกเลือกให้เป็นนิพจน์ที่เรียบง่ายที่สุดเท่าที่จะเป็นไปได้ เพื่อให้สัญกรณ์สามารถเผยพฤติกรรมขีด จำกัด ของฟังก์ชันในรูปที่เรียบง่าย ตัวอย่างเช่น $17 n^3 - 257 n^2 + 65537 = O(n^3).$

สัญกรณ์นี้สามารถขยายไปยังฟังก์ชันที่มีหลายอาร์กิวเมนต์ในวิธีที่ค่อนข้างตรงไปตรงมา ตัวอย่างเช่น ถ้าเรามีสองฟังก์ชัน $g(n,m)$ และ $h(n,m)$ ที่นิยามบนจำนวนเต็มบวก $n$ และ $m$ เราเขียนว่า $g(n,m) = O(h(n,m))$ ถ้ามีจำนวนจริงบวก $c > 0$ และจำนวนเต็มบวก $k_0$ โดยที่

$$g(n,m) \leq c\cdot h(n,m)$$

เมื่อ $n+m \geq k_0.$

เชื่อมโยงสัญกรณ์นี้กับตัวอย่างการบวกจำนวนเต็มไม่เป็นลบ เราสรุปได้ว่ามีครอบครัวของ วงจรบูลีน $\{C_1, C_2,\ldots,\},$ โดยที่ $C_n$ บวกจำนวนเต็มไม่เป็นลบ $n$-บิตสองตัวเข้าด้วยกัน โดยที่ $\operatorname{size}(C_n) = O(n).$ สิ่งนี้เผยคุณลักษณะสำคัญที่สุดของวิธีที่ต้นทุนการบวกขยายตัวตามขนาดอินพุต: มันขยายตัวแบบ linear

สังเกตด้วยว่ามันไม่ขึ้นอยู่กับรายละเอียดเฉพาะว่าเราพิจารณาว่า XOR Gate มีต้นทุนหน่วยหรือต้นทุน $7$ โดยทั่วไป การใช้สัญกรณ์ Big-O ช่วยให้เราสร้างข้อความเกี่ยวกับต้นทุนการคำนวณที่ไม่ไวต่อรายละเอียดระดับต่ำดังกล่าว

ตัวอย่างเพิ่มเติม

นี่คือตัวอย่างเพิ่มเติมของปัญหาจากทฤษฎีตัวเลขเชิงการคำนวณ เริ่มต้นด้วย การคูณ

การคูณจำนวนเต็ม

อินพุต: จำนวนเต็ม $N$ และ $M$
เอาต์พุต: $NM$

การสร้างวงจรบูลีนสำหรับปัญหานี้ยากกว่าการสร้างวงจรสำหรับการบวก แต่โดยคิดเกี่ยวกับอัลกอริทึมการคูณมาตรฐาน เราสามารถคิดวงจรที่มีขนาด $O(n^2)$ สำหรับปัญหานี้ (สมมติว่า $N$ และ $M$ ทั้งคู่แสดงด้วยการแทนค่าแบบไบนารี $n$-บิต) โดยทั่วไปมากขึ้น ถ้า $N$ มี $n$ บิตและ $M$ มี $m$ บิต มีวงจรบูลีนขนาด $O(nm)$ สำหรับการคูณ $N$ และ $M$

มีวิธีการคูณอื่นๆ ที่ขยายตัวได้ดีกว่าจริงๆ ตัวอย่างเช่น อัลกอริทึมการคูณ Schönhage-Strassen สามารถใช้สร้างวงจรบูลีนสำหรับการคูณจำนวนเต็ม $n$-บิตสองตัวที่ต้นทุน $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n)))$ ความซับซ้อนของวิธีการนี้ทำให้เกิด overhead มาก ทำให้ใช้งานได้จริงเฉพาะกับตัวเลขที่มีหลายหมื่นบิตเท่านั้น

ปัญหาพื้นฐานอีกอย่างคือ การหาร ซึ่งเราตีความว่าหมายถึงการคำนวณทั้งผลหารและเศษเหลือโดยกำหนดตัวหารและตัวตั้งหารจำนวนเต็ม

การหารจำนวนเต็ม

อินพุต: จำนวนเต็ม $N$ และ $M\neq0$
เอาต์พุต: จำนวนเต็ม $q$ และ $r$ ที่ตอบสนอง $0\leq r < |M|$ และ $N = q M + r$

ต้นทุนการหารจำนวนเต็มคล้ายกับการคูณ: ถ้า $N$ มี $n$ บิตและ $M$ มี $m$ บิต มีวงจรบูลีนขนาด $O(nm)$ สำหรับแก้ปัญหานี้ และเหมือนกับการคูณ มีวิธีการที่ดีกว่าในเชิง asymptotic ที่รู้จัก

เราสามารถเปรียบเทียบอัลกอริทึมที่รู้จักสำหรับการหา GCD กับอัลกอริทึมสำหรับการบวกและการคูณได้ อัลกอริทึมของออยเลอร์สำหรับการหา GCD ของตัวเลข $n$-บิต $N$ และตัวเลข $m$-บิต $M$ ต้องการวงจรบูลีนขนาด $O(nm)$ คล้ายกับอัลกอริทึมมาตรฐานสำหรับการคูณและการหาร เช่นเดียวกับการคูณและการหาร มีอัลกอริทึม GCD ที่เร็วกว่าในเชิง asymptotic รวมถึงอัลกอริทึมที่ต้องการการดำเนินการพื้นฐาน $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ เพื่อหา GCD ของตัวเลข $n$-บิตสองตัว

การคำนวณที่แพงกว่าบางอย่างที่เกิดขึ้นในทฤษฎีตัวเลขคือ modular exponentiation

Modular exponentiation ของจำนวนเต็ม

อินพุต: จำนวนเต็ม $N,$ $K,$ และ $M$ โดยที่ $K\geq 0$ และ $M\geq 1$
เอาต์พุต: $N^K \hspace{1mm} (\text{mod }M)$

$N^K\hspace{1mm} (\text{mod }M)$ หมายถึงเศษเหลือเมื่อหาร $N^K$ ด้วย $M$ นั่นคือจำนวนเต็มเฉพาะ $r$ ที่ตอบสนอง $0\leq r < M$ และ $N^K = q M + r$ สำหรับจำนวนเต็มบางตัว $q$

ถ้า $N$ มี $n$ บิต, $M$ มี $m$ บิต, และ $K$ มี $k$ บิต ปัญหานี้สามารถแก้ได้ด้วยวงจรบูลีนที่มีขนาด $O(k m^2 + nm)$ สิ่งนี้ไม่ชัดเจนเลย วิธีแก้ไม่ใช่การคำนวณ $N^K$ ก่อนแล้วจึงนำเศษ ซึ่งจะต้องใช้บิตจำนวน exponential เพียงเพื่อจัดเก็บตัวเลข $N^K$ แต่เราสามารถใช้ power algorithm (หรือเรียกอีกอย่างว่า binary method และ repeated squaring) ซึ่งใช้การแทนค่าแบบไบนารีของ $K$ เพื่อทำการคำนวณทั้งหมด modulo $M$ สมมติว่า $N,$ $M,$ และ $K$ ทั้งหมดเป็นตัวเลข $n$-บิต เราได้อัลกอริทึม $O(n^3)$ หรือ อัลกอริทึมเวลา cubic และอีกครั้ง มีอัลกอริทึมที่รู้จักซึ่งซับซ้อนกว่าแต่เร็วกว่าในเชิง asymptotic

ต้นทุนการแยกตัวประกอบจำนวนเต็ม

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

วิธีการง่ายๆ อย่างหนึ่งในการแยกตัวประกอบคือ trial division ซึ่งอัลกอริทึมค้นหาผ่านรายการ $2,\ldots,\sqrt{N}$ เพื่อหาตัวประกอบเฉพาะของตัวเลขอินพุต $N$ สิ่งนี้ต้องการ $O(2^{n/2})$ iteration ในกรณีเลวร้ายที่สุดเมื่อ $N$ เป็นตัวเลข $n$-บิต แต่ละ iteration ต้องการการหาร trial ซึ่งหมายถึงการดำเนินการพื้นฐาน $O(n^2)$ สำหรับแต่ละ iteration (โดยใช้อัลกอริทึมมาตรฐานสำหรับการหารจำนวนเต็ม) เราได้วงจรขนาด $O(n^2 2^{n/2})$ ซึ่ง exponential ในขนาดอินพุต $n$

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

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

การดำเนินการพื้นฐานเพื่อแยกตัวประกอบจำนวนเต็ม $n$-บิตด้วยความน่าจะเป็นสูง แม้ว่าจะค่อนข้างสำคัญที่ $n$ ถูกยกกำลัง $1/3$ ในเลขชี้กำลังของนิพจน์นี้ แต่ความจริงที่ว่ามันปรากฏในเลขชี้กำลังก็ยังคงเป็นปัญหาที่ทำให้การขยายตัวแย่ และอธิบายบางส่วนว่าทำไม RSA1024 ยังอยู่นอกขอบเขตการใช้งานของมัน

ต้นทุนแบบ Polynomial เทียบกับ Exponential

อัลกอริทึมคลาสสิกสำหรับการบวก การคูณ การหาร และการหา GCD ช่วยให้เราแก้ปัญหาเหล่านี้ได้ในพริบตาสำหรับอินพุตที่มีหลายพันบิต การบวกมีต้นทุนแบบ linear ขณะที่ปัญหาอีกสามอย่างมีต้นทุนแบบ quadratic (หรือต้นทุนแบบ subquadratic โดยใช้อัลกอริทึมที่เร็วในเชิง asymptotic) Modular exponentiation แพงกว่าแต่ยังสามารถทำได้อย่างมีประสิทธิภาพพอสมควร ด้วยต้นทุนแบบ cubic (หรือต้นทุนต่ำกว่า cubic โดยใช้อัลกอริทึมที่เร็วในเชิง asymptotic)

สิ่งเหล่านี้ล้วนเป็นตัวอย่างของอัลกอริทึมที่มีต้นทุนแบบ polynomial หมายความว่ามีต้นทุน $O(n^c)$ สำหรับการเลือกค่าคงที่ $c > 0$ ที่ตายตัว เป็นการประมาณคร่าวๆ อันดับแรก อัลกอริทึมที่มีต้นทุนแบบ polynomial ถูกมองอย่างเป็นนามธรรมว่าแทน อัลกอริทึมที่มีประสิทธิภาพ

ในทางกลับกัน อัลกอริทึมคลาสสิกที่รู้จักสำหรับการแยกตัวประกอบจำนวนเต็มมีต้นทุนแบบ exponential บางครั้งต้นทุนของ number field sieve ถูกอธิบายว่าเป็น sub-exponential เพราะ $n$ ถูกยกกำลัง $1/3$ ในเลขชี้กำลัง แต่ในทฤษฎีความซับซ้อนนั้นเป็นเรื่องปกติมากกว่าที่จะสงวนคำนี้ไว้สำหรับอัลกอริทึมที่มีต้นทุน

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

สำหรับ ทุก $\varepsilon > 0$ ปัญหาที่เรียกว่า NP-complete เป็นคลาสของปัญหาที่ไม่รู้ (และทั่วไปสันนิษฐานว่าไม่มี) อัลกอริทึมต้นทุน polynomial การสูตรวงจรของ exponential-time hypothesis ตั้งสมมติฐานบางอย่างที่แข็งแกร่งกว่า นั่นคือไม่มีปัญหา NP-complete ใดที่มีอัลกอริทึมต้นทุน sub-exponential ได้

การเชื่อมโยงอัลกอริทึมต้นทุน polynomial กับอัลกอริทึมที่มีประสิทธิภาพต้องเข้าใจว่าเป็นการนามธรรมแบบหลวมๆ แน่นอนว่าถ้าต้นทุนของอัลกอริทึมขยายตัวเป็น $n^{1000}$ หรือ $n^{1000000}$ สำหรับอินพุตขนาด $n$ มันก็เป็นเรื่องเกินจริงที่จะบอกว่าอัลกอริทึมนั้นมีประสิทธิภาพ อย่างไรก็ตาม แม้แต่อัลกอริทึมที่มีต้นทุนขยายตัวเป็น $n^{1000000}$ ก็ต้องทำอะไรบางอย่างที่ชาญฉลาดเพื่อหลีกเลี่ยงต้นทุนแบบ exponential ซึ่งโดยทั่วไปนั่นคือสิ่งที่เราคาดหวังจากอัลกอริทึมที่ขึ้นอยู่กับ "brute force" หรือ "การค้นหาแบบ exhaustive" ในทางใดทางหนึ่ง แม้แต่การปรับปรุงที่ซับซ้อนของ number field sieve ก็ยังล้มเหลวในการหลีกเลี่ยงการขยายตัว exponential ในต้นทุน ในทางกลับกัน อัลกอริทึมต้นทุน polynomial จัดการใช้ประโยชน์จากโครงสร้างปัญหาในทางใดทางหนึ่งที่หลีกเลี่ยงการขยายตัว exponential

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

เมื่อเราพิจารณาข้อได้เปรียบของควอนตัมคอมพิวติ้งเหนือคอมพิวเตอร์คลาสสิก โดยทั่วไปสายตาของเราหันมองหาข้อได้เปรียบแบบ exponential หรืออย่างน้อย super-polynomial ก่อน ซึ่งเหมาะสมที่สุดคือการหาอัลกอริทึมควอนตัมต้นทุน polynomial สำหรับปัญหาที่ไม่รู้ว่ามีอัลกอริทึมคลาสสิกต้นทุน polynomial ข้อได้เปรียบในลำดับดังกล่าวในเชิงทฤษฎีมีโอกาสสูงสุดในการนำไปสู่ข้อได้เปรียบในทางปฏิบัติจริงๆ แต่การระบุข้อได้เปรียบดังกล่าวเป็นความท้าทายที่ยากมาก ปัจจุบันมีตัวอย่างที่รู้จักเพียงไม่กี่อย่าง แต่การค้นหายังดำเนินต่อไป

ข้อได้เปรียบแบบ polynomial (แต่ไม่ super-polynomial) ในต้นทุนการคำนวณของควอนตัมเหนือคลาสสิกก็น่าสนใจและไม่ควรถูกปฏิเสธ แต่ด้วยช่องว่างปัจจุบันระหว่างเทคโนโลยีควอนตัมและคลาสสิกคอมพิวติ้ง ดูเหมือนจะน่าสนใจน้อยกว่าในขณะนี้ อย่างไรก็ตาม วันหนึ่งอาจมีความสำคัญ อัลกอริทึม Grover ตัวอย่างเช่น ซึ่งครอบคลุมในบทเรียนหลังจากนี้ มอบข้อได้เปรียบแบบ quadratic ของควอนตัมเหนือคลาสสิกสำหรับที่เรียกว่า unstructured searching และมีศักยภาพสำหรับการประยุกต์ใช้ในวงกว้าง

ต้นทุนที่ซ่อนของการคำนวณแบบวงจร

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

สำหรับตัวอย่างทั้งหมดที่เราได้พูดถึง หรือจะพูดถึงในบทเรียนถัดไป มีอัลกอริทึมพื้นฐานที่วงจรถูกพัฒนามาจาก โดยปกติวงจรในครอบครัวจะเป็นไปตามรูปแบบพื้นฐานที่ง่ายต่อการขยายไปยังอินพุตที่ใหญ่ขึ้นเรื่อยๆ เช่น การต่อ full adder เพื่อสร้างวงจรบูลีนสำหรับการบวกหรือการดำเนินการชั้นๆ ของ Hadamard Gate และ Gate อื่นๆ ในรูปแบบที่อธิบายได้ง่าย

แต่จะเกิดอะไรขึ้นถ้ามีต้นทุนการคำนวณที่ห้ามปรามที่เกี่ยวข้องกับรูปแบบในวงจรเอง? ตัวอย่างเช่น คำอธิบายของสมาชิกแต่ละตัว $C_n$ ในครอบครัววงจรอาจในหลักการถูกกำหนดโดยฟังก์ชันของ $n$ ที่ยากมากในการคำนวณ

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