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

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

[msoeken]

Hi @siweisun, the ApplyLowDepthAnd in the example above is implemented explicitly using gates from the Clifford+T library. Each operation call allocates one qubit and applies a T operation to it. The wrong estimates occur because both of these T operations are considered to be in parallel (therefore T depth 1), but the allocated qubit is counted only once (therefore width 7)

[siweisun]

Hi @msoeken, thanks! Could you show me the code of ApplyLowDepthAnd? We tried to implement the Toffoli gate with T-depth 1, 2, and 3 with explicit Clifford+T placement, and the reports are correct.

[siweisun]

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?

[msoeken]

Hi @siweisun, the code for ApplyLowDepthAnd is here: https://github.com/microsoft/QuantumLibraries/blob/master/Standard/src/Canon/And.qs#L112

You can copy the operation but pass the helper qubit to achieve depth 1 as an argument to the operation call.

[siweisun]

Hi @msoeken and @xbonnetain , the following code leads to correct resource estimation.

operation ApplyLowDepthAnd_2() : Unit {
    using ((control1, control2, target, helper,control11, control21, target1, helper1) = (Qubit(), Qubit(), Qubit(), Qubit(),Qubit(), Qubit(), Qubit(), Qubit())) {
        //AssertAllZero([target]);
        H(target);
        within {
            CNOT(target, control1);
            CNOT(control1, helper);
            CNOT(control2, helper);
            CNOT(target, control2);
        }
        apply {
            Adjoint T(control1);
            Adjoint T(control2);
            T(target);
            T(helper);
        }
        HY(target);

        //AssertAllZero([target]);
        H(target1);
        within {
            CNOT(target1, control11);
            CNOT(control11, helper1);
            CNOT(control21, helper1);
            CNOT(target1, control21);
        }
        apply {
            Adjoint T(control11);
            Adjoint T(control21);
            T(target1);
            T(helper1);
        }
        HY(target1);
    }
}

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

[siweisun]

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?

[msoeken]

Hi @siweisun, exactly, this is the workaround I was describing a few comments above:

Hi @siweisun, the ApplyLowDepthAnd in the example above is implemented explicitly using gates from the Clifford+T library. Each operation call allocates one qubit and applies a T operation to it. The wrong estimates occur because both of these T operations are considered to be in parallel (therefore T depth 1), but the allocated qubit is counted only once (therefore width 7)

[siweisun]

Hi @siweisun, exactly, this is the workaround I was describing a few comments above:

Hi @siweisun, the ApplyLowDepthAnd in the example above is implemented explicitly using gates from the Clifford+T library. Each operation call allocates one qubit and applies a T operation to it. The wrong estimates occur because both of these T operations are considered to be in parallel (therefore T depth 1), but the allocated qubit is counted only once (therefore width 7)

My fault. I totally misunderstand your point ... Thanks for your clarification. :)

[bettinaheim]

@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: https://github.com/microsoft/qsharp-runtime/issues/371.

[DmitryVasilevsky]

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

[siweisun]

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.

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

[bettinaheim]

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

[bettinaheim]

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

[rmshaffer]

Sure, @bettinaheim, feel free to open an issue in IQ# for this.

[JamesHDavenport]

Apologies, I've lost track (as a mere user) of where this issue went. Is there an open issue in IQ#?