[Feature Request] Fully automatic resource estimation caching
- Dominant language
- Rust
- Stars
- 1k
- Forks
- 212
- Avg merge
- 3d 8h
- Merged PRs (30d)
- 65
Description
Quantum circuits often have loops that on each iteration apply essentially the same gate. Currently, when running Q# resource estimator on such a loop, it will be decomposed down to primitive gates, which can take very long time.
`Std.ResourceEstimation` has some useful tools to speed this up by caching some resource estimates such as BeginEstimateCaching and RepeatEstimates, but these have limitations:
* User has to add extra code just for resource estimation.
* `RepeatEstimates` only runs the iteration once and multiplies the result by number of iteration, so when run on simulator this is incorrect.
* `BeginEstimateCaching` requires the user to manually convert parameters on which RE depends into pair (String, Int).
* It is easy to make a mistake and use these functions when it's incorrect. For example, use `RepeatEstimates` when not all iterations yield exactly the same gates (see example below) or use `BeginEstimateCaching` and incorrectly encode parameters that affect RE.
I suggest **fully automatic** caching for resource estimates used by an operation, that requires **zero code editing** (e.g no annotations/calls to helpers) and is **guaranteed** to produce correct estimates (that is identical to those obtained without caching).
The high-level design idea:
* For every operation, derive on what function of inputs its resource estimate depends, call this f. I typically resource estimate depends on values of classical inputs and only on shapes of quantum registers, but it needs to be formalized.
* When operation op(inputs) is called:
* If key (op, cache(inputs)) is in cache, don't decompose operation and just add estimates for RE_CACHE[op, f(inputs).
* Otherwise, compute resource estimates for this operation, add them to answer, and store them in CACHE[op, f(inputs)].
("Add" is literal addition for everything except qubits count, for qubits count it's more complicated, but we already handle this for BeginEstimateCaching).
**Example**
Consider for example modular multiplication circuit from [this paper](https://arxiv.org/pdf/[1706.06752](https://arxiv.org/pdf/1706.06752)):
It can be implemented in Q#:
```
operation ModMul(x: Qubit[], y: Qubit[], ans: Qubit[], modulus: BigInt) : Unit {
for i in n-1..0..-1 {
Controlled ModAdd([x[i]], (y, ans));
if (i!=0) {
ModDbl(ans);
}
}
}
```
ModDbl is called `n-1` times with exactly the same inputs, so resource estimates are the same. ModAdd is called with different control qubit, but despite that resource estimate for each call is the same.
With my suggestion, both ModAdd and ModDbl will be resource estimated only once, speeding up RE for ModMul in n times.
Notes:
* This requires no changes to the language, and I believe it can be implemented entirely inside resource estimator.
* This will not work for "quantum-classical" operations (such as quantum-classical addition, comparison etc.), but this will work great for quantum-quantum operations. For quantum-classical operations, where number of gates depends on value of a classical input (although insignificantly) users can use `BeginEstimateCaching` at risk of getting imprecise counts.
Contributor guide
Research direction
Start with Std.ResourceEstimation and its BeginEstimateCaching and RepeatEstimates helpers to understand the current caching behavior and limitations. Define how automatic cache keys and estimate aggregation should preserve exact results, then verify the design against the ModMul example and its repeated ModAdd and ModDbl calls.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100