Can Shor's algorithm factor over the gaussian integers?

Question

This is related to this question about solving the following expression:

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

This can be factored over the gaussian integers as

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

If one could factor a sum of two squares and take the integer component $x$ one could solve the problem.

Can Shor's algorithm factor a term over gaussian integers? More precisely can it be used to solve the sum of two squares problem?

Answer 1

As mentioned in the linked problem, this is a fairly standard problem in algorithmic number theory related to ideal factorization (for example, it is implicit in these notes). Note that a solution along these lines requires Shor's algorithm to factor $x^2+y^2$ (viewing it as the norm of a Gaussian integer --- factoring it is step 2 of the linked notes).

The linked problem also gives a "low-brow" way to solve the problem, at least when $n = p\equiv 1\bmod 4$ is prime. This (implicitly) handles all $n$ though, by

1. factoring $n$ using Shor's,
2. solving the problem for each factor individually, and then
3. combining the solutions using the Brahmagupta–Fibonacci identity.

One can of course generalize this in many ways, but it is not clear what generalization you would be interested in given your current question. In general I would suggest the quantum complexity of the hidden subgroup problem, which has some good references to relevant work.

One other way to view your problem is solving a "norm equation" $N(a) = x$, where $N$ is the field norm of $\mathbb{Q}(\sqrt{-1})$. This has also been done in more generality (quantumly) using techniques similar to Shor's algorithm. See for example the work of Biasse and Song on computing $S$-unit groups, which they mention can be used to solve norm equations $N_{L/K}(x) = \theta$ for $\theta\in K$.

This is all to say

1. your particular case is simple, and has (implicitly) been solved in the previous answer, and
2. there has been recent relevant generalizations, although they are difficult to describe without a lot of algebraic number theory. Perhaps the simplest generalization is that of solving norm equations $N_{L/K}(x) = \theta$, which can be done using Shor-like techniques using recent work of Biasse and Song.