# What can I deduce about $f(x)$ if $f$ is balanced or constant?

$\newcommand{\qr}[1]{|#1\rangle}$Question. Can you check whether this is correct? Also, given the analysis below, what is the domain of and co-domain of $f(\qr{x})$? I think it is $V^4 \to W^4 : f$ because

$$\qr{00} = \qr{0}\otimes\qr{0} = \left[\begin{matrix}1\\0\\0\\0\end{matrix}\right].$$

Analysis. Let

$$\qr{x} = a_{00}\qr{00} + a_{01}\qr{01} + a_{10}\qr{10} + a_{11}\qr{11}$$

and let $U_f$ implement some constant or balanced function $f(x)$. Then I claim the following holds given the linear function nature of $U_f$. \begin{align*} f(\qr{x}) &= U_f\qr{x}\\ &= U_f(a_{00}\qr{00} + a_{01}\qr{01} + a_{10}\qr{10} + a_{11}\qr{11})\\ &= U_f(a_{00}\qr{00}) + U_f(a_{01}\qr{01}) + U_f(a_{10}\qr{10}) + U_f(a_{11}\qr{11})\\ &= a_{00}U_f(\qr{00}) + a_{01}U_f(\qr{01}) + a_{10}U_f(\qr{10}) + a_{11}U_f(\qr{11}), \end{align*}

Now if $f$ is constant --- with $f(\qr{x}) = \qr{00}$ for all $\qr{x}$ ---, then we would have

\begin{align*} f(\qr{x}) &= a_{00}U_f(\qr{00}) + a_{01}U_f(\qr{01}) + a_{10}U_f(\qr{10}) + a_{11}U_f(\qr{11})\\ &= a_{00}\qr{00} + a_{01}\qr{00} + a_{10}\qr{00} + a_{11}\qr{00}\\ &= (a_{00} + a_{01} + a_{10} + a_{11})\qr{00}. \end{align*}

If, on the other hand, $f$ is balanced then with probability $1/2$, we have \begin{align*} f(\qr{x}) &= a_{00}U_f(\qr{00}) + a_{01}U_f(\qr{01}) + a_{10}U_f(\qr{10}) + a_{11}U_f(\qr{11})\\ &= (a_{00} + a_{01} + a_{10} + a_{11})\qr{00} \end{align*} and with probability $1/2$ as well

\begin{align*} f(\qr{x}) &= a_{00}U_f(\qr{00}) + a_{01}U_f(\qr{01}) + a_{10}U_f(\qr{10}) + a_{11}U_f(\qr{11})\\ &= (a_{00} + a_{01} + a_{10} + a_{11})\qr{11}. \end{align*}

• Could you please provide more context to the question? It looks like a homework problem as it is currently written. – Daniel Burkhart Apr 22 '18 at 17:32
• It's not homework. But even if it was, I think I'm looking to get some clarity here and that seems reasonable. Would you want to know what I'm doing? I'm trying to understand Deustch's algorithm and I'm reading these notes I found on the web. Take a look at the first exercise. The exercise is given right after saying that operators are linear. I hope that helps. – R. Chopin Apr 22 '18 at 21:21
• Of relevance perhaps: What to do about homework questions. – R. Chopin Apr 22 '18 at 21:27
• Notational nitpick: don't use $U$ for something you don't intend to be unitary. – AHusain Apr 22 '18 at 21:36
• @AHusain Interesting. Thanks. But, look, they are using it. In these notes, $U_f$ is just a circuit that implements $f$. But very interesting comment. That circuit need not be unitary and such nitpick had not even occurred to me yet. So, thanks. – R. Chopin Apr 22 '18 at 21:52

$f$ being balanced does not mean that it gives one output with probability $0.5$ and the other output with probability $0.5$. Instead, it means that half of the inputs are sent to one output and the other half to a different output.

I don't know what you are referring to in the notes you link, but $f$ is there defined as $f:\{0,1\}^n\mapsto\{0,1\}$, and if it is balanced then it will act for example as $f(00)=f(01)=0$, $f(10)=f(11)=1$. This is totally different from what you wrote, as you will get something like $$|x\rangle\mapsto|f(x)\rangle=(a_{00}+a_{01})|0\rangle+(a_{10}+a_{11})|1\rangle.$$

• @gIs I don't follow you. Are you saying the distribution of (input, output) is not uniform, that being the sole reason the probability of 1 or 0 not being 1/2? – R. Chopin Apr 25 '18 at 0:43
• @gIS I didn't refer to anything in the notes. (It was only background information to someone who requested.) So my $f$ is not that $f$. That $f$ works with a $n$ q-bits, while my $f$ works with 2. Can you point which line is a wrong deduction in my calculations? (Or can you show why yours is correct?) Thank you. – R. Chopin Apr 25 '18 at 0:49
• I referred to the notes because otherwise I don't see how your way of defining a "balanced $f$" makes sense. It is just not the way it is defined in this context. If you don't want to use known notation you have to define what are domain and co-domain of $f$, you cannot ask for it. If you are just defining your objects as in your post, then I don't understand what is the question. – glS Apr 25 '18 at 9:36

The problem here is that $U_f$ as you've defined it is not unitary. To see this, note that the overlaps between states are preserved under the action of a unitary: $\langle\psi|\phi\rangle=\langle\psi|U^\dagger U|\phi\rangle$, while for a constant function $f$ you have $U_f|x\rangle=U_f|x'\rangle$ even if $x\neq x'$ (thereby changing the overlap from 0 to 1).

The way that you set this up as a unitary is with some additional qubits. If $f:x\mapsto y$ where $x\in\{0,1\}^n$ and $y\in\{0,1\}^m$, then you define $U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle$. This is definitely unitary because $$U_fU_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\oplus f(x)\rangle=|x\rangle|y\rangle,$$ so $U_f$ is its own inverse.

Of course, you could define a quantum operation that always sets everything to 0. It's basically a measurement (in the $Z$ basis) followed by a compensating action depending on the measurement outcome. But then you can't use linearity as you did in your analysis, because you have to follow through the different measurement outcomes separately.