qp.PUIsometryFinder

class PUIsometryFinder(basis_states, n_qubits)[source]

Bases: object

Classical algorithm that finds the isometry circuit and bijection for PartialUnaryStatePreparation. The goal is to compute an isometry that maps given computational basis states \(\{|\ell\rangle\}_{\ell \in L}\) to unique states in a \(\lceil\log_2(|L|)\rceil\)-qubit subspace register. The state preparation circuit will then prepare the amplitude \(c_\ell\) on the computational basis state to which \(|\ell\rangle\) was mapped, and run the isometry backwards to distribute the amplitudes to the states \(\{|\ell\rangle\}\).

For example, consider the support \(L=\{0000, 0011, 1100, 1111\}\). Relative to the anchor \(0000\), it is generated by the binary vectors \(0011\) and \(1100\), so it lies in a two-dimensional affine subspace. The forward Clifford circuit CNOT([0, 1]), CNOT([2, 3]), and SWAP([1, 2]) maps the support as

\[0000 \mapsto 0000,\quad 0011 \mapsto 0100,\quad 1100 \mapsto 1000,\quad 1111 \mapsto 1100.\]

The last two bits are now zero, leaving the first two wires as the subspace register. Reversing the circuit maps amplitudes prepared on this register back to the original support.

Parameters:
  • basis_states (list[int]) – Computational basis state indices \(L\) that we want to map to the first \(|L|\) consecutive basis states.

  • n_qubits (int) – Number of qubits on which the state needs to be prepared.

The core idea for this isometry mapping stems from Malvetti et al. (2021). To prepare the mapping, we split the overall wires (excluding dedicated work wires) into a subspace register of size \(n_{\text{subspace}}=\lceil \log_2(|L|)\rceil\) and the remainder register of size \(n_r =n-n_{\text{subspace}}\). The goal then is to map all states \(|\ell\rangle = |\ell_s\rangle \otimes |\ell_r\rangle\) to some unique subspace state \(|f(\ell)\rangle = |f(\ell)\rangle \otimes |0\rangle\), where \(f\) is a bijection. The algorithm works because it successively maps the states to the desired subspace, and does so exclusively with operations that leave the subspace itself untouched, so that all states that have been handled remain static when handling the next ones. Throughout, we will switch between integers and their bit string representation as needed, for example in the split of \(\ell\) into its first \(n_{\text{subspace}}\) bits \(\ell_s\) and the remaining substring \(\ell_r\). Finally, we also define a batch size \(m = \min(2^{\lfloor \log_2(n_r)\rfloor}, |L|)\).

Algorithm description

The algorithm now proceeds iteratively in batches. We will denote some actions in bold, which are both carried out on the bit strings of all the states to be encoded, and recorded in the circuit representation for the isometry. The former is stored in a packed bit tableau, representing each row in a single np.uint64 (for \(n\leq 63\) qubits) or a large Python integer (for \(n>63\)).

  1. Initialize an empty batch \(\mathcal{B}=\{\}\) of integer pairs, a global bijection \(f\) of integers, and a global counter \(k=0\).

  2. If \(j:=|\mathcal{B}| < m-1\), go to step 2, otherwise to step 4.

  3. Search for the next \(\ell'\in L\setminus\mathcal{B}\) that has the \(j\)th remainder bit set to one. There are three stages to this, where the latter two are only used if the previous ones did not succeed.

    • Search for the desired \(\ell'\) in \(L\setminus \mathcal{B}\). If none is found move to the next stage, else continue with step 3.

    • Swap remainder qubit \(j\) with a higher-index remainder qubit that is set to one in at least one bitstring. If none is found and \(j>0\), move to the next stage. If none is found and \(j=0\), move to step 4. If a possible swap move was found, continue with step 3, knowing that we now found a desired \(\ell'\).

    • Find a bitstring that has a one in one of the first \(j\) (note we asserted \(j>0\) above) remainder qubits (at least one such bitstring must exist) and identify a bit in which this bit string differs from the \(j\)th bitstring in \(\mathcal{B}\) (there is at least one such qubit because the bitstrings are unique). Controlled on the found remainder qubit and the differing qubit, flip the \(j\)th remainder qubit. We then have our desired \(\ell'\) with a one on that qubit, and continue with step 3.

    If the above stages did not find an \(\ell'\) and \(\mathcal{B}=\{\}\), we know that all remaining bit strings lie in the subspace register exclusively, and go to step 5.

  4. Controlled on qubit \(j\), flip all other remainder qubits of the found \(\ell\) and set the subspace qubits to the bit string of \(k\). Append \((\ell, k)\) to \(\mathcal{B}\), set \(f(\ell)=k\), and increment \(k\). Go to step 1.

  5. Else, flip the \(i\)th remainder qubit controlled on the bitstring \(k_i\) of the \(i\)th integer pair in \(\mathcal{B}\). Note that this can be done in a batched manner, using unary iteration. Reset the batch to \(\mathcal{B}=\{\}\) (but not the counter \(k\)) and go to step 1.

  6. For all bitstrings \(\ell_0\) that do not have any bit in the remainder register set to one, set \(f(\ell_0)=\ell_0\), i.e. register \(f\) to be the identity mapping on those states. Note that this step happens (most likely) after the bit strings have been manipulated repeatedly by the previous steps.

We now have the complete bijection \(f\) and the recording of the isometry operations required to map \(L\) into the subspace register. The former is used to prepare the dense state \(|\phi_0\rangle=\sum_{\ell\in L} c_{\ell}|f(\ell)\rangle\) on the subspace register. The latter can be executed in reverse to map the states to the desired \(|\psi\rangle = \sum_{\ell \in L } c_\ell |\ell\rangle\).

Why does this work?

We will not go into too much detail about the correctness but want to leave some comments. The elegant core idea of the isometry finding is that any operations we perform controlled on at least one remainder qubit cannot modify the bitstrings that we already mapped to the subspace. This allows us to successively treat the bitstrings, bringing them into the subspace without undoing previous work. The bit strings that have not been mapped, however, are being modified, and for this, it is crucial to keep track of all modifications we make. This class does this with its tableau attribute, which is updated for each operation that we perform during the mapping. (side note: the same logic applies for the swapping step; for already mapped bit strings we just swap two zeroed remainder qubits).

The second neat part of this algorithm is the batched zeroing of remainder qubits via unary iteration. Due to the consecutive integers to which the states of the batch are mapped, unary iteration can be used out of the box, lowering the non-Clifford cost of the isometry circuit. As we already keep track of bit strings, we can reduce the cost further by using partial Select circuits for this step. Those modify the remainder qubits not only for the specific control states in the subspace register, but also for addition control states. Tracking this change in the tableau, we can take these additional modifications into account as a simple side effect of the unary iteration steps.

Note that unfortunately, in our documentation and learning resources the word “partial” is used for this flavour of Select/unary iteration with side effects, whereas Rupprecht and Wölk use the word to point to the sliced range the used unary iteration circuits.

Space-time tradeoff

The isometry finder can naturally make use of a space-time tradeoff; to understand this, note that the batches passed to the partial unary iterators are limited by the maximal size \(m\) inferred from the number of remainder qubits. As the subspace register size is exclusively determined by \(|L|\), adding work wires (or more system wires) directly adds them to the remainder register, thus increasing \(m\).

Overall, the isometry circuit needs to iterate over the entire range \([0,|L|)\), but the smaller the (maximal) batch size, the more iterators are needed, each of which comes with some overhead for the control structure that selects the subspace on which it acts. Increasing the batch size therefore allows for fewer iterators, for which we thus pay less overhead.

fanout(control, bits)

Add a Fanout operation to the circuit ops and apply corresponding CNOTs to the tableau.

find_isometry()

Main method to find the isometry.

pui(k, batch_size)

Add a Partial unary iterator circuit (in form of Select) to the circuit ops and apply the corresponding multicontrolled bit flips to the tableau.

swap(w0, w1)

Add a SWAP operation to the circuit ops and apply SWAP to the tableau.

toffoli(controls, second_ctrl_val, target)

Add a MultiControlledX operation to the circuit ops and apply it to the tableau.

fanout(control, bits)[source]

Add a Fanout operation to the circuit ops and apply corresponding CNOTs to the tableau.

bits is a length-n binary array (the diff vector marking the bits to be flipped). All columns set in bits except control itself are XORed with the control column (per row), while the control column is left unchanged.

find_isometry()[source]

Main method to find the isometry. See main docstring for a detailed description.

pui(k, batch_size)[source]

Add a Partial unary iterator circuit (in form of Select) to the circuit ops and apply the corresponding multicontrolled bit flips to the tableau.

swap(w0, w1)[source]

Add a SWAP operation to the circuit ops and apply SWAP to the tableau.

toffoli(controls, second_ctrl_val, target)[source]

Add a MultiControlledX operation to the circuit ops and apply it to the tableau.

Contents

Using PennyLane

Release news

Development

API

Internals