Deutsch-Yozhi Algorithm

The Deutsch – Jozy algorithm (also referred to as the Deutsch – Josy algorithm) is a quantum algorithm proposed by David Deutsch and Richard Jozhey [en] in 1992, and one of the first examples of algorithms designed to run on quantum computers. Thanks to the use of the quantum entanglement phenomenon and the principle of superposition, these algorithms have a significant increase in execution speed compared to the corresponding classical algorithms.

The task of Deutsch - Yozhi is to determine whether a function is a binary variable constant (takes either the value 0 or 1 for any arguments) or balanced (for the half of the definition area takes the value 0, for the other half 1). It is considered a priori known that the function is either constant or balanced.

To solve this problem, the classical deterministic algorithm needs to be produced computing the function f in the worst case. The classical probabilistic algorithm takes less time to give the correct answer with a high probability. But in any case, to get the right answer with a single probability will be required calculations The algorithm gives the correct answer, once applying the phase request corresponding to the given function f .

If the function unbalanced, the algorithm can give the answer "constant" with a certain probability, and the greater the difference between the number of "0" and "1", the greater will be this probability [1] .

The algorithm of Deutsche-Jozi is based on a similar algorithm developed by David Deutsch in 1985, which is a special case of the first one. In this algorithm, the function was a function of one variable, in contrast to the function of many variables used in a later algorithm.

Algorithm

At the input of the algorithm there is a boolean function from Boolean variables. The algorithm is an application to the zero vector. operator and register state measurement. If all bits of the register are 0, then the value of the function does not depend on otherwise the function is balanced.

Here - Hadamard transform:

- phase request that inverts the phase for register states corresponding to the function units and does not change the state corresponding to the zeros of the function: [2]

The operation of the algorithm on the example of the task Deutsch

The input to the algorithm is a Boolean function of one variable. . In total there are 4 such functions [2] :

No	f (0)	f (1)
one	0	0
2	one	one
3	0	one
four	one	0

Functions 1 and 2 are called constant, and functions 3 and 4 are balanced.

At the first step, we set the zero state to the qubit:

Applying the Hadamard transform we get . In principle, it would be possible to immediately assign a state to a qubit, but it is technically easier to first set the zero state and then convert it using unitary transformations to the desired form.

Applying phase request to our function , we get the following state:

The second Hadamard transform leads to the following state:

When measuring the state of a qubit, we obtain 0 for constant functions and 1 for balanced functions. This can be seen by substituting all sorts of functions f (x) into the expression for the qubit state:

No	f (0)	f (1)	Qubit state	Probability of receiving 0	Probability of receiving 1
one
2
3
four

Notes

1. ↑ M. Sluggish, Quantum Algorithms, Lecture 2.
2. ↑ Go to: 1 2 Quantum algorithms: possibilities and limitations. M. Vyaly, Lecture 2, pp. 12-13 (St. Petersburg, spring 2011)