Ciro Santilli @cirosantilli  40

Compared to Waring's problem, this is potentially much harder, as we can go infinitely negative in our attempts, there isn't a bound on how many tries we can have for each number.

In other words, it is unlikely to have a Conjecture reduction to a halting problem.

math.stackexchange.com/questions/2382011/computational-complexity-of-modular-exponentiation-from-rosens-discrete-mathem mentions:can be calculated in:Remember that $log(m)$ and $log(n)$ are the lengths in bits of $m$ and $n$, so in terms of the length in bits $M$ and $N$ we'd get:

A theorem that is not very important on its own, often an intermediate step to proving something that the author feels deserves the name "theorem".

Some authors use the convention of:

Controlled quantum gates are gates that have two types of input qubits:These gates can be understood as doing a certain unitary operation only if the control qubits are enabled or disabled.

The first example to look at is the CNOT gate.