1. Introduction
The quantum computation is essentially mastering and using the quantum mechanics laws for information processing. The quantum computers use quantum bits which are called qubits. Both states of the qubits 0 and 1 manifest simultaneously and connectedly superposition and entanglement. For the microqubits we can use only the Schrodinger and Heisenberg equations. The entangled states of groups of quantum particles are the key to understanding the implementation of the super huge set of quantum states which are implemented in the quantum processors. The superposition is essentially the ability of the quantum system to be in several states simultaneously. This study examines the inherent power of the entangled cluster states that are used in the quantum computations model by measurement in an “one-way” or measurement based quantum computer (MBQC) with a register initialized in a multi-partite entangled state. Instead through gates, MBQC processes the information by single-qubit measurements, the results of which determine the selection of the subsequent measurements. The arrangement and the selection itself of the measurements determine the algorithm, which is computed. Due to the decisive role of the measurements, the MBQC is irreversible and it placed the beginning of a new way of measurement-based quantum information processing. Through the determination of a common framework of the importance of the computing power of the entangled cluster states, they are presented more accurately. For the conduct of this study double entanglements of Bell and triple entanglements of Greenberger-Horne-Zeilinger (GHZ) are used; it presents the relations between the breach of the realistic models that are local and the computing power of the output entangled states.
In the following sections it will be shown that the entangled cluster states used in measurement-based quantum computations (MBQC) possess remarkable computational power. MBQC is a method for computations, distinctly different from the model of the conventional quantum circuit, where the logical operators of the network processed the information. Unlike it in the standard one-way MBQC model a series of adaptive single-qubit measurements on a multi-qubit output state that is entangled process the information. It is typical for this model that the computational power is determined by entangled classical resources obtained as a result of the measurement and not by the quantum computations themselves. In order to derive this computing power it is necessary to use a classical computer for control, which performs processing and feeding of the preliminary measurement of the outputs and directs the prospective adaptive measurements. From this point of view using this computational model, through the results of the entangled cluster measurement the classical computer achieves considerable exceedance of its own computational capabilities.
2. Cluster of Controlled Computational Operators
2.1. Incrementation
The controlled cluster increment operator increases a value into an additional code, computated by a group of lines [1] - [3] . Implementing an increment gate out of NOT gates is easy, if you’re allowed to have arbitrarily large numbers of controls. The increment only propagates the qubits until it run across an 0 bit, see Figure 1.
At first glance the easiest thing is to apply the construction with large controlled cluster NOT-s [4] . Unfortunately, since this construction requires O(n) operators per each controlled cluster NOT, in the end a quadratic number of operators is needed (because
).
2.2. Single Ancilla Bit
If there is a circuit with n + 1 lines with n incrementing lines and one ancilla line, the goal is the incrementation to be broken up into smaller operations. In this section is not necessary to get all the way to the operators of Toffoli. Instead, the dimension of the implementation simply has to be reduced.
The bottom lines, depending from n/2 top lines, can be avoided, by caching the crossing of these lines in the ancilla bit. In this way the bottom incrementation needs only one control, see Figure 2.
![]()
Figure 1. Circuit using less than O(n) NOT-s.
The controlled cluster increment operator is equipollent to an increment operator with a control line as the new inferior bit. Such an absorbing control is a matter of subsequent switching of the former control line, see Figure 3:
It should be noted that the intent control bit is treated as the slightly bit, though the intented line is in “wrong” position.
The last case with a single ancilla bit is the case with the adopted bit, see Figure 4. This time the solution is much more complicated.
The trick here is to use a bit-wise addition. When the bits of a number in an additional code X are switched, they toggle from storing of X to storing of 
If the complemented value is incremented, after which the complement is taken again, then finally is obtained 
In other words, the surrounding of an increment operator with NOT-s turns it into a decrementing! (and vice versa.)
3. Classification of the Computing Power of the with Entangled Cluster States
In the following sections of this report we will give a more precise definition for the
![]()
Figure 4. Split incrementer from reset to zero bit.
computational power of the correlated sources, we will discuss the natural classical analogue of the measurement-based computation in the context of the quantum non-locality. We will point out that the double and triple qubit entanglements of Bell and Greenberger-Horne-Zeilinger (GHZ) [5] - [7] may be used in a classical computation based on measurement (CCBM).
Framework of MBQC―In this study the computing power of the correlated sources is examined in a more common framework from those of the specific MBQC models [8] - [11] . For this purpose, by both main structural components we will first define the general framework of the computational model: a correlated multi-qubit cluster and a classical computer for control. The correlated multi-qubit cluster consists of numerous entangled qubits, which performs exchanging of classical information with the computer for control, see Figure 5. The entangled cluster states in their results are initialized at the beginning of the process, then no direct communication between the qubits is permitted during the computation. There will be only one exchange of data with each qubit.
The computer for control can preserve classical information, to perform exchanging of the information with it with the qubits and to compute some functions. The only
![]()
Figure 5. The computer for control makes available classical input data to each of the interconnected qubits and obtains one of the results as the output data.
part of the described model, where the active computation occurs is the classical computer for control. Before the start of the computation is necessary the components of the system to be pre-programmed in order to specify what computation will be performed. The classical computer obtains the functions that it will assess and the separate operators will obtain a certain set of bases for measurement on the basis of which shall be carried out the computations.
This model is comprised only of classical objects-all quantum characteristics are hidden in the non-classical quantum nature of the entangled cluster states. The system uses the most common single classical system model that operates with the entangled cluster states subject to the non-communicational limitation that each particle is processed only once. But the inner cluster structure functions with minimum restrictions. As a matter of fact, the defined system is so common that it allows models where the entangled cluster states between the qubits do not defy strictly to the quantum mechanic.
It is normal to check how the original model fits within this framework. Each particle contains one qubit with a cluster state and a device for measurement, programed with measurement basis sets 
and
, where α is partially dependent and is particular for a given computation. In this model k = l = 2, i.e. for each operator is sent only a single bit to clarify the angle sign and the bit that is returned is the actual measurement result. It is noteworthy that the entire universal quantum computing can be accomplished with minimum values of k and l. Since this requirement constitutes the essential feature of a given correlation to demonstrate computational power, we apply it for the rest of this report.
The classical computer for controlling the computation that uses a cluster state does not demand the total power of a given universal classical computer. The only operations necessary for control of the measurements are equivalence computations [12] - [14] , which may be obtained with а logical XOR operator, or for а reversible scheme with а CNOT operator. The MBQC with equivalence is а device applying circuits containing only CNOT and NOT operations. It may solve many problems effectively, such as computing the equivalence of the bit-circuits, and simulating the deterministic quantum circuits [15] [16] . But the MBQC with equivalence cannot compute any logical function that is not balanced, such as OR or TOFFOLI.
In order to take note of the various computational complexity levels [4] , we will make use of the comfortable notations adopted in the computer science. We will examine only classes of complexity which imply a polynomial computing time-a requirement that is physically realistic. The computing power of the computer with equivalence is shown to be laid down in a class of complexity, called Equivalence-L, or ?L [17] [18] , until the classical and quantum computations which are universal are connected respectively to the classes P and BQP. It is considered that ?L is weaker than Р, which itself is weaker than BQP, but neither of these inclusions are proved as strict.
The notation ?L → BQP points out that the computer with equivalence is developed to full quantum universality when the state of the cluster is utilized as an output state. The remaining families of output states may be classified easily in our framework, see Table 1. Two separate groups can be discovered in the literature. The graph states [16] [19] [20] , which use the Pauli operator’s algebra in order to guarantee determinism, are in Class ?L → BQP. Another class is the computation tensor networks (CTN) based on quantum computations from random output results. For example, CTN indicates that it is impossible to be made a correction using the Pauli’s operators only and using in addition the module n > 2. The additional “use” is equal to an AND operation and similar arithmetic is not possible on the MBQC with equivalence. Some CTN states in this way, probably belong to a different computational power class as opposed to the cluster states; and in particular, in class P → BQP, and not ?L → BQP (pointed out with ✕? in Table 1). This also means that ?L → P is not included in these CTN states.
We can now look at the reverse question of the classical computation based on measurement-considering the computer with equivalence, what output states may be used
![]()
Table 1. The cluster and graph states turn the MBQC with equivalence to a quantum universality (?L → BQP, meaning also P → BQP and ?L → P). The CTN states change the universal classical computer into a universal quantum computer (P → BQP). The three-qubit GHZ states allow the MBQC with equivalence to attain full classical computing (?L → P).
1The cross (✕) points out that the source cannot provide the specific computational improvement, with the supposition that the classes of complexity differ―i.e. ?L 6 = P 6 = BQP. ✕? indicate an assumption for this.
for strengthening its computational power? By the addition of any two-bit deterministic operator, which itself is not a NOT and CNOT operations product represents a classical set of universal operator. The output state which turns the computer with equivalence into a classical universality is of class ?L → P [21] [22] , i.e. it facilitates the classical computation based on measurement (CCBM). It is obvious that the states of the cluster (and each state in ?L → BQP) appertain to this class. But it has been unsolved which characteristics of the state of the cluster facilitate this computational improvement and if there are states that turn ?L → P but not ?L → BQP. A way to turn the computer with equivalence (?L) into classical universality (P) is by allowing it access to a number of universal operators that is polynomial, like the NAND operator. One way of doing that would be to give an expanded size of the states of the cluster and each to be sufficiently large to be implemented NAND or TOFFOLI through standard samples for measurement. Naturally, we want to be informed how much the source size can be decreased.
In order to satisfy the condition for non-signaling and to be possible the computer with equivalence to decode the outcome, the value of the NAND of the α and β input bits have to be encoded in the equivalence of both results m1 and m2, see Figure 2. Let 
be the likelihood of success of a similar device acting on the input data α and β. Since the operator is deterministic for all input values must be in force:
(1)
The theorem of Bell determines the classical upper limitation for that quantity to 0.75 and its limit values are 
for all correlations of the biequivalence quantum states. A pair of Bell is a two qubits set in a superposition of all states, i.e. in
the state
. Thus, a biequivalence output state for deterministic com-
putation of a NAND operator in this framework will require stronger correlations than those of the quantum physics, i.e. there is no biequivalence quantum state in which the computer with equivalence can act deterministically to reduce NAND to two independent input bits.
A state of GHZ is a three qubits set in the 
state. In the three
measuring devices the input bits are 
and then they act on the three qu-
bits, forming the state of GHZ,
. There is independency of the first
two bits, the third c = a ? b that is input is fixed as an equivalence of the first two. It is important that this operation to be able to be carried out on the computer for control with equivalence. The measuring devices, which receive bit 0 measure the observed Pauli’s values σx, and those receiving 1 measure σy. The state ![]()
is the only one of the four equations conforming to all four independent selections for incoming data:
![]()
(2)
It is important to note that in all cases (−1)NAND(a,b) is the eigenvalue. If we couple together binary 0 with the eigenvalue +1 that is measured and binary 1 c − 1 and call the measured outgoing bits n1, n2 and n3, accordingly this means that n1 ? n2 ? n3 = NAND (α, β). The computer with equivalence can easily retrieve NAND (a, b) from the results of the measurements mj (i = 1, 2, 3) through a series of CNOT operations. The measurements of a single GHZ state of three qubits, which are controlled by the computer with equivalence, facilitate the deterministic computing of NAND.
From the NAND’s universality and 1 and 2 follows that the polynomial presence of Bell and GHZ states is the foundation of the MBQC with equivalence using deterministic operators, which turns it into a classical universality (?L → P).
Although the superposition of the qubits in a state of GHZ is greater, the Bell pair’s qubits are more strongly entangled. Due to the monogamy of the entanglement, the Bell pair’s qubits are entangled in a greater extent with one another rather than the GHZ state’s qubits. In a GHZ triplet the third qubit has a tendency to be rather unnecessary than useful. Because the Bell pairs can be utilized for certain tasks, which cannot be carried out by GHZ states (e.g. superdense coding), it is good a state of GHZ to be reduced to a Bell pair by removing one of the qubits. Previously it was accepted, that the only means for this is to find the qubit that is not wanted is with a controlled NOT, controlled by one of the remaining participating qubits. This is how the qubit that is not wanted is cleared by reversing its value in the part all-ON of the superposition while remaining it only in the part all-OFF of the superposition. The approach with a controlled NOT works well, but demands the qubit that is not wanted to be in the same location as one of the remaining qubits. But probably the payment of this price of the quantum bandwidth can be avoided, by closing down the third qubit’s value with a gate of Hadamard, performing a measurement on it, and using the result of the measurement to fix the problem with the parity of the phase, for this purpose it is only necessary to be used a classical bandwidth. This is called “erasing” of the qubit. A given qubit may be removed by a state of GHZ via its measurement along the axis of spinning that is perpendicular to the axis of entanglement and with the aid of the result of the measurement to be made a correction of the phase.
4. Conclusion
An important characteristic of our results is that the equivalent measurements may be performed in parallel. Another variant to the application of the circuit by multiple GHZ states measurements is intended to provide the entire logic circuit in outcomes from the measurements of a single entangled state with multiple qubits. This may require novel methods for parallelization of the circuit by quantum methods. An important specificity in this study is that the measurements must be adaptive. The initiated framework for the computational power classification of the entangled cluster states based on measurement leaves the qubits internal structure completely unrestricted. We have demonstrated that the polynomial supply of two-qubit Bell states presents an optimal source of the classical computation based on measurement by restricting the number of particles that share entangled states. The proposed MBQC model with equivalence combines the two paradoxes of the non-locality that are most important, providing them an interpretation as computing tasks and delivering a simple interpretation for the obvious infringement of the restriction ![]()
for GHZ state measurements when using an unconventional definition of the locality used. In a future continuation of these studies, limitations on the permitted operations of the qubits could be placed, for example the internal dimension or the permissible measurement types, and the flow of classical data could be left unrestricted. This can provide further structure in the output states classification and allow a communication of higher degree (i.e. к, l > 2). Such a class of complexity may characterize the computational power required for controlling the measurements on certain states that require non-binary modular arithmetic. We hope this report will help to improve our understanding of the computing power of the quantum entangled states and for the provision of methods for further analysis. This examination reveals numerous open questions and emphasizes the important link between the quantum computational physics and computer sciences.