workbench_algorithms.utils.data_lookup_utils

Utility functions for data-lookup oracles.

validate_qrom_input_params

validate_qrom_input_params(data, b, lambda_val=None)

Checks that the supplied input parameters are valid for use in QROM.

There are several checks that can be done on the inputs to QROM (of all flavors) to ensure that sensible outputs are computed. The checks vary from warnings (for possibly unintentional but still valid operations such as insufficient precision bits resulting in integer overflow) to exceptions (for invalid operations such as non-power-of-2 lambda values).

Parameters:

Name	Type	Description	Default
`data`	`(PauliSum, List[int])`	Hamiltonian terms expressed as a PauliSum to load in or a list of bitvalues to load.	required
`b`	`int`	Number of bits to represent item in list.	required
`lambda_val`	`int`	Power-of-two knob to trade off between gates and qubits. If `None` (default), then optimal lambda is calculated.	`None`

Returns:

Type	Description
`int`	The processed lambda value.

partition_index_register

partition_index_register(index_reg, data, lambda_val)

Determine the SELECT and SwapUp subregisters of the index register.

Parameters:

Name	Type	Description	Default
`index_reg`	`Qubits`	Index register for QROM.	required
`data`	`list`	List of data to load.	required
`lambda_val`	`int`	Power-of-two knob to trade off between gates and qubits.	required

Returns:

Type	Description
`tuple`	A tuple of qubits objects corresponding to slices of the index register iterated over by SELECT and SwapUp. Depending on the if/else branches, one or the other (but never both) may evaluate to `None`.

load_all_at_once

load_all_at_once(target_reg, data, ctrl=0)

Load all values at the same time.

This simply corresponds to the case where the number of output registers you have equals the number of items to load. In this case, we are not actually "multiplexing", in the sense that we apply the data on the target reg without quantum conditioning.

Parameters:

Name	Type	Description	Default
`target_reg`	`Qubits`	Register where we load the data.	required
`data`	`list`	The data to load. It's actually a single item to be applied across all target qubits.	required
`ctrl`	`(Qubits, int)`	A register to control on. Defaults to zero, meaning no control.	`0`

elbow_subtractive_const

elbow_subtractive_const(num_elements, is_controlled=False)

Helper to calculate subtractive constant in SELECT cost.

Parameters:

Name	Type	Description	Default
`num_elements`	`int or Integer`	Number of elements in list to load.	required
`is_controlled`	`bool`	Whether the SELECT is controlled or not. Defaults to False.	`False`

Returns:

Type	Description
`int`	A constant for the cost expression of SELECT.

elbow_count_unoptimized

elbow_count_unoptimized(num_elements, is_controlled=False)

Helper to calculate subtractive constant in SELECT cost.

Parameters:

Name	Type	Description	Default
`num_elements`	`int or Integer`	Number of elements in list to load.	required
`is_controlled`	`bool`	Whether the SELECT is controlled or not. Defaults to False.	`False`

Returns:

Type	Description
`int`	A constant for the cost expression of SELECT.

symbolic_elbow_count_unoptimized

symbolic_elbow_count_unoptimized(
    num_elements, is_controlled=False
)

Helper to calculate subtractive constant in SELECT cost.

Parameters:

Name	Type	Description	Default
`num_elements`	`int`	Number of elements in list to load.	required
`is_controlled`	`bool`	Whether the SELECT is controlled or not. Defaults to False.	`False`

Returns:

Type	Description
`Function`	Callable to allow for calculating the subtractive constant symbolically.

symbolic_elbow_subtractive_const

symbolic_elbow_subtractive_const(
    num_elements, is_controlled=False
)

Helper to calculate subtractive constant in SELECT cost.

Parameters:

Name	Type	Description	Default
`num_elements`	`int`	Number of elements in list to load.	required
`is_controlled`	`bool`	Whether the SELECT is controlled or not. Defaults to False.	`False`

Returns:

Type	Description
`Function`	Callable to allow for calculating the subtractive constant symbolically.

gate_efficient_lambda

gate_efficient_lambda(num_elements, b)

Helper to handle choice of lambda value.

Parameters:

Name	Type	Description	Default
`num_elements`	`int`	Number of elements in list to load.	required
`b`	`int`	b-bit precision for elements in list.	required

Returns:

Type	Description
`int`	lambda value that yields minimal Toff count for QROM.

Notes

This computes the gate-optimal lambda assuming doing one Select-SwapUp pair.
If you are using dirty QROMs, you should double-check against the case of doing a naive QROM (i.e. not using SwapUp at all).

symbolic_gate_efficient_lambda

symbolic_gate_efficient_lambda(num_elements, b)

Symbolic mimic of the above function.

Parameters:

Name	Type	Description	Default
`num_elements`	`Parameter`	Number of elements in list to load.	required
`b`	`Parameter`	b-bit precision for elements in list.	required

Returns:

Type	Description
`Function`	Callable to allow for calculating the gate efficient lambda symbolically.

restack_bitlist

restack_bitlist(data, num_regs, b_of_p)

Given a list of different bitstring values, restack the bits into groups of OR'd bits.

The b_of_p and lambda values will affect the grouping. As an example, suppose I have a list of 4 values, each represented by 2 bits, and I use a lambda value of 2 to restack items:

bit_list = [2, 3, 3, 0] --> in binary --> [10, 11, 11, 00]

We then restack the list so that we now have:

new_list = [1011, 1100] --> in decimal --> [9, 12]

Parameters:

Name	Type	Description	Default
`data`	`list`	List of values indexed by the index register.	required
`num_regs`	`int`	Number of copies of output registers.	required
`b_of_p`	`int`	Number of bits in per datum.	required

Returns:

Type	Description
`list`	Restacked data.

get_fixup_addresses

get_fixup_addresses(
    mmt_result,
    restacked_list,
    b_of_p,
    num_regs,
    num_addresses,
)

Get list of QROM addresses requiring a phase fixup.

The measurement of the output/data register during the uncomputation of a data lookup circuit probabilistically flips the sign of some of the addresses encoded by the index register. To complete the routine, we must determine which addresses have had their sign flipped, and then perform a phase fixup for each one.

An address requires a phase fixup if its corresponding entry in the lookup table toggles an odd number of qubits that have also returned an "ON" measurement result.

Appendix C in arXiv:1902.02134 .

Parameters:

Name	Type	Description	Default
`mmt_result`	`int`	The measurement result returned after reading the output register in a QROM (including "clean" and "junk" qubits).	required
`restacked_list`	`list`	That same data after it has been restacked.	required
`b_of_p`	`int`	Number of bits used to represent each item in the original unscrambled list.	required
`num_regs`	`int`	Number of copies of the output reg; a tunable knob used to trade off between gates and qubits in QROMs.	required
`num_addresses`	`int`	The number of addresses that may possibly need a fixup. Typically equal to the length of the original input data.	required

Returns:

Type	Description
`list[int]`	A list of each address (int) that requires a phase fixup.

make_fixup_table

make_fixup_table(fixup_addresses, loaded_data)

Construct the fixup table for unloading data via QROM.

Each element is either a one or a zero, corresponding to whether a particular address requires or does not require an X gate to be applied by a smaller QROM to fix up the phase.

Parameters:

Name	Type	Description	Default
`fixup_addresses`	`list`	List of addresses that require phase fixups.	required
`loaded_data`	`list`	Data loaded by a QROM.	required

Returns:

Type	Description
`list`	List of zeros and ones where each value at a particular index corresponds to applying or not applying an X gate.