I'll first answer your question (which has a rather straightforward answer that you may be disappointed by), before discussing a mild extension of your problem that we think quantum computers cannot solve, which may interest you.
As a quick side-note regarding the comment
At least in the factoring case if $\log_2(p)=\log_2(q)=\log_2(k)$ then solving the equation is information-theoretically impossible since it's basically a one-time pad.
Generally, how this is handled is to say that an adversary wins if they recover any solution to $x^2+y^2\bmod k$, rather than some specific solution.
This can be seen in things like
- the consistent key recovery game (rather than the target key recovery game), and
- how one-way functions need to recover any preimage of $y$, e.g. any $x$ such that $f(x) = y$, rather than some "exact" $x'$ that is chosen internally during the game.
I will describe things in these terms, as it is standard.
If this isn't suitable for your application, you should perhaps try to describe your application more.
This question is simple: Can Shor's algorithm solve these equations in polynomial time when they are performed with finite arithmetic instead of over integers?
My understanding is that Shor's algorithm being described over $\mathbb{Z}$ rather than $\mathbb{Z}_n$ is not a serious issue with its "real world" implementation. In particular, while one does need to be careful that the finite-precision representations one work with are not too "lossy", my understanding is that these details are much easier to work out than things like building a quantum computer.
Provided this understanding is correct, the answer to both of these questions is roughly trivial --- solve the various equations over $\mathbb{Z}$, and then reduce the answers $\bmod k$ to obtain solutions over $\mathbb{Z}_k$. As poncho points out in the comments, the problem of solving $n = xy\bmod k$ for $x, y$ is even classically easy, so the moral of the story is that imposing modular constraints can make problems (perhaps) dramatically easier, but for these problems they do not make the problems harder.
There is a mild extension of the problem of solving for $n = xy \bmod k$ which is thought to be quantumly hard.
Solving for this congruance can be seen as solving a single-variable (exact) linear equation.
There are two natural ways to generalize this
- more than one variable, and
- more than one equation.
E.g., change the problem to where one is given $\vec b = A\vec s\bmod k$ where $\vec b\in\mathbb{Z}_k^n, A\in\mathbb{Z}_k^{n\times n}, \vec s\in\mathbb{Z}_k^n$.
This is still trivial to "solve" though --- if you choose $A$ to be the identity matrix, then $\vec s = \vec b$ works.
More generally, if you choose $A$ to be invertible over $\mathbb{Z}_k$, then $\vec s = \vec A^{-1}\vec b$ works.
Even if $\vec A$ is non-invertible (say it is non-square) there are things you can do using general linear-algebraic techniques.
All of this is both efficient, and classical, e.g. Shor's is still overkill.
Generally how one stops the above attacks is two-fold
specify some matrix $A$ one must use (so one cannot set $A$ to be the identity, or a random invertible matrix), and
inject some noise into the problem.
Note that the first point alone does suffice (Poncho's attack still works), so the second point should be seen as fundamental.
Concretely, the problem is as follows
Learning With Errors: Let $A\in\mathbb{Z}_k^{n\times n}$ be uniformly random, and let $\vec s\in\mathbb{Z}_k^n$ be a "secret" vector.
For a fixed distribution $\chi$ supported on $\mathbb{Z}_k$, we say the search learning with errors problem is to recover $\vec s$, given $(A, A\vec s + \vec e)$, where $\vec e \gets \chi^n$.
Depending on parameterization, the LWE problem is one of the leading candidates for a hardness assumption that is safe against quantum computers.
This is to say, for a suitable generalization of solving $n \equiv xy\bmod k$, it is thought that Shor's algorithm cannot solve the problem.
As seen above though, the generalization is many steps removed from your initial problem.
There are other similar generalizations in this direction (The Learning Parity with Noise problem, or the Approximate GCD problem) --- the fundamental similarity with all of them is that you have some "noisy" variant of a linear problem.
There is additionally a generalization of the $x^2+y^2\bmod k$ problem that is thought to be quantum-safe, but I do not know as many details, so will write less.
Roughly, one replaces the quadratic polynomial $f(x, y) = x^2+y^2\bmod k$ with an arbitrary quadratic polynomial (or collection of polynomials) in $n$ variables.
Then, the problem of recovering $(x_1,\dots, x_n)$ that are (simultaneous) zeros of multivariate quadratic polynomials $p_0, \dots,p_m$ is (roughly) related to breaking "Multivariate cryptosystems".
Note that the insistence that one recovers zeros of the polynomials (rather than $p(x_0,\dots,x_n) = N$, as you ask for) comes with no loss of generality, as one can recover this by looking at a zero of $p(x_0,\dots,x_n) - N$.
This is all to say that
- Shor's is thought to break both of your problems, but
- there are generalizations of both of your problems that are thought to be quantum-safe. In fact, many of the "leading" quantum-safe hypothesis (everything I know except isogeny-stuff and rank-metric coding things) can be seen as generalizations of your problems.
