Introduction
A well-known unique factorization that plays a crucial role in number theory is the unique factorization of natural numbers in terms of the product of its prime factors [1]. This is the well-known Fundamental Theorem of Arithmetic. There are also other Fundamental Theorems, e.g. the Fundamental Theorem of Calculus, the Fundamental Theorem of Algebra, the Fundamental Theorem of Linear Algebra, etc. These fundamental theorems have far-reaching implications and have played a significant role in shaping the respective branches of mathematics to which they belong. Fundamental theorems are useful tools to solve complex problems.
One more unique factorization is the one that we will develop in this paper. This unique factorization is related to quantum information theory. This is about finding unique factorization of an N-qubit pure quantum state in terms of the tensor product of non-factorable or ``prime'' pure quantum states. We work here on a computational basis. This unique factorization is useful to decide the entanglement status of multi-qubit pure quantum states. One more important application of this unique factorization is in the process of synthesizing a multi-qubit pure quantum state in the laboratory with exponential speedup when the unique factorization obtained for a given multi-qubit pure quantum state has large many factors [2].
Entanglement present in a quantum state is one of the main distinguishing features that separates quantum mechanics from classical mechanics. Schrodinger described it as follows: ``I would not call [entanglement] one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought'' [3]. Entanglement is a resource of great utility in quantum computation and quantum information and its characterization is an important problem [4-7]. Determining whether a given multi-qubit pure quantum state is separable or entangled is one of the important problems in quantum information theory [8-10] and this problem was successfully tackled using factorization algorithms in [11,12]. Entanglement describes a correlation between different parts of a quantum system that exceeds anything that is possible classically. This leads to many highly counterintuitive phenomena [13-18]. Quantum entanglement is a counterintuitive, strange, and challenging topic of research and many remarkable achievements have been made through its extensive study [19-50].
A factorization algorithm based on checking the rank of certain associated matrices was developed in [11]. The algorithm developed in [11] for factorization of an arbitrary N-qubit pure quantum state into non-factorable or ``prime'' factors was developed using the following Simple Criterion: For a given N-qubit pure quantum state there exist two pure quantum states, namely, an m-qubit pure state made up from first m qubits and an n-qubit pure state made up from next n qubits, where m + n = N, as factors of given N-qubit pure quantum state if and only if the rank of the corresponding associated matrix of size 2m × 2n obtained from given N-qubit pure quantum state should be of rank equal to one.
Therefore, as per that criterion, it is enough to check whether the value of the rank of a certain associated matrix is equal to one or not in order to check the existence or non-existence of certain factorization.
An alternative factorization algorithm proposed in [12] for factorization of an arbitrary N-qubit pure quantum state into non-factorable or ``prime'' factor states was developed using the Schmidt decomposition technique. It was shown in [12] that a factorization of an N-qubit state in terms the tensor product of an m-qubit state and an n -qubit state, where N = m + n, exists when the value of Schmidt rank of certain bipartite state is equal to one, where this bipartite state is constructed from the given N-qubit state by expressing the m-qubit state made up from first m qubits as an m-dimensional vector and the n -qubit state made up from next n qubits as an n-dimensional vector. Thus in [12] the given N-qubit state is needed to be expressed as a bipartite state, with the first part an m dimensional vector and the second part an n dimensional vector, and the Schmidt decomposition of the thus formed bipartite state is then needed to be carried out and the corresponding Schmidt rank is then needed to be determined and the desired factorization will exist if and only if the value of the Schmidt rank will be equal to one.
The aim of the present paper is to prove that the said ``factorization'' in terms of non-factorable or ``prime'' factors always ``exists'' and is ``unique'', and can be obtained using the factorization algorithm developed in [11](or [12]). To establish the unique factorization we follow here the criterion and the factorization algorithm developed in [11] due to its simplicity.
Factorization algorithm
Let us now state in brief the criterion given in [11] for the existence of factorization and the steps of the factorization algorithm that follows from it for the sake of completeness.
Notation: Let
be an N-qubit pure state :
expressed in terms of the computational basis. Here the basis vectors
are ordered lexicographically. That is, the corresponding binary sequences are ordered lexicographically:
so that
Let m, n be any integers such that 1 ≤ m, n < N and m + n = N Let the corresponding two sets of computational basis vectors ordered lexicographically be
(each of length m) and
(each of length n). Rewrite
thus :
Here in the symbol, aiujv the suffix iujv is the juxtaposition of the binary sequences iu and jv in that order. Thus we get a 2m × 2n matrix
which will be called the 2m × 2n matrix associated to
Criterion ([11]): The state
given by (1) can be factored as the tensor product,
of an m-qubit state
and an n-qubit state
if and only if the 2m × 2n matrix A associated with
is of rank 1.
A brief description of Factorization Algorithm:
Step 1: The factorization algorithm checks whether the given pure state
given by (1) can be factored as the tensor product,
of a 1-qubit state
and an (N - 1)-qubit state
by checking whether the 21 × 2(N - 1) matrix associated to
is of rank 1 and when the given state
has a linear (1-qubit) factor on the left and an (N - 1)-qubit factor on the right as per the above criterion.
Step 2: If yes, then one goes back to step 1, this time with
Step 3: If no, then one proceeds to check whether the given pure state
given by (1) can be factored as the tensor product,
of a 2-qubit factor on the left and an (N - 2)-qubit factor on the right by checking whether the 22 × 2(N - 2) matrix A associated to
is of rank 1 and when so the given state
has a quadratic (2-qubit) factor on the left and an (N - 2)-qubit factor on the right as per the above criterion.
Step 4: If yes, then one goes back to step 1, this time with
Step 5: If no, then one proceeds to check whether the given pure state
given by (1) can be factored as the tensor product,
of a 3-qubit factor on the left and an (N - 3)-qubit factor on the right by checking whether the 23 × 2(N - 3) matrix A associated to
is of rank 1 and when so the given state
has a cubic (3-qubit) factor on the left and an (N - 3)-qubit factor on the right as per the above criterion, and so on.
Thus, as above the algorithm continues until the factorization of
is completely done.
We now proceed to settle the main aim of this paper, namely to show that such complete factorization of
``exists'' and it is ``unique''.
Existence and uniqueness of the factorization
We now proceed to discuss the main result of this paper. We will show here that the factorization for every N-qubit normalized pure quantum state expressed in computational basis ``exists'' and is ``unique'', in terms of the tensor product of non-factorable or ``prime'' pure quantum states.
Let
be an N-qubit normalized pure quantum state expressed in the computational basis.
Definition 3.1: An N-qubit pure quantum state expressed in the computational basis,
is called a non-factorable or ``prime'' state if there do not exist any integers m, n satisfying 1 ≤ m, n < N and m + n = N such that m, n satisfy the criterion given in section II above, namely, the associated matrix of size 2m × 2n obtained from
has rank equal to one.
Theorem 3.1 (Unique Factorization Theorem): There exists factorization for every N-qubit pure quantum state,
expressed in computational basis in terms of the tensor product of non-factorable (prime) pure quantum states and this factorization is unique (up to normalization).
Proof: We first establish the existence of the factorization. It is to be seen that every N-qubit pure quantum state is either (i) a non-factorable or ``prime'' state or (ii) it can be expressed as a tensor product of some non-factorable or ``prime'' pure states containing less than N-qubits such that the sum of the number of qubits present in each of these non-factorable or ``prime'' pure states will be equal to N.
We proceed by induction on N, the number of qubits. For N = 1 we have a 1-qubit pure quantum state and it is clearly a non-factorable or ``prime'' pure state, therefore the result holds for N = 1.
We assume by strong induction that the claim is true for all pure quantum states containing less than N qubits.
Now, let
be an N-qubit pure quantum state expressed in the computational basis. If
is a non-factorable or ``prime'' state then there is nothing more to prove. Otherwise, there will exist some m, n where 1 ≤ m, n < N and m + n = N, such that
where
is an m-qubit pure state made up from first m qubits and
is an n-qubit pure state made up from next n qubits.
Now, we will have a factorization by induction hypothesis, for the m-qubit state,
and the n-qubit state,
in terms of the tensor product of non-factorable or ``prime'' states
and
respectively as given below:
and
Therefore, we have got the desired factorization of the pure quantum state,
under consideration in terms of the tensor product of non-factorable or ``prime'' pure quantum states, namely,
We now proceed to establish the uniqueness of such a factorization:
We proceed by induction on N, the number of qubits. For N = 1 we have 1-qubit pure quantum state and it is clearly a non-factorable or ``prime'' pure state, and so has unique factorization. Therefore the result holds for N = 1.
We assume by strong induction that the claim is true for all pure quantum states containing less than N qubits.
Now, let
be an N-qubit pure quantum state expressed in the computational basis. If
is a non-factorable or ``prime'' state then there is nothing more to prove. Otherwise, we apply the factorization algorithm described above step-by-step and determine the ``smallest'' m and corresponding n = N - m such that these m, n satisfy the criterion given in section II above, i.e. for these m, n the associated matrix of size 2m × 2n obtained from
has rank equal to one, and therefore, the state
can be factored as the tensor product,
where
is an m-qubit state and
an n-qubit state.
Now, it is easy to check that the m-qubit state
is a non-factorable or ``prime'' pure state. Because suppose not, then there will exist r,s satisfying 1 ≤ r, s < m and r + s = m such that r,s satisfy the criterion given in section II above, i.e. the associated matrix of size 2r × 2s obtained from
has rank equal to one, and therefore we will have
where
is an r-qubit state and
an s-qubit state. Now, let
Therefore,
where
is an r-qubit state, r < m, and
is an p = (s + n)-qubit state, p > n such that we now have r + p = N, i.e. for these r,p there exists the associated matrix of size 2r × 2p obtained from
having rank equal to one, and this is contrary to the supposition made above that m is the ``smallest'' integer such that this m and the corresponding n = N - m satisfy the criterion given in section II above. Thus,
is indeed a non-factorable or ``prime'' pure state as desired. Therefore,
can be factored as the tensor product,
where
is an m-qubit non-factorable or ``prime'' state and
an n-qubit state.
Now, as seen above
an n-qubit state where n < N. Therefore, by the induction hypothesis, we can express this state ``uniquely'' as a tensor product of non-factorable or ``prime'' pure states,
say, such that
as given below:
Therefore, we will have ``unique'' factorization for the given N-qubit state
as given below in terms of the tensor product of non-factorable or ``prime'' pure quantum states as given below:
Hence the result.
Conclusion
This paper has established a unique factorization theorem for pure quantum states. This theorem assures that there always exists unique factorization for any given N-qubit pure quantum state in terms of the tensor product of non-factorable or ``prime'' pure quantum states. One can determine the entanglement status of any given N-qubit pure quantum state by carrying out the unique factorization in terms of the tensor product of non-factorable or ``prime'' pure quantum states as assured by this unique factorization theorem. An N-qubit pure quantum state is separable when it can be expressed as a tensor product of N number of 1-qubit pure quantum states. Therefore, by applying the above-mentioned unique factorization theorem if the given N-qubit state becomes a tensor product of N number of 1-qubit states then and only then it will be a separable state, otherwise, it will be an entangled state having at least one (or more) entangled factor(s).