antisymmetrization_utils
antisymmetrization_utils ¶
num_comps_lower_bound ¶
Lower bound on the number of comparators used in a bitonic sort.
The expression can be found in the Wikipedia article on 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. |
num_comps_upper_bound ¶
Upper bound on the number of comparators used in a bitonic sort.
The expression can be found in the Wikipedia article on 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. |
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 "Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians" (arXiv:1711.10460 ⧉), the probability of observing a collision is upperbounded by the expression shown in Eqn. (A5):
Here \(\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 upper bound 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. |
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. |