# How does a quantum circuit calculating the inverse of a non-injective function act?

Lets say I have a non-injective function $$f()$$, adding image for reference. Now lets say I build a quantum circuit to calculate $$f^{-1}()$$. If the input register has the value $$i$$, does the output register have all the values $$j$$ in superpostion, such that $$f(j)=i$$ ?

• what would you think $f^{-1}(A)$ would be? Jul 9, 2021 at 2:58

This is essentially a matter of definition. If you design and build a function which you are claiming to be $$f^{-1}$$, you first have to define what the output will be if the input is $$C$$, and what you define will determine how you implement it. Outputting some sort of superposition might seem like a reasonable option, but mathematically the function is unlikely to behave how you would expect it to. But that might all come down to the context you're using it in.
• The context I'm using it in is to find the different inputs which have the same image under $f$. You can think of $f$ as a function calculating some cube-roots in a finite field where cube-roots are not injective. Jul 9, 2021 at 14:54
Any operation on a quantum computer has to be reversible, measurement and reset being an exceptions. In your case the operation is not reversible as for C you have two possible inputs - 3 and 4. To implement your operation on QC you have to distinguish between 3 and 4. The most general approach is to copy input state together with the output. For example if input is $$|3\rangle$$, then output will be $$|3\rangle|C\rangle$$ and for input $$|4\rangle$$ you will have $$|4\rangle|C\rangle$$. Now, your operation is reversible.