Schmidt Rank in matrix subspace¶
see paper "Complete hierarchy of linear systems for certifying quantum entanglement of subspaces" doi-link for more details
An important and difficult problem in quantum information field is to ask whether there is a product state in matrix subspace. For this problem, Nathaniel et al. proposed a method to solve it by constructing a set of vectors in higher dimensional space and then inspecting the linear dependency of these vectors. numqi.matrix_space implements this methods and does some optimization to make it more efficient (see last section for a benchmarking).
import numpy as np
try:
import numqi
except ImportError:
%pip install numqi
import numqi
Matrix subspace¶
Given a set of matrices $\{A_1,A_2,\cdots,A_d\}\in\mathbb{C}^{m\times n}$, the matrix subspace is defined as
$$ \mathcal{S}=\langle A_1,A_2,\cdots,A_d \rangle_\mathbb{C}=\left\{ x\in\mathbb{C}^{m\times n}: x=\sum_i a_iA_i,a_i\in\mathbb{C} \right\} $$
One should note that $\mathcal{S}$ is vector space with elements in $\mathbb{C}^{m\times n}$, not $\mathbb{C}^{mn}$, so it's called matrix subspace. The complex filed $\mathcal{C}$ will be used across this tutorial, as the proposed method is not applied in the real field $\mathbb{R}$ which will be discussed in another tutorial. The Schmidt rank $r(\mathcal{S})$ is defined as the minimal rank over all nonzero elements in $\mathcal{S}$
$$ r(\mathcal{S})=\min_x\left\{r(x):x\in\mathcal{S},x\ne 0\right\} $$
where the rank for a matrix $r(x)$ is the number of nonzero singular values of $x$. The rank of a matrix is easy to compute, but the Schmidt rank of a matrix subspace is difficult to compute (TODO, is this NP?). In this tutorial, we will show how to compute the Schmidt rank of a matrix subspace. Let's start with an example (Example 1 from the paper doi-link) $\mathcal{S}=\langle |x_1\rangle,\cdots,|x_8\rangle \rangle_\mathbb{C}\subset\mathbb{C}^{4\times 4}$
$$ |x_{1}\rangle=|00\rangle+|11\rangle+|22\rangle+|33\rangle,|x_{2}\rangle=|00\rangle-|11\rangle+|22\rangle-|33\rangle $$
$$ |x_{3}\rangle=|01\rangle+|12\rangle+|23\rangle,|x_{4}\rangle=|10\rangle+|21\rangle+|32\rangle $$
$$ |x_{5}\rangle=|01\rangle+2|12\rangle+3|23\rangle,|x_{6}\rangle=|10\rangle+2|21\rangle+3|32\rangle $$
$$ |x_{7}\rangle=|01\rangle+|13\rangle,|x_{8}\rangle=|20\rangle+|31\rangle $$
where we use the bra-ket notation $|ij\rangle$ to represent the matrix with 1 at $(i,j)$ and 0 elsewhere. The matrix subspace $\mathcal{S}$ has no rank-$1$ element, which can be verified by the following code.
matrix_subspace,field = numqi.matrix_space.get_matrix_subspace_example(key='hierarchy-ex1')
print(f'field: {field}')
print(f'shape: {matrix_subspace.shape}')
print(f'matrix[0]:\n{matrix_subspace[0]}')
print(f'matrix[1]:\n{matrix_subspace[1]}')
print(f'matrix[2]:\n{matrix_subspace[2]}')
field: complex shape: (8, 4, 4) matrix[0]: [[1. 0. 0. 0.] [0. 1. 0. 0.] [0. 0. 1. 0.] [0. 0. 0. 1.]] matrix[1]: [[ 1. 0. 0. 0.] [ 0. -1. 0. 0.] [ 0. 0. 1. 0.] [ 0. 0. 0. -1.]] matrix[2]: [[0. 1. 0. 0.] [0. 0. 1. 0.] [0. 0. 0. 1.] [0. 0. 0. 0.]]
tag_atleast_rank2 = numqi.matrix_space.has_rank_hierarchical_method(matrix_subspace, rank=2, hierarchy_k=1)
print(f'at least rank 2: {tag_atleast_rank2}')
at least rank 2: True
Above, the algorithm numqi.matrix_space.has_rank_hierarchical_method return a boolean object tag_asleast_rank2, if it's True, then the algorithm can certify that the matris subspace has no rank-$1$ element (nonzero matrix). And for this example, it's indead True.
Let's dive into the details of the algorithm. The algorithm is based on the following theorem in the paper:
Theorem: Let $S\subseteq \mathcal{H}_A\otimes \mathcal{H}_B$ be a matrix subspace with basis $\left\{ \left|x_{1}\right\rangle ,\left|x_{2}\right\rangle ,\cdots,\left|x_{d_{S}}\right\rangle \right\}$. Then all nonzero elements in $S$ has at least rank $r+1$, iff there exists an integer $1\leq k\leq (max\{r,2\}+1)^{d_Ad_B}-r$ such that the set $$ \{ \Phi_{r}^{k}(|x_{j_{1}}\rangle \otimes|x_{j_{2}}\rangle \otimes\cdots\otimes|x_{j_{r+k}}\rangle ):1\leq j_{1}\leq\cdots\leq j_{r+k}\leq d_{S}\} $$ $$ \Phi_{r}^{k}\equiv\left(P_{A,r+1}^{\wedge}\otimes P_{B,r+1}^{\wedge}\otimes I_{AB,k-1}\right)P_{AB,r+k}^{\vee} $$ is linearly independent.
Don't get panic by the theorem. The key part is that build some vectors in higher dimensional space and then inspect the linear dependency of these vectors. The tensor operation $|x_{j_1}\rangle\otimes |x_{j_2}\rangle$ is to project into high dimensional space and then $\Psi_r^k$ is a linear map (think of it as a large matrix) doing some linear transformation in high dimensional space with symmetrization $P^\vee$ and anti-symmetrization $P^\wedge$ operator. After all these operations, the criterion is to check whether the set of vectors is linearly independent, numerically, numqi.matrix_space will check the minimum eigenvalue $\lambda_0$ of the associated matrix $VV^\dagger$,
| if | then |
|---|---|
| $\lambda_0\geq \delta$, independent | $r(\mathcal{S})>r$ |
| $\lambda_0<\delta$, dependent at $k<k_{\mathrm{max}}$ | nothing |
| $\lambda_0<\delta$, dependent at $k=k_{\mathrm{max}}$ | $r(\mathcal{S})\leq r$ |
where $k_{\max}=(\max\{r,2\}+1)^{d_Ad_B}-r$. So this algorithm is able to certify "any" Schimdt rank of matrix subspace. Let's do a numerical test for rank-$3$ matrix subspace (Example 5 in the paper).
matrix_subspace,field = numqi.matrix_space.get_matrix_subspace_example(key='hierarchy-ex5')
print(f'field: {field}')
print(f'shape: {matrix_subspace.shape}')
print(f'matrix[0]:\n{matrix_subspace[0]}')
print(f'matrix[1]:\n{matrix_subspace[1]}')
print(f'matrix[2]:\n{matrix_subspace[2]}')
tag_atleast_rank3 = numqi.matrix_space.has_rank_hierarchical_method(matrix_subspace, rank=3, hierarchy_k=1)
print(f'at least rank 3: {tag_atleast_rank3}')
field: complex shape: (3, 4, 4) matrix[0]: [[1. 0. 0. 0.] [0. 1. 0. 0.] [0. 0. 1. 0.] [0. 0. 0. 1.]] matrix[1]: [[0. 1. 0. 0.] [0. 0. 1. 0.] [0. 0. 0. 1.] [1. 0. 0. 0.]] matrix[2]: [[ 0. 0. 1. 0.] [ 0. 0. 0. 1.] [ 1. 0. 0. 0.] [ 0. -1. 0. 0.]] at least rank 3: True
As expected, the algorithm can certify that the matrix subspace has no rank-$1$ and rank-$2$ element. There are examples that require the hierarchy $k$ to be larger than 1. For example, the following matrix subspace (Example 3 in the paper)
matrix_subspace,field = numqi.matrix_space.get_matrix_subspace_example(key='hierarchy-ex3')
print(f'field: {field}')
print(f'shape: {matrix_subspace.shape}')
tag_atleast_rank2_k1 = numqi.matrix_space.has_rank_hierarchical_method(matrix_subspace, rank=2, hierarchy_k=1)
tag_atleast_rank2_k2 = numqi.matrix_space.has_rank_hierarchical_method(matrix_subspace, rank=2, hierarchy_k=2)
tag_atleast_rank2_k3 = numqi.matrix_space.has_rank_hierarchical_method(matrix_subspace, rank=2, hierarchy_k=3)
print(f'at least rank 2 (k=1): {tag_atleast_rank2_k1}')
print(f'at least rank 2 (k=2): {tag_atleast_rank2_k2}')
print(f'at least rank 2 (k=3): {tag_atleast_rank2_k3}')
field: complex shape: (9, 4, 4)
at least rank 2 (k=1): False at least rank 2 (k=2): False at least rank 2 (k=3): True
As results show, this matrix subspace requires the algorithm to certify at least $k=3$. Before ending this part, let's point out some shortage of this algorithm:
- This algorithm cannot certify the matrix subspace has rank-$r$ element in practice (unless the $k=k_{\mathrm{max}}$)
- complex field $\mathbb{C}$ is required, not applied to real field $\mathbb{R}$
Multipartite subspace¶
The algorithm can be extended to multipartite subspace to certify the so-called completely entangled subspace (CES). For example, the following matrix subspace (Example 6 in the paper) can be certified at $k=2$.
dimA = 2
dimB = 2
dimC = 2
np_list = numqi.matrix_space.get_completed_entangled_subspace((dimA, dimB, dimC), kind='quant-ph/0409032')[0]
tag_k1 = numqi.matrix_space.is_ABC_completely_entangled_subspace(np_list, hierarchy_k=1)
tag_k2 = numqi.matrix_space.is_ABC_completely_entangled_subspace(np_list, hierarchy_k=2)
print(f'completely entangled (k=1): {tag_k1}')
print(f'completely entangled (k=2): {tag_k2}')
completely entangled (k=1): False completely entangled (k=2): True
In the numqi.matrix_space implementation, we do some optimization to make it more efficient making use of tensor contraction, the timing is shown below.
| $(d_A,d_B,d_C)$ | $k$ | paper | numqi |
|---|---|---|---|
| $(2,2,2)$ | 2 | 0.12s | 0.01s |
| $(2,2,3)$ | 2 | 0.30s | 0.22s |
| $(2,2,4)$ | 2 | 0.67s | 0.52s |
| $(2,2,5)$ | 2 | 1.21s | 0.55s |
| $(2,2,6)$ | 2 | 3.47s | 0.69s |
| $(2,2,7)$ | 2 | 6.05s | 0.96s |
| $(2,2,8)$ | 2 | 18.90s | 1.40s |
| $(2,2,9)$ | 2 | 38.40s | 2.18s |
| $(2,3,3)$ | 3 | 19.58s | 1.30s |
| $(2,3,4)$ | 3 | 8.24m | 8.59s |
| $(2,3,5)$ | 3 | 2.50h | 328s |
where the column "paper" is from Table III in the paper and the column numqi is the timing of numqi.matrix_space.is_ABC_completely_entangled_subspace on a mac-studio Apple M1 Ultra with 20 cores.