Quantum computations, irreversibility, unitarity

1. Mar 3, 2008

kdv

A stupid couple of questions...

In quantum computations, one typically starts with some initial quantum state on which an operator is applied.

This operator must be unitary , right? (I guess that otherwise, it would not corerspond to an actual physical quantum setup). And this implies that the operator must be reversible, correct?
So in quantum computing, we consider only irreversible processes, correct?

Now consider Deutsch's algorithm. It deals with a function acting on a single qubit which may be either "balanced" or "constant".

It is balanced if it may give both 0 and 1 a sresult. One possibility is f(0)=0, f(1)=1 and the other balanced possibility is f(0)=1, f(1)=0.

It is constant if it gives the samr answer no matter what the input is. So the first possibility is f(0) =f(1) =0 and the second possibility is f(0)=f(1)=1.

Now, the whole idea of Deutsch's algorithm is to able to distinguish whether f is balanced or constant with a single application of a certain operation which must be chosen judiciously. (and the input state must be chosen judiciously as well).

Now, usually people say: classically, one cannot determine if the function is constant or balanced without two runs fo teh function. (for example, observing that f(0) gives zero does not tell us if it's balanced or not). Then people say that quantum mechanically, one can tell if f is balanced or not with a single run of an operator applied to a suitable combination of two qubits.

Fine. But my question is this: if I understand correctly, the function f(x) itself cannot be represented by any quantum operator , correct? Because in the constant case it is not reversible and therefore could not be associated to a unitary operator.

This kind of surprised me when I thought about this today...It's weird in some sense because the starting point is the operator "f" and yet I have never seen anyone mentioning that f itself cannot be implemented as a quantum operation. Maybe I am missing something?

2. Mar 3, 2008

Hurkyl

Staff Emeritus
He probably means something like the following operation on two qubits:

|x>|y> ---> |x>|y + f(x)>

3. Mar 3, 2008

kdv

Yes, I know this is the operation used in Deutsch's algorithm. I was wondering if I was correct in saying that the operation on a single qubit |x> ---> |f(x)> would be impossible to implement.