|
|
 |
| |
|
|
|
A Simple Rank Testing Procedure and Complexity Analysis for the Factorization Algorithm |
|
|
|
PP: 5-7 |
|
|
|
doi:10.18576/qpl/080102
|
|
|
|
Author(s) |
|
|
|
Dhananjay P. Mehendale,
Pramod S. Joag,
|
|
|
|
Abstract |
|
|
| The problem of characterizing entanglement status of a multipartite pure quantum state was completely solved through the factorization algorithm in [1]. This factorization algorithm for systematically extracting factors is based on utilizing the following criterion: One has a factorization for the given N-qubit pure quantum state as tensor product of an m-qubit state and an n-qubit state, where m + n = N, if and only if the rank of the associated matrix, A, of size 2m × 2n is equal to unity. The main computational effort for factoring is thus centered around checking whether or not the rank of the associated matrices that arise during extraction of factors is equal to unity. This paper is about proposing a smart procedure to check this. Due to this smart procedure the maximum number
of arithmetical operations one needs to carry out to extract one factor, when it exists, become of the order of the cardinality of B, |B| = 2N, where B denotes the corresponding computational basis. Further, for finding full factorization one just needs to repeat the rank testing procedure at most N times as the given N−qubit state can have at most N factors, and thus the overall complexity of complete factorization is of the order N|B|. In this paper we carry out our discussion for the N−qubit case for the sake of simplicity of presentation. The extension to the N-qudit case is straightforward and the computational complexity remains the same. |
|
|
|
|
|
|
|
