alias_sampling_utils

alias_sampling_utils ¶

combined_data_list ¶

combined_data_list(alias_list, threshold_list, num_alias_qubits=None)

Converts classical data specified by alias_list and threshold_list into a combined output list.

This list specifies the classical data to load with a QROM in an alias sampler.

Note

In regular alias sampling, only a single set of data is used, so we can infer the length of the combined terms directly from this data. In multiplexed alias sampling, however, all the sets of data being multiplexed over has to be loaded into the same register, so we need to include a shift not based on the current data, but on the largest set of data being loaded in total. In this case, we need to explicitly pass the number of alias qubits to this function to get the correct shift.

Parameters:

Name	Type	Description	Default
`alias_list`	`list`	List of alias values.	required
`threshold_list`	`list`	List of threshold values.	required
`num_alias_qubits`	`int`	Number of alias qubits. Defaults to `None`.	`None`

Returns:

Type	Description
`list`	List of values to load onto alias and keep registers in an alias sampler.

generate_alias_table ¶

generate_alias_table(input_list, bit_precision)

Generates a table of alias and threshold values.

These values come from a distribution specified as a list of relative probabilties.

The cutoff threshold is calculated as being a uniform distribution, i.e. the bar height is \(1/L\) for \(L\) the length of input_list. The number of "boxes" in the discretization (see Fig. 13 in "Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity" (arXiv:1805.03662 ⧉) for details) is given by len(input_list) * 2 ** bit_precision. The values that are returned correspond to:

alias_list: The value of the index at the top of the final histogram after the discretization and transformation.
threshold_list: The height of the cutoff where one index changes to another.

As a worked example, take the coefficients [1/4, 2/4, 0, 1/4]. There are 4 values, so the height of the uniform distribution is 1/4. The first element is exactly 1/4, so nothing needs to change here: the index corresponding to the top of the bar is 0 and there is only one value in it, so the threshold value is also 0.

The second element is overfull: we take the additional 1/4 and move it into column 2 (using Python indexing). The index corresponding to the top of the bar is 1 and there is only one value in the final column, so the threshold value is 0.

The third element in the prior distribution is 0, but we took 1/4 from the second column and put it in here: the value at the top of the bar thus corresponds to index 1, and there is only one value in the final column, so the threshold value is 0.

Finally, we don't need to change the final value: the alias index is 3 and the threshold value is 0.

Putting it all together, we map:

    [1/4, 2/4, 0, 1/4] -> ([0, 1, 1, 3], [0, 0, 0, 0])

For another example, we have:

    [1/4, 3/8, 1/8, 1/4] -> ([0, 1, 1, 3], [0, 0, 2, 0])

Parameters:

Name	Type	Description	Default
`input_list`	`list`	List of the relative probabilities of the target distibution.	required
`bit_precision`	`int`	Number of bits specifying the threshold values.	required

Returns:

Type	Description
`tuple[list, list]`	List of alias values and list of threshold values.

Note

One can pass any list of values, but this function first normalizes the list so that it corresponds to a probability distribution (that is, sum(normalized_input_list) == 1).