Efficient creation of a modular multiplicative inverse gate using Fermat's Little Theorem

Question

I'm wondering if anyone has ever stumbled upon an efficient way to create a gate that can calculate the multiplicative modular inverse in $\mathbb{Z}_p$, it may even be that somebody has stumbled upon it by accident, without being aware of Fermat's Little Theorem.

In other words a circuit for: $$ |a\rangle|0\rangle \rightarrow |a\rangle|x\rangle, \textrm{where}~ax~\equiv1\mod{p} \tag{1}$$ Or alternatively using Fermat's Little Theorem: $$|a\rangle|0\rangle \rightarrow |a\rangle|a^{p-2}\mod{p}\rangle \tag{2}$$

In fact, from my understanding it should actually be possible to even do the following: $$|a\rangle \rightarrow |a^{p-2}\mod{p}\rangle \tag{3}$$ or in Notation from (1): $$|a\rangle \rightarrow |x\rangle \tag{4}$$ as it is a bijection and hence reverisble. (Note: it is only a bijection when $a^n$, $n = p - 2$, else you will need more information in another register to make it reversible, see the case of squaring in Eq. 5)

Unfortuantely, constructing the Unitary (and then decomposing it, e.g. using Shannon-decomposition) that would correspond to this, is not doable efficentely since the creation of the Unitary requires knowing all modular inverses and hence iterating exponentially over $\mathbb{Z}_p$. Not to mention that such a decomposition doesn't (afaik) guarantee a polynomial number of gates.

However, interestingly I was able to construct, following RNSL's paper (https://arxiv.org/pdf/1706.06752): $$|a\rangle|0\rangle \rightarrow |a\rangle|a^2\mod{p}\rangle \tag{5}$$ which makes me feel optimistic about being able to do: $$|a\rangle|0\rangle \rightarrow |a\rangle|a^{p-2}\mod{p}\rangle$$ Or more in general: $$|a\rangle|0\rangle \rightarrow |a\rangle|a^n\mod{p}\rangle \tag{6}$$

Small note: I am aware it is possible to construct this gate in polynomial time, by creating a quantum EEA algorithm to calculate the GCD. I am explicitly ignoring this solution, as it uses far too many qubits and the papers are not the easiest to understand. I believe that a variant using Fermat's Little Theorem, would also be more interesting, and perhaps even more performant.

Answer 1

You can perform $|a\rangle|0\rangle \rightarrow |a\rangle|a^{-1}\rangle$ efficiently by using superposition masking. This uses some multiplications on the quantum computer to move the expensive computation of an inverse to a classical computer where it's much faster. But this process isn't reversible, so weirdly you can't then uncompute $|a\rangle|a^{-1}\rangle \rightarrow |a\rangle|0\rangle$ with the same technique.

---

I don't think that doing a modular exponentiation under superposition will be cheaper than the standard technique of doing an extended binary gcd under superposition, such as in Figure 6/7 of "Improved quantum circuits for elliptic curve discrete logarithms".