Score:3

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

ธง dz

สิ่งนี้เกี่ยวข้องกับ คำถามนี้ เกี่ยวกับการแก้นิพจน์ต่อไปนี้:

$$x^{2} + y^{2}$$

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

$$(x + iy)(x - iy)$$

ถ้าเราสามารถแยกตัวประกอบของกำลังสองและรับส่วนประกอบของจำนวนเต็มได้ $x$ สามารถแก้ปัญหาได้

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

Score:2
ธง ng

ดังที่กล่าวถึงในปัญหาที่เชื่อมโยง นี่เป็นปัญหาที่ค่อนข้างมาตรฐานในทฤษฎีจำนวนอัลกอริทึมที่เกี่ยวข้องกับ การแยกตัวประกอบในอุดมคติ (เช่น เป็นปริยายใน บันทึกเหล่านี้). โปรดทราบว่าวิธีแก้ปัญหาตามบรรทัดเหล่านี้ต้องใช้อัลกอริทึมของ 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
dz flag
ภาพรวมที่ฉันสนใจมากที่สุดคือคำถามโบนัส ซึ่งฉันคิดว่าแตกต่างมากพอที่จะรับประกันคำถามของตัวเอง ขอบคุณสำหรับคำตอบ - ระบบไม่อนุญาตให้ฉันลงคะแนนด้วยเหตุผลบางประการ แม้จะมีชื่อเสียงเพียงพอก็ตาม

โพสต์คำตอบ

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