We discuss a new mathematical structure for standard quantum algorithms. It says a certain property in case of a special function f that the relation$f\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}f\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}$ holds. That is, the particular mathematical structure of the special function is that$f\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ should be even if we assume$\mathrm{<mo>|</mo>}-x\rangle \mathrm{<mo>=</mo>}-\mathrm{<mo>|</mo>}x\rangle$ .

Keywords: quantum algorithms, quantum computation

In 1985, the Deutsch–Jozsa algorithm was discussed.^1–3 In 1993, the Bernstein–Vazirani algorithm was published.^4,5 This work can be considered an extension of the Deutsch–Jozsa algorithm. In 1994, Simon’s algorithm⁶ and Shor’s algorithm⁷ were discussed. In 1996, Grover et al.⁸ provided the highest motivation for exploring the computational possibilities offered by quantum mechanics.

In this short contribution, we discuss a new mathematical structure for standard quantum algorithms. They say a certain property in case of a special function$f$ that the relation$f\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}f\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}$ holds.

We discuss a new mathematical structure for standard quantum algorithms in case of a special function$f$ . Let us suppose that we are given the following function

$f\mathrm{<mo>:</mo><mo>\{</mo>}-{\mathrm{<mo\; stretchy="false">(</mo>2}}^N-\mathrm{1<mo\; stretchy="false">)</mo>,}-{\mathrm{<mo\; stretchy="false">(</mo>2}}^N-\mathrm{2<mo\; stretchy="false">)</mo>,}\dots {\mathrm{,2}}^N-{\mathrm{2,2}}^N-\mathrm{1<mo>\}</mo>}\to \mathrm{<mo>\{</mo>0,1,}\dots {\mathrm{,2}}^N-{\mathrm{2,2}}^N-\mathrm{1<mo>\}</mo>.}$ (1)

We shall assume that$f\mathrm{<mo\; stretchy="false">(</mo>}y\mathrm{<mo\; stretchy="false">)</mo>}\ge 0$ . Let us introduce a function$g\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ that transforms binary strings into positive integers. We also define$g^{-1}\mathrm{<mo\; stretchy="false">(</mo>}f\mathrm{<mo\; stretchy="false">(</mo>}g\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ . We shall assume, for the time being, that the given function is even. Thus, we have
$\begin{array}{ll}F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\hfill & \mathrm{<mo>=</mo>}F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}\in {\mathrm{<mo>\{</mo>0,1<mo>\}</mo>}}^N\hfill \\ x\hfill & \in {\mathrm{<mo>\{</mo>0,1<mo>\}</mo>}}^N.\hfill \end{array}$    (2)

We see that the condition (2) holds in standard quantum algorithms.

What the function$f\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}$ does in (1) is to map a set of discrete values onto another one. In (2), we assume that$x$ is the binary representation of one element. $x$ will be given by a binary string belonging to the Cartesian product$\stackrel{N}{\overbrace{\mathrm{<mo>\{</mo>0,1<mo>\}</mo>}\times \mathrm{<mo>\{</mo>0,1<mo>\}</mo>}\times \dots \times \mathrm{<mo>\{</mo>0,1<mo>\}</mo>}}}$ , for instance,$x\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>0,1,1,0,0,1,}\dots \mathrm{,1<mo\; stretchy="false">)</mo>}$ . We then define$-x$  as$-\mathrm{<mo\; stretchy="false">(</mo>0,1,1,0,0,1,}\dots \mathrm{,1<mo\; stretchy="false">)</mo>}$ .

Throughout the discussion, we omit any normalization factor. Let us suppose$\mathrm{<mo>|</mo>}-x\rangle \mathrm{<mo>=</mo>}-\mathrm{<mo>|</mo>}x\rangle$ . The input state is

$\mathrm{<mo>|</mo>}{\psi }_1\rangle \mathrm{<mo>=</mo><mo>|</mo>}\stackrel{N}{\overbrace{\mathrm{0,0,}\dots \mathrm{,0,1}}}\rangle \mathrm{<mo>|</mo>}\stackrel{N}{\overbrace{\mathrm{1,1,}\dots \mathrm{,1}}}\rangle \mathrm{.}$            (3)

The function$F$ is evaluated by using the following unitary$2N$ qubits gate

$U_F\mathrm{<mo>:</mo><mo>|</mo>}x\mathrm{,}z\rangle \to \mathrm{<mo>|</mo>}x\mathrm{,}z+F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\rangle$    (4)

with

$U_F\mathrm{<mo>:</mo><mo>|</mo>}x\mathrm{,}z\rangle \to \mathrm{<mo>|</mo>}x\mathrm{,}z+F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\rangle$

$\iff -\mathrm{<mo>|</mo>}x\mathrm{,}z\rangle \to -\mathrm{<mo>|</mo>}x\mathrm{,}z+F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\rangle$

$\iff \mathrm{<mo>|</mo>}-x\mathrm{,}z\rangle \to \mathrm{<mo>|</mo>}-x\mathrm{,}z+F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}\rangle$

$\iff \mathrm{<mo>|</mo>}-x\mathrm{,}z\rangle \to \mathrm{<mo>|</mo>}-x\mathrm{,}z+F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}\rangle$                (5)

And employing the fact that$F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}$ . Here,$z+F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}{z}_1\oplus F_1\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>,}{z}_2\oplus F_2\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>,}\dots \mathrm{,}{z}_N\oplus F_N\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$ (the symbol $\oplus$ indicates addition modulo 2).

We have the following fact

$U_F\mathrm{<mo>|</mo>}\stackrel{N}{\overbrace{\mathrm{0,0,...,0,1}}}\rangle \mathrm{<mo>|</mo>}\stackrel{N}{\overbrace{\mathrm{1,1,...,1}}}\rangle \mathrm{<mo>=</mo>} \mathrm{<mo>|</mo>}\stackrel{N}{\overbrace{\mathrm{0,0,...,0,1}}}\rangle \mathrm{<mo>|</mo>}\overline{F\mathrm{<mo\; stretchy="false">(</mo>0,0,...,0,1<mo\; stretchy="false">)</mo>}}\rangle \mathrm{.}$ (6)

Here, for example, if we have$F\mathrm{<mo\; stretchy="false">(</mo>0,0,...,0,1<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>0,1,1,0,0,1,}\dots \mathrm{,1<mo\; stretchy="false">)</mo>}$ , then$\overline{F\mathrm{<mo\; stretchy="false">(</mo>0,0,...,0,1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>1,0,0,1,1,0,}\dots \mathrm{,0<mo\; stretchy="false">)</mo>}$ . Surprisingly the relation $F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}$  is necessary for the fundamental relation (6) as shown below. From the definition in (5), we have

$U_F\mathrm{<mo>|</mo>}x\rangle \mathrm{<mo>|</mo>}\stackrel{N}{\overbrace{\mathrm{1,1,...,1}}}\rangle \mathrm{<mo>=</mo><mo>|</mo>}x\rangle \mathrm{<mo>|</mo>}\overline{F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}}\rangle \mathrm{.}$            (7)

 This implies for$x\to -x$ , wit $x\ne 0$

$U_F\mathrm{<mo>|</mo>}-x\rangle \mathrm{<mo>|</mo>}\stackrel{N}{\overbrace{\mathrm{1,1,...,1}}}\rangle \mathrm{<mo>=</mo><mo>|</mo>}-x\rangle \mathrm{<mo>|</mo>}\overline{F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}}\rangle \mathrm{.}$    (8)

We state that$\mathrm{<mo>|</mo>}-x\rangle \mathrm{<mo>=</mo>}-\mathrm{<mo>|</mo>}x\rangle$ . Then it follows that the minus sign on left and right hand side of (8) drop off. This implies

$U_F\mathrm{<mo>|</mo>}x\rangle \mathrm{<mo>|</mo>}\stackrel{N}{\overbrace{\mathrm{1,1,...,1}}}\rangle \mathrm{<mo>=</mo><mo>|</mo>}x\rangle \mathrm{<mo>|</mo>}\overline{F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}}\rangle \mathrm{.}$          (9)

We furthermore assume such that

$\mathrm{<mo>|</mo>}P\rangle \mathrm{<mo>=</mo><mo>|</mo>}Q\rangle \iff P\mathrm{<mo>=</mo>}Q\mathrm{.}$             (10)

Comparing (7) with (9) we see$\mathrm{<mo>|</mo>}\overline{F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}}\rangle \mathrm{<mo>=</mo><mo>|</mo>}\overline{F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}}\rangle$ . Hence, we cannot avoid the following property of the function in order to maintain consistency for the fundamental relation (6)

$\overline{F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}\overline{F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{.}$      (11)

That is, the function under study is even

$F\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}F\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>.}$      (12)

In conclusion, we have discussed a new mathematical structure for standard quantum algorithms. They have said a certain property in case of a special function$f$ that the relation$f\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}f\mathrm{<mo\; stretchy="false">(</mo>}-x\mathrm{<mo\; stretchy="false">)</mo>}$ holds.

We thank Professor Han Geurdes for valuable discussions.

Authors declare there is no conflict of interest.

1. Deutsch D. Quantum theory, the Church–Turing principle and the universal quantum computer. Proceedings of the Royal Society A: Mathematical and Physical Sciences. 1985;400(1818):1–182.
2. Deutsch D, Jozsa R. Rapid solution of problems by quantum computation. Proceedings of the Royal Society A: Mathematical and Physical Sciences. 1992;439(1907):441–700.
3. Cleve R, Ekert A, Macchiavello C, et al. Quantum algorithms revisited. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 1998;454(1969).
4. Bernstein E, Vazirani U. Quantum complexity theory. Proceedings of the Twenty–Fifth Annual ACM Symposium on Theory of Computing (STOC ’93). 1993;26:11–20.
5. Bernstein E, Vazirani U. SIAM Journal on Computing. 1997;26(5):1411–1473.
6. Simon DR. On the Power of Quantum Computation. Proceedings of 35th Annual Symposium on Foundations of Computer Science. 1994;20(22):116–123.
7. Shor PW. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th IEEE Symposium on Foundations of Computer Science. 1994;124.
8. Grover LK. A fast quantum mechanical algorithm for database search. Proceedings of the Twenty–Eighth Annual ACM Symposium on Theory of Computing. 1996;212–219.