Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Quantum compact genetic algorithm for hard problems
Year (A.D.)
2021
Document Type
Thesis
First Advisor
ประภาส จงสถิตย์วัฒนา
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
วิศวกรรมศาสตรดุษฎีบัณฑิต
Degree Level
ปริญญาเอก
Degree Discipline
วิศวกรรมคอมพิวเตอร์
DOI
10.58837/CHULA.THE.2021.952
Abstract
งานวิจัยทางด้านคอมพิวเตอร์เชิงควอนตัม (Quantum computer) ยังคงเป็นความท้าทายสำหรับนักวิจัยในการพัฒนาเทคนิคต่างๆเพื่อให้การประมวลผลข้อมูลควอนตัมขนาดใหญ่สามารถทำได้จริง มีงานวิจัยหลากหลายสาขาเกี่ยวกับการจำลองระบบควอนตัม โดยเฉพาะด้านอัลกอริทึมควอนตัมสำหรับแก้ปัญหา NP-hard ซึ่งใช้เวลาแก้ปัญหานานเกินกว่าจะเป็นไปได้จริงในเครื่องคอมพิวเตอร์ดั้งเดิม งานวิจัยนี้นำเสนอขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัม ซึ่งเป็นการนำข้อได้เปรียบจากการประมวลผลเชิงควอนตัม ได้แก่ สภาวะซ้อนทับของสถานะควอนตัม และการประมวลผลควอนตัมแบบขนานในอัลกอริทึมการค้นหาของโกรเวอร์ (Grover's search algorithm) มาประยุกต์ใช้ในกระบวนการคัดเลือกโครโมโซมของขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดดั้งเดิมที่มีการคัดเลือกโครโมโซมที่ดี เพื่อให้ได้ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัมที่มีประสิทธิภาพดีขึ้นในแง่ของความถูกต้องของคำตอบ ขั้นตอนวิธีที่นำเสนอสามารถแก้ปัญหา traveling salesman ขนาดเล็กได้บนเครื่องจำลองคอมพิวเตอร์ควอนตัม เนื่องจากจำนวนคิวบิตที่มีอย่างจำกัดจึงไม่สามารถทำการทดลองกับปัญหา traveling salesman ขนาดใหญ่ได้ แม้ว่าจำนวนฟังก์ชันที่ใช้ในการประเมินค่าความเหมาะสมของขั้นตอนวิธีที่นำเสนอมีแนวโน้มเพิ่มขึ้นเป็นเอ็กโปเน็นเชียลเมื่อจำนวนเมืองเพิ่มขึ้น แต่ยังสามารถหาคำตอบที่ถูกต้องได้ดีกว่าขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดดั้งเดิม นอกจากนี้ผลการทดลองแสดงให้เห็นว่าจำนวนรอบของโกรเวอร์ที่เหมาะสมช่วยเพิ่มประสิทธิภาพในการหาคำตอบที่เหมาะสมที่สุด ในขณะที่จำนวนช็อตหรือจำนวนรอบที่รันอัลกอริทึมช่วยเพิ่มความน่าเชื่อถือให้กับคำตอบที่ได้จากการวัดค่าสถานะคิวบิต
Other Abstract (Other language abstract of ETD)
Research in the field of quantum technology remains a great challenge to researchers in the future to develop techniques for making large-scale quantum information processing a reality. The simulation of quantum systems is an important problem in many fields. A quantum algorithm is one of the topics being studied for solving NP-hard problems that take too long to solve on classical computers. This paper aims to propose the Quantum compact genetic algorithm, that exploits the advantages of quantum computing. There is quantum superposition and quantum parallelism in Grover's search algorithm. It was combined with a compact genetic algorithm with an elite (cGA with an elite) in the selection process to get a higher performance in term of the solution quality. The proposed algorithm can be run on an IBM QASM simulator to solve the small-sized traveling salesman problem (TSP). Although the number of function evaluations of the proposed algorithm grows exponentially as the number of cities grows, it still outperforms the cGA with an elite in finding the optimal solution. The results also showed that utilizing the right number of Grover iterations increases the efficiency in finding the optimal solution, whereas the number of shots increases the reliability of the answers.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
สุขเสน, กมลลักษณ์, "ขั้นตอนวิธีเชิงพันธุกรรมแบบกระชับชนิดควอนตัมสำหรับปัญหายาก" (2021). Chulalongkorn University Theses and Dissertations (Chula ETD). 5494.
https://digital.car.chula.ac.th/chulaetd/5494