




A Simple Rank Testing Procedure and Complexity Analysis for the Factorization Algorithm 

PP: 57 

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 Nqubit pure quantum state as tensor product of an mqubit state and an nqubit 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 NB. In this paper we carry out our discussion for the N−qubit case for the sake of simplicity of presentation. The extension to the Nqudit case is straightforward and the computational complexity remains the same. 




