Như đã đề cập trong bài toán liên kết, đây là một bài toán khá chuẩn trong lý thuyết số thuật toán liên quan đến thừa số lý tưởng (ví dụ, nó được ngầm định trong những ghi chú này).
Lưu ý rằng một giải pháp dọc theo những dòng này yêu cầu thuật toán của Shor để phân tích $x^2+y^2$ (xem nó như là chuẩn của số nguyên Gaussian --- bao thanh toán nó là bước 2 của các ghi chú được liên kết).
Vấn đề được liên kết cũng đưa ra cách giải quyết vấn đề "thấp kém", ít nhất là khi $n = p\equiv 1\bmod 4$ là nguyên tố.
Điều này (ngầm) xử lý tất cả $n$ mặc dù, bởi
- bao thanh toán $n$ sử dụng Shor's,
- giải quyết vấn đề cho từng yếu tố riêng lẻ, và sau đó
- kết hợp các giải pháp bằng cách sử dụng Nhận dạng BrahmaguptaâFibonacci.
Tất nhiên, người ta có thể khái quát hóa điều này theo nhiều cách, nhưng không rõ bạn sẽ quan tâm đến sự khái quát hóa nào cho câu hỏi hiện tại của mình.
Nói chung tôi sẽ đề nghị độ phức tạp lượng tử của vấn đề nhóm con ẩn, trong đó có một số tài liệu tham khảo tốt cho công việc có liên quan.
Một cách khác để xem vấn đề của bạn là giải một "phương trình chuẩn" $N(a) = x$, ở đâu $N$ là chuẩn trường của $\mathbb{Q}(\sqrt{-1})$.
Điều này cũng đã được thực hiện một cách tổng quát hơn (lượng tử) bằng cách sử dụng các kỹ thuật tương tự như thuật toán của Shor.
Xem ví dụ công việc của Biasse và bài hát trên máy tính $S$-các nhóm đơn vị, mà họ đề cập có thể được sử dụng để giải các phương trình định mức $N_{L/K}(x) = \theta$ vì $\theta\bằng K$.
Đây là tất cả để nói
- trường hợp cụ thể của bạn rất đơn giản và đã (ngầm) được giải quyết trong câu trả lời trước và
- đã có những khái quát hóa phù hợp gần đây, mặc dù chúng rất khó để mô tả nếu không có nhiều lý thuyết số đại số. Có lẽ khái quát hóa đơn giản nhất là giải phương trình chuẩn $N_{L/K}(x) = \theta$, có thể được thực hiện bằng cách sử dụng các kỹ thuật giống như Shor bằng tác phẩm gần đây của Biasse và Song.
