ก่อนอื่นฉันจะตอบคำถามของคุณ (ซึ่งมีคำตอบที่ค่อนข้างตรงไปตรงมาซึ่งคุณอาจผิดหวัง) ก่อนที่จะพูดถึงปัญหาของคุณที่ขยายออกไปเล็กน้อยซึ่งเราคิดว่าคอมพิวเตอร์ควอนตัม ไม่ได้ แก้ปัญหาซึ่งคุณอาจสนใจ
เป็นหมายเหตุด่วนเกี่ยวกับความคิดเห็น
อย่างน้อยก็ในกรณีการแยกตัวประกอบถ้า $\log_2(p)=\log_2(q)=\log_2(k)$ ดังนั้นการแก้สมการจึงเป็นไปไม่ได้ในทางทฤษฎีด้วยข้อมูล เนื่องจากโดยพื้นฐานแล้วเป็นการแก้สมการเพียงครั้งเดียว
โดยทั่วไป วิธีการจัดการคือการบอกว่าฝ่ายตรงข้ามชนะหากพวกเขาฟื้นตัว ใดๆ วิธีการแก้ปัญหา $x^2+y^2\bmod k$แทนที่จะเป็นโซลูชันเฉพาะบางอย่าง
สิ่งนี้สามารถเห็นได้ในสิ่งต่าง ๆ เช่น
- เกมกู้คืนคีย์ที่สอดคล้องกัน (ไม่ใช่เกมกู้คืนคีย์เป้าหมาย) และ
- ฟังก์ชันแบบทางเดียวจำเป็นต้องกู้คืนภาพล่วงหน้าใด ๆ ของ $y$, เช่น. ใดๆ $x$ ดังนั้น $f(x) = y$แทนที่จะ "แน่นอน" บางอย่าง $x'$ ที่เลือกไว้ภายในระหว่างเกม
ฉันจะอธิบายสิ่งต่าง ๆ ในเงื่อนไขเหล่านี้เนื่องจากเป็นมาตรฐาน
หากไม่เหมาะกับใบสมัครของคุณ คุณอาจลองอธิบายใบสมัครของคุณเพิ่มเติม
คำถามนี้ง่าย: อัลกอริทึมของ Shor สามารถแก้สมการเหล่านี้ในเวลาพหุนามได้หรือไม่ เมื่อดำเนินการด้วยเลขคณิตจำกัดแทนจำนวนเต็ม
ความเข้าใจของฉันคืออัลกอริทึมของ Shor ถูกอธิบายไปแล้ว $\mathbb{Z}$ ค่อนข้างมากกว่า $\mathbb{Z}_n$ ไม่ใช่ปัญหาร้ายแรงในการใช้งาน "ในโลกแห่งความเป็นจริง" โดยเฉพาะอย่างยิ่ง ในขณะที่เราต้องระวังว่าการแทนค่าที่มีความแม่นยำจำกัดนั้นไม่ "สูญเสีย" เกินไป แต่ความเข้าใจของฉันคือรายละเอียดเหล่านี้หาได้ง่ายกว่าการสร้างคอมพิวเตอร์ควอนตัม
หากความเข้าใจนี้ถูกต้อง คำตอบของคำถามทั้งสองนี้เป็นเรื่องเล็กน้อย --- แก้สมการต่างๆ $\mathbb{Z}$แล้วลดคำตอบลง $\bmod k$ เพื่อรับแนวทางแก้ไข $\mathbb{Z}_k$. ดังที่ปอนโชชี้ให้เห็นในความคิดเห็น ปัญหาในการแก้ไข $n = xy\bmod k$ สำหรับ $x, y$ เท่ากัน คลาสสิก ง่าย ดังนั้น คุณธรรมของเรื่องราวก็คือ การกำหนดข้อจำกัดแบบโมดูลาร์จะทำให้ปัญหา (อาจจะ) ง่ายขึ้นอย่างมาก แต่สำหรับปัญหาเหล่านี้ มันไม่ได้ทำให้ปัญหายากขึ้น
มีการขยายเล็กน้อยของการแก้ปัญหาสำหรับ $n = xy \bmod k$ ซึ่งคิดว่าเป็นควอนตัมยาก
การแก้ความสอดคล้องนี้อาจมองได้ว่าเป็นการแก้สมการเชิงเส้นตัวแปรเดียว (แบบแน่นอน)
มีสองวิธีตามธรรมชาติในการสรุปสิ่งนี้
- มากกว่าหนึ่งตัวแปร และ
- มากกว่าหนึ่งสมการ
เช่น เปลี่ยนโจทย์ให้เป็นที่กำหนด $\vec b = A\vec s\bmod k$ ที่ไหน $\vec b\in\mathbb{Z}_k^n, A\in\mathbb{Z}_k^{n\times n}, \vec s\in\mathbb{Z}_k^n$.
นี่ยังคงเป็นเรื่องเล็กน้อยที่จะ "แก้ไข" แม้ว่า --- หากคุณเลือก $A$ ให้เป็นเมทริกซ์เอกลักษณ์แล้ว $\vec s = \vec b$ ทำงาน
โดยทั่วไปถ้าคุณเลือก $A$ กลับด้านได้ $\mathbb{Z}_k$, แล้ว $\vec s = \vec A^{-1}\vec b$ ทำงาน
ถึงแม้ว่า $\vec A$ ไม่สามารถกลับด้านได้ (บอกว่ามันไม่เป็นรูปสี่เหลี่ยมจัตุรัส) มีหลายสิ่งที่คุณสามารถทำได้โดยใช้เทคนิคพีชคณิตเชิงเส้นทั่วไป
ทั้งหมดนี้มีทั้งประสิทธิภาพและคลาสสิก เช่น Shor's ยังคง overkill
โดยทั่วไปวิธีการหยุดการโจมตีข้างต้นนั้นมีสองเท่า
ระบุเมทริกซ์บางอย่าง $A$ ต้องใช้ (จึงไม่สามารถตั้งค่าได้ $A$ เป็นตัวตนหรือเมทริกซ์กลับด้านแบบสุ่ม) และ
ใส่เสียงรบกวนเข้าไปในปัญหา
โปรดทราบว่าจุดแรกเพียงอย่างเดียวก็เพียงพอแล้ว (การโจมตีของ Poncho ยังคงใช้งานได้) ดังนั้นจุดที่สองควรถูกมองว่าเป็นพื้นฐาน
โดยสรุปปัญหามีดังนี้
การเรียนรู้ด้วยข้อผิดพลาด: อนุญาต $A\in\mathbb{Z}_k^{n\times n}$ สุ่มอย่างสม่ำเสมอและปล่อยให้ $\vec s\in\mathbb{Z}_k^n$ เป็นเวกเตอร์ "ความลับ"
สำหรับการกระจายแบบคงที่ $\chi$ รองรับบน $\mathbb{Z}_k$เราว่า ค้นหาการเรียนรู้ด้วยข้อผิดพลาด ปัญหาคือการกู้คืน $\vec s$, ที่ให้ไว้ $(ก, ก\vec s + \vec e)$, ที่ไหน $\vec e \gets \chi^n$.
ขึ้นอยู่กับการกำหนดพารามิเตอร์ ปัญหา LWE เป็นหนึ่งในตัวเลือกชั้นนำสำหรับการสันนิษฐานความแข็งที่ปลอดภัยต่อคอมพิวเตอร์ควอนตัม
กล่าวคือ เพื่อการสรุปผลทั่วไปที่เหมาะสม $n \equiv xy\bmod k$ก็คิดว่าเป็นอัลกอริทึมของชอร์ ไม่ได้ แก้ปัญหา.
ดังที่ได้กล่าวไปแล้ว การสรุปเป็นขั้นตอนหลายขั้นตอนที่ลบออกจากปัญหาเริ่มต้นของคุณ
มีความคล้ายคลึงกันอื่น ๆ ในทิศทางนี้ (ปัญหาความเท่าเทียมกันของการเรียนรู้กับปัญหาเสียงรบกวนหรือปัญหา GCD โดยประมาณ) --- ความคล้ายคลึงกันพื้นฐานกับสิ่งเหล่านี้ทั้งหมดคือคุณมีตัวแปร "ที่มีเสียงดัง" ของปัญหาเชิงเส้น
นอกจากนี้ยังมีลักษณะทั่วไปของ $x^2+y^2\bmod k$ ปัญหาที่คิดว่าจะปลอดภัยควอนตัม แต่ฉันไม่ทราบรายละเอียดมากดังนั้นจะเขียนน้อยลง
ประมาณหนึ่งแทนที่พหุนามกำลังสอง $f(x, y) = x^2+y^2\bmod k$ ด้วย ตามอำเภอใจ พหุนามกำลังสอง (หรือชุดของพหุนาม) ใน $n$ ตัวแปร
จากนั้นปัญหาของการฟื้นตัว $(x_1,\จุด, x_n)$ นั่นคือศูนย์ (พร้อมกัน) ของพหุนามกำลังสองหลายตัวแปร $p_0, \จุด,p_m$ เกี่ยวข้องกับการทำลาย "ระบบเข้ารหัสลับหลายตัวแปร" (โดยประมาณ)
โปรดทราบว่าการยืนกรานที่จะกู้คืนศูนย์ของพหุนาม (แทนที่จะเป็น $p(x_0,\dots,x_n) = N$ตามที่คุณขอ) มาพร้อมกับลักษณะทั่วไปที่ไม่สูญเสียไป เนื่องจากเราสามารถกู้คืนสิ่งนี้ได้โดยดูที่ศูนย์ของ $p(x_0,\dots,x_n) - N$.
นี่คือทั้งหมดที่จะบอกว่า
- Shor's คิดที่จะทำลายปัญหาของคุณทั้งคู่ แต่
- มีภาพรวมของปัญหาทั้งสองของคุณที่คิดว่าปลอดภัยควอนตัม ในความเป็นจริง สมมติฐานที่ปลอดภัยเกี่ยวกับควอนตัม "ชั้นนำ" จำนวนมาก (ทุกอย่างที่ฉันรู้ยกเว้นสิ่งที่เป็นไอโซจีนีและการเข้ารหัสอันดับเมตริก) สามารถมองได้ว่าเป็นภาพรวมของปัญหาของคุณ