qsharp-runtime: Width and depth metrics from ResourcesEstimator can seem inconsistent

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:

namespace Namespace {
  open Microsoft.Quantum.Canon;

  operation Operation() : Unit {
    using (qs = Qubit[6]) {
      ApplyLowDepthAnd(qs[0], qs[1], qs[2]);
      ApplyLowDepthAnd(qs[3], qs[4], qs[5]);
    }
  }
}

C# driver:

namespace Namespace {
  public class Program {
    public static void Main(string[] args) {
      var sim = new ResourcesEstimator();

      Operation.Run(sim).Wait();
      Console.WriteLine(sim.ToTSV());
    }
  }
}

Output:

Metric          Sum            
CNOT            16
QubitClifford   6
R               0
Measure         0
T               8
Depth           1
Width           7
BorrowedWidth   0

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.

About this issue

Original URL
State: closed
Created 4 years ago
Reactions: 6
Comments: 21 (10 by maintainers)

Most upvoted comments

It would be great if this issue with the estimator could be fixed. The result in https://github.com/microsoft/qsharp-runtime/pull/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 on Jun 25, 2020

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.

xbonnetain on Sep 3, 2020

@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.

bettinaheim on Jul 23, 2020

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. We are currently working to fix this issue by computing compatible pairs for these two extremes. Our current plan is to output two pairs of numbers: First pair - minimum depth and corresponding compatible width, second pair - minimum width and corresponding compatible depth. Exact definitions and implementation is underway. The question of minimizing depth given certain width is a question in between these extremes. It is out of scope of the current work and is a separate issue (#371 ).

DmitryVasilevsky on Sep 9, 2020

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?

bettinaheim on May 20, 2020

@rmshaffer @cgranade For input and awareness about the request for plotting the execution path with minimal depth/width.

bettinaheim on Oct 21, 2020