workbench_algorithms.utils.antisymmetrization_utils
Utils for antisymmetrization routines.
permutation_parity
Determine the parity of the given permutation.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
permutation
|
List[int]
|
List of integers with no collisions. |
required |
Returns:
| Type | Description |
|---|---|
bool
|
True if even parity, False if odd parity. |
prob_no_collision
Probability of finding no collisions in measured seed register.
We can calculate the probability of observing no collisions, and thus, the probability of continuing the antisymmetrization procedure after measuring all of the seed registers as a function of the number of registers we sort, and a user-input value, which one can tune to the probability.
In https://arxiv.org/abs/1711.10460, the probability of observing a collision is upperbounded by the expression shown in Eqn. (A5):
\(\eta (\eta - 1) / 2f\)
where \(\eta\) is the number of registers we are sorting, and \(f\) is a tunable knob. The probability of not observing a collision is simply 1 minus this quantity. This upperbound is valid only for values of \(f >= \eta\).
Ensuring a probability of success of at least 1/2 for all \(\eta\) requires \(f = \eta^2\).
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
num_regs
|
int
|
Number of registers we are sorting. |
required |
prob_knob
|
int
|
A tunable knob to determine the probability of success. |
required |
Returns:
| Type | Description |
|---|---|
float
|
The probability of not observing a collision. |
seed_reg_size
Compute the size of each seed register.
The size per seed register is determined by the tunable knob value chosen to parametrize the probability of success of the seed reg sort.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
prob_knob
|
int
|
A tunable knob to determine the probability of success. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Size of each seed register. |
num_comps_upper_bound
Upper bound on the number of comparators used in a bitonic sort.
The expression can be found on Wikipedia: https://en.wikipedia.org/wiki/Bitonic_sorter
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
num_regs
|
int
|
Number of registers we are sorting. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Upper bound of number of comparators used. |
num_comps_lower_bound
Lower bound on the number of comparators used in a bitonic sort.
The expression can be found on Wikipedia: https://en.wikipedia.org/wiki/Bitonic_sorter
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
num_regs
|
int
|
Number of registers we are sorting. |
required |
Returns:
| Type | Description |
|---|---|
int
|
Lower bound of number of comparators used. |
total_sort_num_comps
Numerically determine the number of comparators in a bitonic sort.
In addition to upper and lower bounds on the number of necessary comparators, we can determine the exact number used numerically by accumulating a counter and recursively calling this function in the same call-path structure used by the sorting methods in the bitonic sort Qubrick.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
num_regs
|
int
|
Number of registers we are sorting. |
required |
low
|
(int, Optional)
|
Index at which the sequence to be sorted starts. Defaults to (and starts at) 0. |
0
|
cnt
|
(Optional, int)
|
Number of elements to be sorted. Defaults to (and starts
at) |
None
|
acc
|
(int, Optional)
|
An accumulator we simply increment to keep track of the number of comparators. Defaults to (and starts at) 0. |
0
|
Returns:
| Type | Description |
|---|---|
int
|
The exact number of comparators used in a bitonic sort. |