I have read that the way we must program Quantum Computers is through Total functions only. Why is this the case? Is it because quantum circuits are less forgiving in terms of logical errors?
Could you provide an academic reference?
Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this communityI have read that the way we must program Quantum Computers is through Total functions only. Why is this the case? Is it because quantum circuits are less forgiving in terms of logical errors?
Could you provide an academic reference?
It is due to the inherent linearity of Quantum Mechanics. By definition, applying a function to a quantum state means mapping this quantum state to another one. Now, a quantum state can be represented as a unitary vector lying in an Hilbert space, and every transformation it undergoes follows Shrödinger equation, ensuring that any such transformation is actually an unitary matrix.
It does not make sense to define an unitary matrix $M$ such that $M|\psi\rangle$ is well-defined but $M|\varphi\rangle$ is not, for given unitary vectors lying in the same Hilbert space as $M$'s columns. Thus, for any input you can provide your function with, this function has to be defined for this output.
I'm not sure this is on point, but you can work with partial functions in quantum computing to a partial extent though, using Zhandry's compressed oracle, as explained in this draft paper by Unruh.
The idea is the following: let us say that you want to work with a partial function $f$ defined on $n$ inputs $\left(x_i,y_i\right)$ and undefined on the other ones. Your goal is to provide the user (the "adversary") with a unitary oracle $\mathcal{O}_f$ that works as follows:
$$\mathcal{O}_f|x\rangle=\begin{cases}y_i&\text{if }x=x_i\\\text{A uniformly random output}&\text{otherwise}\end{cases}\,.$$
Note that this oracle has to stay unitary. As such, if the adversary queries the oracle on $\left|x\neq x_i\right\rangle$, the oracle will choose an output $|y\rangle$ for this input, and will always answer with this output when being queried for $|x\rangle$. To put it differently, $f$ is now defined on $n+1$ inputs, which are the $x_i$ and $x$. The beauty of Zhandry's compressed oracle is that even though the description we just made makes sense for classical queries (that is, queries on basis states), the oracle still works for superposition queries: it will choose an output once the adversary measures the associated input.
Furthermore, the formalism used in Zhandry's compressedd oracle allows to pre-define $f$ on as much inputs as you like, by storing them in the database before the adversary can access $\mathcal{O}_f$.
The fact that implementing this oracle as described in Zhandry's paper ensures that:
is proven in Zhandry's paper and, I think, out of the scope of this question.
A condensed answer:
Any operation on a quantum computer, measurement and reset being exceptions, are described by a unitary matrix. This follows from Schrodinger equation which solution for discrete time steps is a unitary matrix. A unitary matrix is invertible and its columns form a orthonormal basis of a vector space. Hence, it defines a 1:1 mapping (a total function in your words).