Method of performing the superposition operation of a Grover's or a Deutsch-Jozsa's quantum algorithm and a relative quantum gate

[0001] The present invention relates to quantum algorithms, and in particular, to a method of superpositioning a Grover's or a Deutsch-Jozsa's quantum algorithm and a relative hardware quantum gate.

[0002] Quantum algorithms are global random searching algorithms based on quantum mechanics, laws, and quantum effects. They are used for controlling a process or for processing data in a database, and more specifically, to control a process and/or including search-of-minima intelligent operations.

[0003] In a quantum search algorithm, each design variable is represented by a finite linear superposition of classical initial states with a sequence of elementary unitary steps manipulating the initial quantum state |i> (for the input) such that a measurement of the final state of the system yields the correct output. Usually, three principle operators, i.e., linear superposition (coherent states), entanglement and interference are used in the quantum search algorithm.

[0004] For a better comprehension on the field of application of the present invention, a brief description of quantum search algorithms is provided below.

Overview on Quantum Algorithms

[0005] The problems solved by quantum algorithms may be stated as follows:

[0006] $\begin{array}{cc}\mathrm{Input}& A\mathrm{function}f\text{:}{\left\{0,1\right\}}^n\to {\left\{0,1\right\}}^m\\ \mathrm{Problem}& \mathrm{Find}a\mathrm{certain}\mathrm{property}\mathrm{of}f.\end{array}\hspace{1em}$

[0007] The structure of a quantum algorithm is outlined by a high level representation in the schematic diagram of FIG. 1. The input of a quantum algorithm is a function f from binary strings into binary strings. This function is represented as a map table, defining for every string its image. The function f is first encoded into a unitary matrix operator U_F depending on f properties. This operator calculates f when its input and output strings are encoded into canonical basis vectors of a Complex Hilbert Space: U_F maps the vector code of every string into the vector code of its image by f.

[0008] $\begin{array}{c}\begin{array}{c}\begin{array}{c}\mathrm{BOX}1\text{:}\mathrm{UNITARY}\mathrm{MATRIX}{U}_F\\ \\ A\mathrm{squared}\mathrm{matrix}{U}_F\mathrm{on}\mathrm{the}\mathrm{complex}\mathrm{field}\mathrm{is}\mathrm{unitary}\mathrm{if}\mathrm{its}\end{array}\\ \mathrm{inverse}\mathrm{matrix}\mathrm{coincides}\mathrm{with}\mathrm{its}\mathrm{conjugate}\mathrm{transpose}\text{:}\end{array}\\ U_F^{-1}=U_F^t\\ A\mathrm{unitary}\mathrm{matrix}\mathrm{is}\mathrm{always}\mathrm{reversible}\mathrm{and}\mathrm{preserves}\mathrm{the}\mathrm{norm}\\ \mathrm{of}\mathrm{vectors}.\end{array}$

[0009] When the matrix operator U_F has been generated, it is embedded into a quantum gate G, which is a unitary matrix whose structure depends on the form of matrix U_F and on the problem we want to solve. The quantum gate is the heart of a quantum algorithm. In every quantum algorithm, the quantum gate acts on an initial canonical basis vector (the same vector can always be chosen) to generate a complex linear combination (i.e., a superposition) of basis vectors as the output. This superposition contains all the information to answer the initial problem.

[0010] After the superposition has been created, a measurement takes place to extract this information. In quantum mechanics, the measurement is a non-deterministic operation that produces as output only one of the basis vectors in the entering superposition. The probability of every basis vector being the measurement output depends on its complex coefficient (probability amplitude) in the entering complex linear combination.

[0011] The segmental action of the quantum gate and of the measurement forms the quantum block. The quantum block is repeated k times to produce a collection of k basis vectors. Since the measurement is a non-deterministic operation, these basic vectors will not be necessarily identical and each one of them will encode a piece of the information needed to solve the problem.

[0012] The last part of the algorithm includes the interpretation of the collected basis vectors in order to get the right answer for the initial problem with a certain probability.

Encoder

[0013] The behavior of the encoder block is described in the detailed schematic diagram of FIG. 2. The function f is encoded into matrix U_F in three steps.

Step 1

[0014] The map table of the function f: {0,1}ⁿ→{0,1}^m is transformed into the map table of the injective function F: {0,1}^n+m→{0,1}^n+m such that:
F(x₀, . . . , x_n−1, y₀, . . . , y_m−1)=(x₀, . . . , x_{n−1, f}(x₀, . . . , x_n−1)⊕(y₀, . . . , y_m−1))  (2)

[0015] The need to deal with an injective function comes from the requirement that U_F is unitary. A unitary operator is reversible, so it can not map 2 different inputs in the same output. Since U_F will be the matrix representation of F, F is supposed to be injective. If we directly used the matrix representation of the function f, we could obtain a non-unitary matrix since f could be non-injective. Injectivity is thus fulfilled by increasing the number of bits and considering the function F instead of the function f. The function f can always be calculated from F by putting (y₀, . . . , y_m−1)=(0, . . . , 0) in the input string and reading the last m values of the output string.

[0016] $\begin{array}{c}\begin{array}{c}\begin{array}{c}\begin{array}{c}\begin{array}{c}\begin{array}{c}\mathrm{BOX}2\text{:}\mathrm{XOR}\mathrm{OPERATOR}\oplus \\ \\ \mathrm{The}\mathrm{XOR}\mathrm{operator}\mathrm{between}\mathrm{two}\mathrm{binary}\mathrm{strings}p\mathrm{and}q\mathrm{of}\end{array}\\ \mathrm{length}m\mathrm{is}a\mathrm{string}s\mathrm{of}\mathrm{length}m\mathrm{such}\mathrm{that}\mathrm{the}i\text{-}\mathrm{th}\mathrm{digit}\mathrm{of}\end{array}\\ s\mathrm{is}\mathrm{calculated}\mathrm{as}\mathrm{the}\mathrm{exclusive}\mathrm{OR}\mathrm{between}\mathrm{the}i\text{-}\mathrm{th}\mathrm{digits}\mathrm{of}\end{array}\\ p\mathrm{and}q\text{:}\end{array}\\ p=\left(p_0,\dots ,p_{n-1}\right)\end{array}\\ q=\left(q_0,\dots ,q_{n-1}\right)\\ s=p\oplus q=\left(\left(p_0+q_0\right)\mathrm{mod}2,\dots ,\left(p_{n-1}+q_{n-1}\right)\mathrm{mod}2\right))\end{array}$
Step 2

[0017] The function F map table is transformed into a U_F map table based upon the following constraint:
∀sε{0,1}^n+m: U_F[τ(s)]=τ[F(s)]  (3)
The code map τ: {0,1}^n+m→c^2n+m(c^2n+m is the target Complex Hilbert Space) is such that:

[0018] $\tau \left(0\right)=\left(\begin{array}{c}1\\ 0\end{array}\right)=0\rangle \tau \left(1\right)=\left(\begin{array}{c}0\\ 1\end{array}\right)=1\rangle$ $\tau \left(x_0,\dots ,x_{n+m-1}\right)=\tau \left(x_0\right)\otimes \dots \otimes \tau \left(x_{n+m-1}\right)=x_0\dots x_{n+m-1}\rangle$
Code τ maps bit values into complex vectors of dimension 2 belonging to the canonical basis of C². Besides, using tensor product, τ maps the general state of a binary string of dimension n into a vector of dimension 2ⁿ. This reduces this state to the joint state of the n bits composing the register. Every bit state is transformed into the corresponding 2-dimesional basis vector, and then the string state is mapped into the corresponding 2ⁿ-dimesional basis vector by composing all bit-vectors through tensor products. In this sense a tensor product is the vector counterpart of state conjunction.

[0019] $\begin{array}{c}\begin{array}{c}\begin{array}{c}\mathrm{BOX}3\text{:}\mathrm{VECTOR}\mathrm{TENSOR}\mathrm{PRODUCT}\otimes \\ \end{array}\\ \mathrm{The}\mathrm{tensor}\mathrm{product}\mathrm{between}\mathrm{two}\mathrm{vectors}\mathrm{of}\mathrm{dimensions}h\mathrm{and}k\end{array}\\ \mathrm{is}a\mathrm{tensor}\mathrm{product}\mathrm{of}\mathrm{dimension}h·k,\mathrm{such}\mathrm{that}\text{:}\end{array}$ $x\rangle \otimes y\rangle =\left(\begin{array}{c}{x}_1\\ \dots \\ x_h\end{array}\right)\otimes \left(\begin{array}{c}{y}_1\\ \dots \\ y_k\end{array}\right)=\left(\begin{array}{c}{x}_1{y}_1\\ \dots \\ x_1{y}_k\\ \dots \\ x_h{y}_1\\ \dots \\ x_h{y}_k\end{array}\right)\Rightarrow \begin{array}{c}\underset{\_}{\mathrm{Physical}\mathrm{interpretation}}\text{:}\\ \mathrm{If}a\mathrm{component}\mathrm{of}a\mathrm{complex}\mathrm{vector}\mathrm{is}\\ \mathrm{interpreted}\mathrm{as}\mathrm{the}\mathrm{probability}\mathrm{amplitude}\\ \mathrm{of}a\mathrm{system}\mathrm{being}\mathrm{in}a\mathrm{given}\mathrm{state}\\ \left(\mathrm{indexed}\mathrm{by}\mathrm{the}\mathrm{component}\mathrm{number}\right),\mathrm{the}\\ \mathrm{tensor}\mathrm{product}\mathrm{between}\mathrm{two}\mathrm{vectors}\\ \mathrm{describes}\mathrm{the}\mathrm{joint}\mathrm{probability}\\ \mathrm{amplitude}\mathrm{of}\mathrm{two}\mathrm{systems}\mathrm{being}\mathrm{in}a\\ \mathrm{joint}\mathrm{state}.\end{array}$

[0020] $\begin{array}{c}\begin{array}{cc}\left(0,0\right)\stackrel{\tau }{\to }\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right)=00\rangle & \left(0,1\right)\stackrel{\tau }{\to }\left(\begin{array}{c}1\\ 0\end{array}\right)\otimes \left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right)=01\rangle \\ \left(1,0\right)\stackrel{\tau }{\to }\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}1\\ 0\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right)=10\rangle & \left(1,1\right)\stackrel{\tau }{\to }\left(\begin{array}{c}0\\ 1\end{array}\right)\otimes \left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right)=11\rangle \end{array}\end{array}$

[0021] Basis vectors are denoted using the ket notation |i>. This notation is taken from the Dirac description of quantum mechanics.

Step 3

[0022] The U_F map table is transformed into U_F using the following transformation rule:
[U_F]_ij=1U_F|j>=|i>  (4)
This rule can easily be understood considering vectors |i> and |j> are column vectors. Since these vectors belong to the canonical basis, U_F defines a permutation map of the identity matrix rows. In general, row |i> is mapped into row |i>.

[0023] This rule will be illustrated in detail on the first example of a quantum algorithm, such as Grover's algorithm.

Quantum Block

[0024] The heart of the quantum block is the quantum gate, which depends on the properties of the matrix U_F. The scheme in FIG. 3 gives a more detailed description of the quantum block. The matrix operator U_F in FIG. 3 is the output of the encoder block represented in FIG. 2. Here, it becomes the input for the quantum block.

[0025] This matrix operator is first embedded into a more complex gate: the quantum gate G. The unitary matrix is applied k times to an initial canonical basis vector |i> of dimension 2^n+m. Every time, the resulting complex superposition G|0 . . 01 . . . 1> of basis vectors is measured, and one basis vector |x_i> is produced as a result. All the measured basis vectors {|x₁>, . . . , |x_k>} are collected together. This collection is the output of the quantum block.

[0026] The intelligence of such algorithms is in the ability to build a quantum gate that is able to extract the information necessary to find the required property of f, and to store it into the output vector collection. The structure of the quantum gate for every quantum algorithm will be discussed in detail, observing that a general description is possible. To represent quantum gates we are going to employ some special diagrams called quantum circuits.

[0027] An example of a quantum circuit, relative to the so called Deutsch-Jozsa's quantum algorithm, is illustrated in FIG. 4. Every rectangle is associated to a matrix 2ⁿ×2ⁿ, where n is the number of lines entering and leaving the rectangle. For example, the rectangle marked U_F is associated to matrix U_F.

[0028] Quantum circuits let us provide a high level description of the gate, and using some transformation rules which are listed in FIGS. 5A–5F, it is possible to compile them into the corresponding gate matrix.

[0029] It will be clearer how to use these rules when we discuss the first examples of a quantum algorithm.

[0030] $\begin{array}{c}\begin{array}{c}\underset{\_}{\mathrm{BOX}4\text{: }\mathrm{MATRIX}\mathrm{TENSOR}\mathrm{PRODUCT}\otimes }\end{array}\\ \begin{array}{c}\mathrm{The}\mathrm{tensor}\mathrm{product}\mathrm{between}\mathrm{two}\mathrm{matrices}{X}_{n\times m}\mathrm{and}{Y}_{h\times k}\mathrm{is}a\left(\mathrm{block}\right)\\ \mathrm{matrix}\left(n·h\right)\times \left(m·k\right)\mathrm{such}\mathrm{that}\text{:}\end{array}\\ X\otimes Y=\left[\begin{array}{ccc}{x}_{11}Y& \cdots & x_{1m}Y\\ \cdots & \cdots & \cdots \\ x_{\mathrm{n1}}Y& \cdots & x_{nm}Y\end{array}\right]\mathrm{with}X=\left[\begin{array}{ccc}{x}_{11}& \cdots & x_{1m}\\ \cdots & \cdots & \cdots \\ x_{\mathrm{n1}}& \cdots & x_{nm}\end{array}\right]\end{array}$

[0031] $\begin{array}{c}\left[\begin{array}{cc}1& 2\\ 3& 4\end{array}\right]\otimes \left[\begin{array}{cc}5& 6\\ 7& 8\end{array}\right]=\left[\begin{array}{cc}1·\left[\begin{array}{cc}5& 6\\ 7& 8\end{array}\right]& 2·\left[\begin{array}{cc}5& 6\\ 7& 8\end{array}\right]\\ 3·\left[\begin{array}{cc}5& 6\\ 7& 8\end{array}\right]& 4·\left[\begin{array}{cc}5& 6\\ 7& 8\end{array}\right]\end{array}\right]\\ =\left[\begin{array}{cccc}5& 6& 10& 12\\ 7& 8& 14& 16\\ 15& 18& 20& 24\\ 21& 24& 28& 32\end{array}\right]\end{array}$
Decoder

[0032] The decoder block has the function to interpret the basis vectors collected after the iterated execution of the quantum block. Decoding these vectors means to retranslate them into binary strings and interpreting them directly if they already contain the answer to the starting problem or use them, for instance, as coefficient vectors for some equation system in order to get the searched solution. This part will not be discussed in detail because it is well known by those skilled in the art.

[0033] Because of the particular importance of the Grover's quantum algorithm in the realization of controllers, a brief description of the Grover's algorithm is given below.

Grover's Problem

[0034] Grover's problem is stated as follows:

[0035] $\begin{array}{cc}\mathrm{Input}& \begin{array}{c}A\mathrm{function}f\text{:}{\left\{0,1\right\}}^n\to \left\{0,1\right\}\mathrm{such}\mathrm{that}\\ \exists x\in {\left\{0,1\right\}}^n\text{:}f\left(x\right)=1\bigwedge \forall y\in {\left\{0,1\right\}}^n\text{:}x\ne y\Rightarrow f\left(y\right)=0)\end{array}\\ \mathrm{Problem}& \mathrm{Find}x\end{array}\hspace{1em}$

[0036] In Deutsch-Jozsa's algorithm there are two classes of input functions, and it must be determined what class the input function belongs to. In this case the problem is in some sense identical in its form, even if it is harder because now we are dealing with 2ⁿ classes of input functions. Each function of the kind described forms a class.

[0037] The diagram of the Grover's algorithm is depicted in FIG. 6, and the gate equation is
G=[(D_nI)·U_F]^h·(ⁿ⁺¹H)
Operator D_n is called the diffusion matrix of order n and it is responsible for interference in this algorithm. This matrix is defined as follows:

[0038] $\begin{array}{cccccccc}{D}_n& 0.\mathrm{.0}>& 0.\mathrm{.1}>& \dots & i>& \dots & 1.\mathrm{.0}>& 1.\mathrm{.1}>\\ 0.\mathrm{.0}>& -1+1/2^{n-1}& 1/2^{n-1}& \dots & 1/2^{n-1}& \dots & 1/2^{n-1}& 1/2^{n-1}\\ 0.\mathrm{.1}>& 1/2^{n-1}& -1+1/2^{n-1}& \dots & 1/2^{n-1}& \dots & 1/2^{n-1}& 1/2^{n-1}\\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ i>& 1/2^{n-1}& 1/2^{n-1}& \dots & -1+1/2^{n-1}& \dots & 1/2^{n-1}& 1/2^{n-1}\\ \dots & \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ 1.\mathrm{.0}>& 1/2^{n-1}& 1/2^{n-1}& \dots & 1/2^{n-1}& \dots & -1+1/2^{n-1}& 1/2^{n-1}\\ 1.\mathrm{.1}>& 1/2^{n-1}& 1/2^{n-1}& \dots & 1/2^{n-1}& \dots & 1/2^{n-1}& -1+1/2^{n-1}\end{array}$

[0039] Grover's algorithm may be implemented in routines for searching a desired item in a set, by representing in vector form each item of the set forming an input set of vectors, and applying the Grover's algorithm to this set of vectors. The output vector represents the desired item.

[0040] The implementation of a Grover's algorithm clearly implies the calculation of several vector products. In fact, all qubits must be multiplied for matrix H, must be subjected to the entanglement operator U_F and all qubits but the latter must be multiplied for matrix D_n.

[0041] A similar problem is present for implementing the well known Deutsch-Jozsa's quantum algorithm that is used in decision making algorithms. As it may be inferred from FIG. 4, which represent the quantum circuit of the Deutsch-Jozsa's algorithm, the gate equation is
G=(ⁿHI)·U_F·(ⁿ⁺¹H)
Even if the Deutsch-Jozsa's algorithm implies a smaller number of calculations than the Grover's algorithm, its running result will be burdensome when the number n is relatively large.

[0042] Actually, these calculations are carried out by software routines, but such routines run slowly because of the large number of multiplications to be performed. For this reason, routines based on a Grover's or a Deutsch-Jozsa's algorithm need a long time to produce their output.

[0043] In view of the foregoing background, an object of the present invention to provide a quantum gate for carrying out the superposition operation of a Grover's or of a Deutsch-Jozsa's quantum algorithm. The quantum gate of the invention carries out the superposition operation in a very fast manner because it performs all multiplications by using logic gates that immediately output the result.

[0044] The superposition operation of a Grover's and of a Deutsch-Jozsa's quantum algorithm substantially includes performing the Hadamard rotation over an input set of vectors producing a set of rotated vectors, and calculating the tensor product of all the rotated vectors among them outputting a linear superposition set of vectors. The tensor product of all rotated vectors among them may be carried out by logic gates.

[0045] It has been noticed that, only for Grover's or Deutsch-Jozsa's algorithms, the components of each rotated vector may be only 1 and −1 multiplied by a scale factor. In fact, the output vectors Q of Grover's and Deutsch-Jozsa's quantum gates are given by
Q=[(D_nI)·U_F]^h·Y
and
Q=(ⁿHI)·U_F·Y
respectively, where the tensor product vector Y representing the linear superposition set of vectors is given by the following:
Y=└y₁, y₂ . . . y_j . . . y_2n+1┘
y₁=(−1)^j+1/2^(n+1)/2
Neglecting the scale factor ½^(n+1)/2, the vector Y calculated by performing a superposition operation is formed only by two different values, thus suggesting that there could be a way for performing the multiplications by logic gates.

[0046] The method according to the invention performs the superposition operation of a Grover's or of a Deutsch-Jozsa's quantum algorithm over an input set of vectors by carrying out a Hadamard rotation of each vector of the input set producing a corresponding rotated vector. The tensor product of the rotated vectors among them is also performed by: performing the tensor product of the rotated vectors among them by encoding the component of each rotated vector with a low logic value if negative and with a high logic value if positive; ANDing all possible different pairs of components of distinct vectors producing an encoded matrix of logic components; decoding the components of the encoded matrix producing a numeric matrix; and multiplying the numeric matrix by a scale factor producing a scaled numeric matrix whose columns form the linear superposition set of vectors.

[0047] According to a preferred embodiment, the method of the invention comprises calculating a rotated vector by carrying out a dot product between a Hadamard matrix and a vector of the input set by: encoding each component of an input vector with a low logic value if null and a high logic value if non null; encoding all components of the Hadamard matrix with a high logic value; ANDing components of an input vector with corresponding components of a first and second row of the Hadamard matrix, producing first and second pairs of logic values, respectively; decoding all values of the logic sets producing two corresponding sets of numeric values; and summing the values of the first numeric pair and subtracting a second value from a first value of the second numeric pair for respectfully producing a first and a second component of a rotated vector.

[0064] The quantum gate of the invention is suitable for fast running decision making or data searching routines, based on the Deutsch-Jozsa's quantum algorithm or on the Grover's quantum algorithm applied over a set of input vectors. The quantum gate is composed of a superposition subsystem carrying out a linear superposition, an entanglement subsystem carrying out an entanglement operation and an interference subsystem carrying out an interference operation according to the Grover's or the Deutsch-Jozsa's quantum algorithm.

[0065] An essential characteristic of the quantum gate of the invention includes the fact that the superposition subsystem comprises logic gates for carrying out multiplications. The use of logic gates is particularly effective because of their speed in outputting a result. For this reason, the quantum gate of the invention may be conveniently used for running decision making algorithms or searching routines in a large database in a very fast manner.

[0066] For better illustrating the features of the invention, an embodiment of a quantum gate of the invention will be described for the case in which the superposition block is to carry out only the operations H|0> and H|1>. H is the Hadamard rotation matrix and |0> and |1> are the input vectors, and the tensor product of the rotated vectors are among them. Neglecting the constant factor ½^0.5 of each input vector, the superposition subsystem calculates the following expression:

[0067] $\begin{array}{cc}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\otimes \left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\otimes \left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\left[\begin{array}{c}0\\ 1\end{array}\right]& \left(5\right)\end{array}$
The dot product between the Hadamard matrix and each input vector can be performed via AND gates. In fact,
1*1=1^1=1; −1*1=−(1^1)=−1; 1*0=(1^0)=0
According to a preferred embodiment of the invention, the quantity H|0> may be calculated and obtained by the dot product gate depicted in FIG. 7a. Similarly, H|1> may be calculated using another dot product gate, as depicted in FIG. 7b. Such dot product gates are composed of two pairs of AND gates connected to a respective adder. Each pair of AND gates outputs the products between the components of an input vector and the components of a respective row of the Hadamard matrix. How a dot gate works is relatively straightforward by looking at FIGS. 7a and 7b.

[0068] Should the superposition block be input with a string of n+1 qubits, 4(n+1) AND gates and 2(n+1) adders would be necessary for calculating all dot products. Optionally but less conveniently, such dot products may also be performed by a software routine. In fact, the number of multiplications to be carried out for performing all dot products increases linearly with n, thus all dot products may be performed in a relatively fast manner even if n is large.

[0069] On the contrary, the number of multiplications involved by all tensor products increases exponentially with n. Therefore, it is clear that the most burdensome operation for performing a linear superposition is the tensor product of all the rotated vectors among them. The quantum gate excellently solves such a problem, as will now be described below.

[0070] Carrying out all the dot products, expression (5) becomes

[0071] $\begin{array}{cc}\left[\begin{array}{c}1\\ 1\end{array}\right]\otimes \left[\begin{array}{c}1\\ 1\end{array}\right]\otimes \left[\begin{array}{c}1\\ -1\end{array}\right]={\left[\begin{array}{cccccccc}1& -1& 1& -1& 1& -1& 1& -1\end{array}\right]}^T& \left(6\right)\end{array}$
The result of the tensor product is formed only by 1 and −1, and thus there is the possibility of using logic gates for performing all tensor products. According to the method of the invention, each component is encoded with a high logic value 1 if positive or with a low logic value 0 if negative. The problem is thus to calculate the following tensor product:

[0072] $\begin{array}{cc}\left[\begin{array}{c}1\\ 1\end{array}\right]\otimes \left[\begin{array}{c}1\\ 1\end{array}\right]\otimes \left[\begin{array}{c}1\\ 0\end{array}\right]& \left(7\right)\end{array}$

[0073] Expression (7) may be calculated by performing the rightmost tensor product, after calculating the second tensor product:

[0074] $\begin{array}{cc}\left[\begin{array}{c}1\\ 1\end{array}\right]\otimes \left(\left[\begin{array}{c}1\\ 1\end{array}\right]\otimes \left[\begin{array}{c}1\\ 0\end{array}\right]\right)& \left(8\right)\end{array}$

[0075] According to an embodiment of the quantum gate of the invention, the tensor product in parenthesis may be performed by the elementary tensor product gate depicted in FIG. 8a. The tensor product may be easily carried out by ANDing paired logic components of the two logic vectors inputting the tensor gate.

[0076] The second tensor product is performed by the tensor gate of FIG. 8b. It differs from the similar elementary tensor gate of FIG. 8a in that it has twice the number of inputs of the elementary gate. The tensor gate of FIG. 8b may be easily obtained by paralleling two elementary tensor gates. It receives an input with the logic components of the leftmost vector of expression (8) and the output of the elementary gate of FIG. 8a. A superposition subsystem of quantum gates of the invention for carrying out the tensor product (7) may be obtained simply by connecting the tensor gate of FIG. 8b in cascade to the gate of FIG. 8a.

[0077] It is evident that a quantum gate of the invention carrying out n+1 tensor products will be provided by a superposition subsystem comprising a cascade of n+1 tensor gates. The first tensor gate is an elementary gate, and all the remaining tensor gates of the cascade are formed by a number of elementary gates that is double the number of elementary gates of the preceding tensor gate in the cascade. Each tensor gate of the cascade may be easily obtained by paralleling an appropriate number of elementary tensor gates, as depicted in the example of FIG. 8b.

[0078] Therefore, the superposition subsystem of the quantum gate of the invention has a modular architecture, that is, the number of qubits may be increased at any time by simply adding other tensor gates in cascade to the latter.

[0079] The components output by the last tensor gate in the cascade are decoded by associating the value −1 to the low logic value and the value 1 to the high logic value. The resulting vector is finally multiplied for a scale factor before being subjected to the Entaglement operation. For the considered example, the scale factor of the resulting vector is the product of the three constant factors of each input vector:

[0080] $\frac{1}{\sqrt{2}}·\frac{1}{\sqrt{2}}·\frac{1}{\sqrt{2}}=\frac{1}{2\sqrt{2}}$
thus the vector output by the superposition subsystem is

[0081] ${\left[\frac{1}{2\sqrt{2}}-\frac{1}{2\sqrt{2}}\frac{1}{2\sqrt{2}}-\frac{1}{2\sqrt{2}}\frac{1}{2\sqrt{2}}-\frac{1}{2\sqrt{2}}\frac{1}{2\sqrt{2}}-\frac{1}{2\sqrt{2}}\right]}^T$
Alternatively, the multiplication of the resulting vector by the scale factor may be carried out preliminarily by the entanglement subsystem.

[0082] A detailed PSPICE diagram of an embodiment of the superposition subsystem of a quantum gate of the invention, carrying out expression (5), is depicted in FIG. 9.