Width and depth metrics from ResourcesEstimator can seem inconsistent

[msoeken]

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.

[bettinaheim]

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?

[KittyYeungQ]

@geduardo to add clarification in docs

[cryptosidh]

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.

[bettinaheim]

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

[xbonnetain]

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.

[siweisun]

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