Alias Sampling¶
The example we used so far was nice to establish some basic terminology. But let's be honest, it was contrived and not very practical. So now we'll take an existing example from a paper and try to get some resource estimations for it using bartiq!
For that we'll use Alias Sampling – an algorithm proposed by Babbush et al. in Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity ⧉. This is what the circuit looks like:
It comes from fig 11 from the original paper.
In this tutorial we won't be explaining how the algorithm works in details – partly because this is not the place, and partly because Craig Gidney already did it in his blogpost ⧉
So let's just briefly discuss what the building blocks we'll be using are:
- $UNIFORM_L$ – prepares a state which is a uniform superposition of $L$ states
- $H^{\otimes\mu}$ - uniform superposition of $2^{\mu}$ states
- QROM – loads data into "data" registers depending the value of $In_{\ell}$
- Comparator – Sets target register to 1 after comparing values of two input registers
- Controlled SWAP
Now, before we map all these subroutines to bartiq, it would be good to know what the costs of each of the subroutines are. After carefully reading the paper we can deduce what the costs are. But before we get there, let's define our symbols to have consistent naming. The authors use same letters for different variables in different figures, so it can get confusing without reading the paper carefully – that's why we'll stick to the naming from the figure above to keep things simple.
- $L$ – number of states we want to load.
- $\mu$ – bits of precision for coefficients we load.
- $k$ is the greatest common factor of $L$. This is not a widely mathematical operation, but fortunately in
bartiqwe have a shorthand for that, and we can say thatk = multiplicity(2, L). You can check how it's defined in sympy ⧉.
Given all that – what are the costs of our routines?
- Uniform: $8log_2(\frac{L}{k})$ T gates and a 2 rotation gates. It comes Fig 12 and its caption. We omit the $O(log(1/\epsilon)$ term, because it corresponds to those two rotations that we count separately.
- Hadamards: It doesn't require any T gates.
- QROM: $4L-4$ – this comes from Fig. 10.
- compare: $4\mu-4$ – this is not stated explicitly in the text, but comes from a careful analysis of the caption of Fig. 11.
- Swap: $O(log_2(L))$ – this is not stated explicitly in the text, but comes from a careful analysis of the caption of Fig. 11.
These expressions don't take into account some nuances – for example the uniform state preparation (USP) can be implemented as a layer of Hadamard gates if $L$ is a power of two.
Armed with this knowledge, we can now write each individual routine. However, since in this case all the routines have similar structure, we can use the following helper function:
NOTE:
Unfortunately the costs presented in this example are quite complicated. It would be great to just point you to a single place in the paper, get an expression and type it into bartiq. That's not the case though and if there are any mistakes or oversimplifications – please let us know! However, the fact that even a relatively simple routine presents such challenges, shows that we need better tools for working with quantum algorithms.
Also, as it turns out in the follow-up work not all the costs from this paper are correct, as some routines can be optimized. But explaining that is way beyond the scope of this tutorial.
usp_dict = {
"name": "usp",
"type": None,
"ports": [
{"name": "in", "direction": "input", "size": "R"},
{"name": "out", "direction": "output", "size": "R"},
],
"resources": [
{"name": "T_gates", "type": "additive", "value": "8*L/multiplicity(2,L)"},
{"name": "rotations", "type": "additive", "value": "2"},
],
"input_params": ["L"],
"local_variables": ["R=ceiling(log_2(L))"],
}
There are two things that we did here which might not be straight-forward.
- We used
ceilingfunction for the port size – that's because port sizes need to be integer. - We introduced new field –
local_variables. This allows us to define some "helper" variables, which are only used in the scope of this routine and save us some typing
had_dict = {
"name": "had",
"type": None,
"ports": [
{"name": "in", "direction": "input", "size": "N"},
{"name": "out", "direction": "output", "size": "N"},
],
}
qrom_dict = {
"name": "qrom",
"type": None,
"ports": [
{"name": "in_l", "direction": "input", "size": "R"},
{"name": "in_alt", "direction": "input", "size": "R"},
{"name": "in_keep", "direction": "input", "size": "mu"},
{"name": "out_l", "direction": "output", "size": "R"},
{"name": "out_alt", "direction": "output", "size": "R"},
{"name": "out_keep", "direction": "output", "size": "mu"},
],
"resources": [{"name": "T_gates", "type": "additive", "value": "4*L-4"}],
"input_params": ["L", "mu"],
"local_variables": ["R=ceiling(log_2(L))"],
}
compare_dict = {
"name": "compare",
"type": None,
"ports": [
{"name": "in_sigma", "direction": "input", "size": "mu"},
{"name": "in_keep", "direction": "input", "size": "mu"},
{"name": "in_flag", "direction": "input", "size": "1"},
{"name": "out_sigma", "direction": "output", "size": "mu"},
{"name": "out_keep", "direction": "output", "size": "mu"},
{"name": "out_flag", "direction": "output", "size": "1"},
],
"resources": [{"name": "T_gates", "type": "additive", "value": "4*mu-4"}],
"input_params": ["mu"],
}
swap_dict = {
"name": "swap",
"type": None,
"ports": [
{"name": "in_control", "direction": "input", "size": "1"},
{"name": "in_target_0", "direction": "input", "size": "X"},
{"name": "in_target_1", "direction": "input", "size": "X"},
{"name": "out_control", "direction": "output", "size": None},
{"name": "out_target_0", "direction": "output", "size": None},
{"name": "out_target_1", "direction": "output", "size": None},
],
"resources": [{"name": "T_gates", "type": "additive", "value": "O(log_2(X))"}],
"connections": [
{"source": "in_control", "target": "out_control"},
{"source": "in_target_0", "target": "out_target_0"},
{"source": "in_target_1", "target": "out_target_1"},
],
"input_params": ["X"],
}
We follow the same naming convention in all the subroutines to make things easier to follow. But in swap, we decided to use X instead of R=ceil(log_2(L)). Why?
It shows, that we can use whatever naming we want for any particular subroutine – we don't need to stick to one convention in all the subroutines. This is what you would often want to do in practice. If you would like to reuse this controlled swap in some other algorithm, a generic X is a much better choice than a very specific R.
Now that we have all these defined, let's construct the dictionary for the whole algorithm:
alias_sampling_dict = {
"name": "alias_sampling",
"children": [usp_dict, had_dict, qrom_dict, compare_dict, swap_dict],
"type": None,
"ports": [
{"name": "in_0", "direction": "input", "size": "R"},
{"name": "in_1", "direction": "input", "size": "mu"},
{"name": "in_2", "direction": "input", "size": "R"},
{"name": "in_3", "direction": "input", "size": "mu"},
{"name": "in_4", "direction": "input", "size": "1"},
{"name": "out_0", "direction": "output", "size": None},
{"name": "temp_0", "direction": "output", "size": None},
{"name": "temp_1", "direction": "output", "size": None},
{"name": "temp_2", "direction": "output", "size": None},
{"name": "temp_3", "direction": "output", "size": None},
],
"connections": [
{"source": "in_0", "target": "usp.in"},
{"source": "in_1", "target": "had.in"},
{"source": "in_2", "target": "qrom.in_alt"},
{"source": "in_3", "target": "qrom.in_keep"},
{"source": "in_4", "target": "compare.in_flag"},
{"source": "usp.out", "target": "qrom.in_l"},
{"source": "had.out", "target": "compare.in_sigma"},
{"source": "qrom.out_l", "target": "swap.in_target_0"},
{"source": "qrom.out_alt", "target": "swap.in_target_1"},
{"source": "qrom.out_keep", "target": "compare.in_keep"},
{"source": "compare.out_flag", "target": "swap.in_control"},
{"source": "swap.out_target_0", "target": "out_0"},
{"source": "compare.out_sigma", "target": "temp_0"},
{"source": "swap.out_target_1", "target": "temp_1"},
{"source": "compare.out_keep", "target": "temp_2"},
{"source": "swap.out_control", "target": "temp_3"},
],
"input_params": ["mu", "L"],
"local_variables": ["R=ceiling(log_2(L))"],
"linked_params": [
{"source": "L", "targets": ["usp.L", "qrom.L", "swap.X"]},
{"source": "mu", "targets": ["had.mu", "qrom.mu", "compare.mu"]},
],
}
alias_sampling_qref = {'version': 'v1', 'program': alias_sampling_dict}
from bartiq.integrations import qref_to_bartiq
uncompiled_routine = qref_to_bartiq(alias_sampling_qref)
from bartiq import compile_routine
compiled_routine = compile_routine(uncompiled_routine)
It went pretty well, let's see what's the we got:
for resource in compiled_routine.resources.values():
print(f"{resource.name}: {resource.value}")
T_gates: 4*L + 8*L/multiplicity(2, L) + 4*mu + swap.O(log2(L)) - 8 rotations: 2
In the caption of Fig. 11 we had: $4(L + \mu) + O(log_2(L))$, and these two expressions actually match pretty well.
- We have the $4(L + \mu)$ in both versions.
- We have a
swap.O(log_2(L))which corresponds toO(log_2(L)) - The
8*L/multiplicity(2, L)term is alsoO(log_2(L)) - Constant factor of
-8can also be incorporated inO(log_2(L))
Let's see how it looks like for some concrete values:
from bartiq import evaluate
assignments = {"L=120", "mu=8"}
evaluated_routine = evaluate(compiled_routine, assignments)
for resource in evaluated_routine.resources.values():
print(f"{resource.name}: {resource.value}")
T_gates: swap.O(log2(120)) + 824 rotations: 2
Well, we're almost there...
There's still swap.O() in our expression – what is it?
This is good opportunity to talk about how to substitute arbitrary functions in bartiq!
As you can see, the functions in bartiq are namespaced by default – that's why why we have swap.O rather than O. Alternatively, you can compile your routine with global_functions keyword. That will remove the swap. namespace.
compiled_routine = compile_routine(uncompiled_routine, global_functions=["O"])
for resource in compiled_routine.resources.values():
print(f"{resource.name}: {resource.value}")
T_gates: 4*L + 8*L/multiplicity(2, L) + 4*mu + O(log2(L)) - 8 rotations: 2
We still have big O there, but at least now we got rid of the swap. So let's assume the simplest case, i.e.O(x) = x.
def big_O(x):
return x
functions_map = {"O": big_O}
evaluated_routine = evaluate(compiled_routine, assignments, functions_map=functions_map)
for resource in evaluated_routine.resources.values():
print(f"{resource.name}: {resource.value}")
T_gates: log2(120) + 824 rotations: 2
And now we finally have some concrete numbers!
Summary¶
Let's sum up what we covered in this tutorial:
- How to take an algorithm from a paper and compile it into
bartiq - How to create a routine with multiple resources,
local_variablesand custom functions