Some theoretically organized algorithm for quantum computers (Q2300853)

In the paper under review the authors suggest a new algorithm to treat positively the plural evaluations of some logical function in parallel instead of testing the function for finding out an attribute of it. Let \(\mathbb Z_2 =\{ 0, 1\}\) and \(N\) be a natural number. The problem is to evaluate a Boolean function \(f(x) : \mathbb Z_2^N \to \mathbb Z_2\) for different \(x\) simultaneously. The problem is well konwn in classical computing with exponential complexity. The parallel computing is outperformed by quantum computing. The authors propose a new algorithm to solve the problem by using the novel quantum parallel computing. The algorithm is to: 1) select a function \(f_i(x)\) from a list of all associated mappings, 2) make the operator \(U_{f_i}\) acting on a special state \(|\psi_0\rangle\), \(U_{f_i}: |x,y\rangle \mapsto |x,y\oplus f_i(x)\rangle\) to obtain the state \(|\psi_i\rangle\), \(i=0,1,\dots, 2^{2^N}-1\), where the symbol \(\oplus\) is used for the sum modulo 2, 3) obtain the mappings concerning \(f_i\). The result of Section 3 is then illustrated by an atom system in Section 5.