SelectSwapQROM

from qualtran import Bloq, CompositeBloq, BloqBuilder, Signature, Register
from qualtran import QBit, QInt, QUInt, QAny
from qualtran.drawing import show_bloq, show_call_graph, show_counts_sigma
from typing import *
import numpy as np
import sympy
import cirq

QROMBase

Interface for Bloqs to load data[l] when the selection register stores index l.

Overview

The action of a QROM can be described as

\[ \text{QROM}_{s_1, s_2, \dots, s_K}^{d_1, d_2, \dots, d_L} |s_1\rangle |s_2\rangle \dots |s_K\rangle |0\rangle^{\otimes b_1} |0\rangle^{\otimes b_2} \dots |0\rangle^{\otimes b_L} \rightarrow |s_1\rangle |s_2\rangle \dots |s_K\rangle |d_1[s_1, s_2, \dots, s_k]\rangle |d_2[s_1, s_2, \dots, s_k]\rangle \dots |d_L[s_1, s_2, \dots, s_k]\rangle \]

A behavior of a QROM can be understood in terms of its classical analogue, where a for-loop over one or more (selection) indices can be used to load one or more classical datasets, where each of the classical dataset can be multidimensional.

>>> # N, M, P, Q, R, S, T are pre-initialized integer parameters.
>>> output = [np.zeros((P, Q)), np.zeros((R, S, T))]
>>> # Load two different classical datasets; each of different shape.
>>> data = [np.random.rand(N, M, P, Q), np.random.rand(N, M, R, S, T)]
>>> for i in range(N): # For loop over two selection indices i and j.
>>>     for j in range(M):
>>>        # Load two multidimensional classical datasets data[0] and data[1] s.t.
>>>        # |i, j⟩|0⟩  -> |i, j⟩|data[0][i, j, :]⟩|data[1][i, j, :]⟩
>>>        output[0] = data[0][i, j, :]
>>>        output[1] = data[1][i, j, :]

The parameters that control the behavior and costs of a QROM are -

1. Number of selection registers (eg: \(i\), \(j\)) and their iteration lengths (eg: \(N\), \(M\)).

2. Number of target registers, their quantum datatype and shape.

   • Number of target registers: One for each classical dataset to load (eg: \(\text{data}[0]\) and \(\text{data}[1]\))

   • QDType of target registers: Depends on dtype of the \(i\)’th classical dataset

   • Shape of target registers: Depends on shape of classical data (eg: \((P, Q)\) and \((R, S, T)\) above)

Specification of classical data via data_or_shape

Users can specify the classical data to load via QROM by passing in an appropriate value for data_or_shape attribute. This is a list of numpy arrays or Shaped objects, where each item of the list corresponds to a classical dataset to load.

Each classical dataset to load can be specified as a numpy array (or a Shaped object for symbolic bloqs). The shape of the dataset is a union of the selection shape and target shape, s.t.

\[ \text{data[i].shape} = \text{selection\_shape} + \text{target\_shape[i]} \]

Note that the \(\text{selection\_shape}\) should be same across all classical datasets to be loaded and correspond to a tuple of iteration lengths of selection indices (i.e. \((N, M)\) in the example above).

The target shape of each classical dataset can be different and parameterizes the size of the desired output that should be loaded in a target register.

Number of selection registers and their iteration lengths

As describe in the previous section, the number of selection registers and their iteration lengths can be inferred from the shape of the classical dataset. All classical datasets to be loaded must have the same \(\text{selection\_shape}\), which is a tuple of iteration lengths over each dimension of the dataset (i.e. the range for each nested for-loop).

In order to load a data set with \(\text{selection\_shape} == (P, Q, R, S)\) the QROM bloq needs four selection registers with bitsizes \((p, q, r, s)\) where each of \(p,q,r,s \geq \log_2{P}, \log_2{Q}, \log_2{R}, \log_2{S}\).

In general, to load \(K\) dimensional data, we use \(K\) named selection registers \((\text{selection}_0, \text{selection}_1, ..., \text{selection}_k)\) to index and load the data. For the \(i\)’th selection register, its size is configured using attribute \(\text{selection\_bitsizes[i]}\) and the iteration range is configued using \(\text{data\_or\_shape[0].shape[i]}\).

Number of target registers, their quantum datatype and shape

QROM bloq uses one target register for each entry corresponding to classical dataset in the tuple data_or_shape. Thus, to load \(L\) classical datsets, we use \(L\) names target registers \((\text{target}_0, \text{target}_1, ..., \text{target}_L)\)

Each named target register has a bitsize \(b_{i}=\text{target\_bitsizes[i]}\) that represents the size of the register and depends upon the maximum value of individual elements in the \(i\)’th classical dataset.

Each named target register has a shape that can be configured using attribute \(\text{target\_shape[i]}\) that represents the number of target registers if the output to load is multidimensional.

Parameters

• data_or_shape: List of numpy ndarrays specifying the data to load. If the length of this list (\(L\)) is greater than one then we use the same selection indices to load each dataset. The shape of a classical dataset is a concatenation of selection_shape and target_shape[i]; i.e. data_or_shape[i].shape = selection_shape + target_shape[i]. Thus, each data set is required to have the same selection shape \((S_1, S_2, ..., S_K)\) and can have a different target shape given by target_shapes[i]. For symbolic QROMs, pass a list of Shaped objects instead with shape \((S_1, S_2, ..., S_K) + target_shape[i]\).

• selection_bitsizes: The number of bits used to represent each selection register corresponding to the size of each dimension of the selection_shape \((S_1, S_2, ..., S_K)\). Should be the same length as the selection shape of each of the datasets and \(2**\text{selection\_bitsizes[i]} >= S_i\)

• target_shapes: Shape of target registers for each classical dataset to be loaded. Must be consistent with data_or_shape s.t. len(data_or_shape) == len(target_shapes) and data_or_shape[-len(target_shapes[i]):] == target_shapes[i].

• target_bitsizes: Bitsize (or qdtype) of the target registers for each classical dataset to be loaded. This can be deduced from the maximum element of each of the datasets. Must be consistent with data_or_shape s.t. len(data_or_shape) == len(target_bitsizes) and target_bitsizes[i] >= max(data[i]).bitsize.

• num_controls: The number of controls to instanstiate a controlled version of this bloq.

SelectSwapQROM

Gate to load data[l] in the target register when the selection register stores integer l.

Let N:= Number of data elements to load. b:= Bit-length of the target register in which data elements should be loaded.

The SelectSwapQROM is a hybrid of the following two existing primitives:

• Unary Iteration based QROM requires O(N) T-gates to load N data elements into a b-bit target register. Note that the T-complexity is independent of b.

• SwapWithZeroGate can swap a b bit register indexed x with a b bit register at index 0 using O(b) T-gates, if the selection register stores integer x. Note that the swap complexity is independent of the iteration length N.

The SelectSwapQROM uses square root decomposition by combining the above two approaches to further optimize the T-gate complexity of loading N data elements, each into a b bit target register as follows:

• Divide the N data elements into batches of size B (a variable) and load each batch simultaneously into B distinct target signature using the conventional QROM. This has T-complexity O(N / B).

• Use SwapWithZeroGate to swap the i % B’th target register in batch number i / B to load data[i] in the 0’th target register. This has T-complexity O(B * b).

This, the final T-complexity of SelectSwapQROM is O(B * b + N / B) T-gates; where B is the block-size with an optimal value of O(sqrt(N / b)).

This improvement in T-complexity is achieved at the cost of using an additional O(B * b) ancilla qubits, with a nice property that these additional ancillas can be dirty; i.e. they don’t need to start in the |0> state and thus can be borrowed from other parts of the algorithm. The state of these dirty ancillas would be unaffected after the operation has finished.

For more details, see the reference below:

References

• Trading T-gates for dirty qubits in state preparation and unitary synthesis. Low, Kliuchnikov, Schaeffer. 2018.

• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization. Berry et al. 2019. Appendix A. and B.

from qualtran.bloqs.data_loading.select_swap_qrom import SelectSwapQROM

Example Instances

data1 = np.arange(5)
data2 = np.arange(5) + 1
qroam_multi_data = SelectSwapQROM.build_from_data(data1, data2)

data1 = np.arange(25).reshape((5, 5))
data2 = (np.arange(25) + 1).reshape((5, 5))
qroam_multi_dim = SelectSwapQROM.build_from_data(data1, data2)

N, b, k, c = sympy.symbols('N b k c', positive=True, integers=True)
qroam_symb_dirty_1d = SelectSwapQROM.build_from_bitsize(
    (N,), (b,), log_block_sizes=(k,), num_controls=c
)

N, M, b1, b2, k1, k2, c = sympy.symbols('N M b1 b2 k1 k2 c', positive=True, integers=True)
log_block_sizes = (k1, k2)
qroam_symb_dirty_2d = SelectSwapQROM.build_from_bitsize(
    (N, M), (b1, b2), log_block_sizes=log_block_sizes, num_controls=c
)

N, b, k, c = sympy.symbols('N b k c', positive=True, integers=True)
qroam_symb_clean_1d = SelectSwapQROM.build_from_bitsize(
    (N,), (b,), log_block_sizes=(k,), num_controls=c, use_dirty_ancilla=False
)

N, M, b1, b2, k1, k2, c = sympy.symbols('N M b1 b2 k1 k2 c', positive=True, integers=True)
log_block_sizes = (k1, k2)
qroam_symb_clean_2d = SelectSwapQROM.build_from_bitsize(
    (N, M), (b1, b2), log_block_sizes=log_block_sizes, num_controls=c, use_dirty_ancilla=False
)

Graphical Signature

from qualtran.drawing import show_bloqs
show_bloqs([qroam_multi_data, qroam_multi_dim, qroam_symb_dirty_1d, qroam_symb_dirty_2d, qroam_symb_clean_1d, qroam_symb_clean_2d],
           ['`qroam_multi_data`', '`qroam_multi_dim`', '`qroam_symb_dirty_1d`', '`qroam_symb_dirty_2d`', '`qroam_symb_clean_1d`', '`qroam_symb_clean_2d`'])

Call Graph

from qualtran.resource_counting.generalizers import ignore_split_join
qroam_multi_data_g, qroam_multi_data_sigma = qroam_multi_data.call_graph(max_depth=1, generalizer=ignore_split_join)
show_call_graph(qroam_multi_data_g)
show_counts_sigma(qroam_multi_data_sigma)

Counts totals:

• QROM((5,), ((1,), (1,)), (3, 3)): 2

• Xor: 4