1 Introduction

Quantum computing is explained as follows [1]: —The design and theory of computer systems that depend on quantum effects for their operation. On one level, this can be the use of small components, at the atomic or molecular level, to store or process information. An example would be a storage system that used two different spin states of atoms to store bits of information, or a logic gate that depends on the movement or spin of a single electron. Systems of this type are studied in nanocomputing. At a more fundamental level, the term ‘quantum computing’ implies the use of quantum effects that have no classical analogue to process information. In a ‘classical’ computer information is held in bits, which can have two alternative values (0 and 1). In a quantum computer the 0 and 1 values are held simultaneously in a superposition state. This unit of information is called a quantum bit (or qubit). Much more information can be held in this way and, in principle, it is possible to do parallel processing of the information. Quantum computers would be much faster than conventional machines and capable of performing calculations that could not realistically be done otherwise. Ion traps, cavity QED, and spin measurements have been used in research in this area.

Articles on the history of research into quantum computing are mentioned as follows. An implementation of a quantum algorithm to solve Deutsch’s problem [2,3,4] on a nuclear magnetic resonance quantum computer is reported [5]. An implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer is reported [6]. Oliveira et al. implements Deutsch’s algorithm with polarization and transverse spatial modes of the electromagnetic field as qubits [7]. A single-photon Bell states are prepared and measured [8]. The decoherence-free implementation of Deutsch’s algorithm is introduced by using such a single-photon and by using two logical qubits [9]. A one-way based experimental implementation of Deutsch’s algorithm is reported [10].

In 1993, the Bernstein-Vazirani algorithm was published [11, 12]. By utilizing a Boolean-valued function, it is extended to determine the values of the function [13]. In 1994, Simon’s algorithm [14] and Shor’s algorithm [15] were discussed. In 1996, Grover [16] provided the motivation for exploring the computational possibilities offered by quantum mechanics. An implementation of a quantum algorithm to solve the Bernstein-Vazirani parity problem without entanglement in an ensemble quantum computer is mentioned [17]. Fiber-optics implementation of the Deutsch-Jozsa and Bernstein-Vazirani quantum algorithms with three qubits is discussed [18]. The question whether or not quantum learning is robust against noise is a subject of a study [19].

A quantum algorithm for approximating the influences of Boolean functions and its applications are studied [20]. Quantum computation with coherent spin states and the close Hadamard problem are reported [21]. Transport implementation of the Bernstein-Vazirani algorithm with ion qubits is studied [22]. Quantum Gauss-Jordan elimination and simulation of accounting principles on quantum computers are discussed [23]. The dynamical analysis of Grover’s search algorithm in arbitrarily high-dimensional search spaces is studied [24]. A method of computing many functions simultaneously by using many parallel quantum systems is reported [25]. An algorithm for fast determining a homogeneous linear function is proposed [26]. A method of calculating a multiplication by using the generalized Bernstein-Vazirani algorithm is studied [27]. A new mathematical structure for quantum algorithms in case of a special function is reported [28]. Efficient quantum algorithm for the parity problem of a certain function is given [29].

In 2015, it was discussed that the Deutsch-Jozsa algorithm can be used for quantum key distribution [30]. In 2017, it was discussed that secure quantum key distribution based on Deutsch’s algorithm using an entangled state [31]. A highly speedy secure quantum cryptography based on the Deutsch-Jozsa algorithm is proposed [32]. The relation between quantum computer and secret sharing with the use of quantum principles is discussed [33]. An application of quantum Gauss-Jordan elimination code to quantum secret sharing code is studied [34]. Designing quantum circuit by one step method and similarity with neural network are discussed [35]. Efficient quantum algorithms of finding the roots of a polynomial function are discussed [36, 37].

There are many researches concerning quantum computing, quantum algorithm, and their experiments. However, a complete understanding of a fundamental structure of quantum computing is not given. There is a meaningful motivation of looking for a condition of obtaining the success of a quantum computing experiment. Namely, it is useful for experimental investigations for judging if the experiments are success. For example, the Bernstein-Vazirani algorithm in a noisy environment is studied [22, 31] and a success probability is given. Here an all-versus-nothing theorem is investigated.

Assume a 2N qubit-quantum computing which starts with the state \(|\overbrace {0,0,...,0,1}^{N}\rangle |\overbrace {1,1,...,1}^{N}\rangle \) as follows: Uf|0,0,...,0,1〉|1,1,...,1〉 = |0,0,...,0,1〉 \(|\overline {f(0,0,...,0,1)}\rangle . \) Recently, it is shown that the relation f(x) = f(−x) is a necessary condition of holding this fundamental relation of quantum computing performed with, for example, the Deutsch-Jozsa algorithm or the Bernstein-Vazirani algorithm if we assume |− x〉 = −|x〉 [28, 29]. It is interesting to study whether the relation f(x) = f(−x) is also a sufficient condition.

In this contribution, a necessary and sufficient condition for quantum computing is proposed. Surprisingly the relation f(x) = f(−x) is the necessary and sufficient condition of holding this fundamental relation if local unitary operations can be used. A quantum algorithm (computing) experiment is success if f(x) = f(−x), otherwise the experiment is not success.

The argumentations for finding this evenness: f(x) = f(−x) of the function f(x) is assumed to a practical use in combination together with quantum error correction algorithms for qubits/qudits (or even topological anyons in topological quantum error correction). See [38] and [39]. After an error correction the problem is protected from any kinds of bit flip or spin flip actions and the argumentations work well.

The rest of the paper is organized as follows:

In Section 2, a necessary and sufficient condition for quantum computing is given. Finally, the conclusion is drawn in Section 3.

2 A Necessary and Sufficient Condition for Quantum Computing

In this section, a necessary and sufficient condition for quantum computing is proposed. Assume |− x〉 = −|x〉. This is realized as follows:

  • Prepare |− x〉.

  • Introduce the flip operator σx = |− x〉〈x| + |x〉〈−x|.

  • Notice σx|− x〉 = |x〉.

  • Operate − I to |x〉 in giving −|x〉.

Notice

  • Prepare −|x〉.

  • Introduce the flip operator σx = |− x〉〈x| + |x〉〈−x|.

  • Notice σx(−|x〉) = −|− x〉.

  • Operate − I to −|− x〉 in giving |− x〉.

Therefore, transformations |− x〉 to −|x〉 and −|x〉 to |− x〉 are realised by using local unitary operations. In the following, local unitary operations can be used in order to justify the assumption |− x〉 = −|x〉. Roughly speaking, the entire argumentations are held under the assumption that local unitary operations can be used.

Assume that the following function is given

$$\begin{array}{@{}rcl@{}} &&f:\{-(2^{N}-1),-(2^{N}-2),\ldots,2^{N}-2,2^{N}-1\}\rightarrow\\ &&\{0,1,\ldots,2^{N}-2,2^{N}-1\}. \end{array} $$
(1)

Assume that f(y) ≥ 0. Introduce a function g(x) that transforms binary strings into an integer. Define g− 1(f(g(x))) = F(x). The construction of F(x) is independent of the choice of the function g. Assume such a function F(x)(= g− 1(f(g(x)))) and such a function g indeed exist, for example to make precise, choose the function g such that for any string x = (xN,…,x0), g(x) = xN2N + … + x121 + x0. This function g is invertible and g− 1 converts the integer x = xN2N + … + x121 + x0 back to the bit-string (xN,…,x1,x0). y = g(x) is the integer representation of the binary string x. For example, x = (1,1) if y = 3. Assume that the given function f is even. Namely,

$$ F(x)=F(-x)\in \{0,1\}^{N}, $$
(2)

where x ∈{0,1}N. The condition (2) is a sufficient condition for quantum computing as shown below.

What the function f(x) does in (1) is to map a set of discrete values onto another one. In (2), assume that x is the binary representation of an integer. x will be given by a binary string belonging to the Cartesian product \(\overbrace {\{0,1\} \times \{0,1\} \times {\ldots } \times \{0,1\}}^{N}\), for instance, x = (0,1,1,0,0,1,…,1). Define − x as − (0,1,1,0,0,1,…,1).

Throughout the discussion, any normalization factors are omitted. The input state is

$$\begin{array}{@{}rcl@{}} &&|\psi_{1}\rangle=|\overbrace{0,0,\ldots,0,1}^{N}\rangle |\overbrace{1,1,\ldots,1}^{N}\rangle. \end{array} $$
(3)

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

$$\begin{array}{@{}rcl@{}} U_{F}:|x,z\rangle\rightarrow|x,z+ F(x)\rangle \end{array} $$
(4)

with

$$\begin{array}{@{}rcl@{}} U_{F}:&&|x,z\rangle\rightarrow |x,z+ F(x)\rangle\\ &\Leftrightarrow&-|x,z\rangle\rightarrow -|x,z+ F(x)\rangle\\ &\Leftrightarrow&|-x,z\rangle\rightarrow |-x,z+ F(x)\rangle\\ &\Leftrightarrow&|-x,z\rangle\rightarrow |-x,z+ F(-x)\rangle \end{array} $$
(5)

employing the fact that F(x) = F(−x). Here, z + F(x) = (z1 ⊕ F1(x),z2 ⊕ F2(x),…,zN ⊕ FN(x)) (the symbol ⊕ indicates addition modulo 2). And, \(\overline {F(x)}=(1\oplus F_{1}(x), 1\oplus F_{2}(x), \ldots , 1\oplus F_{N}(x))\). For example, F(0,0,...,0,1) = (0,1,1,0,0,1,…,1) if \(\overline {F(0,0,...,0,1)} =(1,0,0,1,1,0,\ldots ,0)\).

The state |ψ1〉 (3) can be decomposed as follows:

$$\begin{array}{@{}rcl@{}} &&|\psi_{1}\rangle=\\ &&\sum\limits_{x=-(2^{N}-1)}^{-2} |x\rangle|\overbrace{1,1,\ldots,1}^{N}\rangle + \sum\limits_{x=+ 1}^{2^{N}-1} |x\rangle|\overbrace{1,1,\ldots,1}^{N}\rangle. \end{array} $$
(6)

Start the discussion from the following

$$\begin{array}{@{}rcl@{}} &&U_{F}|\psi_{1}\rangle =|\psi_{2}\rangle\\ &&=\sum\limits_{x=-(2^{N}-1)}^{-2} |x\rangle|\overline{F(x)}\rangle +\sum\limits_{x=+ 1}^{2^{N}-1} |x\rangle|\overline{F(x)}\rangle \end{array} $$
(7)

and

$$\begin{array}{@{}rcl@{}} |\psi_{2}\rangle &=&\sum\limits_{x=-(2^{N}-1)}^{-2} |x\rangle|\overline{F(x)}\rangle +\sum\limits_{x=+ 1}^{2^{N}-1} |x\rangle|\overline{F(x)}\rangle. \end{array} $$
(8)

This implies for x →−x, with x≠ 0 to the first term;

$$\begin{array}{@{}rcl@{}} |\psi_{2}\rangle=\sum\limits_{x=+ 2}^{2^{N}-1} |-x\rangle|\overline{F(-x)}\rangle + \sum\limits_{x=+ 1}^{2^{N}-1} |x\rangle|\overline{F(x)}\rangle. \end{array} $$
(9)

Therefore, using \(\overline {F(x)}=\overline {F(-x)}\);

$$\begin{array}{@{}rcl@{}} |\psi_{2}\rangle=\sum\limits_{x=+ 2}^{2^{N}-1} |-x\rangle|\overline{F(x)}\rangle + \sum\limits_{x=+ 1}^{2^{N}-1} |x\rangle|\overline{F(x)}\rangle. \end{array} $$
(10)

Therefore, using |− x〉 = −|x〉;

$$\begin{array}{@{}rcl@{}} |\psi_{2}\rangle=-\sum\limits_{x=+ 2}^{2^{N}-1} |x\rangle|\overline{F(x)}\rangle + \sum\limits_{x=+ 1}^{2^{N}-1} |x\rangle|\overline{F(x)}\rangle. \end{array} $$
(11)

Thus, the terms except for x = 1 cancel;

$$\begin{array}{@{}rcl@{}} |\psi_{2}\rangle=|0,0,\ldots,0,1\rangle |\overline{F(0,0,\ldots,0,1)}\rangle. \end{array} $$
(12)

The following fundamental relation in quantum computing is derived.

$$\begin{array}{@{}rcl@{}} &&U_{F}|\overbrace{0,0,...,0,1}^{N}\rangle |\overbrace{1,1,...,1}^{N}\rangle\\ &&=|\overbrace{0,0,...,0,1}^{N}\rangle |\overline{F(0,0,...,0,1)}\rangle. \end{array} $$
(13)

Therefore, the relation F(x) = F(−x) is a sufficient condition for the fundamental relation (13). The relation F(x) = F(−x) is also a necessary condition for the fundamental relation (13) as shown below [28, 29].

From the definition in (5), notice

$$ U_{F}|x\rangle |\overbrace{1,1,...,1}^{N}\rangle =|x\rangle|\overline{F(x)}\rangle. $$
(14)

This implies for x →−x, with x≠ 0

$$ U_{F}|-x\rangle |\overbrace{1,1,...,1}^{N}\rangle =|-x\rangle|\overline{F(-x)}\rangle. $$
(15)

Assume |− x〉 = −|x〉. It follows that the minus sign on the left and right hand sides of (15) drops off. This implies

$$ U_{F}|x\rangle |\overbrace{1,1,...,1}^{N}\rangle =|x\rangle|\overline{F(-x)}\rangle. $$
(16)

Assume such that

$$ |P\rangle=|Q\rangle \Leftrightarrow P=Q. $$
(17)

Comparing (14) with (16), notice \(|\overline {F(x)}\rangle =|\overline {F(-x)}\rangle \). Hence, the following property of the function in order to maintain a consistency for the fundamental relation (13) cannot be avoided.

$$\begin{array}{@{}rcl@{}} \overline{F(x)}=\overline{F(-x)}. \end{array} $$
(18)

The fact that the function under study is even is derived.

$$\begin{array}{@{}rcl@{}} F(x)=F(-x). \end{array} $$
(19)

Thus the relation F(x) = F(−x) is a necessary condition for the fundamental relation (13).

It is indeed surprise to show the relation f(x) = f(−x) is the necessary and sufficient condition of holding this fundamental relation if local unitary operations can be used. Again, a quantum algorithm (computing) experiment is success if f(x) = f(−x), otherwise the experiment is not success. It is the all-versus-nothing theorem.

A quantum algorithm does not distinguish f(−x) from f(x). In other words, the minus sign does not change anything in the outcome of the quantum algorithm. This fact is due to the Galilean transformation that changes the Cartesian coordinate from x to − x. The non-relativistic quantum theory are invariant under the Galilean transformation. The all-versus-nothing theorem is explained as follows: the quantum algorithms is invariant under the Galilean transformation.

3 Conclusions

In conclusion, a necessary and sufficient condition for quantum computing has been proposed. Assume a 2N qubit-quantum computing which starts with the state \(|\overbrace {0,0,...,0,1}^{N}\rangle |\overbrace {1,1,...,1}^{N}\rangle \) as follows: Uf|0,0,...,0,1〉|1,1,...,1〉 = |0,0,...,0,1〉 \(|\overline {f(0,0,...,0,1)}\rangle . \) Surprisingly the relation f(x) = f(−x) has been the necessary and sufficient condition of holding this fundamental relation if local unitary operations can be used.