Skip to content

workbench_algorithms.subroutines.multiplexed_alias_sampling

Qubricks for implementing multiplexed alias sampling.

MultiplexedAliasSampling 

MultiplexedAliasSampling(
    multiplexed_usp, multiplexed_qrom, **kwargs
)

Bases: Qubrick

Implements the multiplexed alias sampling subroutine for multiplexed arbitrary state preparation.

Overview

The goal of this protocol is to take a list of lists of coefficients (probabilities corresponding to the squares of statevector amplitudes), load these coefficients using QROM, and prepare the state formed as the superposition of the states defined by each list of coefficients. This method is heavily based on the Alias Sampling technique used in quantum computing.

Steps of the Routine

Assuming familiarity with regular alias sampling, the steps are:

  1. Superposition Preparation:

    • MultiplexedUSP is used to prepare a superposition of uniform superposition states multiplexed over indices \( i \).
    • The dimension of the \( i \)th USP state corresponds to the length of the coefficients for the \( i \)th state that we want to prepare.

  2. Computing alt and keep Values:

    • We calculate the alt and keep values for each set of coefficients.
    • The size of the alt register is buffered to fit the largest value for all states in superposition.
    • This is managed by bit-shifting the keep values by this maximum value, similar to regular alias sampling.

  3. Multiplexor of Multiplexors:

    • We load the alt and keep values in superposition using the construction from arXiv:2007.14460.

  4. Partitioning QROM Output:

    • The multiplexed QROM output is partitioned into alt and keep registers.

  5. Creating a Coin Flip State:

    • Hadamards are applied to create a uniform superposition in the coin flip register.

  6. Conditional Swapping:

    • A comparator checks whether coin_toss_reg is less than keep_reg.
    • If true, the input prep_reg is swapped with alt_reg.
Note
  • This construction is based on step 3 in the THC paper.
  • As implemented, this routine is deterministic. However, in the reference above, it only succeeds conditioned on a success flag.
  • The success flag comes from the comparator in MultiplexedUSP.
  • Currently, this always succeeds because rotations are directly implemented.
  • Once synthesis is introduced, alias sampling will succeed only conditionally based on the USP.

Parameters:

Name Type Description Default
multiplexed_usp Qubrick

A subroutine implementation for multiplexed USP.

 required
multiplexed_qrom Qubrick

A subroutine implementation for multiplexed QROM.

 required
**kwargs dict[str, Any]

Other arguments to pass to the init.

 {}

compute 

compute(
    prep_reg,
    index,
    data_reg,
    data,
    bit_precision,
    inner_lambda_val=None,
    outer_lambda_val=None,
) -> None

Compute the multiplexed alias sampling.

Parameters:

Name Type Description Default
prep_reg Qubits

Register in which we want to prepare our superposition of states.

 required
index Qubits

Register containing the coefficients for the multiplexing loop.

 required
data_reg Qubits

Register with the different d values loaded in for computing the multiplexed USP.

 required
data List[List[int]]

A list of lists of coefficients representing each of the states to be prepared in superposition.

 required
bit_precision int

Number of bits of precision to be used in the alias sampling discretization procedure.

 required
inner_lambda_val int

Power-of-two knob to trade off between gates and qubits for the inner loop in multiplexed QROM. Defaults to None.

 None
outer_lambda_val int

Power-of-two knob to trade off between gates and qubits for the outer loop in multiplexed QROM. Defaults to None.

 None