ดังที่กล่าวถึงในปัญหาที่เชื่อมโยง นี่เป็นปัญหาที่ค่อนข้างมาตรฐานในทฤษฎีจำนวนอัลกอริทึมที่เกี่ยวข้องกับ การแยกตัวประกอบในอุดมคติ (เช่น เป็นปริยายใน บันทึกเหล่านี้).
โปรดทราบว่าวิธีแก้ปัญหาตามบรรทัดเหล่านี้ต้องใช้อัลกอริทึมของ Shor เพื่อแยกตัวประกอบ $x^2+y^2$ (โดยมองว่าเป็นบรรทัดฐานของจำนวนเต็มเกาส์เซียน --- การแยกตัวประกอบเป็นขั้นตอนที่ 2 ของบันทึกที่เชื่อมโยง)
ปัญหาที่เชื่อมโยงยังให้วิธีการแก้ปัญหาแบบ "คิ้วต่ำ" อย่างน้อยก็เมื่อใด $n = p\equiv 1\bmod 4$ เป็นนายก
สิ่งนี้ (โดยปริยาย) จัดการทั้งหมด $n$ แม้ว่าโดย
- แฟคตอริ่ง $n$ ใช้ Shor's
- แก้ปัญหาสำหรับแต่ละปัจจัยเป็นรายบุคคลและจากนั้น
- รวมโซลูชันโดยใช้ พรหมคุปต์âFibonacci identity.
แน่นอนว่าใคร ๆ ก็สามารถสรุปสิ่งนี้ได้หลายวิธี แต่ยังไม่ชัดเจนว่าคุณจะสนใจภาพรวมทั่วไปใดเมื่อพิจารณาจากคำถามปัจจุบันของคุณ
โดยทั่วไปฉันจะแนะนำ ความซับซ้อนเชิงควอนตัมของปัญหากลุ่มย่อยที่ซ่อนอยู่ซึ่งมีการอ้างอิงที่ดีเกี่ยวกับงานที่เกี่ยวข้อง
อีกวิธีหนึ่งในการมองปัญหาของคุณคือการแก้ "สมการบรรทัดฐาน" $N(ก) = x$, ที่ไหน $N$ เป็นบรรทัดฐานของฟิลด์ $\mathbb{Q}(\sqrt{-1})$.
สิ่งนี้ได้รับการทำในลักษณะทั่วไปมากขึ้น (เชิงปริมาณ) โดยใช้เทคนิคที่คล้ายคลึงกับอัลกอริทึมของ Shor
ดูตัวอย่างผลงานของ Biasse และเพลง บนคอมพิวเตอร์ $S$กลุ่มหน่วยที่พวกเขากล่าวถึงสามารถใช้ในการแก้สมการบรรทัดฐาน $N_{L/K}(x) = \theta$ สำหรับ $\theta\ใน K$.
นี่คือทั้งหมดที่จะพูด
- กรณีของคุณนั้นเรียบง่ายและได้รับการแก้ไข (โดยปริยาย) ในคำตอบก่อนหน้าและ
- มีการสรุปภาพรวมที่เกี่ยวข้องเมื่อเร็วๆ นี้ แม้ว่าจะอธิบายได้ยากหากไม่มีทฤษฎีจำนวนเชิงพีชคณิตมากมาย บางทีการสรุปที่ง่ายที่สุดคือการแก้สมการบรรทัดฐาน $N_{L/K}(x) = \theta$ซึ่งทำได้โดยใช้เทคนิคคล้ายชอร์จากผลงานล่าสุดของ Biasse และ Song