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?
3
-
$\begingroup$ What do you mean by Total function? $\endgroup$– Martin VeselyJul 28, 2021 at 10:57
-
1$\begingroup$ All elements from domain are mapped, ie not a partial function. $\endgroup$– newlogicJul 28, 2021 at 11:03
-
2$\begingroup$ where have you read this? $\endgroup$– glS ♦Jul 28, 2021 at 14:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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:
- The oracle is unitary;
- This oracle is perfectly indistinguishable from a truly random function for the adversary, no matter what its input state is;
is proven in Zhandry's paper and, I think, out of the scope of this question.
answered Jul 28, 2021 at 11:50
-
$\begingroup$ Hi Tristan thanks for your answer, do you have any references directly about programming Quantum Computers with total functions? $\endgroup$– newlogicJul 28, 2021 at 13:58
-
2$\begingroup$ @newlogic I'm not sure about what you mean: "Programming Quantum computers with total functions" is equivalent to "Programming quantum Computers", since total functions applied on quantum states are juste unitary matrices, which is the approach taken in every quantum computing book I know of $\endgroup$ Jul 28, 2021 at 15:00
$\begingroup$
$\endgroup$
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).
answered Jul 28, 2021 at 17:57