ในช่วงทศวรรศที่ 1830 – เครื่องคอมพิวเตอร์เครื่องแรกถูกสร้างขึ้นโดย ชาร์ลส์ แบบเบจ (Charles Babbage) เป็นเครื่องจักรไอน้ำขนาดใหญ่ที่สามารถโปรแกรมการทำงานได้ร้อยกว่าปีถัดมาใน สมัยสงครามโลกครั้งที่สอง อลัน ทูริ่ง (Alan Turing) เปลี่ยนแนวคิดของแบบเบจให้กลายเป็นทฤษฎีพื้นฐานของการประมวลผลข้อมูลที่ใช้ ในคอมพิวเตอร์ปัจจุบันในช่วงเวลาเดียวกัน คล็อด แชนน่อน (Claude Shannon) ได้เขียนทฤษฎีสารสนเทศ (information theory) ขึ้นมาเป็นตัวรองรับการประมวลผลข้อมูลโดยใช้คอมพิวเตอร์ ทูริ่ง แชนน่อน และ จอห์น ฟอน นอยแมนน์ (John Von Neumann) ร่วมกันสร้าง ENIAC – Electronic Numerical Integrator and Calculator ซึ่งถือว่าเป็นเครื่องคอมพิวเตอร์ electronic เครื่องแรกของโลก ทำงานโดยพื้นฐานของลอจิก ‘0’ และ ‘1’ โดยอาศัยหลอดสุญญากาศเป็นสื่อแทนค่า 0/1 .. ในปี 1960 หลอดสุญญากาศก็ถูกแทนที่ด้วย transistor ต่อมาไม่นานก็มีการยุบ transistor หลายๆ ตัวรวมเป็นแผ่นวงจร ทุกวันนี้เราสามารถบรรจุทรานซิสเตอร์หลายล้านตัวอยู่ในแผ่นวงจรรวมขนาดไม่ กี่ตาราง mm .. ก็ที่เขาพูดๆ กันว่าเป็น 0.18 micron technology น่ะแหละ.. ถ้าเรายังคงย่อขนาดลงไปเรื่อยๆ สุดท้ายเราคงหนีไม่พ้นการสร้าง logic gate จากอะตอมหรืออนุภาคไม่กี่ตัว .. ปัจจุบันเราอาจจะสร้าง gate แบบนั้นได้โดย nanotechnology แต่ด้วยขนาดที่เล็กขนาดนั้นหมายถึงเรากำลังเดินข้ามขีดจำกัดของฟิสิกส์ คุณสมบัติของ logic gate จะต่างจาก gate ทั่วๆ ไป นักวิทยาศาสตร์ทราบดีว่าในระดับอนุภาค ปรากฏการณ์ต่างๆ ที่เกิดขึ้นยากที่จะใช้ฟิสิกส์ทั่วไปมาทำนายได้ .. แต่ก็ยังมีแขนงวิชาหนึ่งที่สามารถทำนายปรากฏการณ์ในโลกระดับ sub-atomic ได้นั่นก็คือกลศาสตร์ควอนตัม .. และนี่คือที่มาของ “Quantum computing”
..Quantum ?
เดี๋ยวๆๆ.. Quantum ที่ว่านี่ไม่ใช่ยี่ห้อฮาร์ดดิสก์นะครับ แล้วก็ไม่ใช่บริษัทขายของทางทีวีตอนดึกๆ ด้วย…. อย่างที่บอกล่ะครับว่าคำว่า quantum computing มีความเกี่ยวโยงกับทฤษฎีกลศาสตร์ควอนตัมซึ่งเป็นพื้นฐานที่ใช้อธิบาย ปรากฏการณ์ต่างๆ ที่เกิดในระดับอะตอมได้ สิ่งที่น่าสนใจใน quantum computing ไม่ใช่ว่ามันจะเป็นคอมพิวเตอร์ที่ logic gate สร้างโดยใช้อะตอมไม่กี่ตัวหรอกครับ แต่เป็นสิ่งที่มันจะทำได้ต่างหาก .. จุดสำคัญของ quantum computing ก็คือมันเป็น “การประมวลผลแบบขนาน” .. ว้า .. ไม่เห็นแปลก การประมวลผลแบบมีมาตั้งนานแล้วนี่.. อืมม. ก็จริงครับ แต่ถ้าพิจารณาดูเราจะพบว่าการประมวลผลแบบขนานที่มีอยู่เป็นการเอา CPU หลายๆ ตัวมาทำงานพร้อมๆ กัน.. แล้วข้างใน CPU จริงๆ ก็ทำงานทีละคำสั่ง (sequential) กับข้อมูลทีละไม่กี่ bits แม้ว่าจะใช้ pipelining/vectorization มันก็ยังไม่พ้นการทำงานแบบ sequential อยู่ดีเพราะข้อจำกัดอยู่ที่รีจิสเตอร์ที่เก็บข้อมูลได้ตัวเดียวในเวลา หนึ่งๆ.. อ้าว.. แล้ว quantum computing ทำอะไรได้ดีกว่านี้ล่ะ ? .. ก็นี่แหละที่จะมาเล่าให้ฟัง
จะพูดถึง quantum computing เห็นจะหนีการอธิบายปรากฏการณ์ที่เกิดในระดับอะตอมไม่พ้นล่ะครับเพราะนั่นคือ สิ่งที่เราเอามาใช้ประโยชน์ล่ะ .. quantum mechanics มีประโยคยอดฮิตอยู่อันนึงกล่าวไว้ว่า “โลกในระดับ sub-atomic scale ไม่มีอะไรเหมือนโลกที่เราอยู่เลย” ความหมายก็คือกฏของฟิสิกส์ทั่วไปที่เคยอธิบายปรากฏการณ์ต่างๆ บนโลกแทบจะไม่มีประโยชน์ในการใช้อธิบายในระดับอนุภาค (เขียน e-mag เที่ยวนี้เลยต้องค้นเยอะมากกว่าทุกครั้งที่ผ่านมา.. เล่นเอาเหนื่อยเลย) .. ..ใครคล่องๆ เรื่องพวกนี้ พบที่ผิดตรงไหนก็บอกกันด้วยนะครับ .. ..เอาล่ะ ลองมาดูกัน .. ใน quantum mechanics มีปรากฏการณ์อยู่สองอย่างที่น่าสนใจและสามารถนำมาใช้ประโยชน์ได้ นั่นก็คือ “coherent superposition” และ “entanglement” :
Coherent superposition สามารถสังเกตได้จากการทดลองนี้ครับ
เอา beamsplitter วางทำมุม 45 องศากับเครื่องยิงอนุภาคโฟตอน (photon – อนุภาคของแสง) แล้วก็เอา photodetector วางไว้ที่มุมสะท้อนของ beamsplitter อันนึง (A) และหลัง beamsplitter อันนึง (B) โดย A และ B มีระยะห่างจากจุดตกกระทบเท่ากัน ตัวbeamsplitter จะยอมให้แสงผ่านได้ 50% และสะท้อนแสง 50% การทดลองนี้จะยิง photo ทีละตัวให้ไปตกกระทบที่ beamsplitter โฟตอนแต่ละอนุภาคมี โอกาสสะท้อนแล้วไปปรากฏที่ A 50% หรืออาจจะทะลุไปปรากฏที่ B 50% ดังนั้นในการยิง photon หนึ่งตัว มันก็อาจจะสะท้อนไปปรากฏที่ detector A “หรือ” ทะลุกระจกไปปรากฏที่ B อันใดอันหนึ่งใช่มั้ยครับ ?… ถ้าตอบว่าใช่ละก็ “ผิด” ครับ สิ่งที่เกิดขึ้นในการทดลองนี้คือโฟตอน “หนึ่ง” ตัวนั้นวิ่งไปทั้ง “สอง” ทาง – ทั้งสะท้อนและทะลุกระจก – ไปปรากฏทั้งที่ A และ B ในเวลาเดียวกัน !! .. แปลว่าอะไรเนี่ย ?? ก็แปลว่าอนุภาคตัวเดียวสามารถปรากฏตัวได้สองตำแหน่งในเวลาเดียวกันน่ะสิครับ ที่จริงจะมีการทดลองอีกสองแบบต่อจากนี้ที่ยืนยันผลว่าโฟตอนตัวเดียวสามารถ ปรากฏตัวได้สองตำแหน่งในเวลาเดียวกันจริงๆ แต่ผมคิดว่าเอาเท่านี้คงพอเข้าใจการเกิด superposition ของอนุภาคได้ระดับนึงแล้ว…
Entanglementพบครั้งแรกใน EPR Experiment ปี 1935 การทดลองนี้ทำขึ้นโดย อัลเบิร์ต ไอน์สไตน์ บอริส โปโดลสกี้ และ นาธาน โรเซน (Albert Einstein, Boris Podolsky, และ Nathan Rosen) เพื่อจะหาตำแหน่งและวัด สปินของอนุภาคในขณะเวลาหนึ่ง .. ปัญหาก็คือการจะวัดค่าทั้งสองค่าได้เที่ยงตรงไม่สามารถทำได้เนื่องจากหลัก ความไม่แน่นอนของไฮเซนเบิร์ก (จำกันได้ไหมเนี่ย ?? – ยิ่งวัดค่านึงได้ถูกต้องเพียงไร ก็จะทำให้วัดอีกค่าได้ผิดพลาดมากขึ้น) ไอน์สไตน์ก็เลยหาทางเลี่ยงโดยใช้อนุภาคสองตัว สมมติเป็น A กับ B ซึ่งมีขนาดเท่ากัน แต่มี spin ตรงกันข้าม เอา A กับ B ยิงสวนกันด้วยความเร็วเท่ากัน (ความเร็วแสง) ทั้งสามเชื่อว่าวิธีนี้ทำให้วัดตำแหน่งของ A โดยตรงได้ แต่หลังจากวัดตำแหน่งของ A แล้วผลกระทบจากการวัดตำแหน่งจะทำให้ไม่สามารถวัดสปินได้ถูกต้องตามหลักความ ไม่แน่นอน จึงใช้วิธีวัด spin ของ B เพื่อหาการเปลี่ยนแปลง moment มาคำนวณหา spin ของ A อีกที.. .. อืมม.. ฟังดูก็น่าจะใช้ได้ใช่มั้ยครับ แต่ก็ผิดอีกแล้ว..ERP Experiment เป็นการทดลองที่ล้มเหลวครับ หลักของไฮเซนเบิร์ก ยังคงใช้ได้แม้แต่ในระดับอนุภาค ซึ่งตรงกับที่ทฤษฏีควอนตัมสมัยนั้นทำนายผลของ EPR Experiment เอาไว้ว่า “ผลกระทบจากการวัดค่าที่ A จะเกิดขึ้นกับ B ด้วย แม้ว่า A กับ B จะอยู่ห่างกันไกลแค่ไหนก็ตาม” จะพูดอีกอย่างก็คืออะไรที่เกิดขึ้นกับ A ก็จะเกิดกับ B ในลักษณะเดียวกัน !! .. ตรงนี้เองที่ทำให้ไอน์สไตน์ถกเถียงกับ นีล บอห์ร (Neil Bohr) ว่าทฤษฎี quantum ไม่สมบูรณ์ เนื่องจาก การที่ผลของ A จะมีกับ B ได้แสดงว่าจะต้องมี “information” หรือสัญญาณ หรือแรงบางอย่างที่ส่งระหว่าง A กับ B แต่อนุภาค A กับ B กำลังเคลื่อนที่ด้วยความเร็วแสงออกห่างจากกัน ดังนั้นไม่ว่าสื่อที่เชื่อมระหว่าง A กับ B นั้นจะเป็นอะไร มันต้องเดินทางด้วยความเร็วมากกว่าแสงซึ่งเป็นไปไม่ได้ตามทฤษฎีสัมพันธภาพ พิเศษ .. การถกเถียงกันนี้ใช้เวลาหลายปีกว่าจะได้ผลสรุปว่า ทฤษฎีควอนตัมสมบูรณ์และถูกต้องแล้ว แม้ว่าทฤษฎีสัมพันธภาพพิเศษจะใช้อธิบาย EPR Experiment ไม่ได้แต่ก็ยังคงถูกต้องสมบูรณ์เช่นกัน …เกือบลืม…การทดลองนี้ทำให้เห็นว่าอนุภาคสองอันถ้าเตรียมถูกวิธีจะทำให้ มันมี “Entanglement” – อนุภาคสองตัวมีอะไรบางอย่างเป็นตัวผูกมันไว้ด้วยกัน แม้ว่าจะอยู่ห่างกันแค่ไหนก็ตามสิ่งที่เกิดกับอนุภาคนึงจะไปปรากฏกับคู่ของ มันด้วย (อันที่จริงอนุภาคของทั้งจักรวาลก็มี entanglement อยู่แล้ว) เราเรียกคู่อนุภาคนี้ว่ามันเกิด “quantum mechanically entangled” ระหว่างกัน .. การทดลองในปัจจุบันสามารถสร้าง entanglement ระหว่างอนุภาคในระยะราว 20 km. ..
Quantum Bits..
เอ้า..จบ เรื่อง quantum แล้ว ทีนี้ย้อนกลับมาที่คอมพิวเตอร์กัน ..เป็นที่รู้กันว่าการทำงานของคอมพิวเตอร์จริงๆ แล้วก็คือการประมวลผล “Binary Digit” หรือ bit ซึ่งเป็นพื้นฐานที่สุดที่ใช้บอกสถานะการทำงานและข้อมูล ข้อมูล 1 bit มีสองสถานะคือ “0” กับ “1” ตามนิยามของเลขฐานสอง ในกรณีของ quantum computing จะใช้สถานะของอนุภาคเป็นตัวแทนของ bit แต่เนื่องจาก coherent superposition อนุภาคตัวเดียวจึงแทนได้ทั้งสถานะของ 0 และ 1 ในเวลาเดียวกัน (ไม่ใช่ “0 หรือ 1” นะครับ ..แต่เป็น “0 และ 1 ในเวลาเดียวกัน”) ทำให้เราสามารถ encode อนุภาคนั้นให้เป็นทั้ง 0 และ 1 ได้ในครั้งเดียว เราเรียกอนุภาคที่เป็นตัวแทนข้อมูลที่มีสองสถานะนี้ว่า “quantum bit” หรือ “qubit”
ใน information theory กล่าวไว้ว่าเมื่อเอาหลายๆ bits มาต่อกันก็จะสามารถแทนสถานะหรือข้อมูลได้หลายรูปแบบมากขึ้น อย่างเช่น register ขนาด 3 bits จะสามารถแทนได้ 8 สถานะเป็นต้น อย่างไรก็ตามในขณะเวลาหนึ่งจะมีเพียงสถานะเดียวปรากฏอยู่ใน register นั้น .. แต่ถ้าเราเปลี่ยน 3-bit register เป็น 3-qubit register จะกลายเป็นว่าในขณะเวลาหนึ่งจะมีทั้ง 8 สถานะปรากฏอยู่เพราะแต่ละ qubit เป็นทั้ง 0 และ 1 ในขณะนั้น.. ดังนั้น register ขนาด n qubits จะสามารถเก็บข้อมูลได้ 2n ตัวในครั้งเดียว .. นี่แหละครับที่มันต่างจาก computer ธรรมดาและต่างจากการประมวลผลแบบขนานที่เรารู้จักกัน เพราะ parallelism ใน quantum computing เกิดขึ้นตั้งแต่หน่วยที่เล็กที่สุดในการประมวลผล การทำงานจึงเป็นแบบขนานตั้งแต่ qubit เลยล่ะ การประมวลผลเพียงครั้งเดียวกับ qubit register จะเป็นการประมวลผลข้อมูลทั้งหมดที่มีอยู่ใน qubit register นั้น … ลองคิดเปรียบเทียบ n-qubit quantum computer กับ n-bit computer ดูนะครับ .. n-qubit quantum computer ประมวลผลข้อมูล 2n ตัวในครั้งเดียว ในขณะที่ n-bit computer ต้องประมวลผล 2n ครั้ง หรือใช้ computer 2n ตัวช่วยกันประมวลผล … ยิ่ง n มากเท่าไหร่ quantum computer ยิ่งได้เปรียบเยอะเพราะมันเพิ่มขึ้นแบบ exponential
Quantum Algorithms ?
ที่ จริงแล้วคอมพิวเตอร์ธรรมดาในปัจจุบันก็สามารถคำนวณหาคำตอบตามที่เราต้องการ ได้หมดแหละครับ แต่จะใช้เวลาเท่าไหร่เท่านั้นเอง ดังนั้นขีดจำกัดของคอมพิวเตอร์ทั่วไปจึงอยู่ที่เวลาและหน่วยความจำที่ใช้ใน การประมวลผล ปัจจุบันยังมีปัญหาจำนวนมากที่ไม่สามารถหาคำตอบได้เพราะใช้เวลานานเกินไป บางปัญหาจึงใช้วิธีการจำลองแบบ (simulation) เพื่อหาคำตอบแทน แต่การจำลองแบบระบบที่ซับซ้อนมากๆ ก็ยังต้องใช้เวลานานแม้จะใช้ซูเปอร์คอมพิวเตอร์ที่เร็วที่สุดในปัจจุบัน ..เอ้า..ว่ากันเป็นเรื่องเป็นราวซักหน่อย ..โดยทั่วไปเวลาในการประมวลผลจะขึ้นกับความซับซ้อนของปัญหา ในคอมพิวเตอร์เราแบ่งความซับซ้อนของปัญหาออกเป็น 4 classes ครับ คือ P-problems, NP-Problems, NP-complete problems และ Exponential problems:
- P-problems ก็คือปัญหาที่สามารถแก้ได้ในขอบเขตของ polynomial time/space – จำนวนครั้งในการประมวลผลอยู่ในขอบเขตของ nc เมื่อ n เป็นขนาดของปัญหาและ c เป็นค่าคงที่ที่หาได้แน่นอน ปัญหาระดับ P-problem ถือว่าเป็นแก้ได้ง่ายที่สุด และใช้ทรัพยากรน้อยที่สุด
- NP-problems เป็น nondeterministic polynomial time อธิบายง่ายๆ หน่อยก็คือแต่ละ n ต้องเดาว่าคำตอบคืออะไรและการจะหาว่าคำตอบนั้นถูกหรือไม่สามารถทำได้ใน ขอบเขตของ polynomial time/space ไม่ว่าคำตอบนั้นจะถูกหรือผิด มีปัญหาหลายๆอันที่นักคณิตศาสตร์เคยคิดว่าเป็น NP-problem แต่จริงๆ แล้วไม่ใช่ การที่มีคนพิสูจน์ได้ว่าปัญหาที่เป็น NP-problem หลายๆ ปัญหาลดลงมาเหลือ P-problem ได้ ทำให้มีความหวังว่าปัญหาทั้งหมดไม่ว่าจะซับซ้อนเพียงไร ก็อาจจะหาคำตอบได้ภายในขอบเขตของ polynomial time/space
- NP-complete problems แบ่งเป็นสองกลุ่มย่อยคือ NP-Hard problem: เป็นปัญหาที่สามารถเอา algorithm ในการแก้ปัญหามาแปลงเพื่อแก้ปัญหา NP-problem อื่นๆ ได้ หรือในทางกลับกันคือ NP-problem ทุกอันสามารถแปลงเป็น NP-Hard ได้…NP-complete: คือปัญหาที่เป็นทั้ง NP-problem และ NP-Hard problem (เริ่มงงแล้ว…หึๆๆ) ตัวอย่างเช่น Traveling Salesman Problem (TSP) สิ่งที่น่าสนใจของ NP-complete คือ algorithm สำหรับแก้ปัญหาอย่างนึงสามารถแปลงไปแก้ปัญหา NP-complete อื่นๆ ได้..ดังนั้นเมื่อไหร่ที่ NP-complete มี algorithm ที่ลดรูปเหลือ P-problem ได้ก็จะหมายความว่า NP-complete อื่นๆ จะถูกลดลงมาเหลือแค่ P-problem ซึ่งเป็น class ที่ใช้ space/time น้อยที่สุด…มีนักคณิตศาสตร์จำนวนมากพยายามค้นหา algorithm ลักษณะนี้ จนถึงทุกวันนี้ยังไม่มีใครพบแม้แต่ algorithm เดียว.. แต่ก็ไม่สามารถพิสูจน์ว่ามันไม่มีอยู่จริง
- Exponential problem คือปัญหาที่แก้ได้ในขอบเขตของ exponential time/space – จำนวนครั้งในการประมวลผลอยู่ในขอบเขตของ cn ปัญหาลักษณะนี้ถือว่ามีความซับซ้อนมากที่สุด ต้องใช้ space/time สูงสุดในบรรดาปัญหาที่แก้ได้ด้วย computer .. Exponential problem ที่รู้จักกันดีก็คือ Tower of Hanoi ซึ่งมีจำนวนครั้งของการย้ายจานเป็น exponential function ของจำนวนจาน
คอมพิวเตอร์ทั่วไปเราใช้แก้ ปัญหาใน class P-problem เท่านั้น หากเกินจาก P-problem แปลว่าต้องใช้เวลาหรือ resource มากเกินไป ซึ่งส่วนใหญ่ถือว่าไม่คุ้มที่จะทำ แต่ขอบเขตตรงนี้อาจจะหมดไปได้ (หรืออย่างน้อยก็ลดลงไปได้) หากเราใช้ quantum computing .. อย่างใรก็ตาม quantum computing ไม่ได้แก้ปัญหาได้ดีกว่า computer ธรรมดาไปซะทุกอย่างหรอกครับ quantum computing ยังมีข้อจำกัดอยู่ประการหนึ่งคือการ access ข้อมูลใน qubit register จะทำได้เพียงครั้งเดียวเท่านั้น ทั้งนี้เนื่องจากการวัดค่าใดๆ กับอนุภาคที่เอามาใช้เป็น qubit register จะเป็นการทำลายสถานะของอนุภาคในขณะนั้นด้วย ข้อมูลที่ encode ไว้จึงสลายไปทันทีหลังจากถูก access ดังนั้นการจะใช้ประโยชน์จาก quantum computing จึงต้องออกแบบ algorithm ขึ้นมาเพื่อแก้ปัญหาข้อจำกัดของ qubit register และใช้ประโยชน์จาก coherent superposition กับ entanglement ให้เต็มที่ .. เราเรียก algorithm กลุ่มนี้ว่าเป็น “Quantum Algorithms” …หลายคนมีความหวังว่า quantum algorithm บางตัวอาจจะแก้ปัญหาใน class NP-Problems ได้ แต่ปัจจุบันก็ยังไม่มีใครค้นพบ algorithm ดังกล่าว อย่างไรก็ตาม quantum algorithms ก็มีออกมาพอสมควรแล้วครับ ตัวอย่างเช่น ลอฟ โกรเวอร์ (Lov Glover) ซึ่งเป็นนักวิทยาศาสตร์ประจำบริษัท ลูเซนท์ เทคโนโลยี เขียน quantum algorithm ในการ search ข้อมูลที่ไม่มีการเรียงลำดับได้ภายใน O(SQRT(n) ) ในขณะที่คอมพิวเตอร์ทั่วไปต้องใช้ถึง O(n/2) โดยเฉลี่ย .. กิลส์ บราสสาร์ด (Gilles Brassard) เอา algorithm ของโกรเวอร์ มาใช้เพื่อทำการกุญแจถอดรหัสของ Data Encryption Standard (DES) .. DES ใช้กุญแจขนาด 56-bit ดังนั้นจึงมีกุญแจที่เป็นไปได้ 256 keys (ประมาณ 7 x 1016) สมมติให้คอมพิวเตอร์ทั่วไปทดสอบกุญแจได้ 1 ล้าน ตัวต่อวินาที ก็ยังต้องใช้เวลานับพันปีกว่าจะได้กุญแจที่ถูกต้อง แต่ด้วย quantum computing + Grover’s algorithm จะใช้เวลาน้อยกว่า 4 นาที .. สิ่งที่แปลงอย่างนึงของ quantum computing คือ algorithm ส่วนใหญ่มักจะเกี่ยวข้องกับ cryptography ครับ.. อย่าง ปีเตอร์ ชอร์ (Peter Shor) ก็คิด quantum algorithm สำหรับแยกตัวประกอบของเลขจำนวนเต็มขนาดใหญ่ .. ผลกระทบของ Shor’s algorithm กับ quantum computing ทำให้ cryptography ที่มีในปัจจุบันไม่ปลอดภัยเพียงพอซะแล้ว…
Quantum Cryptography
ใน ปัจจุบันถือว่า public key cryptography มีความปลอดภัยสูงมาก การจะหากุญแจที่ถูกต้องทำได้ยากเพราะต้องใช้วิธีการหาค่า inverse ของฟังก์ชันทางเดียว เช่น การแยกตัวประกอบของเลขจำนวนเฉพาะที่มีค่ามากๆ .. นักคณิตศาสตร์เชื่อว่าการแยกตัวประกอบอยู่ใน class ของ super-polynomial time/space (เป็น P-problem ที่เกือบจะเป็น NP)… ปัจจุบันขนาดของกุญแจ ที่ใช้ใน public key cryptography เป็นตัวเลขขนาดประมาณ 512 – 4096 bits..ถ้าใช้ คอมพิวเตอร์ธรรมดา + algorithm ที่เร็วที่สุดในปัจจุบันก็อาจจะไม่สามารถแยกตัวประกอบได้เลย (แปลว่าใช้เวลาเฉลี่ยนานกว่าอายุของจักรวาล -_-”) แต่ถ้าใช้ quantum computing + Shor’s algorithm ความซับซ้อนจะเหลือเพียง O(CUBE(n)) ซึ่งใช้เวลาเพียงไม่กี่วินาทีก็ได้คำตอบ..ดังนั้นเมื่อไหร่ที่มี quantum computer ขึ้นมาจริงๆ ความปลอดภัยของ public key cryptography ในปัจจุบันจะไม่มากพอที่จะรักษาความลับของข้อมูลได้อีกต่อไป.. สิ่งที่จะมาแทนอาจจะเป็น “Quantum Cryptography” ล่ะครับ .. Quantum cryptography ตอนนี้กำลังมีการทำวิจัยกันเยอะมาก เมื่อไหร่ที่ทำได้สมบูรณ์อาจจะออกเป็น product เพื่อทดแทน public key cryptography ในปัจจุบัน สิ่งที่ quantum cryptography แตกต่างจาก cryptography ทั่วไปอย่างชัดเจนคือพื้นฐานที่ใช้เป็นตัวรักษาความลับของกุญแจ .. อย่าง public key cryptography ใช้ความยากในการแก้สมการคณิตศาสตร์ หากมีคนพยายามจะหากุญแจนั้นจะต้องแก้สมการให้ออกจึงจะได้กุญแจที่ถูกต้อง .. แต่ กรณีของ quantum cryptography จะใช้วิธีของ one-time pad (อ่านดูรายละเอียดของ one-time pad ใน e-mag ตอน cryptographyได้ครับ) และใช้คุณสมบัติของอนุภาคในการแลกกุญแจ..วิธีการก็คือให้ A random 0/1 ขึ้นมาจำนวนหนึ่งเพื่อใช้เป็นกุญแจของ one-time pad ทำการ encode 0/1 ลงในอนุภาคแล้วส่งอนุภาคนั้นไปให้ B ก็จะทำให้ B อ่านค่าแล้วแปลงกลับเป็นกุญแจที่ B ส่งมาได้ หากมีใครพยายามดักอ่านค่าจากโฟตอนที่กำลังส่งก่อนจะถึงมือ B จะทำให้สถานะของอนุภาคเปลี่ยนไป (จำได้มั้ยครับ เราวัดค่าใดๆ จากอนุภาคได้ถูกต้องเพียงครั้งแรกครั้งเดียวเท่านั้น) ค่าที่ B ได้รับก็จะไม่เหมือนกับที่ A ส่งมา .. A กับ B สามารถตรวจสอบได้ว่ามีคนแอบอ่านค่าจากอนุภาคโดยการเปรียบเทียบส่วนหนึ่งของ key ที่ A ส่งให้ B .. หากว่าค่าตรงกันมากพอ A และ B ก็มั่นใจได้ว่ากุญแจที่ได้รับถูกต้องและไม่มีใครล่วงรู้นอกจาก B เท่านั้น .. A และ B ก็จะสามารถใช้กุญแจส่วนที่เหลือมาเข้า/ถอดรหัสข้อมูลได้ จะเห็นว่าการเปรียบเทียบส่วนหนึ่งของกุญแจทำได้อย่างเปิดเผยเพราะส่วนที่ใช้ เปรียบเทียบจะไม่เอามาใช้เข้า/ถอดรหัส ในทางปฏิบัติมีการทดลองโดยใช้โฟตอนยิงผ่านสายใยแก้วในการส่งกุญแจซึ่ง ปัจจุบันทำได้สำเร็จแล้วในระยะไม่เกิน 48 กม. แต่ยังติดปัญหาที่ส่งได้ช้าและมีจุดที่ต้องแก้ใขเพื่อให้ปลอดภัยยิ่งขึ้น
Building Quantum Computers
Quantum computer ก็สร้างจาก network of logic gates เหมือนกับคอมพิวเตอร์ปกติน่ะแหละครับ.. ที่จะต่างก็คือตัว logic gate
จะต้องสร้างและทำงานกับสถานะของ quantum superpositions ได้ด้วย อย่างรูปข้างล่างนี้เป็นตัวจำลองของ Half-Adder การที่จะใช้ quantum superposition จะต้องรักษาสถานะของอนุภาคใน qubits ไม่ให้ออกไปรบกวนสิ่งแวดล้อมภายนอก ไม่งั้นข้อมูลใน qubit register จะรั่วออกไปได้ เราเรียกว่าเป็น “decoherence process” … งานหลักของผู้ออกแบบสร้าง quantum computer จึงเป็นการสร้างระบบขนาดเล็กระดับอะตอมหรืออนุภาคที่แต่ละ qubit register ให้มี entanglement และ superposition ได้แต่จะต้องอยู่เฉพาะภายใน qubit register นั้นๆ นักฟิสิกส์เชื่อว่าถึงจะสร้างระบบแบบนั้นขึ้นมาได้แต่การประมวลผลอย่างต่อ เนื่องโดยไม่ให้เกิด decoherence เลยเป็นเรื่องที่เป็นไปได้ยากมากๆ…ข้อจำกัดนี้ทำให้ quantum computer ประมวลผลได้ไม่กี่ steps ก่อนที่จะเกิด decoherence ..ฟังดูแล้วเหมือนจะไม่ได้ประโยชน์อะไรมากหากประมวลผลได้ไม่กี่ steps แต่จริงๆ ไม่กี่ steps ที่ว่านี่ก็เพียงพอแล้วครับ อย่าง quantum cryptography ใช้เพียง 1-2 qubits กับ 1 steps เท่านั้น, Glover’s algorithm ก็ใช้ประมาณ 3+ qubits กับ 6+ steps, หรือ Shor’s algorithm ก็ใช้แค่ 6+ qubits กับราวๆ 100 steps
Quantum computer ที่ใหญ่ที่สุดในปัจจุบันคำนวณได้ราว 100 logic operations กับข้อมูล 2 qubits หรือ 10 operations กับ 7 qubits ซึ่งยังเล็กเกินกว่าจะใช้ประโยชน์อะไรได้เต็มที่ บางระบบยังทำได้เพียง superposition เพียงอย่างเดียวอีกต่างหาก (เช่น Nuclear Magnetic Resonance Spectrometer ซึ่งเทียบเท่ากับ 7-qubit quantum computer) .. ส่วนตัวอย่างการทำ entanglement ปัจจุบันทำได้ในห้องทดลองโดยใช้ ion trap เป็นตัวดักอนุภาคไว้และใช้แสงเลเซอร์เป็นตัวสร้าง entangled state ซึ่งได้ความน่าเชื่อถือราวๆ 90% .. พูดถึงความน่าเชื่อถือก็เลยนึกขึ้นได้ quantum computing จะเป็นไปได้จริงก็ต่อเมื่อมี information theory มารองรับการประมวลผลครับ ส่วนนึงที่กล่าวถึงใน information theory ก็คือเรื่อง error correction .. ใน computer ปัจจุบันเราสามารถเลี่ยงปัญหาการเกิด error จาก noise ได้โดยการขยายสัญญาณให้แรงขึ้น ใน quantum mechanics เราไม่สามารถทำอย่างนั้นกับสถานะของอนุภาคได้ แต่ก็โชคดีที่คุณสมบัติ entanglement ของอนุภาคช่วยให้ทำ error correction ได้ขอเพียงรู้ว่าสถานะของอนุภาคถูกเปลี่ยนแปลงไปอย่างไรบ้างก็จะสามารถหา สถานะที่ถูกต้องของอนุภาคได้ .. quantum error correction เป็น area ที่พัฒนาไปได้มากที่สุดใน quantum information theory และจะเป็นสิ่งที่ได้นำไปใช้จริงเมื่อมีการสร้าง quantum computer มาใช้งานกัน ..Register ใน quantum computing อาจจะมีลักษณะเป็นอย่างในภาพนี้ครับ แท่ง 4 แท่งสีฟ้าๆ ตรงกลางนั่นเป็น electrode สำหรับดักให้ Calcium ion ลอยอยู่ตรงกลางซึ่งเป็นพื้นที่ของสนามแม่เหล็ก 0.01 Tesla ขนาดกว้างประมาณ 1 mm ion ทั้งหมดมีประจุเหมือนกันจึงมีแรงผลักซึ่งกันและกันอยู่ทำให้เกิดการ เคลื่อนที่ในหลายๆ รูปแบบเรียกว่า “phonons” การจะทำให้เกิด phonons ในรูปแบบใดๆ สามารถทำได้โดยการยิงแสง laser ไปที่ ion ที่ตำแหน่งต่างๆ กัน .. laser ยังใช้ในการลดอุณหภูมิและเพิ่มความเสถียรของ ion ด้วย
Trends ?
เอา เท่านี้ก่อนดีกว่าครับ ที่เล่าให้ฟังนี้แค่พื้นๆ เท่านั้นเอง ยังมีเรื่องอื่นๆ ที่ต่อเนื่องจากเรื่องนี้อีกเยอะ เช่น quantum information theory, quantum communications, และ quantum teleportations .. โดยสรุป ทฤษฎีที่เป็นตัวรองรับการประมวลผลด้วย quantum computing ในปัจจุบันก็มากเพียงพอที่จะกล่าวได้ว่า quantum computing มีความเป็นไปได้ในอนาคต ทุกวันนี้นักวิทยาศาสตร์และวิศวกรทำงานร่วมกันเพื่อสร้าง quantum computer ออกมา นักวิทยาศาสตร์คาดกันว่าในช่วง 10 ปีข้างหน้าจะมี quantum computer สำหรับประมวลผลเฉพาะทางอย่างน้อยก็ในระดับ 10 qubits ขึ้นไป เมื่อถึงเวลานั้น RSA public key cryptography จะถูก break ได้สำเร็จ quantum simulation ระบบขนาดเล็กจะเกิดขึ้น การพยากรณ์สภาพอากาศจะทำได้ถูกต้องและรวดเร็วกว่าปัจจุบัน ..ใน 50-100 ปี คาดว่าจะมี 100-qubit general-purpose quantum computer .. ถึงเวลานั้น ถ้าเรา หรือ Microsoft ยังอยู่บนโลก อาจจะได้เห็น Microsoft Windows Quantum Edition กันมั่งล่ะ… สงสัยจังว่ามันจะยัง hang อีกมั้ย.. อาจจะมี error message ใหม่ๆ เช่น “Your computer produces unstable entanglements, shutting down the system” หรือไม่ก็ “Windows cannot determine quantum states, system halted” ..เหอะๆๆๆๆ
