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$ ? 
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ what would you think $f^{-1}(A)$ would be? $\endgroup$– Mark SpinelliCommented Jul 9, 2021 at 2:58
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Jul 9, 2021 at 6:56
-
$\begingroup$ 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. $\endgroup$ Commented Jul 9, 2021 at 14:54
$\begingroup$
$\endgroup$
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.
answered Jul 9, 2021 at 5:35