Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การศึกษาการเปรียบเทียบประสิทธิภาพของอัลกอริธึมของกรูเวอร์ในการแก้ปัญหาบูลีนด้วยวงจรควอนตัม
Year (A.D.)
2025
Document Type
Thesis
First Advisor
Prabhas Chongstitvatana
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Computer Science
DOI
10.58837/CHULA.THE.2025.184
Abstract
This study explores how well Grover's Algorithm performs in solving the Boolean Satisfiability Problem (SAT) using quantum circuits. The algorithm is implemented with IBM's Qiskit framework and compared to classical brute-force methods. Experiments focus on 3-SAT, 4-SAT, and 5-SAT problems, using quantum simulators and IBM quantum hardware. The results show that Grover's Algorithm is more efficient, offering a theoretical quadratic speedup over classical methods. However, practical issues like limited qubit availability, hardware noise, and optimization challenges impact its current performance. The data highlights the potential for quantum computing to scale and solve NP-complete problems. This research shows how quantum computing can improve problem-solving and lays the groundwork for future studies on more complex SAT problems and advanced quantum hardware.
Other Abstract (Other language abstract of ETD)
การศึกษานี้สำรวจว่าประสิทธิภาพของอัลกอริธึมของกรูเวอร์ในการแก้ปัญหาบูลีนเป็นอย่างไรโดยใช้วงจรควอนตัม อัลกอริธึมนี้ถูกนำมาใช้งานโดยใช้เฟรมเวิร์กคิสคิทของไอบีเอ็มและมีการเปรียบเทียบกับวิธีลองผิดลองถูกแบบดั้งเดิม การทดลองมุ่งเน้นไปที่ปัญหาสามแซท, สี่แซท, และห้าแซท โดยใช้ทั้งตัวจำลองควอนตัมและฮาร์ดแวร์ควอนตัมของไอบีเอ็ม ผลการทดลองแสดงให้เห็นว่าอัลกอริธึมของกรูเวอร์มีประสิทธิภาพมากกว่า โดยมีความได้เปรียบทางทฤษฎีแบบกำลังสองเมื่อเทียบกับวิธีคลาสสิก อย่างไรก็ตาม ในการใช้งานจริงยังคงเผชิญกับข้อจำกัด เช่น จำนวนคิวบิทที่มีอยู่จำกัด, สัญญาณรบกวนจากฮาร์ดแวร์, และความท้าทายในการปรับแต่งและเพิ่มประสิทธิภาพของวงจรควอนตัม งานวิจัยนี้แสดงให้เห็นว่าคอมพิวเตอร์ควอนตัมสามารถยกระดับความสามารถในการแก้ปัญหาทางคณิตศาสตร์ที่ซับซ้อนได้ และวางรากฐานสำหรับการศึกษาต่อไปในอนาคตเกี่ยวกับปัญหาบูลีนที่ซับซ้อนยิ่งขึ้น และการพัฒนาฮาร์ดแวร์ควอนตัมที่ล้ำหน้ามากยิ่งขึ้น
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Jipipob, Jirapas Unison, "A benchmarking study of grover's algorithm for solving boolean sat with quantum circuits" (2025). Chulalongkorn University Theses and Dissertations (Chula ETD). 75071.
https://digital.car.chula.ac.th/chulaetd/75071