อัลกอริทึมของ Shor สามารถแยกตัวประกอบของจำนวนเต็มเกาส์เซียนได้หรือไม่?

ดังที่กล่าวถึงในปัญหาที่เชื่อมโยง นี่เป็นปัญหาที่ค่อนข้างมาตรฐานในทฤษฎีจำนวนอัลกอริทึมที่เกี่ยวข้องกับ การแยกตัวประกอบในอุดมคติ (เช่น เป็นปริยายใน บันทึกเหล่านี้). โปรดทราบว่าวิธีแก้ปัญหาตามบรรทัดเหล่านี้ต้องใช้อัลกอริทึมของ Shor เพื่อแยกตัวประกอบ $x^2+y^2$ (โดยมองว่าเป็นบรรทัดฐานของจำนวนเต็มเกาส์เซียน --- การแยกตัวประกอบเป็นขั้นตอนที่ 2 ของบันทึกที่เชื่อมโยง)

ปัญหาที่เชื่อมโยงยังให้วิธีการแก้ปัญหาแบบ "คิ้วต่ำ" อย่างน้อยก็เมื่อใด $n = p\equiv 1\bmod 4$ เป็นนายก สิ่งนี้ (โดยปริยาย) จัดการทั้งหมด $n$ แม้ว่าโดย

1. แฟคตอริ่ง $n$ ใช้ Shor's
2. แก้ปัญหาสำหรับแต่ละปัจจัยเป็นรายบุคคลและจากนั้น
3. รวมโซลูชันโดยใช้ พรหมคุปต์âFibonacci identity.

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

อีกวิธีหนึ่งในการมองปัญหาของคุณคือการแก้ "สมการบรรทัดฐาน" $N(ก) = x$, ที่ไหน $N$ เป็นบรรทัดฐานของฟิลด์ $\mathbb{Q}(\sqrt{-1})$. สิ่งนี้ได้รับการทำในลักษณะทั่วไปมากขึ้น (เชิงปริมาณ) โดยใช้เทคนิคที่คล้ายคลึงกับอัลกอริทึมของ Shor ดูตัวอย่างผลงานของ Biasse และเพลง บนคอมพิวเตอร์ $S$กลุ่มหน่วยที่พวกเขากล่าวถึงสามารถใช้ในการแก้สมการบรรทัดฐาน $N_{L/K}(x) = \theta$ สำหรับ $\theta\ใน K$.

นี่คือทั้งหมดที่จะพูด

1. กรณีของคุณนั้นเรียบง่ายและได้รับการแก้ไข (โดยปริยาย) ในคำตอบก่อนหน้าและ
2. มีการสรุปภาพรวมที่เกี่ยวข้องเมื่อเร็วๆ นี้ แม้ว่าจะอธิบายได้ยากหากไม่มีทฤษฎีจำนวนเชิงพีชคณิตมากมาย บางทีการสรุปที่ง่ายที่สุดคือการแก้สมการบรรทัดฐาน $N_{L/K}(x) = \theta$ซึ่งทำได้โดยใช้เทคนิคคล้ายชอร์จากผลงานล่าสุดของ Biasse และ Song