Quantum Computing

หมายเหตุ: บทความนี้เป็นส่วนหนึ่งของ "บทความชุด Article with Machine Translation" ซึ่งเป็นการแปลบทความจากต้นฉบับภาษาต่างประเทศด้วย Machine translation ดังนั้นจึงมีข้อผิดพลาดอยู่หลายจุด ขอให้ผู้อ่านโปรดใช้วิจารณญาณในการอ่าน ทาง EPT ไม่ขอรับประกันว่าข้อมูลที่ท่านได้อ่านเป็นข้อมูลที่ถูกต้อง และไม่ขอรับผิดชอบความเสียหายใด ๆ ที่เกิดต่อผู้อ่านทั้งทางร่างกาย จิตใจ ทรัพย์สิน ฯลฯ นะครับ

การคำนวณเชิงควอนตัม

การคำนวณเชิงควอนตัม คือ การคำนวณโดยใช้ปรากฎการณ์เชิงกลศาสตร์ควอนตัม เช่น การซ้อนทับ (superposition) และการพัวพัน (entanglement) 

คอมพิวเตอร์ควอนตัม คือ อุปกรณ์ที่ทำการคำนวณเชิงควอนตัมซึ่งมันแตกต่างจาก คอมพิวเตอร์ทั่วๆไปที่เราใช้กันอยู่ในปัจจุบันซึ่งเป็นแบบเลขฐาน 2 ที่เป็นอิเล็กทรอนิกส์มีพื้นฐานอยู่บนทรานซิสเตอร์ ในขณะที่การคำนวณดิจิทัลธรรมดาๆต้องการข้อมูลที่ถูก encode ไปยังตัวเลขฐาน 2 (บิต)(bit) ซึ่งแต่ละบิตจะอยู่ 1 ใน 2 ของสถานะที่แน่นอน (ไม่ 0 ก็ 1) การคำนวณ ควอนตัมใช้ควอนตัมบิต (qubit)ซึ่งสามารถเป็น superposition ของสถานะได้ เครื่องจักร Turing แบบ Quantum เป็นโมเดลทางทฤษฎีของคอมพิวเตอร์และยังรู้จักกันใน ฐานะที่เป็นคอมพิวเตอร์ควอนตัมแบบทั่วไป (Universal Quantum Computer) อีกด้วย ในสาขาของการคำนวณเชิงควอนตัมนี้เริ่มต้นขึ้นด้วยงานของ Paul Benioff และ Yuri Manin ในปี 1980 , Richard Feynman ในปี 1982 และ David Deutsch ในปี 1985 คอมพิวเตอร์ควอนตัมที่ใช้การสปินเป็นบิตควอนตัมซึ่ง ถูกพัฒนาขึ้นสำหรับใช้เป็นควอนตัมกาลอวกาศในปี 1968 

เมื่อถึงปี 2018 การพัฒนาคอมพิวเตอร์ควอนตัมที่เกิดขึ้นจริงยังอยู่ในช่วงแรกเริ่ม แต่การทดลองได้ดำเนินการแล้วในการคำนวณเชิงควอนตัมซึ่งเป็นการใช้ควอนตัมบิต (qbit)จำนวนน้อยๆ การวิจัยทั้งทางปฏิบัติและทางทฤษฎียังคงดำเนินต่อไป หน่วย งานรัฐบาลของหลายๆประเทศและหน่วยงานทางทหารหลายแห่งได้ให้เงินทุนสนับสนุนการวิจัยคอมพิวเตอร์ควอนตัมเพิ่มเติมใน การพยายามพัฒนาคอมพิวเตอร์ควอนตัมสำหรับพลเรือน , ธุรกิจ , การค้า , สิ่งแวดล้อมและจุด ประสงค์เพื่อความมั่นคงแห่งชาติ เช่น การเข้ารหัส คอมพิวเตอร์ควอนตัม ขนาดเล็กๆ 20-qubit ถูกสร้างขึ้นสำหรับการทดลองผ่านทางโครงการ IBM quantum experience ระบบ D-Wave Systems ได้ถูกพัฒนาเวอร์ชั่นของพวกเขา เองของคอมพิวเตอร์ควอนตัมที่ใช้การหลอม

คอมพิวเตอร์ควอนตัมแบบขนาดใหญ่ ในทางทฤษฎียังสามารถที่จะใช้แก้ปัญหา ได้รวดเร็วกว่าคอมพิวเตอร์แบบคลาสสิคใดๆที่มีอยู่แล้วอย่างแน่นอน เมื่อเปรียบเทียบกับ Computer แบบ Classical แม้แต่Super Computer ที่ดีที่สุดที่ในปัจจุบัน 

ในการคำนวนแบบควอนตัมเราจำเป็นต้องมี Algorithm แบบใหม่ให้กับปัญหานั้นๆ กล่่าวคือ Algorithm แบบปกติที่ใช้ใน Classical Computer ไม่สามารถ Copy แล้วมา run บน Quantum Computer ได้เลยต้องมีการพัฒนา Algorithm แบบใหม่สำหรับ Quantum Computer 

Algorithm สำหรับ Quantum Computer ที่โด่งดังเช่น

1.  การแยกตัวประกอบเฉพาะของจำนวนเต็ม  Shor's algorithm (ซึ่งเป็นอัลกอริทึมควอนตัม) (ซึ่งสามารถ Attack Algorithm RSA และกระบวนการเข้ารหัสของ 90 % ของ ระบบ Computer ทั่วโลก ตั้งแต่ตอนที่คุณเข้า WEB โป้ไปดูหนังโป้(ถ้า WEB โป้ ใช้ protocol แบบ Https)จนกระทั้งถึงตอนที่คุณกดรหัสบัตร ATM ที่ตู้ ATM )

2. การจำลองของระบบควอนตัม many-body มันยังมีควอนตัมอัลกอริทึม เช่น Simon's algorithm ซึ่งรันได้รวดเร็ว กว่าอัลกอริทึมคลาสสิกที่น่าจะเป็นไปได้ใดๆ

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

ความรู้พื้นฐาน

คอมพิวเตอร์คลาสสิคจะมีหน่วยความจำที่ทำขึ้นมาจากบิต (Bit) ที่แต่ละบิตเป็นตัว แทนของ 1 หรือ 0 อย่างใดอย่างหนึ่งในเวลาเดียวเท่านั้น (อาจจะเป็นการมีประจุไม่มีประจุ / การมีความต่างศักดิ์ ไม่มีความต่างศักดิ์ แทนก็ได้)คอมพิวเตอร์ควอนตัมมีลำดับของ qubits โดย qubit เดี่ยวๆสามารถแทน 1 , 0 หรือการทับซ้อนใดๆของควอนตัมของ สถานะ qubit ทั้ง 2 นี้ คู่ของ qubits สามารถอยู่ในการซ้อนทับของควอนตัมใดๆ ของ 4 สถานะก็ได้และถ้ามี 3 qubits ในการทับซ้อนใดๆจะมีได้ใน 8 สถานะ โดยปกติแล้ว คอมพิวเตอร์ควอนตัมด้วย n qubits สามารถที่จะอยู่ในการทับซ้อนที่พลการของ  2n สถานะที่แตกต่างกันไปพร้อมกันได้ (สิ่งนี้เปรียบเทียบกับคอมพิวเตอร์ธรรมดา ที่สามารถเป็น 1 ในสถานะ 2n นี้ได้ในเวลาใดเวลาหนึ่งเท่านั้น) 

พูดให้ชัดเจนคือ สิ่งนี้ทำให้คอมพิวเตอร์แบบ Quantum สามารถทำงานได้เร็วขึ้นมากว่า Computer ธรรมดาเพราะว่าสามารถแทนหลายๆสถานะในเวลาเดียวกันได้ เนื่องจาก qubit ไม่ได้จำเป็นต้องเป็น 0 หรือ 1 ในเวลาเดียวกันเท่านั้น qubit สามารถเป็นสถานะที่อยู่ระหว่าง 1 หรือ 0 (ใน Complex Space ได้ ) หลายคนกล่าวว่าสิ่งนี้เป็นการยืมพลังประมาณผลจาก จักรวาลอื่นมาใช้ นี่เป็นคำอธิบายที่สอดคล้องกับผลการทดลอง ซึ่งในปัจจุบันนักฟิสิกส์หลายคนก็เชื่อในทฤษฏี จักรวาลคู่ขนาน ทฤษฏีหลายๆจักรวาล (Multivers Theory) แต่สำหรับบทความนี้เราจะไม่ แตะต้องสิ่งที่ยังคลุมเคลืออยู่แบบนั้นเราจะสนใจเฉพาะสิ่งที่เกิดขึ้นจริงในห้องทดลองและพิสูจณ์ได้ด้วยคณิตศาสตร์เท่านั้น

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

จบลงด้วย measurement , การยุบระบบของ qubits ไปเป็น 1 ใน 2n 

eigenstates ที่ๆแต่ละ qubit เป็น 0 หรือ 1 และสลายตัวไปเป็นสถานะคลาสสิค ถึงแม้กระนั้น ผลลัพธ์ที่ได้จึงเป็นบิตคลาสสิค n ของข้อมูลที่มีความน่าจะเป็นมากที่สุด (หรือถ้า อัลกอริทึมไม่ได้จบด้วย measurement    ผลลัพธ์ คือ สถานะควอนตัมที่ไม่มีใคร สังเกตเห็น) อัลกอริทึมควอนตัมมักเป็นความน่าจะเป็นในการที่พวกเขาให้แนวทาง ที่ถูกต้องเฉพาะกับความน่าจะเป็นที่รู้จักเท่านั้น โน๊ตว่าในแง่ของการคำนวณที่ไม่ใช่ การกำหนดจะต้องไม่ถูกใช้ในกรณีนี้ เพื่อหมายความถึงความเป็นไปได้ (การคำนวณ) เพราะว่าในแง่ที่ไม่ใช่การกำหนดมีความ หมายแตกต่างกันออกไป ในวิทยาศาสตร์คอมพิวเตอร์ 

ตัวอย่างของการดำเนินการ qubits ของคอมพิวเตอร์ควอนตัมสามารถเริ่มต้นด้วย การใช้อนุภาคกับ 2 สถานะสปิน : “ลง” และ “ขึ้น” (โดยปกติแล้วจะเขียนว่า |↓⟩ และ |↑⟩ หรือ |0⟩ และ |1⟩) นี่เป็นความจริงเนื่องจากระบบดังกล่าวสามารถแมป ไปยังระบบ spin-1/2 ที่มีประสิทธิภาพได้   
 

กฎของการดำเนินการ

หมายเหตุ : ในส่วนนี้รวมลิสต์รายการของแหล่งอ้างอิงต่างๆ แต่แหล่งที่มายังไม่ ชัดเจนเนื่องจากมี inline citations ที่ไม่เพียงพอ โปรดช่วยเพื่อที่จะปรับปรุงส่วนนี้ โดยการแนะนำการอ้างอิงที่แม่นยำมากขึ้น (กุมภาพันธ์ 2018) 

คอมพิวเตอร์ควอนตัมที่มีจำนวน qubits เป็นพื้นฐานที่แตกต่างจากคอมพิวเตอร์ แบบคลาสสิกประกอบด้วยหมายเลขเดียวกันกับบิตคลาสสิค ยกตัวอย่างเช่น การเป็นตัวแทนของสถานะของระบบ n-qubit บนคอมพิวเตอร์คลาสสิคที่ต้องการ การจัดเก็บค่าสัมประสิทธิ์ที่ซับซ้อน 2n ในขณะที่การจำแนกสถานะของระบบ คลาสสิค n-bit มันเพียงพอสำหรับการจัดหาค่าของ n bits นั่นแหละ เฉพาะเลข n เท่านั้น ถึงแม้ว่าความเป็นจริงนี้อาจจะดูเหมือนเพื่อแสดงว่า qubits สามารถที่จะ รองรับข้อมูลที่มากขึ้นทางเอ็กโปเน็นเชียลได้มากกว่าแบบคลาสสิคที่ที่คล้ายกัน ของพวกเค้า ต้องระมัดระวังไม่ให้มองข้ามข้อเท็จจริงที่ว่า qubits เป็นเพียงการ ซ้อนทับของทุกสถานะเท่านั้น นั่นหมายความว่าเมื่อสถานะสุดท้ายของ qubits ถูก วัด พวกมันจะถูกค้นพบใน 1 ของการกำหนดค่าที่เป็นไปได้ที่พวกเขาอยู่ก่อน measurement โดยปกติแล้วมันเป็นเรื่องที่ผิดที่จะคิดว่าระบบของ qubits เป็น สถานะใดสถานะหนึ่งเฉพาะก่อน measurement เพราะว่าความจริงที่ว่า พวก เขาอยู่ในการทับซ้อนของสถานะก่อน measurement มีผลโดยตรงต่อผลลัพธ์ที่ เป็นไปได้ของการคำนวณ

Qubits ประกอบด้วยอนุภาคควบคุมและวิธีการควบคุม (เช่น อุปกรณ์ที่ดักจับ อนุภาคและสลับพวกมันจากสถานะหนึ่งไปยังอีกสถานะหนึ่ง)

เพื่อการเข้าใจที่ดีขึ้นในจุดนี้ พิจารณาคอมพิวเตอร์คลาสสิคที่ดำเนินการบนการลง ทะเบียน 3 บิต ถ้าสถานะที่แน่นอนของการลงทะเบียนในเวลาที่กำหนดไม่รู้จัก มัน สามารถถูกอธิบายเป็นการกระจายความน่าจะเป็นที่มากกว่า 2 กำลัง 3 = 8 โดย 3 บิตสตริงที่แตกต่าง 000, 001, 010, 011, 100, 101, 110 และ 111 ถ้ามันไม่มี ความไม่แน่นอนเหนือสถานะของมัน จริงๆแล้วมันคือ 1 ในสถานะเหล่านี้ด้วย ความเป็นไปได้ 1 อย่างไรก็ตาม ถ้าเป็นคอมพิวเตอร์ที่มีความน่าจะเป็นก็มีความ เป็นไปได้ที่จะอยู่ในสถานะที่แตกต่างกันไป สถานะของคอมพิวเตอร์ควอนตัม 3 qubit ถูกอธิบายในทิศทางเดียวกันโดยเวกเตอร์แปดมิติ
(a0,a1,a2,a3,a4,a5,a6,a7) (หรือเวกเตอร์ 1 มิติด้วย vector node แต่ละตัวที่ รองรับแอมพลิจูดและสถานะเป็นบิตสตริงของ qubits) อย่างไรก็ตาม ที่นี่ค่า สัมประสิทธิ์ aiเป็นจำนวนเชิงซ้อนและมันเป็นผลรวมของกำลังของค่า สัมประสิทธิ์ของค่าสัมบูรณ์ ที่ต้องเท่ากับ 1 สำหรับ i แต่ละตัว ค่าสัมบูรณ์กำลัง 2 ของ ให้ความน่าจะเป็นแก่ระบบที่ถูกพบเจอในสถานะ i-th 

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

ถ้าคุณวัด 3 qubits คุณจะสังเกตเห็นสตริง 3 บิต ความน่าจะเป็นของการวัดสตริงที่ กำหนด คือ ขนาดความยาวของสตริงที่มีค่าสัมประสิทธิ์สตริง (กล่าวคือ ความน่าจะ เป็นของการวัด , ความเป็นไปได้ของการวัด,และอื่นๆ)

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

เวกเตอร์ 8 มิติสามารถถูกระบุในหลายๆทางที่แตกต่างกันขึ้นอยู่กับว่าพื้นฐาน อะไรที่ถูกเลือกสำหรับพื้นที่ว่าง พื้นฐานของบิตสตริง (เช่น 000, 001, …, 111) ถูกรู้จักกันในฐานะที่เป็นพื้นฐานการคำนวณ พื้นฐานอื่นๆที่เป็นไปได้ คือ เวกเตอร์ หน่วยความยาว , มุมฉากและ eigenvectors ของ Pauli-x operator     

Ket notation ถูกใช้บ่อยๆเพื่อสร้างตัวเลือกของความขัดแย้งพื้นฐาน ยกตัวอย่าง เช่น สถานะ ในพื้นฐานการคำนวณสามารถเขียน ได้เป็น :

พื้นฐานการคำนวณสำหรับ qubit เดี่ยว (2 มิิติ) คือ และ

การใช้ eigenvectors ของ Pauli-x operator โดย qubit เดี่ยวๆคือ และ

การดำเนินการ

หมายเหตุ : ส่วนนี้ไม่ใช่ cite ของ sources ใดๆ โปรดช่วยปรับปรุงส่วนนี้ โดยการ เพิ่มการอ้างอิงไปยังแหล่งข้อมูลที่น่าเชื่อถือ อาจมีการคัดค้านและนำ material ที่ ไม่ใช่ source ออก (กุมภาพันธ์ 2018) 

ขณะที่สถานะคลาสสิค 3-bit และสถานะควอนตัม 3-qubit แต่ละอันเป็นเวกเตอร์ 8 มิติ พวกมันถูกควบคุมค่อนข้างที่จะแตกต่างกันสำหรับการคำนวณแบบควอนตัม หรือแบบคลาสสิค สำหรับการคำนวณในแต่ละกรณี ระบบจะต้องเริ่มต้น ตัวอย่าง สำหรับสตริง 0 ทั้งหมด |000⟩ สัมพันธ์กับเวกเตอร์ (1,0,0,0,0,0,0,0) ในการ คำนวณแบบสุ่มแบบคลาสสิก ระบบจะวิวัฒนาการไปตามการใช้เมทริกซ์แบบสุ่ม (stochastic matrices) ซึ่งรักษาความน่าจะเป็นที่เพิ่มขึ้นเป็น 1 (กล่าวคือ รักษา    L1 norm) 

ในทางกลับกัน ในการคำนวณควอนตัม การดำเนินงานที่ได้รับอนุญาตเป็น unitaries เมทริกซ์ซึ่งเป็นการหมุนที่มีประสิทธิภาพ (พวกเขารักษาว่าผลรวมของ การยกกำลัง 2 จะเท่ากับหนึ่ง , Euclidean or L2 norm) (แท้ที่จริงแล้ว unitaries แบบไหนที่สามารถนำมาประยุกต์ใช้ได้นั้นขึ้นอยู่กับฟิสิกส์ของอุปกรณ์ควอนตัม) ดังนั้น เพราะการหมุนสามารถถูก undo ด้วยการหมุนย้อนกลับ การคำนวณ ควอนตัมสามารถย้อนกลับได้ (ในทางเทคนิคแล้ว การดำเนินการควอนตัม สามารถเป็นการรวมกันของความน่าจะเป็นของ unitaries ได้ ดังนั้น การคำนวณ ควอนตัมสามารถเป็น generalize (รูปทั่วไป) ของการคำนวณแบบคลาสสิคได้ ดูที่ quantum circuit [วงจรควอนตัม] สำหรับสูตรที่แม่นยำยิ่งขึ้น) 

สุดท้ายนี้ เมื่อสิ้นสุดอัลกอริทึม ผลลัพธ์จำเป็นที่จะต้องถูกอ่านออกมา ในกรณีของ คอมพิวเตอร์แบบคลาสสิค ตัวอย่างมาจาก probability distribution (การกระจาย ตัวของความน่าจะเป็น) บน register 3-bit เพื่อให้ได้สตริง 3 บิตที่แน่นอน ที่บอกว่า 000

ในทางกลไกของควอนตัม 1 measures สถานะ 3-qubit ซึ่งสมดุลที่จะยุบสถานะ ควอนตัมลงไปเป็นการกระจายตัวแบบคลาสสิค (ด้วยค่าสัมประสิทธิ์ของสถานะ แบบคลาสสิคเป็นค่าที่ยกกำลังแล้วของขนาด (magnitude) ของค่าสัมประสิทธิ์ สำหรับสถานะแบบควอนตัมอย่างที่อธิบายไว้ด้านบน) ตามด้วยค่าที่ sampling ได้จากการกระจายนั้น สิ่งนี้ทำลายสถานะควอนตัมดั้งเดิม หลายๆอัลกอริทึม จะให้เฉพาะคำตอบที่ถูกต้องด้วยความน่าจะเป็นที่แน่นอนเท่านั้น อย่างไรก็ตาม ด้วยการเริ่มต้น รันและวัดผลลัพธ์ทั้งหมดซ้ำๆของคอมพิวเตอร์ควอนตัม , ความน่าจะเป็นที่จะได้รับคำตอบที่ถูกต้องสามารถเพิ่มขึ้นได้ ในทางกลับกัน การคำนวณควอนตัม counterfactual (counterfactual quantum computation) อนุญาตให้คำตอบที่ถูกต้องถูกอนุมานเมื่อคอมพิวเตอร์ควอนตัมไม่ได้รันจริงๆใน ความรู้สึกทางเทคนิค ถึงแม้ว่าการเริ่มต้นด้วยความรวดเร็วและ measurements ที่ถี่เป็นส่วนหนึ่งของโปรโตคอลการคำนวณ counterfactual ก็ตาม

สำหรับรายละเอียดเพิ่มเติมเกี่ยวกับลำดับขั้นของการดำเนินการต่างๆที่สามารถใใช้ได้มากมาย quantum algorithms , ดูที่ universal quantum computer, Shor's algorithm, Grover's algorithm, Deutsch–Jozsa algorithm, amplitude amplification, quantum Fourier transform, quantum gate, quantum adiabatic algorithm และ quantum error correction.

สิ่งที่สามารถเกิดขึ้นได้

Integer factorization (การแยกตัวประกอบของจำนวนเต็ม) เป็นรากฐานที่สำคัญ ที่ใช้ในการรักษาความปลอดภัยของระบบการเข้ารหัสลับแบบคีย์สาธารณะ
(public key cryptographic) ซึ่งการแยกตัวประกอบที่เป็นจำนวนเฉพาะของ จำนวนเต็มใหญ่ๆถูกเชื่อว่าไม่สามารถทำได้ด้วยคอมพิวเตอร์ธรรมดา (เช่น ผลลัพธ์ ของจำนวนเฉพาะ 2 ตัวของเลข 300 หลัก) เพื่อให้เห็นภาพชัดเจน คอมพิวเตอร์ แบบควอนตัมสามารถแก้ปัญหานี้ได้อย่างมีประสิทธิภาพโดยการใช้
Shor's algorithm เพื่อที่จะหาตัวประกอบของมัน ความสามารถนี้จะช่วยให้ คอมพิวเตอร์ควอนตัมสามารถทำลายระบบการเข้ารหัสลับต่างๆที่ใช้งานได้ใน ปัจจุบัน ในแง่ที่ว่าจะเป็นอัลกอริทึมเวลาพหุนาม (polynomial time) (ในจำนวน หลักของจำนวนเต็ม) สำหรับการแก้ปัญหาโดยเฉพาะอย่างยิ่ง รหัสคีย์สาธารณะ ที่เป็นที่นิยมที่สุด มีพื้นฐานอยู่บนการแยกตัวประกอบจำนวนเต็มที่มีความยาก หรือปัญหาล็อกการิทึม ที่เป็นไปได้ ทั้ง 2 อันนี้ สามารถถูกแก้ได้โดย Shor's algorithm โดยเฉพาะอัลกอริทึม RSA, Diffie-Hellman, และ elliptic curve Diffie-Hellman สามารถถูกทำให้พังได้ สิ่งเหล่านี้ใช้เพื่อปกป้องความปลอดภัยของ Web pages , อีเมลที่เข้ารหัสและชนิดของข้อมูลอื่นๆอีกมากมาย การทำลายเหล่า นี้จะมีการแตกกิ่งก้านที่ สำคัญต่อความเป็นส่วนตัวและความปลอดภัยของข้อมูล อิเล็กทรอนิกส์ 

อย่างไรก็ตาม อัลกอริทึมการเข้ารหัสลับอื่นๆจะไม่ปรากฎเพื่อถูกทำให้พังโดย อัลกอริทึมเหล่านั้น อัลกอริทึม public-key บางอันขึ้นอยู่บนปัญหาอื่นๆ นอกเหนือ จากการแยกตัวประกอบจำนวนเต็มและเป็น log ที่ไม่ต่อเนื่องไปยังอันที่ประยุกต์ ใช้ Shor's algorithm เช่น ระบบรหัสลับ McEliece  มีพื้นฐานอยู่บนปัญหาใน ทฤษฎีการเขียนโค้ด ระบบรหัสลับ Lattice-based ยังไม่รู้ว่าจะถูกทำให้พังด้วย คอมพิวเตอร์ควอนตัมและหาอัลกอริทึม polynomial time สำหรับแก้ปัญหาของ กลุ่มย่อยของ dihedral ที่ถูกซ่อน ซึ่งจะพังตาข่ายหลายๆอันที่มีพื้นฐานของระบบ รหัสลับ เป็นปัญหาปลายเปิดกรณีศึกษาที่ดีมาก ได้รับการพิสูจน์แล้วว่า การใช้ อัลกอริทึมของ Grover เพื่อที่จะแยกอัลกอริทึมสมมาตร (คีย์ลับ) โดย brute-force ต้องใช้เวลาร้องขอเท่ากับประมาณ 2n/2 ของอัลกอริทึมการเข้ารหัสลับพื้นฐาน เทียบกับประมาณ 2n ในกรณีคลาสสิค หมายความว่าความยาวของคีย์สมมาตรจะ ลดลงครึ่งหนึ่งได้อย่างมีประสิทธิภาพ : AES-256 มีการรักษาความปลอดภัยเดียว กันต่อการโจมตีโดยใช้ Grover's algorithm ที่ AES-128 มีการต่อต้านต่อการ ค้นหา brute-force (ดูที่ Key size) การเข้ารหัสลับสามารถที่จะเติมเต็มที่อาจเกิด ขึ้นของบางฟังก์ชั่นของการเข้ารหัสคีย์สาธารณะได้

นอกเหนือจากการแยกตัวประกอบและ logarithms ที่ไม่ต่อเนื่องแล้ว quantum algorithms ยังเสนอสิ่งที่มากกว่าการเร่งความเร็วพหุนามซึ่งมากกว่าอัลกอริทึม คลาสสิกที่รู้จักกันดีที่ได้รับการค้นพบสำหรับหลายๆปัญหา รวมไปถึงการจำลอง กระบวนการทางฟิสิกส์ควอนตัมจากเคมีสถานะฟิสิกส์ที่เป็นของแข็ง , การ ประมาณของ Jones polynomials และแก้ปัญหา Pell's equation ไม่มีการ พิสูจน์ทางคณิตศาสตร์ที่ถูกพบว่าอัลกอริทึมคลาสสิคที่มีความเร็วเท่ากันไม่สามารถถูกค้นพบได้ แม้ว่าจะถือว่าไม่น่าเป็นไปได้ สำหรับปัญหาบางอันคอมพิวเตอร์ ควอนตัมเสนอ polynomial speedup ตัวอย่างที่เป็นที่รู้จักมากที่สุดของสิ่งนี้ คือ quantum database search (การค้นหา quantum database) ซึ่งสามารถถูก แก้ไขได้โดย Grover's algorithm โดยการใช้คำถามในเชิงสมการกำลังสองไปยัง database ที่น้อยกว่าที่ต้องการโดยอัลกอริทึมแบบคลาสสิก ในกรณีนี้ข้อดี คือ สามารถพิสูจน์ได้ ตัวอย่างอื่นๆบางตัวอย่างของ quantum speedups ที่สามารถ พิสูจน์ได้ สำหรับปัญหาการสอบถามซึ่งต่อมาถูกค้นพบ เช่น สำหรับการหาการชน กันในฟังก์ชั่น 2 ไป 1 และการประเมิน NAND trees

พิจารณาปัญหาที่มีคุณสมบัติ 4 อย่างนี้ :

1. วิธีเดียวที่จะแก้ปัญหามัน คือ การเดาคำตอบซ้ำๆแล้วตรวจสอบมัน
2. จำนวนคำตอบที่เป็นไปได้ที่จะเช็ก คือ เท่ากันกับจำนวนของ inputs
3. ทุกๆคำตอบที่เป็นไปได้ใช้เวลาที่เท่ากันในการเช็ก
4. มันไม่มีคำใบ้เลยว่าคำตอบไหนจะดีที่สุด : สร้างความเป็นไปได้แบบสุ่มที่ดี พอๆกับที่จะเช็กพวกมันในลำดับพิเศษบางอย่าง 

ตัวอย่างของสิ่งนี้ คือ password cracker ที่ตั้งใจที่จะเดารหัสสำหรับไฟล์ที่เข้ารหัส (สมมติว่ารหัสมีความยาวที่เป็นไปได้สูงสุด)

สำหรับปัญหาที่มีคุณสมบัติ 4 อย่างนี้ เวลาสำหรับคอมพิวเตอร์ควอนตัมที่จะแก้ไข ปัญหานี้จะเป็นสัดส่วนของรากที่ 2 ของจำนวนของ inputs มันสามารถใช้เป็นการ โจมตี symmetric ciphers ได้ด้วย เช่น Triple DES และ AES โดยตั้งใจที่จะเดา

คีย์ลับ (secret key) นั้น

Grover's algorithm สามารถที่จะถูกใช้เพื่อให้ได้รับความเร็วเป็นสองเท่าในการ ค้นหาแบบ brute-force สำหรับคลาสของปัญหาที่รู้จักกันในชื่อ NP-complete มันถูกแสดงว่าคอมพิวเตอร์ควอนตัมตัวแปรที่ไม่ใช่ท้องถิ่นที่ถูกซ่อนสามารถ ดำเนินการการค้นหาของฐานข้อมูล N-item ได้มากที่สุดที่ขั้นตอน สิ่งนี้จะรวดเร็วกว่าขั้นตอน ที่นำมาโดย Grover's algorithm วิธีการค้นหาไม่อนุญาตให้คอมพิวเตอร์ควอนตัมทำการแก้ปัญหา NP-Complete ใน polynomial time    

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

Quantum Supremacy

John Preskill ได้ทำการแนะนำในแง่ของ Quantum Supremacy เพื่อที่จะอ้างถึง ข้อดีของ speedup ในทางข้อสันนิษฐานว่าคอมพิวเตอร์ควอนตัมสามารถที่จะ ครอบคลุมคอมพิวเตอร์คลาสสิคได้ในบางสาขา Google ได้ประกาศในปี 2017 ว่ามันคาดหวังที่จะประสบความสำเร็จในเรื่องของ Quantum Supremacy ในตอน ปลายปีและ IBM พูดว่าคอมพิวเตอร์คลาสสิคที่ดีที่สุดจะพ่ายแพ้ในงานบางอย่าง ภายในประมาณ 5 ปี Quantum Supremacy ยังไม่ประสบความสำเร็จในตอนนี้และ คนขี้ระแวงอย่าง 

• Gil Kalai สงสัยว่าจะเป็นอย่างไร 

• Bill Unruh สงสัยในความเป็น จริงของคอมพิวเตอร์ควอนตัมในบทความ ที่ตีพิมพ์ย้อนกลับไปในปี 1994 

• Paul Davies ชี้ให้เห็นว่าเครื่องคอมพิวเตอร์ขนาด 400-qubit อาจมีความขัด แย้งกับข้อมูลเกี่ยวกับดาราศาสตร์ที่เป็นนัยด้วยหลักการโฮโลแกรม

สิ่งเหล่านี้ เช่น Roger Schlafly ได้ชี้ให้เห็นว่าผลประโยชน์ทางทฤษฎีที่อ้างถึงของ การคำนวณด้วยควอนตัมเกินกว่าทฤษฎีที่พิสูจน์แล้วของกลศาสตร์ควอนตัมและ แปลว่าการตีความที่ไม่ได้มาตรฐานเช่นโลกหลายแห่งและความเป็นไปได้ในเชิงลบ

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

สำหรับผู้คนที่ชื่นชอบการตีความ Bayesian ของกลศาสตร์ควอนตัมมากกว่าได้ ตั้งคำถามเกี่ยวกับธรรมชาติทางฟิสิกส์ของนามธรรมเชิงคณิตศาสตร์ที่ถูกใช้   

อุปสรรค

มันมีความท้าทายทางเทคนิคมากมายในการสร้างคอมพิวเตอร์ควอนตัมแบบ large-scale และจนป่านนี้คอมพิวเตอร์ควอนตัมมีการแก้ปัญหาที่รวดเร็วกว่า คอมพิวเตอร์แบบคลาสสิค David DiVincenzo จาก IBM ได้ลิสต์ความ ต้องการสำหรับคอมพิวเตอร์ควอนตัมในทางปฎิบัติไว้ด้านล่างนี้ : 

• ปรับขนาดได้ในทางฟิสิกส์เพื่อที่จะเพิ่มจำนวนของ qubits ;
• qubits ที่สามารถถูกเริ่มต้นเป็นค่าโดยพลการ (arbitrary values) ;
• quantum gates ที่รวดเร็วกว่าเ้วลาที่หย่อนคล้อย ;
• ชุด universal gate ;
• qubits ที่สามารถอ่านได้อย่างง่ายดาย  

Quantum Decoherence  

บทความหลัก : Quantum decoherence

1 ในความท้าทายที่ยิ่งใหญ่ที่สุด คือ การควบคุมหรือลบ quantum decoherence (ความหย่อนคล้อยของควอนตัม)ออก ซึ่งมักจะหมายถึงการแยกระบบออก จากสภาพแวดล้อมของมัน เมื่อมีการปฏิสัมพันธ์กับโลกภายนอกเป็นสาเหตุที่ จะทำให้ระบบทำการ decohere อย่างไรก็ตาม sources อื่นๆของ decoherence ยังมีอยู่ ในตัวอย่างรวม quantum gates , การสั่นสะเทือนตาข่ายและพื้นหลังของ thermonuclear spin ของระบบทางฟิสิกส์ ใช้เพื่อที่จะทำการดำเนินการ qubits     

Decoherence เป็นสิ่งที่ไม่สามารถย้อนกลับได้ เนื่องจากมี non-unitary ที่มี ประสิทธิภาพและมักเป็นสิ่งที่ควรได้รับการควบคุมอย่างดีถ้าหลีกเลี่ยงไม่ได้

ระยะเวลา Decoherence สำหรับระบบผู้สมัครโดยเฉพาะช่วงเวลาผ่อนคลาย T2  

(สำหรับเทคโนโลยี NMR และ MRI อาจจะเรียกได้ว่าเวลา dephasing time) โดย ปกติจะอยู่ระหว่างช่วงเวลาระหว่าง nanoseconds กับวินาทีที่อุณหภูมิต่ำ ในปัจจุบัน คอมพิวเตอร์ควอนตัมบางเครื่องต้องการให้ qubits ของพวกเขาเย็นถึง 20 มิลลิ เคลวิน เพื่อที่จะป้องกันการเกิด decoherence ที่สำคัญ 

ดังนั้น งานที่กินเวลามากๆอาจทำให้อัลกอริทึมควอนตัมไม่สามารถทำงานได้ เนื่องจากการรักษาสถานะของ qubits เป็นเวลานานพอสมควรจะทำให้ superpositions เสียหาย

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

ถ้าอัตราความผิดพลาดมันเล็กพอ มันเป็นความคิดที่เป็นไปได้ที่จะใช้การแก้ไขข้อ ผิดพลาดควอนตัมซึ่งทำการแก้ไขข้อผิดพลาดเนื่องจาก decoherence จึงช่วยให้ เวลาการคำนวณทั้งหมดจะยาวกว่าเวลา decoherence ตัวเลขที่ถูกอ้างถึงบ่อยๆ สำหรับอัตราความผิดพลาดที่ต้องการในแต่ละ gate คือ 10−4  ซึ่งหมายความว่า แต่ละ gate จะต้องทำการดำเนินงานของมันในครั้งที่ 10,000 ของเวลาที่เชื่อมโยง กันของระบบ 

การมาถึงเงื่อนไขที่มีการปรับขนาดได้มันเป็นไปได้สำหรับระบบในวงกว้าง อย่างไรก็ตาม การใช้การแก้ไขข้อผิดพลาดนำค่าใช้จ่ายของการเพิ่มขึ้นอย่างเยอะ ของจำนวน qubits ที่ต้องการ ต้องระบุจำนวนเพื่อที่จะแยกตัวประกอบของ จำนวนเต็มโดยการใช้ Shor's algorithm ยังคงเป็นพหุนามอยู่และคิดว่าจะเป็น ระหว่าง L และ L2 ที่ๆ L คือจำนวนของ qubits ในจำนวนที่จะถูกทำการแยกตัว ประกอบ ; อัลกอริทึมการแก้ไขข้อผิดพลาดจะขยายตัวเลขนี้โดยตัวประกอบเพิ่ม เติมของ L สำหรับตัวเลข 1000-bit นี้หมายถึงความต้องการประมาณ 104 บิต โดยปราศจากการแก้ไขข้อผิดพลาด ด้วยการแก้ไขข้อผิดพลาด ตัวเลขจะเพิ่มขึ้น ประมาณ 107 bits เวลาของการคำนวณ คือ ประมาณ L2 หรือประมาณ 107 ขั้น ตอนและที่ 1 MHz ประมาณ 10 วินาที

วิธีการที่แตกต่างกันมากๆของปัญหา decoherence ที่เสถียรภาพ คือ การสร้าง คอมพิวเตอร์ควอนตัมเชิงโทโปโลยีด้วย anyons , อนุภาคเสมือนใช้เป็นเส้นใยโดย อาศัยทฤษฎี braid เพื่อสร้าง logic gates ที่มั่นคง

การพัฒนา

มันมีจำนวนของโมเดลการคำนวณควอนตัมมากมายที่โดดเด่นด้วยองค์ประกอบ พื้นฐานที่การคำนวณถูกย่อยสลาย โมเดล 4 อันหลักของความสำคัญเชิงปฏิบัติ 

คือ :

• Quantum gate array (การคำนวณย่อยสลายไปเป็นลำดับของ few-qubit quantum gates) 
• One-way quantum computer (การคำนวณย่อยสลายไปเป็น one-qubit measurements ถูกนำไปประยุกต์ใช้กับสถานะเริ่มต้นที่ยุ่งมากๆหรือสถานะ cluster) 
• Adiabatic quantum computer มีพื้นฐานอยู่บนการหลอมควอนตัม (การคำนวณย่อยสลายไปเป็นการแปลงที่ต่อเนื่องอย่างช้าของHamiltonian เริ่มต้นไปยัง Hamiltonian อันสุดท้าย ซึ่งสถานะพื้นมีการแก้ปัญหา)
• Topological quantum computer (การคำนวณสลายไปเป็นการถักเกลียว ของ anyons ในตาข่าย 2D)   

เครื่อง quantum Turing machine มีความสำคัญเชิงทฤษฎีแต่ในการดำเนินการ ทางตรงของโมเดลนี้ไม่ได้รับการติดตาม โมเดลทั้งหมด 4 อันของการคำนวณได้ รับการแสดงให้เห็นอย่างเท่าเทียมกัน; แต่ละอันสามารถจำลองอันอื่นๆได้ด้วยไม่ มากกว่าพหุนามที่มากเกินไป

สำหรับการดำเนินการทางฟิสิกส์ของคอมพิวเตอร์ควอนตัม ผู้ที่เข้าร่วมที่แตกต่าง กันหลายๆคนได้รับการติดตามท่ามกลางพวกเขา (โดดเด่นด้วยระบบทางฟิสิกส์ที่ ใช้เพื่อตระหนักถึง qubits) :

• คอมพิวเตอร์ควอนตัมตัวนํายิ่งยวด (qubit ถูกดำเนินการโดยสถานะของ วงจร ตัวนำยิ่งยวดเล็กๆ (Josephson junctions))
• คอมพิวเตอร์ควอนตัมที่ดักจับไอออน (qubit ดำเนินการโดยสถานะภายใน ของการดักจับไอออน)
• ตาข่ายออฟติคเคิล (qubit ดำเนินการโดยสถานะภายในของ neutral atoms ที่ถูกดักจับในตาข่ายออฟติคเคิล)
• คอมพิวเตอร์ Quantum dot , spin-based (เช่น  Loss-DiVincenzo quantum computer) (qubit ถูกให้โดยสถานะ spin ของการดักจับ อิเล็กตรอน)
• คอมพิวเตอร์ Quantum dot , spatial-based (qubit ถูกให้โดยตำแหน่ง อิเล็กตรอนใน double quantum dot)
• การสะท้อนด้วยคลื่นแม่เหล็กไฟฟ้าบนโมเลกุลในการแก้ปัญหา (สถานะของ เหลว NMR) (qubit ถูกจัดหาให้โดย nuclear spins ภายในโมเลกุลที่ละลาย)
• สถานะของแข็ง NMR Kane quantum computers (qubit ถูกตระหนักถึง โดยสถานะ nuclear spin ของ ผู้บริจาคฟอสฟอรัสในซิลิคอน)
• คอมพิวเตอร์ควอนตัมอิเล็กตรอนบนฮีเลียม (qubit คือ electron spin)
• Cavity quantum electrodynamics (CQED) (qubit ถูกจัดหาให้โดยสถานะ ภายในของการดักจับอะตอมที่คู่กับช่อง high-finesse)
• แม่เหล็กโมเลกุล (qubit ถูกให้มาโดยสถานะ spin)
• Fullerene-based ESR quantum computer (qubit มีพื้นฐานอยู่บน electronic spin ของอะตอมหรือโมเลกุลที่ห่อหุ้มใน fullerenes)
• คอมพิวเตอร์ควอนตัมออฟติคเคิลเส้นตรง (qubits ถูกตระหนักถึงโดย สถานะการดำเนินการของโหมดที่แตกต่างของไฟผ่านองค์ประกอบเส้นตรง เช่น กระจก , เครื่องแยกลำแสงและเฟือง)
• Diamond-based quantum computer (qubit ถูกตระหนักถึงโดย อิเล็กทรอนิกส์หรือ nuclear spin ของศูนย์กลางที่ว่างของไนโตรเจนใน เพชร)
• คอมพิวเตอร์ควอนตัม Bose–Einstein condensate-based
• คอมพิวเตอร์ควอนตัม Transistor-based  – คอมพิวเตอร์ควอนตัม สตริงด้วย entrainment ของหลุมบวกโดยใช้การดักจับ electrostatic
• คอมพิวเตอร์ควอนตัมที่มีพื้นฐานของอนินทรีย์คริสตัลที่มีไอออนเหล็กของ โลกที่หายากเจืออยู่ (qubit ถูกตระหนักถึงโดยสถานะ electronic ภายในของ สารเจือปนในออฟติคเคิลไฟเบอร์)
• คอมพิวเตอร์ควอนตัมที่มีพื้นฐานของเมทัลลิคที่เหมือนกับ carbon nanospheres

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

ความสัมพันธ์กับทฤษฎีการคำนวณที่ซับซ้อน

บทความหลัก : Quantum complexity theory
 

ความสัมพันธ์ที่น่าสงสัยของ BQP กับพื้นที่ว่างของปัญหาอื่นๆ

ชั้นของปัญหาที่สามารถแก้ไขได้อย่างมีประสิทธิภาพโดยคอมพิวเตอร์ควอนตัมถูก เรียกว่า  BQP  สำหรับ “ข้อผิดพลาดที่จำกัด , ควอนตัม , เวลาพหุนาม” คอมพิวเตอร์ควอนตัมรันเฉพาะอัลกอริทึมความน่าจะเป็น ดังนั้น BQP บน คอมพิวเตอร์ควอนตัม คือ ของคู่กันของ BPP (“ความผิดพลาดที่มีข้อจำกัด , ควอนตัม , เวลาพหุนาม”) บนคอมพิวเตอร์คลาสสสิค มันถูกกำหนดเป็นชุดของ ปัญหาที่สามารถแก้ไขได้ด้วยอัลกอริทึม polynomial-time ที่ๆความน่าจะเป็นของ ความผิดพลาดถูกตั้งขอบเขตให้ห่างไกลจากครึ่งหนึ่ง 

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

BQP ถูกรวมไว้ในคลาสความซับซ้อน #P (หรืออย่างแม่นยำมากขึ้นในคลาสที่ เกี่ยวข้องของปัญหาการตัดสินใจ P#P) ซึ่งเป็นคลาสย่อยของ PSPACE      

BQP ถูกสงสัยว่าเป็นอะไรที่ไม่เป็นระเบียบจาก  NP-complete และ superset ที่ เข้มงวดของ P แต่มันไม่เป็นที่รู้จัก ทั้งการแยกตัวประกอบจำนวนเต็มและ log ที่ ไม่ต่อเนื่องอยู่ใน BQP ปัญหาทั้ง 2 อย่างนี้เป็นปัญหา NP ที่ถูกสงสัยว่าอยู่นอก BPP และดังนั้นก็นอก P ด้วย ทั้ง 2 อันถูกสงสัยว่าจะไม่ได้เป็น NP-complete  มันเป็นการเข้าใจผิดที่ปกติธรรมดาว่าคอมพิวเตอร์ควอนตัมสามารถแก้ไขปัญหา NP-complete ในเวลาพหุนามได้ สิ่งนี้ไม่ทราบว่าเป็นความจริงและโดยทั่วไป ถูกสงสัยว่าเป็นเท็จ

ความจุของคอมพิวเตอร์ควอนตัมเพื่อที่จะเร่งอัลกอริทึมคลาสสิคมีข้อจำกัดที่ เข้มงวด — ขอบเขตบนของความซับซ้อนของการคำนวณควอนตัม 

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

Bohmian Mechanics คือ การตีความตัวแปรที่ซ่อนอยู่ในที่ไม่ใช่ท้องถิ่นของ กลศาสตร์ควอนตัม มันถูกแสดงว่าเป็นตัวแปรคอมพิวเตอร์ควอนตัมที่ถูกซ่อนที่ ไม่ใช่ท้องถิ่นสามารถดำเนินการค้นหาฐานข้อมูล N-item ที่มากที่สุดในขั้นตอน สิ่งนี้รวดเร็วกว่าขั้นตอน เล็กน้อยที่ถูกเอามาโดย Grover's algorithm ไม่ทั้งวิธีการค้นหาจะอนุญาตให้คอมพิวเตอร์แก้ปัญหา NP-Complete ใน polynomial time 

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

ควอนตัมเหล่านี้ได้ ดังนั้น คอมพิวเตอร์ควอนตัมไม่สามารถที่จะแก้ปัญหาที่ยัง ไม่ได้ถูกตัดสินใจได้เหมือนอย่าง halting problem (การหยุดปัญหา) การมีอยู่ของ คอมพิวเตอร์ควอนตัม "มาตรฐาน" ไม่สามารถพิสูจน์ Church–Turing thesis ได้ 

ได้รับการสันนิษฐานว่าทฤษฎีของ quantum gravity เช่น M-theory หรือ loop quantum gravity อาจช่วยให้สามารถสร้างคอมพิวเตอร์ได้เร็วขึ้น ในปัจจุบัน การกำหนดการคำนวณในทฤษฎีเหล่านี้เป็นปัญหาปลายเปิดเนื่องจาก problem of time กล่าวคือ ปัจจุบันไม่มีวิธีอธิบายที่ชัดเจนว่ามันหมายความว่าอย่างไรสำหรับ ผู้สังเกตที่จะ submit input ไปยังคอมพิวเตอร์และได้รับเอาท์พุตในภายหลัง

References :

https://en.wikipedia.org/wiki/Quantum_computing