Alias Sampling vs LKS Quantum Resource Estimation¶
In this notebook we will look at how to use the the witness filter to perform QRE for Alias Sampling and LKS.
import numpy as np
# import QPU setups from workbench
from psiqworkbench import QPU, Qubits
# import QROM instances
from workbench_algorithms import (
USP,
DataLookupClean,
SwapUp,
BinaryTreeSelect, # using the optimized elbows from Babbush et al. and LKS's SELECT-SWAP trick for better quantum resource estimation
)
# import utility functions
from workbench_algorithms.experimental.utils import (
StatePrepData,
LKS_get_b_from_epsilon,
SupportedOps,
alias_sampling_get_b_from_epsilon,
)
# import experimental Qubricks
from workbench_algorithms.experimental.subroutines import (
AliasSampling,
MultiplexedSingleQubitRotationViaQROM,
RotationViaPhaseGradientAddition,
ArbitraryStatePrep,
ProgrammableRotArray,
)
For apples-to-apples comparison between Alias Sampling we will only feed in input with positive real amplitudes.
Now let's create a larger quantum state to perform some QRE. We will now try to generate the circuit (but not simulating the state vector result) for a quantum state with $L = 2^{12} = 4096$ amplitudes, and set $\epsilon = 10^{-10}$.
n = 12
epsilon = 1e-10
num_coeffs = 2 ** n
np.random.seed(37)
coeffs = [np.random.rand() for _ in range(num_coeffs)]
Now let's use the alias_sampling_get_b_from_epsilon() utility function to give us the required precision bit number $\mu$ (which gives a total of $\log(L) + \mu$ effective precision bits) for Alias Sampling. We also print out the actual l2-norm difference.
mu, _, as_actual_diff = alias_sampling_get_b_from_epsilon(coeffs, epsilon, return_theory_bound_and_actual_diff=True)
print(mu)
print(as_actual_diff)
36 9.842632517667865e-11
Similarly, we can use the LKS_get_b_from_epsilon() utility function to give us the required precision bit number $b$ (which is essentially the effective precision bits) for LKS:
b, _, lks_actual_diff = LKS_get_b_from_epsilon(coeffs, epsilon, return_theory_bound_and_actual_diff=True)
print(b)
print(lks_actual_diff)
35 9.216797079981414e-11
Note that it is typically impossible to make the two actual diff exactly match each other due to the entire differen ways the circuits are constructed. Here we deliberately choose an instance where the actual l2 error for LKS is smaller than that of Alias Sampling but also quite close.
Next we can set up some data and circuit instance that can be shared by AS and LKS:
# use the same data class (interoperability!)
data = StatePrepData(coeffs, epsilon=epsilon)
num_prep = int(np.ceil(np.log2(len(coeffs))))
# use the same QROM instance (Select with SEL-SWAP trick)
qrom_instance = DataLookupClean(select=BinaryTreeSelect(), swap_up=SwapUp())
We now use the witness filter and call the metrics function to perform QRE for Alias Sampling. Note that we only construct the circuit but not actually simulating it (it would be impossible to do so anyway since we will have hundreds of qubits!)
as_qc = QPU(filters=[">>witness>>"])
as_qc.reset(int(np.ceil(np.sqrt(2 ** n)) * 100)) # need to setup larger ancilla qubit space to hold ancilla qubits from the SELECT-SWAP trick in LKS to optimize Toffoli
as_target_reg = Qubits(num_prep, "target_reg", as_qc)
usp_instance = USP()
as_state_prep = AliasSampling(qrom=qrom_instance, usp=usp_instance)
as_state_prep.compute(as_target_reg, data)
as_costs = as_qc.metrics() # call metrics() to collect the dictionary of resource count
print(as_costs)
{'qubit_highwater': 404, 'toffoli_count': 893, 'measurement_count': 881, 'rotation_count': 0, 't_count': 0, 'active_volume': 197590, 'total_num_ops': 2607}
We can see that the majority of the cost now comes from CNOT (clifford_count) of $O(2^n)$. The Toffoli cost is marginal after the SELECT-SWAP trick that reduces it from $O(2^n)$ down to $O(\sqrt{2^n})$.
Do the same thing for LKS:
lks_qc = QPU(filters=[">>witness>>"]) # setting to the witness filter so that we only construct the circuit but not actually simulating it
lks_qc.reset(int(np.ceil(np.sqrt(2 ** n)) * 100)) # need to setup larger ancilla qubit space to hold ancilla qubits from the SELECT-SWAP trick in LKS to optimize Toffoli
lks_target_reg = Qubits(num_prep, "target_reg", lks_qc)
rotation_qbk_instance = RotationViaPhaseGradientAddition()
mplxr_instance = MultiplexedSingleQubitRotationViaQROM(qrom=qrom_instance, rotation_qbk=rotation_qbk_instance)
mux_rot = ProgrammableRotArray(op=SupportedOps.RY, mplxr=mplxr_instance) # define the uniformly controlled rotations
lks_state_prep = ArbitraryStatePrep(mux_rot) # finally, build the arbitrary state prep
lks_state_prep.compute(lks_target_reg, data)
# note that we skipped the uncomputation for the Fourier state for a "fair" comparison with alias sampling which comtains garbage
# in principle we should also skip the uncomputation for each of the SELECT-SWAP (or do some tricks to merge different QROMs), will need to figure this out
# qc.release_all_rotation_catalyst_qubits()
lks_costs = lks_qc.metrics()
print(lks_costs)
{'qubit_highwater': 342, 'toffoli_count': 2111, 'measurement_count': 2471, 'rotation_count': 34, 't_count': 1, 'active_volume': 265480.5, 'total_num_ops': 8332}
We can see that the majority of the cost now also comes from CNOT (clifford_count) of $O(2^n)$.
Comparing to Alias Sampling (feeding in an input of the same size), we can see that there is more Toffoli gates required because we will need to run $n$ QROMs (rather than $1$ in Alias Sampling) which amount to roughly $\sum_{l=0}^{n}\sqrt{2^{l-1}} \approx (\sqrt{2} + 1)\sqrt{2^n}$, 2.4 times than that of the Toffoli gates required for Alias Sampling's QROM. However, the Active Volume might be smaller because the effective bits of precision is smaller than that of Alias Sampling.
This difference will become even larger for larger input instances (since there the CNOT cost will completely dominate). See the table in the design doc for a full-scale comparison, and try play it yourself :)