RFC: Layerwise Richardson Extrapolation (LRE)

[purva-thakre]

Link to the RFC: https://docs.google.com/document/d/1yAQI8K8ShGI4jdn8OtpBv-H0X5SvkFVXA7DKtVOqm-8/edit?usp=sharing

[purva-thakre]

I am done with the first draft of the RFC in case anyone else wants to take a look at it. Based on a conversation we had over Discord, @vprusso plans to review the RFC by next week.

Note that this is only the RFC for LRE.

Noise-aware folding from https://arxiv.org/abs/2401.12495 will have a separate RFC.

[purva-thakre]

@andreamari @natestemen I discussed the RFC with @vprusso this afternoon and both of us were unsure of how to design the default inputs for the main function. Would appreciate some feedback on this.

The way I understand the results of the LRE paper, multiple noise-scaled versions of the input circuit could be created in 2 different ways. A user could provide:

1. a list of vectors of scale factors as an input along with the extrapolation order d or
2. provide the extrapolation order d along with some int value for the minimum_noise_scaling_gap.

If Option 1 is used, we would have to create a function to check we get a square sample matrix with the desired extrapolation order and the vectors of scale factors. In this case, we would also have to make sure the user does not provide us with a value for minimum_noise_scaling_gap.

If Option 2 is used, the linked Jupyter notebook has 2 functions defined on lines 74 and 75 that will create a list of vectors of scale factors for the noise scaling function. Note that the arXiv upload uses the label minimum_noise_scaling_gap whereas the notebook uses the label fold_multiplier.

Do we want to allow both options or prefer one over the other?

[natestemen]

Option 1 seems preferable to me since it seems to give more control to the user. If that isn't quite correct, let me know! So that I understand properly, the main concern is that it would be possible to pass in scale_factors: list[list[float]] and extrapolation_order: int such that combine for an invalid extrapolation? What are the constraints on extrapolation_order given scale_factors is an $n \times m$ matrix?

I think we should start with a single API. Start simple, add functionality later (if needed).

[purva-thakre]

I think we should start with a single API. Start simple, add functionality later (if needed).

If this is the case, starting with Option 2 is better. scale_factors have to follow a pattern similar to what's shown below. LRE paper refers to this as graded lexicographic order.

For extrapolation_order = 2 and num_layers_input_circuit = 2, the graded lexicographic order looks like this:

Giving control over to the user wouldn't work unless they manually figure out the ordering of the monomial terms. The function compute_folding_patterns does this for the user.

Based on the above screenshot, the first scale factor vector would have no scaling for the input layers, the second scale factor vector would scale the first layer only, the third scale factor vector would scale the second layer only, and so on.

[natestemen]

I'm a little confused. My understanding of this technique as described in section II.B of the LRE paper is that after a collection of vectors are used to collect $\langle O(\boldsymbol{\lambda}_i)\rangle$ values then this set $\mathcal{M}(\boldsymbol{\lambda}, d)$ gets created. I would have thought (maybe naively) that this could be hidden from the user. Can you help me understand why it can't be?

If this would be easier to explain on a call happy to do that, or on the google doc!

[andreamari]

I don't know if it helps, but there is a kind of condensed workflow of LRE at page 5 of the LRE paper in which it is perhaps more clear what are the input hyperparameters and what could be internally generated by Mitiq.

In particular, there is a recommended choice of scale factor vectors in Eq. (21) that could be internally generated by Mitiq.

A more general choice of scale factors is in principle possible but there are two constraints:

1. The number $M$ of scale factor vectors is fixed and must be equal to (11).
2. The determinant of the sample matrix $A$ must be different from zero, i.e., Eq. (18).

A way of finding a good balance between simplicity and flexibility, that we also applied for other techniques, is to have simple options in the high-level execute_with_xxx function but more flexible options for low-level functions.

E.g., it would be nice if expert users had low-level utilities at their disposal such that they could manually choose arbitrary custom strategies. But it is probably ok to keep execute_with_xxx less flexible, but easy for non experts.