-
Notifications
You must be signed in to change notification settings - Fork 93
Width and depth metrics from ResourcesEstimator can seem inconsistent #192
Comments
Being explicit about that the depth and width output are minimal counts that are not necessarily mutually satisfiable is a good first step. @msoeken, do you want to pick this up and make a PR to clarify that? |
@geduardo to add clarification in docs |
It would be great if this issue with the estimator could be fixed. The result in #267 is disappointing. Renaming metrics to WidthLowerBound and DepthLowerBound would have been a welcome first step. We have been using Q# in our research to determine resource estimates for quantum cryptanalysis such as Grover's algorithm for key search on block ciphers and Shor's algorithm to compute elliptic curve discrete logarithms. With NIST currently in the process of standardizing post-quantum cryptography, there is a need for precise resource estimates of quantum attacks in order to inform the selection of cryptosystem parameters. A correct and consistent resource estimate is important in that it provides an upper bound on the resources an attacker needs to break a certain cryptosystem with one possible implementation. It is also important to identify the currently best known attack. Reporting independent lower bounds is confusing, it might hide the actual cost of an attack and people will assume that these metrics are simultaneously realizable. There is a lot of potential for using Q# for analyzing many cryptanalytic algorithms, but if resources are underestimated, Q# might not be the right tool. |
@cryptosidh @msoeken We are looking into properly addressing this. We have work scheduled in the upcoming month to enable getting estimates that are mutually satisfiable when a) minimizing depth and b) minimizing width. We'll keep you posted. |
Hi all, I totally agree with @cryptosidh. I planned to use Q# for cost estimates of cryptanalyses, and I was quite disappointed to discover this soundness issue, as it forces to compute these metrics manually. @bettinaheim Besides these 2 estimates, having a "minimizing depth for a given width" (or the converse) would also be useful, as it would easily allow to get tradeoff curves. |
Hi Bonnetain, @xbonnetain , did you try to construct a quantum circuit in Q# with only Clifford+T (every gate in this group is explicitly write down) gates? In this case, is the resource estimation accurate?
|
Hi @siweisun, the |
Hi @msoeken, thanks! Could you show me the code of |
Hi @msoeken , I wonder whether it is possible to have some coder-side workaround about this issue by playing with the code. By the way, do you have some experience with Qiskit? Are there any similar functionalities estimating the resource? |
Hi @siweisun, the code for You can copy the operation but pass the helper qubit to achieve depth 1 as an argument to the operation call. |
Hi @msoeken and @xbonnetain , the following code leads to correct resource estimation.
Metric Sum Max |
Hi @msoeken and @xbonnetain , does this give some hints at what is wrong? Can we have a workaround by sticking to some artificial rules when coding the circuits? |
Hi @siweisun, exactly, this is the workaround I was describing a few comments above:
|
My fault. I totally misunderstand your point ... Thanks for your clarification. :) |
@xbonnetain Regarding the feature request to support minimizing depth for a given with, I absolutely agree. We will however first address the immediate issue tracked here of getting consistent estimates before we can look at other improvements. I hence filed a separate issue to track that here: #371. |
Current numbers for Width and Height are, indeed, incompatible. "Depth" is the lower bound on depth of the quantum circuit. To achieve such depth a substantial number of qubits may be needed. On the other hand, "Width" attempts to establish a lower bound on the number of qubits allocated during operation. To achieve such width, depth may need to be increased substantially from the lower bound. These numbers represents two extremes - one number per extreme. |
@DmitryVasilevsky That sounds great! But after you output the compatible depth-width pairs, is it possible to output the circuits achieving the depth-width combinations? Thanks. |
@rmshaffer @cgranade For input and awareness about the request for plotting the execution path with minimal depth/width. |
@rmshaffer Merging the PR automatically closed this issue. I think it makes more sense to track the request to emit the circuit for that depth-width pair on the iqsharp repo rather than keeping this one open. What do you think? |
Sure, @bettinaheim, feel free to open an issue in IQ# for this. |
Apologies, I've lost track (as a mere user) of where this issue went. Is there an open issue in IQ#? |
Please describe what you would like the feature to accomplish.
The ResourcesEstimator does not take potential dependencies between width and depth into account, which may result in resource estimates that seem inconsistent. This issue is to discuss alternatives on how to make the output more clear.
The following example illustrates the problem:
Q# code:
C# driver:
Output:
Here, width and depth are conflicting, because we cannot distribute 8 T gates over 7 qubits in depth 1.
Describe the solution you'd like
At least change the output to ToTSV() and add clarifications to the documentation. The preferred solution would be to output consistent width and depth estimates.
The text was updated successfully, but these errors were encountered: