Deutsch-Jozsa algorithm

The algorithm of German is a quantum algorithm for quantum computers , can determine with whom you whether operating on a bit function is constant or balanced. This task is known as the problem of German . Deutsch's algorithm is hardly of any practical use, but historically it was the first quantum algorithm that demonstrably solves a problem faster than a classic algorithm and thus demonstrates the theoretical possibilities of quantum computers.

One generalization is the Deutsch-Jozsa algorithm . The problem is transferred from German to several bits.

The algorithms were named after their creators David Deutsch and Richard Jozsa .

history

In a paper from 1985 David Deutsch dealt with the special case of the problem (problem of German, number of input bits: 1).

In 1992 the idea was generalized by David Deutsch and Richard Jozsa (problem from Deutsch-Jozsa, any number of input bits).

The algorithm originally proposed by Deutsch was de facto not deterministic . He was successful with a probability of 0.5. The original Deutsch-Jozsa algorithm was deterministic, but in contrast to Deutsch's algorithm, it required two function evaluations instead of just one.

R. Cleve, A. Ekert, C. Macchiavello and M. Mosca made further improvements in 1998, so that now only one function evaluation is required and the algorithm remains deterministic.

The Deutsch-Jozsa algorithm served as the inspiration for the Shor algorithm and the Grover algorithm , two of the most revolutionary quantum algorithms.

The problem of German

Problem formulation

Given a function . The task now is to find out whether the given function is constant ( ) or balanced / equilibrium ( ). It should be noted that it is only given as a black box, i.e. the exact definition is unknown - only one component is available which calculates the value for a bit . To underline the importance of the Deutsch algorithm, it should be assumed that this component is expensive to use. ${\displaystyle f:\lbrace 0,1\rbrace \to \lbrace 0,1\rbrace }$ ${\displaystyle f(0)=f(1)}$ ${\displaystyle f(0)\neq f(1)}$ ${\displaystyle f}$ ${\displaystyle b}$ ${\displaystyle f(b)}$

To illustrate this, imagine being asked to decide whether a given coin is fair (heads on one side, tails on the other) or unfair (heads or tails on both sides of the coin).

Classic solution

In the classic way, there is nothing left but to evaluate and compare the function both for and. This is equivalent to looking at a coin on both sides. The black box (or oracle) is therefore required twice. In the following it is shown that the quantum algorithm of Deutsch gets by with only one call. This is advantageous when you consider that once accepted, a call is very expensive (but the cost is asymptotically the same). ${\displaystyle f(0)}$ ${\displaystyle f(1)}$

The quantum algorithm

Quantum circuit that implements Deutsch's algorithm

The quantum algorithm applies the given function to a superposition of the two possible inputs. With only one application of the oracle, he receives sufficient information about and through skillful evaluation . ${\displaystyle f(0)}$ ${\displaystyle f(1)}$

Since all calculation steps in quantum informatics must be reversible, a special variant of is required here, using (addition with subsequent modulo 2) described by the figure ${\displaystyle f}$ ${\displaystyle \oplus }$

${\displaystyle U_{f}:\left|x\right\rangle \left|y\right\rangle \mapsto \left|x\right\rangle \left|f(x)\oplus y\right\rangle }$

The algorithm uses a register of two qubits (with the tensor product , which is usually represented with ) and consists of the following steps: ${\displaystyle \left|x\right\rangle \cdot \left|y\right\rangle }$ ${\displaystyle \cdot }$ ${\displaystyle \otimes }$

1. Initialize as follows:
   

   ${\displaystyle {\begin{aligned}\left|x\right\rangle \left|y\right\rangle &=\left|0\right\rangle \left|1\right\rangle \\&=\left|a\right\rangle \end{aligned}}}$

2. Apply the Hadamard transform to both qubits: ${\displaystyle H}$
   

   ${\displaystyle {\begin{aligned}\left|x\right\rangle \left|y\right\rangle &\rightarrow H\left|x\right\rangle H\left|y\right\rangle \\&={\frac {1}{\sqrt {2}}}{\bigl (}\left|0\right\rangle +\left|1\right\rangle {\bigr )}\cdot {\frac {1}{\sqrt {2}}}{\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&={\frac {1}{2}}{\bigl (}\left|0\right\rangle \left|0\right\rangle -\left|0\right\rangle \left|1\right\rangle +\left|1\right\rangle \left|0\right\rangle -\left|1\right\rangle \left|1\right\rangle {\bigr )}\\&=\left|b\right\rangle \end{aligned}}}$

3. Values from: ${\displaystyle U_{f}}$
   

   ${\displaystyle {\begin{aligned}\left|x\right\rangle \left|y\right\rangle &\rightarrow U_{f}\left|x\right\rangle \left|y\right\rangle \\&={\frac {1}{2}}{\Bigl (}\left|0\right\rangle \left|0\oplus f(0)\right\rangle -\left|0\right\rangle \left|1\oplus f(0)\right\rangle +\left|1\right\rangle \left|0\oplus f(1)\right\rangle -\left|1\right\rangle \left|1\oplus f(1)\right\rangle {\Bigr )}\\&={\frac {1}{2}}{\Bigl (}\left|0\right\rangle \cdot {\bigl (}\left|f(0)\right\rangle -\left|1\oplus f(0)\right\rangle {\bigr )}+\left|1\right\rangle \cdot {\bigl (}\left|f(1)\right\rangle -\left|1\oplus f(1)\right\rangle {\bigr )}{\Bigr )}\\&={\frac {1}{2}}{\Bigl (}(-1)^{f(0)}\left|0\right\rangle \cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}+(-1)^{f(1)}\left|1\right\rangle \cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}{\Bigr )}\\&={\frac {1}{2}}{\bigl (}(-1)^{f(0)}\left|0\right\rangle +(-1)^{f(1)}\left|1\right\rangle {\bigr )}\cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&=\left|c\right\rangle \end{aligned}}}$
   

   ${\displaystyle \left|c\right\rangle }$is in the constant case and otherwise ${\displaystyle {\frac {1}{2}}{\Bigl (}\pm {\bigl (}\left|0\right\rangle +\left|1\right\rangle {\bigr )}{\Bigr )}\cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}}$ ${\displaystyle {\frac {1}{2}}{\Bigl (}\pm {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}{\Bigr )}\cdot {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}}$

4. Apply the Hadamard transform to the first qubit: ${\displaystyle H}$
   

   ${\displaystyle \left|x\right\rangle \rightarrow H\left|x\right\rangle }$

5. Measure the first qubit:
   

   Has the value , it is constant, otherwise balanced. ${\displaystyle \left|x\right\rangle }$ ${\displaystyle \left|0\right\rangle }$ ${\displaystyle f}$

So the trick is that we shift the function values ​​into the amplitude.

realization

The first experimental realization was reported by S. Gulde in Nature 421, 48 (2003) . The qubits required for this were implemented in a trap using the electronic and vibratory degrees of freedom of an ion. ${\displaystyle Ca^{+}}$

The problem of Deutsch-Jozsa

Problem formulation

The function is now generalized to input bits: It is guaranteed that the function is either constant (all inputs are mapped to one and the same value) or balanced (half of the inputs are mapped to and the other half to ). It is now necessary to find out which of the two alternatives applies. It should again be noted that it is only given as a black box or oracle. ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle f:\lbrace 0,1\rbrace ^{n}\to \lbrace 0,1\rbrace }$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle f}$

Classic solution

In the worst case, a classic computer would have to evaluate the function for more than half of all possible inputs. It can happen, for example, that even with the most skilful choice, the first (half as many as possible) tested entries lead to the value and it is still not known which alternative applies. If the next evaluation also results , then the function is constant, if it results, however , it is balanced. ${\displaystyle 2^{n-1}}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$

In the worst case, a classic algorithm therefore requires evaluations of . As shown below, the Deutsch-Jozsa algorithm only needs a single evaluation. This represents an exponential gain in runtime, which is a real improvement in contrast to Deutsch's problem / algorithm . ${\displaystyle 2^{n-1}+1}$ ${\displaystyle f}$

The quantum algorithm

Quantum circuit that implements the Deutsch-Jozsa algorithm

The quantum algorithm applies the given function to a superposition of all possible inputs. With only one application of the oracle, he receives sufficient information about all function values ​​through skillful evaluation.

Due to the reversibility to be obtained, a special variant of is required again, described by the figure ${\displaystyle f}$

${\displaystyle U_{f}:\left|x\right\rangle \left|y\right\rangle \mapsto \left|x\right\rangle \left|f(x)\oplus y\right\rangle }$

where the input is the length . ${\displaystyle \left|x\right\rangle }$ ${\displaystyle n}$

The algorithm uses qubits and goes through the following steps: ${\displaystyle n+1}$

1. Initialization: set the first bits to and the last bit to : ${\displaystyle n}$ ${\displaystyle \left|0\right\rangle }$ ${\displaystyle \left|1\right\rangle }$
   

   ${\displaystyle {\begin{aligned}\left|x\right\rangle \left|y\right\rangle &=\left|0\right\rangle ^{\otimes n}\left|1\right\rangle \\&=\left|a\right\rangle \end{aligned}}}$

2. Apply the Hadamard transformation (i.e. to all qubits): ${\displaystyle H_{n+1}}$ ${\displaystyle H_{2}}$
   

   ${\displaystyle {\begin{aligned}\left|x\right\rangle \left|y\right\rangle &\rightarrow H_{n+1}\left|x\right\rangle \left|y\right\rangle \\&=\left({\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}\left|x\right\rangle \right)\cdot {\frac {1}{\sqrt {2}}}{\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&={\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}\left|x\right\rangle {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&=\left|b\right\rangle \end{aligned}}}$

3. Values from: ${\displaystyle U_{f}}$
   

   ${\displaystyle {\begin{aligned}\left|x\right\rangle \left|y\right\rangle &\rightarrow U_{f}\left|x\right\rangle \left|y\right\rangle \\&={\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}\left|x\right\rangle {\bigl (}\left|f(x)\right\rangle -\left|1\oplus f(x)\right\rangle {\bigr )}\\&={\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left|x\right\rangle {\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&=\left({\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left|x\right\rangle \right)\cdot {\frac {1}{\sqrt {2}}}{\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&=\left|c\right\rangle \end{aligned}}}$

4. Apply the Hadamard transform to: ${\displaystyle \left|x\right\rangle }$
   

   ${\displaystyle {\begin{aligned}\left|x\right\rangle \left|y\right\rangle &\rightarrow {\bigl (}H_{n}\left|x\right\rangle {\bigr )}\left|y\right\rangle \\&=\left({\frac {1}{2^{n}}}\sum _{z=0}^{2^{n}-1}\sum _{x=0}^{2^{n}-1}(-1)^{{\vec {x}}\cdot {\vec {z}}+f(x)}\left|z\right\rangle \right)\cdot {\frac {1}{\sqrt {2}}}{\bigl (}\left|0\right\rangle -\left|1\right\rangle {\bigr )}\\&=\left|d\right\rangle \end{aligned}}}$

5. Measure the register : ${\displaystyle \left|x\right\rangle }$
   

   If it is , then it is constant, otherwise it is balanced. ${\displaystyle \left|0\ldots 0\right\rangle }$ ${\displaystyle f}$

The interpretation of the measurement result can be seen as follows: If the balance is balanced, the signs for equalize each other , so that the value is measured with a probability . In the other case, i.e. when is constant, the amplitudes for are exactly the same , since for those that can always be classified in such a way that half of the scalar multiplied by an even value results, the other half an odd value. ${\displaystyle f}$ ${\displaystyle \left|z\right\rangle =\left|0\right\rangle }$ ${\displaystyle 0}$ ${\displaystyle \left|0\right\rangle }$ ${\displaystyle f}$ ${\displaystyle \left|z\right\rangle \neq \left|0\right\rangle }$ ${\displaystyle 0}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle z}$

Individual evidence

1. ^ David Deutsch : The Church-Turing principle and the universal quantum computer . (PDF) In: Proceedings of the Royal Society of London A . 400, 1985, p. 97. doi : 10.1098 / rspa.1985.0070 .
2. ^ David Deutsch and Richard Jozsa: Rapid solutions of problems by quantum computation . (PDF) In: Proceedings of the Royal Society of London A . 439, 1992, p. 553. doi : 10.1098 / rspa.1992.0167 .
3. ^ R. Cleve, A. Ekert, C. Macchiavello and M. Mosca: Quantum algorithms revisited . (pdf) In: Proceedings of the Royal Society of London A . 454, 1998, pp. 339-354. arxiv : quant-ph / 9708016 . doi : 10.1098 / rspa.1998.0164 .
4. ^ Lov K. Grover : A fast quantum mechanical algorithm for database search . In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing . 1996, pp. 212-219. arxiv : quant-ph / 9605043 . doi : 10.1145 / 237814.237866 .
5. ↑ Peter W. Shor : Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer . (PDF) In: SIAM J. Sci. Extra Comput. . 26, 1997, p. 1484. arxiv : quant-ph / 9508027 . doi : 10.1137 / S0097539795293172 .

literature

• M. Homeister: Understanding Quantum Computing Springer Vieweg, Wiesbaden 2018, fifth edition, ISBN 978-3-6582-2883-5 , p. 62ff.
• B. Lenze: Mathematik und Quantum Computing Logos Verlag, Berlin 2020, second edition, ISBN 978-3-8325-4716-5 , p. 51ff.
• RJ Lipton, KW Regan: Quantum Algorithms via Linear Algebra: A Primer MIT Press, Cambridge MA 2014, ISBN 978-0-2620-2839-4 , pp. 77ff.
• MA Nielsen, IL Chuang: Quantum Computation and Quantum Information Cambridge University Press, Cambridge MA 2010, ISBN 978-1-1070-02173 , p. 32ff.