Skip to content

is_unextendible_product_basis

Check if a set of states form an unextendible product basis.

is_unextendible_product_basis 

is_unextendible_product_basis(
    vecs: list[ndarray], dims: list[int]
) -> tuple[bool, ndarray | None]

Check if a set of vectors form an unextendible product basis (UPB) 1.

Consider a multipartite quantum system \(\mathcal{H} = \bigotimes_{i=1}^{m} \mathcal{H}_{i}\) with \(m\) parties with respective dimensions \(d_i, i = 1, 2, ..., m\). An (incomplete orthogonal) product basis (PB) is a set \(S\) of pure orthogonal product states spanning a proper subspace \(\mathcal{H}_S\) of \(\mathcal{H}\). An unextendible product basis (UPB) is a PB whose complementary subspace \(\mathcal{H}_S-\mathcal{H}\) contains no product state. This function is inspired from IsUPB in 2.

Parameters:

  • vecs (list[ndarray]) –

    The list of states.

  • dims (list[int]) –

    The list of dimensions.

Returns:

  • bool –

    Returns a tuple. The first element is True if input is a UPB and False otherwise. The second element is a

  • ndarray | None –

    witness (a product state orthogonal to all the input vectors) if the input is a PB and None otherwise.

Raises:

  • ValueError –

    If product of dimensions does not match the size of a vector.

  • ValueError –

    If at least one vector is not a product state.

Examples:

See tile(). All the states together form a UPB:

import numpy as np
from toqito.states import tile
from toqito.state_props import is_unextendible_product_basis
upb_tiles = np.array([tile(i) for i in range(5)])
dims = np.array([3, 3])
print(is_unextendible_product_basis(upb_tiles, dims))

(True, None)

However, the first 4 do not:

import numpy as np
from toqito.states import tile
from toqito.state_props import is_unextendible_product_basis
non_upb_tiles = np.array([tile(i) for i in range(4)])
dims = np.array([3, 3])
print(is_unextendible_product_basis(non_upb_tiles, dims))

(False, array([-0.00000000e+00,  0.00000000e+00,  0.00000000e+00, -0.00000000e+00,  0.00000000e+00,  0.00000000e+00, -1.11022302e-16,  7.07106781e-01,
        7.07106781e-01]))

The orthogonal state is given by

\[ \frac{1}{\sqrt{2}} |2\rangle \left( |1\rangle + |2\rangle \right) \]

References

1 Bennett, Charles and DiVincenzo, David and Mor, Tal and Shor, Peter and Smolin, John and Terhal, Barbara. Unextendible Product Bases and Bound Entanglement. Physical Review Letters. vol. 82(26). (1999). doi:10.1103/physrevlett.82.5385.
2 Johnston, Nathaniel. {{QETLAB}: {A MATLAB} toolbox for quantum entanglement}. doi:10.5281/zenodo.44637.

Source code in toqito/state_props/is_unextendible_product_basis.py 
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
def is_unextendible_product_basis(vecs: list[np.ndarray], dims: list[int]) -> tuple[bool, np.ndarray | None]:
    r"""Check if a set of vectors form an unextendible product basis (UPB) [@bennett1999unextendible].

    Consider a multipartite quantum system \(\mathcal{H} = \bigotimes_{i=1}^{m} \mathcal{H}_{i}\) with \(m\)
    parties with respective dimensions \(d_i, i = 1, 2, ..., m\). An (incomplete orthogonal) product basis (PB) is a
    set \(S\) of pure orthogonal product states spanning a proper subspace \(\mathcal{H}_S\) of
    \(\mathcal{H}\).  An unextendible product basis (UPB) is a PB whose complementary subspace
    \(\mathcal{H}_S-\mathcal{H}\) contains no product state.  This function is inspired from `IsUPB` in
    [@qetlablink].

    Args:
        vecs: The list of states.
        dims: The list of dimensions.

    Returns:
        Returns a tuple. The first element is `True` if input is a UPB and `False` otherwise. The second element is a
        witness (a product state orthogonal to all the input vectors) if the input is a PB and `None` otherwise.

    Raises:
        ValueError: If product of dimensions does not match the size of a vector.
        ValueError: If at least one vector is not a product state.

    Examples:
        See [tile()][toqito.states.tile.tile]. All the states together form a UPB:

        ```python exec="1" source="above" result="text"
        import numpy as np
        from toqito.states import tile
        from toqito.state_props import is_unextendible_product_basis
        upb_tiles = np.array([tile(i) for i in range(5)])
        dims = np.array([3, 3])
        print(is_unextendible_product_basis(upb_tiles, dims))
        ```

        However, the first 4 do not:

        ```python exec="1" source="above" result="text"
        import numpy as np
        from toqito.states import tile
        from toqito.state_props import is_unextendible_product_basis
        non_upb_tiles = np.array([tile(i) for i in range(4)])
        dims = np.array([3, 3])
        print(is_unextendible_product_basis(non_upb_tiles, dims))
        ```

        The orthogonal state is given by

        \[
            \frac{1}{\sqrt{2}} |2\rangle \left( |1\rangle + |2\rangle \right)
        \]

    """
    vecs = np.array(vecs)
    dims = np.array(dims)

    if np.prod(dims) != vecs.shape[1]:
        raise ValueError("Product of dimensions does not equal the size of each vector")

    if not all(is_product(vec, dims)[0] for vec in vecs):
        raise ValueError("At least one vector is not a product state")

    # Number of parties (m).
    num_parties = dims.shape[0]

    # Number of vectors (n).
    num_vecs = vecs.shape[0]

    # If n < m vectors are provided, then we cannot generate set partitions, so it is not a UPB. We will extend the set
    # with m-n null vectors and run the same algorithm.
    if (num_vecs := vecs.shape[0]) < num_parties:
        vecs = np.append(vecs, np.zeros(shape=(num_parties - num_vecs, *vecs.shape[1:])), axis=0)
        num_vecs = vecs.shape[0]

    # Split products.
    vecs_split = np.array([is_product(vec, dims)[1] for vec in vecs])

    # Acquire generator to m-partitions of [0, n-1].
    parts_unordered = set_partitions(list(range(num_vecs)), num_parties)

    # Memoize null-space SVDs. For a fixed party ``i`` the null space depends only
    # on the *set* of columns in the block (row order does not change the null
    # space), so each distinct ``(frozenset(block), i)`` pair is computed once per
    # partition rather than once for every one of the ``m!`` orderings.
    null_space_cache: dict[tuple[frozenset, int], np.ndarray] = {}

    for part_unordered in parts_unordered:
        for part_ordered in permutations(part_unordered):
            # Witness vectors.
            wit = []
            witness_found = True
            for i in range(num_parties):
                # Find the basis of the null space (memoized on the block/party).
                cache_key = (frozenset(part_ordered[i]), i)
                null_basis = null_space_cache.get(cache_key)
                if null_basis is None:
                    # For the i-th party, acquire the matrix.
                    mat = np.stack([vecs_split[col, i, :] for col in part_ordered[i]])
                    null_basis = null_space(mat)
                    null_space_cache[cache_key] = null_basis
                # If null space is empty then break.
                if null_basis.shape[1] == 0:
                    witness_found = False
                    break
                # If null space is non-empty, add a basis vector of null space to witness.
                wit.append(null_basis[:, 0])
            # If witness was found, then it is not a UPB, return tensor product of witness vectors.
            if witness_found:
                # If wit is empty, tensor returns None.
                return False, tensor(wit)

    # If no witness was found, it is a UPB.
    return True, None