Как упоминалось в связанной задаче, это довольно стандартная проблема в алгоритмической теории чисел, связанная с идеальная факторизация (например, это подразумевается в эти заметки).
Обратите внимание, что решение в этом направлении требует, чтобы алгоритм Шора учитывал $х^2+у^2$ (рассматривая это как норму целого числа Гаусса --- разложение на множители является шагом 2 связанных заметок).
Связанная проблема также предлагает «незаметный» способ решения проблемы, по крайней мере, когда $n = p\equiv 1\bmod 4$ является простым.
Это (неявно) обрабатывает все $n$ хотя, по
- факторинг $n$ с помощью Шора,
- решение проблемы для каждого фактора в отдельности, а затем
- объединение решений с помощью Брахмагупта — тождество Фибоначчи.
Конечно, это можно обобщить по-разному, но неясно, какое обобщение вас интересует, учитывая ваш текущий вопрос.
В общем, я бы предложил квантовая сложность проблемы скрытых подгрупп, в котором есть несколько хороших ссылок на соответствующую работу.
Еще один способ рассмотреть вашу проблему - решить «уравнение нормы». $N(а) = х$, куда $N$ является полевой нормой $\mathbb{Q}(\sqrt{-1})$.
Это также было сделано в более общем виде (квантово) с использованием методов, подобных алгоритму Шора.
См., например, работу Биас и песня на вычислениях $S$-единичные группы, которые они упоминают, могут быть использованы для решения уравнений нормы $N_{L/K}(x) = \тета$ за $\тета\в К$.
Это все, чтобы сказать
- ваш конкретный случай прост и (неявно) решен в предыдущем ответе, и
- в последнее время были сделаны соответствующие обобщения, хотя их трудно описать без большого количества алгебраической теории чисел. Возможно, самым простым обобщением является решение уравнений нормы $N_{L/K}(x) = \тета$, что можно сделать с помощью методов, подобных Шору, с использованием недавней работы Биассе и Сонга.
