# Einstein Relatively Easy

### What's Up

User Rating: 5 / 5      Quantum parallelism is a fundamental feature of many quantum algorithms. Heuristically, quantum parallelism allows quantum computers to evaluate a function f(x) for many different values of x simultaneously.

The Deutsch-Jozsa algorithm - published by David Deutsch and Richard Jozsa in 1992 - is one of the first quantum algorithms with nice speedup over its classical counterpart, and it represents a good example of quantum parallelism.

##### Constant and balanced functions

In most typical cases where functions are involved, we are mostly interested in finding the result of a function. But in some cases though, the function evaluations are not important, but the characteristics or the properties of the functions are. In this area, quantum algorithms can be helpful.

In general, the functions we consider are noted as f(x) where f is the function that operates on an input variable called x. The evaluation of a function for a specific input is also called the result and sometimes noted as y, where y = f(x).

Let's start with a very simple function f which takes a single bit (a boolean value) as its input, and it produces a single bit as well. The function thus only operates on either '0' and '1' and its result is either '0' or '1'

Let f :{0, 1}→{0, 1}.

The combination of 2 input options and 2 output options leads to 4 possible cases for this function, which we will name f1, f2, f3 and f4:

f1: f(0) = 0 and f(1) = 0

f2: f(0) = 0 and f(1) = 1

f3: f(0) = 1 and f(1) = 0

f4: f(0) = 1 and f(1) = 1

##### The Deutsch problem

This being said, the question that we ask ourselves is very simple: does f(0) =f(1)?

This is often stated in a much more pedantic way for whatever reasons: “Is f constant or balanced?

- by constant, we mean f(0) = f(1),

- by balanced we mean f(0) != f(1).

This is to say in much more words ;-)

From those defintions, it appears that f1 and f4 are constant functions, and f2 and f3 are balanced functions.

We can state the Deutsch problem in an even more pedantic way, as follows:

Determine the value of the parity of f(0) ⊕ f(1) where ⊕ denotes addition modulo two.

Show that if f is constant then the parity is zero, and if f is balanced then the parity is one.

In the Deutsch algorithm, one of the four functions is provided, but we don’t know what function it is. We know it is f1, f2, f3 or f4 but that’s all we know.

We are now asked to find out if this function is constant or balanced. Keep in mind that our task is not to find out if the provided function is f1, f2, f3 or f4 .

Now we get to the intersting part, solving the problem.

##### Solving the problem

First, we can ask ourselves how many classical queries does it take to solve this problem?

That’s a pretty easy exercise.  It’s two.  It must be two since the values of f(0) and f(1) are completely independent of each other.

We have to ask what both values are, then compare to see if they’re the same ordifferent.

For example, suppose we measure f(0) and the result is 1. From the table above, it seems that in this case, our function is either f3 (which is balanced) or f4 (which is constant). Hence, we don’t have enough information.

In case the result of measuring f(0) is 0, the table above shows that the function is either f1 (which is constant) or f4 (which is balanced). Again, this proves that measuring f(0) is not enough to conclude whether the function is constant or balanced. It can be either.

If the number of input bits is increased to n, to verify a function is balanced, we query f for 2n-1 +1 in the worst case. We have a problem with query complexity that can grow exponentially in the worst case

##### From functions to Oracle

We can not simply apply a function to a qubit. In our article  Introduction to quantum logic gates we explained that all quantum gates need to be reversible.

A function that, after being applied makes it impossible to retrieve the original input, can not be used in a quantum circuit. Therefore, the function first need to be transformed into a reversible quantum gate.

More precisely, we need to transform our function into an quantum oracle. An oracle is used to describe a "quantum black box". Internally, it is composed of one or more quantum gates, but we typically don’t know which gates. By querying the oracle (e.g. by sending input and measuring the output), we can learn more about the properties of the oracle. Because an oracle is composed of quantum gates, the oracle itself needs to be reversible as well.

Every classical function that we described earlier can be represented by a specific oracle. Since we had  four possible functions f1, f2, f3 and f4, we also have four possible oracles.

Let’s expand n to 2 qubits. We can use Hadamard gates to prepare a superposition representing all four possible bit combinations. We assume that we have an Oracle function (a kind of a super smart quantum circuit). It uses the quantum parallelism concept to compute all values of f(x) from the superposition in polynomial time, instead of growing exponentially with the number of bases. Let’s not bother on how this oracle function is implemented for now.

By creating a superposition, we allow an Oracle function to work on all possible configurations all at once.

We remember from our article Parallel superposition and Hadamard gates  that starting with a state of n qubits |0...0n⟩, if we apply the Hadamard gate to each qubit it results in the following state: Let’s lay down a big picture of our circuit before detailing it Let us follow the states along to see what happens in this circuit:

We first apply a Pauli X-gate to the second qubit which converts it from |0⟩ to |1⟩. We then apply a Hadamard gate to each of the qubits and put them into a superposition Now, our first qubit is in a superposition representing both possible input |0⟩ and|1⟩ for  the function implemented as a quantum oracle Of.

The oracle maps the state to , where is addition modulo 2. In other words, the oracle leaves the |x> qubit in its original state, and the |y> qubit is replaced by the XOR operation between y and f(x). If we replace |x> and |y> by our superposition states, we get: By definition, either f(x)=0 or f(x)=1 thus: By examining both outputs, we can generalize the equation as: Now replacing |x> by 1/√2(|0> + |1>) yields to: We can go through all possible combination of f and compute the superposition of the first qubit for each scenario. We find that for the same function type, the values differ by a sign only. i.e. by a global phase with the Δγ equals π.

But we remember from our article Introduction to quantum logic gates (section dedicated to the Bloch Sphere) that an arbitrary single qubit state can be written as e times any |state> expression, as qubit states with arbitrary values of γ are all represented by the same point on the Bloch sphere because the factor of e has no observable effects, and we can therefore effectively omit this term.

This is excellent news for us! Within the same function type, states which differ by a sign only will always measure the same way.

So our focus is applying a transformation so different groups end up with different measurements.

From the same article, we know that Hadamard gate is a reversible gate so that H|+>=|0> and |H|->=|1> So that if we apply a final Hadamard gate to our states in superposition and if we do a measurement:

- if we measure 0, we are certain to deal with a constant function

- if we measure 1, we are certain to deal with a balanced function

Compared to a classical resolution, we have thus divided the number of queries by 2, as only one and only one measure gives us the expected result in a quantum context.

##### Multiple-bit input: the Deutsch-Jozsa algorithm

Let’s try to expand our solution for input with n bits, which would lead to a more general quantum algorithm, which we shall refer to as the Deutsch–Jozsa algorithm.

We can apply n Hadamard gates to prepare the superposition (as seen in our article Parallel superposition and Hadamard gates), leading to: That is, the Hadamard transform produces an equal superposition of all computational basis states.

After the Hadamard transform on the query register (or first qubit) and the Hadamard gate on the answer register (or second qubit) we have the state The query register is now a superposition of all values, and the answer register is in an evenly weighted superposition of 0 and 1.

Next, the function f is evaluated by applying the same oracle which maps the state to , and for the same reasons as for above, giving: Then, we apply n Hadamard gate again.

Fortunately, we know from our previous article Parallel superposition and Hadamard gates that  the general equation for the Hadamard gate transformation on multiple qubits can be summarized in the very useful below equation: Applying this equation to |φ2> we get Let's consider now the state |0>⊗n, its amplitude is easily deduced as Let’s look at the two possible cases – f constant and f balanced – to discern what happens. In the case where f is constant, the amplitude for |0>⊗n is +1 if f(x)=0 or −1 if f(x)=1.

And because the state is of unit length, it follows that all the other amplitudes must be zero, and an observation will yield 0s for all qubits in the query register.

At the contrary, if f is balanced then the positive and negative contributions to the amplitude for |0>⊗n cancel, leaving an amplitude of zero, and a measurement must yield a result other than 0 on at least one qubit in the query register.

We’ve shown that a quantum computer can solve Deutsch-Jozsa’s problem with one evaluation of the function f compared to the classical requirement for 2n-1 + 1 evaluations.

### Quotes

"The essence of my theory is precisely that no independent properties are attributed to space on its own. It can be put jokingly this way. If I allow all things to vanish from the world, then following Newton, the Galilean inertial space remains; following my interpretation, however, nothing remains.."
Letter from A.Einstein to Karl Schwarzschild - Berlin, 9 January 1916

"Quantum mechanics is certainly imposing. But an inner voice tells me that it is not yet the real thing. The theory says a lot, but does not really bring us any closer to the secret of the 'old one'. I, at any rate, am convinced that He is not playing at dice."
Einstein to Max Born, letter 52, 4th december 1926