Rewriting symbolic expressions¶
As quantum algorithms increase in complexity their symbolic resource expressions similarly become more complex. For a state of the art algorithm like double factorization ⧉ the resource expressions can be almost impossible to parse, due to the sheer number of terms and symbols.
bartiq includes a set of utilities for manipulating symbolic expressions – rewriting them to make them simpler and easier to analyze. They're known as rewriters; this functionality is contained in the analysis submodule, and backend-specific rewriters can be imported directly.
In [1]:
Copied!
from bartiq.analysis import sympy_rewriter
from bartiq.analysis import sympy_rewriter
NOTE:
This tutorial, as well as all the other tutorials, has been written as a jupyter notebook.
If you're reading it online, you can either keep reading, or go to docs/tutorials to explore them in a more interactive way!
Here we will provide a brief demo of how to use rewriters applied to a state-of-the-art algorithm in the literature.
Double factorization (DF) is an important subroutine in quantum computations of chemistry. We will not explore the construction of the algorithm nor the intricacies of the circuit itself due to its complexity. Instead, we can load in a pre-built bartiq CompiledRoutine object representing this algorithm.
In [2]:
Copied!
from bartiq import CompiledRoutine, sympy_backend
import yaml
with open("../data/double_factorization_compiled.yaml", "r") as f:
df = CompiledRoutine.from_qref(yaml.safe_load(f), sympy_backend)
from bartiq import CompiledRoutine, sympy_backend
import yaml
with open("../data/double_factorization_compiled.yaml", "r") as f:
df = CompiledRoutine.from_qref(yaml.safe_load(f), sympy_backend)
This CompiledRoutine has the following associated resources:
In [3]:
Copied!
list(df.resource_values.keys())
list(df.resource_values.keys())
Out[3]:
['active_volume', 'gidney_lelbows', 'gidney_relbows', 'measurements', 'ppms', 'pprs', 'rotations', 't_gates', 'toffs']
We choose not to display all of the expressions due to their sheer complexity. Instead, let's see how many $T$-gates --- a common bottleneck in fault tolerant quantum computing implementations --- this algorithm requires:
In [4]:
Copied!
df.resource_values["t_gates"]
df.resource_values["t_gates"]
Out[4]:
$\displaystyle \left(N_{spatial} - 1\right) \theta\left(- \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right) + 2.5, 0\right) \theta\left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \left(N_{spatial} - 1\right) \theta\left(- \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right) + 2.5, 0\right) \theta\left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \theta\left(2.5 - \max\left(b_{as}, b_{givens}, b_{mas}\right), 0\right) \theta\left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \theta\left(\max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \theta\left(- \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right) + 2.5, 0\right) \theta\left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \left(24 \left(\min\left(M_{r} - \left(1 \bmod \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil\right) + 1, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)\right)\right)$
Needless to say, it is difficult to extract any useful insights from this expression.
The actual meaning of the symbols involved is out of scope for this tutorial, but $N_{spatial}$, $R$ and $M_r$ are related to the physical system being considered, and $b_{as}$, $b_{mas}$ and $b_{givens}$ are bits of precision parameters we are free to modify prior to runtime.
Here we will show that rewriters can be used to make this expression useful!
The rewriter dataclass structure is designed with interactive environments (such as Jupyter notebooks) in mind, and so their __repr__ method returns a $\LaTeX$-friendly expression: for practical purposes this is akin to wrapping the sympy expression in a more user-friendly class.
First, let's create a rewriter object for the $T$-gate expression above.
In [5]:
Copied!
tgates = sympy_rewriter(df.resource_values["t_gates"])
tgates
tgates = sympy_rewriter(df.resource_values["t_gates"])
tgates
Out[5]:
$\displaystyle \left(N_{spatial} - 1\right) \theta\left(- \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right) + 2.5, 0\right) \theta\left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \left(N_{spatial} - 1\right) \theta\left(- \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right) + 2.5, 0\right) \theta\left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \theta\left(2.5 - \max\left(b_{as}, b_{givens}, b_{mas}\right), 0\right) \theta\left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \theta\left(\max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \theta\left(- \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right) + 2.5, 0\right) \theta\left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right) - 2.5, 0\right) + \left(24 \left(\min\left(M_{r} - \left(1 \bmod \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil\right) + 1, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)\right)\right)$
Rewriters contain a number of helpful methods, but only some of these work to modify the input expression. They are:
.simplify(): Run the built-in backend simplify functionality..expand(): Run the built-in backend expand functionality; expand all brackets..assume(assumption): Add an assumption onto a variable or expression..substitute(expr, replace_with): Perform a substitution in the expression.
There are also a number of methods that don't rewrite the expression, but act to provide information.
.focus(symbols): Only show terms in the expression that contain specific symbols..all_functions_and_arguments(): Show a set of all functions and their arguments in the expression, including nested functions (sympy only)..list_arguments_of_function(function_name): Show a list of all the unique arguments of a given function (sympy only).
A more complete overview of the functionality of rewriters can be found on the Rewriter page of Concepts.
Looking at the $T$-gates expression above, note that the function $$\max\left(b_{as}, b_{givens}, b_{mas}\right),$$ shows up repeatedly. We don't want to make any assumptions about which of these will be the maximum, but to simplify the expression we can substitute this for another symbol:
In [6]:
Copied!
tgates = tgates.substitute("max(b_as, b_givens, b_mas)", "B")
tgates
tgates = tgates.substitute("max(b_as, b_givens, b_mas)", "B")
tgates
Out[6]:
$\displaystyle \left(N_{spatial} - 1\right) \theta\left(- B - \max\left(0, - B + b_{mas}\right) + 2.5, 0\right) \theta\left(B + \max\left(0, - B + b_{mas}\right) + \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right) - 2.5, 0\right) + \left(N_{spatial} - 1\right) \theta\left(- B - \max\left(0, - B + b_{mas}\right) - \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right) - \max\left(0, - B + b_{mas} - \max\left(0, - B + b_{mas}\right) - \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right)\right) + 2.5, 0\right) \theta\left(B + \max\left(0, - B + b_{mas}\right) + \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right) + \max\left(0, - B + b_{mas} - \max\left(0, - B + b_{mas}\right) - \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right)\right) + \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right) - \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right) - \max\left(0, - B + b_{mas} - \max\left(0, - B + b_{mas}\right) - \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right)\right)\right) - 2.5, 0\right) + \theta\left(2.5 - B, 0\right) \theta\left(B + \max\left(0, - B + b_{mas}\right) - 2.5, 0\right) + \theta\left(B - 2.5, 0\right) + \theta\left(- B - \max\left(0, - B + b_{mas}\right) - \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right) + 2.5, 0\right) \theta\left(B + \max\left(0, - B + b_{mas}\right) + \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right) + \max\left(0, - B + b_{mas} - \max\left(0, - B + b_{mas}\right) - \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{mas}\right)\right)\right) - 2.5, 0\right) + \left(24 \left(\min\left(M_{r} - \left(1 \bmod \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil\right) + 1, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)\right)\right)$
There are still a lot of max functions, so we can print all the arguments that occur:
In [7]:
Copied!
tgates.list_arguments_of_function("max")
tgates.list_arguments_of_function("max")
Out[7]:
[(0, -B + b_mas), (0, -B + b_mas - Max(0, -B + b_mas) - Max(0, -B + b_givens - Max(0, -B + b_mas))), (0, -B + b_givens - Max(0, -B + b_mas)), (0, -B + b_givens - Max(0, -B + b_mas) - Max(0, -B + b_givens - Max(0, -B + b_mas)) - Max(0, -B + b_mas - Max(0, -B + b_mas) - Max(0, -B + b_givens - Max(0, -B + b_mas))))]
$\max(0,-B + b_{mas})$ occurs in all of these arguments! Since we defined $B:=\max\left(b_{as}, b_{givens}, b_{mas}\right)$, we know that $-B + b_{mas} \leq 0$, and therefore $\max(0,-B + b_{mas})\equiv 0$. To pass this information into our expression, we add an assumption onto this expression:
In [8]:
Copied!
tgates = tgates.assume("b_mas - B <= 0")
tgates
tgates = tgates.assume("b_mas - B <= 0")
tgates
Out[8]:
$\displaystyle \left(N_{spatial} - 1\right) \theta\left(2.5 - B, 0\right) \theta\left(B + \max\left(0, - B + b_{givens}\right) - 2.5, 0\right) + \left(N_{spatial} - 1\right) \theta\left(- B - \max\left(0, - B + b_{givens}\right) + 2.5, 0\right) \theta\left(B + \max\left(0, - B + b_{givens}\right) + \max\left(0, - B + b_{givens} - \max\left(0, - B + b_{givens}\right)\right) - 2.5, 0\right) + \theta\left(2.5 - B, 0\right) \theta\left(B - 2.5, 0\right) + \theta\left(B - 2.5, 0\right) + \theta\left(- B - \max\left(0, - B + b_{givens}\right) + 2.5, 0\right) \theta\left(B + \max\left(0, - B + b_{givens}\right) - 2.5, 0\right) + \left(24 \left(\min\left(M_{r} - \left(1 \bmod \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil\right) + 1, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)\right)\right)$
Note we can't add an assumption like b_mas <= B --- the sympy symbolic engine does not support relationships between symbols. Now if we print the arguments of max, the list will be updated:
In [9]:
Copied!
tgates.list_arguments_of_function("max")
tgates.list_arguments_of_function("max")
Out[9]:
[(0, -B + b_givens - Max(0, -B + b_givens)), (0, -B + b_givens)]
We can do the same simplification here with another assumption:
In [10]:
Copied!
tgates = tgates.assume("b_givens - B <= 0")
tgates
tgates = tgates.assume("b_givens - B <= 0")
tgates
Out[10]:
$\displaystyle 2 \left(N_{spatial} - 1\right) \theta\left(2.5 - B, 0\right) \theta\left(B - 2.5, 0\right) + 2 \theta\left(2.5 - B, 0\right) \theta\left(B - 2.5, 0\right) + \theta\left(B - 2.5, 0\right) + \left(24 \left(\min\left(M_{r} - \left(1 \bmod \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil\right) + 1, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)\right)\right)$
The expression is already much easier to parse! Note there are a number of Heaviside ($\theta$) functions that could be simplified. Because our $b_x$ variables are bits of precisions, we know they are positive and real-valued, and for practical purposes they will be greater than 5 or so. We can add this onto our variable $B$:
In [12]:
Copied!
tgates = tgates.assume("B>5")
tgates
tgates = tgates.assume("B>5")
tgates
Out[12]:
$\displaystyle \left(24 \left(\min\left(M_{r} - \left(1 \bmod \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil\right) + 1, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)\right)\right) + 1$
There is one more simplification we can make: the mod function has the following arguments:
In [13]:
Copied!
tgates.list_arguments_of_function("mod")
tgates.list_arguments_of_function("mod")
Out[13]:
[(1, ceiling(log2(2**(ceiling(log2(M_r)) + 1)*M_r*(R - 1) + 2**(ceiling(log2(M_r)) + ceiling(log2(M_r*(R - 1))) + 1)*(2**(b_mas + 1) - 1) + 2*M_r + 1)))]
Where mod(a,b)is printed as $a~\mathrm{mod}(b)$. Obviously $1~\mathrm{mod}(b)=1$ for $b>1$. Our variables are all positive and real valued, so it's a safe assumption to say that the second argument to mod is greater than 1. However, it would be tedious to type that whole argument out! As an alternative we can apply a wildcard substitution.
For sympy rewriters symbols can be marked as wild during substitutions. Wild symbols will match to anything, and constitutes pattern matching rather than one-to-one substitutions. To avoid having to type out the second argument of the mod function, we can simply say:
"any
modfunction where 1 is the first argument should be replaced by 1, regardless of the second argument".
To mark a symbol as 'wild', we preface it with a $:
In [14]:
Copied!
tgates = tgates.substitute("mod(1, $x)", "1")
tgates
tgates = tgates.substitute("mod(1, $x)", "1")
tgates
Out[14]:
$\displaystyle 24 \min\left(M_{r}, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) + 1$
This is an extremely tidy representation of the number of $T$-gates in our double factorization algorithm.
Wildcard substitutions are extremely powerful, but should be used with caution! There are a number of caveats listed in the Substitutions subsection on the rewriter Concepts page.
As mentioned rewriters are designed with interactive environments in mind, so there is no need to constantly redefine the variable. All of our previous instructions can be done in a single cell via method chaining:
In [ ]:
Copied!
tgates = (
sympy_rewriter(df.resource_values["t_gates"])
.substitute("max(b_as, b_givens, b_mas)", "B")
.assume("b_mas - B <= 0")
.assume("b_givens - B <= 0")
.assume("B>5")
.substitute("mod(1, $b)", "1")
)
tgates
tgates = (
sympy_rewriter(df.resource_values["t_gates"])
.substitute("max(b_as, b_givens, b_mas)", "B")
.assume("b_mas - B <= 0")
.assume("b_givens - B <= 0")
.assume("B>5")
.substitute("mod(1, $b)", "1")
)
tgates
Out[ ]:
$\displaystyle 24 \min\left(M_{r}, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) + 1$
Each method call returns a new instance of the rewriter, and results are not stored unless a new variable is defined on the output. This makes rewriting expressions extremely dynamic, with results shown immediately via the _repr_.
Rewriting routines and reusing history¶
While the sympy_rewriter function acts only on a single expression, we are able to take the instructions we've applied and apply them to all expressions in a bartiq CompiledRoutine object!
To see all the instructions previously applied to an expression, we can call the history() method:
In [17]:
Copied!
tgates.history()
tgates.history()
Out[17]:
[Initial(), Substitution(expr='max(b_as, b_givens, b_mas)', replacement='B', backend='SympyBackend'), Assumption(symbol_name='b_mas-B', comparator='<=', value=0), Assumption(symbol_name='b_givens-B', comparator='<=', value=0), Assumption(symbol_name='B', comparator='>', value=5), Substitution(expr='mod(1, $b)', replacement='1', backend='SympyBackend')]
To apply each of these instructions onto every expression in the routine hierarchy, we can import another function:
In [19]:
Copied!
from bartiq.analysis import rewrite_routine_resources
from bartiq.analysis import rewrite_routine_resources
We can create a new routine object by combining our instructions with our double factorization routine. We are able to choose which resources we apply the instructions to, and we've chosen just the t_gates resource here.
In [20]:
Copied!
rewritten_df = rewrite_routine_resources(routine=df, resources="t_gates", instructions=tgates.history())
rewritten_df.resource_values["t_gates"]
rewritten_df = rewrite_routine_resources(routine=df, resources="t_gates", instructions=tgates.history())
rewritten_df.resource_values["t_gates"]
Out[20]:
$\displaystyle 24 \min\left(M_{r}, \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) + 1$
We applied all of the instructions in the history of our tgates variable to the t_gates resource in every subroutine, at every level of the routine hierarchy. We can apply this to more resources if we wish:
In [28]:
Copied!
rewritten_df_more_resources = rewrite_routine_resources(
routine=df, resources=["t_gates", "toffs"], instructions=tgates.history()
)
rewritten_df_more_resources.resource_values["toffs"]
rewritten_df_more_resources = rewrite_routine_resources(
routine=df, resources=["t_gates", "toffs"], instructions=tgates.history()
)
rewritten_df_more_resources.resource_values["toffs"]
Out[28]:
$\displaystyle 2 B \left(2 N_{spatial} - 2\right) + 4 N_{spatial} + 2 b_{givens} \left(-1 + \frac{b_{givens} \left(N_{spatial} - 1\right) \left(\lambda - 1\right) + b_{givens} \left(N_{spatial} - 1\right)}{b_{givens} \left(N_{spatial} - 1\right)}\right) \left(N_{spatial} - 1\right) + \left(-2 + \frac{2 \left(b_{mas} + \left(b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) \left(\lambda - 1\right) + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)}{b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil}\right) \left(b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) + \left(-1 + \frac{2 b_{as} + 2 \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil}{b_{as} + \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil}\right) \left(b_{as} + \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil\right) + \left(\frac{\left(\lambda - 1\right) \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil}{\left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil} - 1\right) \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil + 4 \theta\left(\left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil - 1.5, 0\right) + \theta\left(\left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil - 0.5, 0\right) + 2 \theta\left(\left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil - \operatorname{ntz}{\left(R + 1 \right)} - 1.5, 0\right) + 4 \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil + 2 \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil$
This expression for the Toffolis is slightly easier to parse than the original:
In [29]:
Copied!
df.resource_values["toffs"]
df.resource_values["toffs"]
Out[29]:
$\displaystyle 4 N_{spatial} + 2 b_{givens} \left(-1 + \frac{b_{givens} \left(N_{spatial} - 1\right) \left(\lambda - 1\right) + b_{givens} \left(N_{spatial} - 1\right)}{b_{givens} \left(N_{spatial} - 1\right)}\right) \left(N_{spatial} - 1\right) + \left(-2 + \frac{2 \left(b_{mas} + \left(b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) \left(\lambda - 1\right) + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)}{b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil}\right) \left(b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) + \left(-1 + \frac{2 b_{as} + 2 \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil}{b_{as} + \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil}\right) \left(b_{as} + \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil\right) + \left(2 N_{spatial} - 2\right) \left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \left(2 N_{spatial} - 2\right) \left(\max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{mas} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(0, b_{givens} - \max\left(0, b_{mas} - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) - \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \max\left(b_{as}, b_{givens}, b_{mas}\right)\right) + \left(\frac{\left(\lambda - 1\right) \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil}{\left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil} - 1\right) \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil + 4 \theta\left(\left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil - 1.5, 0\right) + \left(\theta\left(\left(1 \bmod \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil\right) + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil - 1.5, 0\right)\right) + 2 \theta\left(\left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil - \operatorname{ntz}{\left(R + 1 \right)} - 1.5, 0\right) + 4 \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil + 2 \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil$
We targeted our substitutions and assumptions for the t_gates resource expression, so toffs would likely need more bespoke instructions. If we wanted to start our analysis of toffs from this point though, we can skip the step where we apply the instructions to a whole routine, and instead instantiate a sympy_rewriter with the with_instructions method:
In [30]:
Copied!
toffs = sympy_rewriter(df.resource_values["toffs"]).with_instructions(tgates.history())
toffs
toffs = sympy_rewriter(df.resource_values["toffs"]).with_instructions(tgates.history())
toffs
Out[30]:
$\displaystyle 2 B \left(2 N_{spatial} - 2\right) + 4 N_{spatial} + 2 b_{givens} \left(-1 + \frac{b_{givens} \left(N_{spatial} - 1\right) \left(\lambda - 1\right) + b_{givens} \left(N_{spatial} - 1\right)}{b_{givens} \left(N_{spatial} - 1\right)}\right) \left(N_{spatial} - 1\right) + \left(-2 + \frac{2 \left(b_{mas} + \left(b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) \left(\lambda - 1\right) + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right)}{b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil}\right) \left(b_{mas} + \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil\right) + \left(-1 + \frac{2 b_{as} + 2 \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil}{b_{as} + \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil}\right) \left(b_{as} + \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil\right) + \left(\frac{\left(\lambda - 1\right) \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil}{\left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil} - 1\right) \left\lceil{\operatorname{log}_{2}{\left(2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + 1} M_{r} \left(R - 1\right) + 2^{\left\lceil{\operatorname{log}_{2}{\left(M_{r} \right)}}\right\rceil + \left\lceil{\operatorname{log}_{2}{\left(M_{r} \left(R - 1\right) \right)}}\right\rceil + 1} \left(2^{b_{mas} + 1} - 1\right) + 2 M_{r} + 1 \right)}}\right\rceil + 4 \theta\left(\left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil - 1.5, 0\right) + \theta\left(\left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil - 0.5, 0\right) + 2 \theta\left(\left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil - \operatorname{ntz}{\left(R + 1 \right)} - 1.5, 0\right) + 4 \left\lceil{\operatorname{log}_{2}{\left(R \right)}}\right\rceil + 2 \left\lceil{\operatorname{log}_{2}{\left(R + 1 \right)}}\right\rceil$
Summary¶
Rewriters are a powerful tool for simplifying symbolic expressions. This tutorial has only shown a brief preview of the utility available in rewriters, and we invite the reader to inspect the dedicated Rewriter summary page as well as the API reference.