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 community
It is well-known that by utilizing quantum parallelism we can calculate a function $f(x)$ for many different values of $x$ simultaneously. However, some clever manipulations is needed to extract the information of each value, i.e. with Deutsch's algorithm.
Consider the reverse case: can we use quantum parallelism to calculate many functions (say $f(x),g(x),\dots$) simultaneously for a single value $x_0$?
The exact answer depends on the exact kind of superposition you want. The answers by pyramids and Niel both give you something like
$$A\sum_{t=1}^n |\,\,f_t (x)\,\,\rangle \otimes |F_t\rangle$$
Here I've followed Niel in labelling the different functions $f_1$, $f_2$, etc, with $n$ as the total number of functions you want to superpose. Also I've used $F_t$ to denotes some description of the function $f_t$ as a stored program. The $A$ is just whatever number needs to be there for the state to be normalized.
Note that this is not simply a superposition of the $f_t(x)$. It is entangled with the stored program. If you were to trace out the stored program, you'd just have a mixture of the $f_t(x)$. This means that the stored program could constitute 'garbage', which prevents interference effects that you might be counting on. Or it might not. It depends on how this superposition will be used in your computation.
If you want rid of the garbage, things get more tricky. For example, suppose what you want is a unitary $U$ that has the effect
$$U : \,\,\, | x \rangle \otimes |0\rangle^{\otimes N} \rightarrow A \sum_{t=1}^n |\,\,f_t (x)\,\,\rangle$$
for all possible inputs $x$ (which I am assuming are bit strings written in the computational basis). Note that I've also included some blank qubits on the input side, in case the functions have longer outputs than inputs.
From this we can very quickly find a condition that the functions must satisfy: since the input states form an orthogonal set, so must the outputs. This will put a significant restriction on the kinds of functions that can be combined in this way.
The functions $f,g,\ldots $ that you want to evaluate in different computational branches must, in order to be computable at all, be specifiable in some way (e.g. a sequence of classical logic gates). And the set $\{ f_1, f_2 , \ldots \}$ of the functions you wish to compute ought itself to be computable: for a given $t $, you must be able to compute a specification of how $f_t $ is to be computed on its argument. In effect: you must have a means of describing the functions $f_t $ as stored programs. (These are all necessary, even before we consider quantum computation, for the question of "computing one/all of the functions $f_1, f_2, \ldots $ on an input $x_0$" to be meaningful.)
Once you have a way of specifying functions as stored programs, you're basically done: a program is essentially another kind of input, which you can prepare in superposition, and e.g. evaluate on a fixed input, or a superposition of inputs, by computing the functions from their specifications in each branch.
To gain a comptational advantage from doing so is a different matter, and will have to involve some specific structure in the functions $f_t $ that you can take advantage of, but simply to "evaluate in superposition" is easily done if you have enough information for the question to be sensible.
Describing the circuit that gives the function $f$ as $U_f$ and the circuit giving $g$ as $U_g$, there are a few ways to go about doing this:
Starting with the qubit registers in $\left|00x\right>$, Prepare a state $\alpha\left|01\right>+\beta\left|10\right>$ on the first two registers. This can be done by applying a unitary1 on the first register to put that register in the state $\alpha\left|0\right> + \beta\left|1\right>$ before applying CNOT, then $I\otimes X$. Then, apply $CU_f$ from the first register to the third and $CU_g$ from the second to the third.
1.1. This gives that the third register is now in the state $\left(\alpha U_f + \beta U_g\right)\left|x\right>$, when the initial operations (up to $I\otimes X$) on the first two registers are reversed. However, owing to the general difficulties of implementing arbitrary controlled-unitary operations (as well as using extra qubits unnecessarily) it would probably be easier to implement this directly by dialling up the unitary $\alpha U_f + \beta U_g$. Note that this is neither implementing $f$ nor $g$, but a new, different function $f+g$
1.2. Not reversing the initial operations on the first two registers puts the third in some entangled state of $f$ and $g$, which is discussed in other answers.
Starting with the state $\left|xx\right>$ and applying $U_f$ to the first register and $U_g$ to the second. This is the closest to classical parallelism, where both functions are applied independently to copies of the same state. Aside from requiring twice the number of qubits, the issue here is that, due to no-cloning, in order to copy $\left|x\right>$, it either has to be known, or be a classical state (i.e. not involve superpositions in the computational basis). Approximate cloning could also be used.
Start with the state $\left|0x\right>$, as well as a classical register. Apply a unitary1 to put the first register in the superposition $\alpha\left|0\right>+\beta\left|1\right>$. Now, measure this register (putting the result in the classical register) and apply the classical operation IF RESULT = 0 U_f ELSE U_g. While this may seem less powerful than either of the above operations, this is in some sense, equivalent to the quantum channel $\mathcal E\left(\rho\right) = \lvert\alpha\rvert^2U_f\rho U_f^\dagger + \lvert\beta\rvert^2U_g\rho U_g^\dagger$. Such methods can be used to make random unitaries, which have applications in e.g. boson sampling and randomised benchmarking
1 given by $$\begin{pmatrix}\alpha &&-\beta^* \\ \beta && \alpha^*\end{pmatrix}$$
Yes, one can. The trick is to define (and implement) a new function $f_\mathrm{all}(y,x)$ that evaluates to $f(x)$ if $y=0$, to $g(x)$ if $y=1$, etc. Then one prepares the qubits representing $y$ in the desired superposition and set $x$ to $x_0$.
