qml.compute_sos_encoding

compute_sos_encoding(bits)

Map \(D\) different bitstrings of length \(r\) to \(D\) different bitstrings \(b\) of length \(m = \min(r, 2d-1)\) where \(d=\lceil\log_2(D)\rceil\). The function computes both the mapping \(U\) and the output bitstrings \(b\). This algorithm forms the constructive proof of Lemma 1 in Fomichev et al., PRX Quantum 5, 040339. It is the main classical coprocessing step required for the sparse state preparation (sum-of-Slaters preparation) presented in this paper, enabling its resource efficiency.

Parameters:

bits (np.ndarray) – Bitstrings of length \(r\) that are input into Lemma 1. The i-th bitstring \(v_i\) is stored in the \(i\)-th column, so that for \(D\) bitstrings, the input shape is \((r, D)\).

Returns:

Two bit arrays. The first is \(U\), which maps the input bits to \(D\) distinct bitstrings \(\{b_i\}\) of length \(\min(r, m)\), where \(m=2\lceil \log_2(D)\rceil-1\). The second array are the bitstrings \(\{b_i\}\) themselves, stored as columns.

Return type:

tuple[np.ndarray]

Warning

It is recommended to first subselect bits via select_sos_rows() in order to work with a reduced input here. Furthermore, this function assumes that the bitstrings are not overly redundant, so that it might error out if select_sos_rows is not used.

See also

select_sos_rows()

Example

Consider an array of bits with distinct columns:

>>> bits = np.array([
...     [0, 1, 1, 0, 1, 0, 0],
...     [0, 0, 1, 1, 1, 0, 0],
...     [1, 1, 1, 1, 1, 1, 1],
...     [0, 0, 1, 0, 0, 0, 1],
...     [1, 1, 0, 0, 0, 0, 1],
...     [0, 0, 0, 0, 0, 1, 1],
... ])
>>> from pennylane.templates.state_preparations.sum_of_slaters import (
...     compute_sos_encoding, _columns_differ
... )
>>> print(_columns_differ(bits))
True
>>> print(bits.shape)
(6, 7)

Our goal is to encode these bitstrings as new, distinct bitstrings of length m=5:

>>> D = bits.shape[1]
>>> m = 2 * qml.math.ceil_log2(D) - 1
>>> print(m)
5

We can achieve this with compute_sos_encoding, which computes the encoding matrix U and the obtained encoded bitstrings b:

>>> U, b = compute_sos_encoding(bits)
>>> print(U)
[[1 0 0 0 0 0]
 [0 1 0 0 0 0]
 [0 0 1 0 0 0]
 [0 0 0 1 0 0]
 [0 0 0 0 1 0]]
>>> print(b)
 [[0 1 1 0 1 0 0]
 [0 0 1 1 1 0 0]
 [1 1 1 1 1 1 1]
 [0 0 1 0 0 0 1]
 [1 1 0 0 0 0 1]]
>>> print(_columns_differ(b))
True

The encoded bitstrings b are provided for convenience. They can equivalently be computed from U and the input bits via (U @ bits) % 2:

>>> np.array_equal((U @ bits) % 2, b)
True

Note that in this particular example, we could have achieved the reduction simply by selecting \(4<m\) rows of the input bits, still obtaining different bitstrings. There is a function that does just that:

>>> from pennylane.templates.state_preparations.sum_of_slaters import select_sos_rows
>>> select_ids, sub_bits = select_sos_rows(bits)
>>> print(sub_bits)
[[0 1 1 0 1 0 0]
 [0 0 1 1 1 0 0]
 [0 0 1 0 0 0 1]
 [1 1 0 0 0 0 1]]

In practice, this sub-selection of bits via select_sos_rows is combined with compute_sos_encoding to achieve lowest cost. Note that there may be edge cases where compute_sos_encoding errors out if select_sos_rows is not used before, because the input bitstrings are too redundant in this case.

Implementation notes

We are given \(D\) distinct bitstrings \(\{v_i\}\) with length \(r\). We assume \(D\geq r\) and \(\operatorname{rank}(V)\geq r\), which can always be achieved by first calling select_sos_rows on the bitstrings.

Our goal is to find a linear map \(U:\mathbb{Z}_2^{r}\to \mathbb{Z}_2^{m}\) from the input bitstrings to \(D\) new distinct bitstrings with length \(m\leq 2d-1\), where \(d:=\lceil\log_2(D)\rceil\), such that

\[U(v_i-v_j)\neq 0 \ \ \forall i, j, \quad\text{and}\quad U(v_i)\neq 0 \ \ \forall i \quad\text{unless}\quad v_i=0.\]

It will be instructive to rewrite this as

\[v_i-v_j\not\in \ker U \ \ \forall i, j, \quad\text{and}\quad v_i\not\in \ker U \ \ \forall i \quad\text{unless}\quad v_i=0.\qquad(1)\]

We will speak of \(U\) and its matrix representation of zeros and ones interchangeably. Since \(k\) bits can represent at most \(2^k\) different bitstrings, we know that \(D\) different bitstrings \(\{v_i\}\) require at least \(d\) bits to be represented, i.e. we know that \(r\geq d\). We will proceed in two cases from here on, differentiated by \(r\).

Case 1: \(d\leq r\leq 2d-1\)

In this case, we do not need to do anything; the bitstrings \(\{v_i\}\) already have length \(m:=r\leq 2d-1\), so we simply set \(U\) to be the identity map. This scenario may actually occur in practice, and it leads to simplifications of the quantum circuit for the state preparation. This depends on the specific bitstrings, though. This case is handled directly in the main function of compute_sos_encoding.

Case 2: \(2d-1 < r\)

Fix \(m=2d-1\) and define \(t:=r-m\) so that \(r=m+t\). According to the rank theorem, any candidate linear map \(U\) satisfies \(\dim (\mathrm{Im} U) + \dim (\ker U)=r\). If we guarantee linear independence of the rows of \(U\), we know that \(\dim (\mathrm{Im} U)\) matches the dimensions of the target space, \(m\), and thus \(\dim (\ker U)=r-m=t\).

Our strategy now will be to find \(t\) linearly independent vectors \(\{w_k\}\) such that the space \(\mathcal{W}:=\operatorname{span}\{w_1, \dots w_t\}\) spanned by them satisfies

\[v_i-v_j\not\in \mathcal{W} \ \ \forall i, j, \quad\text{and}\quad v_i\not\in \mathcal{W} \ \ \forall i \quad\text{unless}\quad v_i=0.\qquad (2)\]

and to construct a map \(U\) with linearly independent rows such that \(U w_k=0 \ \ \forall k\), i.e. \(\mathcal{W}\subset\ker U\). Given that we know the kernel dimension to be \(t\) and \(\dim(\mathcal{W})=t\), this will imply \(\mathcal{W}=\ker U\).

math comment

To see that this strategy actually ensures \(U\) to have the properties we are after, assume that \(U v_i=0\) for some \(i\) with \(v_i\neq 0\) (or \(U(v_i-v_j)\) for some \((i,j)\)). Due to \(\ker U=\mathcal{W}\), this would imply \(v_i\in\mathcal{W}\) (or \(v_i-v_j\in\mathcal{W}\)), which is false by construction of the vectors \(\{w_k\}\), in particular due to Eq. (2).

The main work thus is to actually construct these vectors \(\{w_k\}\) with the required properties. The construction of the map \(U\) itself will then be a simple linear algebraic task. We perform the construction of the vectors iteratively, corresponding to a proof by induction on \(t\).

Given \(D\) vectors \(\{v_i\}\) of length \(r\) with rank \(r\) (i.e., there are at least \(r\) linearly independent vectors), our task is to build \(t=r-(2\lceil \log_2 (D)\rceil -1)\) linearly independent vectors \(\{w_k\}\) from the space \(\operatorname{span}\{v_i\}\) such that the resulting vector space \(\mathcal{W}=\operatorname{span}\{w_k\}\) does not contain the \(\{v_i\}\) or their pairwise differences, see Eq.(2). We can again separate two scenarios.

Case 2a: \(t=1\)

For this case, there is a particularly simple method: we can brute-force a search of \(w_1\) over \(\mathbb{Z}_2^r\setminus (\{v_i\}\cup \{v_i-v_j\})\). This is implemented in _find_single_w. See “Computing U” below for the remaining thing we need to do in this case.

Case 2b: \(t>1\)

If \(t>1\), we recursively construct the \(\{w_k\}\), which is implemented in _find_w. We proceed in the following steps, thinking of ordered sets whenever we speak of sets.

1. First, we select \(r\) of the input vectors \(\mathcal{V}=\{v_i\}\) that are linearly independent (and thus form a–likely not orthonormal–basis of \(\mathbb{Z}_2^r\)). We relabel the vectors so that this selection of vectors has the indices \(\{1,\dots, r\}\), i.e. the basis is \(\mathcal{B}=\{v_1,\dots,v_r\}\). This is implemented in qml.math.binary_select_basis, which returns the basis and the remaining columns separately. This step will only ever be executed once.

2. If \(t=1\) (which can happen despite \(t>1\) initially, because we will use recursion), go to step 3. Else go to step 4.

3. Brute-force search a linear combination \(w_1\) of the basis vectors \(\mathcal{B}\) that is not contained in the set \(\mathcal{V}\cup(\mathcal{V}-\mathcal{V})\cup \{0\}\), where the set difference is meant pairwise between elements. Return \(\{w_1\}\). This is implemented in _step_3_in_find_w.

4. We split \(\mathcal{V}\) into three sets: First, \(\mathcal{M}\) contains all vectors that lie in the span \(\mathcal{K}\) of all but the last basis vector, which we denote as \(v_l\). The second set is simply \(\{v_l\}\). Third, \(\mathcal{N}\) contains all vectors that require both \(v_l\) and a linear combination of the other basis vectors. We maintain the relative ordering within each set, so that the first vectors in \(\mathcal{M}\) correspond to the basis vectors (except for \(v_l\) which is not in \(\mathcal{M}\) by definition).

5. Map each vector in \(\mathcal{N}\) to the space \(\mathcal{K}\) by adding \(v_l\), and call the resulting set \(\mathcal{N}'\).

6. Brute-force search a bitstring \(\ell\) that is not contained in the set \(\mathcal{L}=\mathcal{M}\cup\mathcal{N}'\cup(\mathcal{M}+\mathcal{N})\cup\{0\}\), where addition of sets denotes pairwise addition of elements. \(\ell\) is guaranteed to exist.

7. Form a new set of vectors \(\mathcal{V}'=\mathcal{M}\cup(\mathcal{N}'+\ell)\cup\{\ell\}\), while preserving ordering. Split off the first vectors \(\mathcal{B}'\) that correspond to the original basis vectors (except for \(v_l\)) off this set. Set \(\mathcal{B}\gets\mathcal{B}'\), \(\mathcal{V}\gets\mathcal{V}'\) and \(t\gets t'=t-1\), and go to step 2 to compute a set of \(t'\) vectors \(\mathcal{W}'\) that satisfy the desired properties.

8. Append \(w_t=\ell+v_l\) to \(\mathcal{W}'\) to obtain \(\mathcal{W}\) and return \(\mathcal{W}\).

This procedure will produce the desired linearly independent vectors \(\{w_k\}\).

Computing U

Computing the matrix \(U\) such that the vectors \(\{w_k\}\) are in its kernel is rather simple. This is because the problem is self-dual, i.e., we actually need to find vectors in the kernel of \(W^T\), and will construct \(U\) from the kernel vectors as rows. The same is true for case 2b), where we only had to compute a single \(w_1\).

code/api/pennylane.compute_sos_encoding

 

Download Python script

 

Download Notebook

 

View on GitHub