คลังเก็บป้ายกำกับ: Exponential

ความเร็วของควอนตัมคอมพิวเตอร์

พวกเราคงจำข่าวที่ Google ทดสอบประสิทธิภาพของควอนตัมคอมพิวเตอร์ยี่ห้อ D-Wave X2 แล้วได้ผลว่ามันทำงานได้เร็วกว่าดิจิทัลคอมพิวเตอร์ทั่วไปเป็น 100 ล้านเท่ากันได้

และผมก็คิดว่าพวกเราคงรู้กันแล้วล่ะ ว่าเบื้องหลังความเร็วของควอนตัมคอมพิวเตอร์ เกิดจากการประยุกต์ใช้สภาวะ Superposition ของคิวบิต

ทีนี้ ผมเลยอยากจะช่วยขยายความเพิ่มลงในระดับของทฤษฎีความซับซ้อนในการคำนวณนิดนึง เพื่อให้พวกเราเห็นภาพมากขึ้นว่าทำไมควอนตัมคอมพิวเตอร์จึงเร็ว

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

ด้วยข้อเท็จจริงแบบนี้ จึงทำให้ดิจิทัลคอมพิวเตอร์ ต้องเผชิญกับปัญหาความซับซ้อนในการคำนวณหลายระดับ ทั้งระดับชั้น Polynomial, Exponential หรือ Factorial

ซึ่งโดยพื้นฐานแล้ว …

  • ปัญหาระดับชั้น Polynomial ก็ต้องแก้ในเวลา Polynomial
  • ปัญหาระดับชั้น Exponential ก็ต้องแก้ในเวลา Exponential
  • ปัญหาระดับชั้น Factorial ก็ต้องแก้ในเวลา Factorial

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

ซึ่งจะเห็นว่า ดิจิทัลคอมพิวเตอร์มันมีขีดจำกัดของความซับซ้อนในการคำนวณ มันเหมือนกับตัวละคร Iron Man ในภาพยนต์เรื่อง The Avengers ที่โดยพื้นฐานมีกำลังและความสามารถเหมือนมนุษย์ (แก้ปัญหาระดับชั้น Polynomial ในเวลา Polynomial) แต่พอใส่ชุดเกราะเพิ่มพลังก็กลายเป็นยอดมนุษย์ทันที (แก้ปัญหาระดับชั้น Exponential ในเวลา Polynomial หรือ แก้ปัญหาระดับชั้น Factorial ในเวลา Exponential)

เปรียบเทียบความเร็วของดิจิทัลคอมพิวเตอร์กับควอนตัมคอมพิวเตอร์
เปรียบเทียบความเร็วของดิจิทัลคอมพิวเตอร์กับควอนตัมคอมพิวเตอร์

แต่ในอีกด้านหนึ่ง ควอนตัมคอมพิวเตอร์กลับเหมือนกับตัวละคร Thor ในภาพยนต์เรื่อง The Avengers ที่โดยพื้นฐานก็เป็นเผ่าพันธุ์ต่างดาวสมมติเทพ ที่มีกำลังและความสามารถเหนือมนุษย์ตั้งแต่ต้น (แก้ปัญหาระดับชั้น Polynomial, Exponential และ Factorial ได้ในเวลา Polynomial แบบชิว ๆ)

การเป็นยอดมนุษย์ตั้งแต่เกิด มันต่างกับการเปลี่ยนมาเป็นยอดมนุษย์ภายหลังจากเกิดเยอะเลยครับ และการที่ควอนตัมคอมพิวเตอร์มันเร็วกว่าดิจิทัลคอมพิวเตอร์ ก็เพราะมันเร็วกว่าดิจิทัลคอมพิวเตอร์มาตั้งแต่เกิดนั่นเอง