2
$\begingroup$

Let's assume I want to implement a rotation $R_Z(\theta)$ for a lattice-surgery based computation, for $\theta$ being an arbitrary angle (i.e. the gate is not necessarily Clifford nor a $T$-gate).

It can typically be done by

  1. Decomposing $R_Z(\theta)$ on Clifford+T gateset (possible up to some approximation $\epsilon$). I call $N_T$ the number of $T$-gates in the decomposition.
  2. The Clifford are "commuted" toward the end of the algorithm (we do the measurement based lattice surgery framework), which changes each of the $T$-gate in $\exp(-i P \pi/8)$ for some single-qubit Pauli $P$ (not anymore necessarily $Z$).

Hence, the duration of one $R_Z(\theta)$ should from my understanding be equal to $N_T$ logical timesteps. If we have many $R_Z(\theta)$ gates, the total duration of these gates should be $N_T \times D_R$ where $D_R$ is the depth associated to these gates (the number of layers containing at least one gate $R_Z(\theta)$).

However, while reading this paper (which explains the assumptions behind the Azure resource estimator), assuming no $T$-gates nor Toffoli nor measurements are in the end-user algorithm, they would find a total number of logical timestep, based on Eq (D3) on page 30:

$$C_{\min}=M_R+N_T \times D_R$$

What I call $N_T$ correspond to their $A \log_2(M_R/\epsilon)+B$ in their notation.

Basically, they add on my counting $M_R$ which is the total number of $R_Z(\theta)$ gates. Why should it be added? Isn't the term $N_T \times D_R$ sufficient?


[Edit]: Below is a concrete example showing why for me $C_{\min}=N_T \times D_R$ should be the formula (without $M_R$):

Left: two logical qubits are shown, on each of them I implement a $R_Z$ (of an angle that is not Clifford, and neither the one of a $T$-gate (i.e. not $\pi/4$).

Middle: this rotation is decomposed on Clifford+T gateset (the gates with label "C" represent single qubit Clifford).

Right: The Clifford are commuted through the $T$-gates. It results a circuit with only "generalized" $T$-gates (i.e. the rotation angle are $\pi/4$ but not necessarily around the $Z$ axis for the $T_i$).

In this example the circuit depth would be $N_T \times D_R$: I don't get why we should add $M_R$ on top.

enter image description here

The ancilla doing state injection are not represented in this image, but they would not change the number of logical timesteps (as doing one of the $T$-gate is essentially measuring a multi-Pauli observable which is done in a single timestep).

$\endgroup$

1 Answer 1

2
$\begingroup$

This number corresponds to the sentence "...the number of logical time steps required is simply the number of measurements needed to entangle the algorithm and synthesis ancillas." - that step is separate from the synthesis itself. (And yes, synthesis = Clifford + T decomposition.)

To answer the updated question: in your concrete example, you're doing synthesis on the algorithmic data qubits directly, rather than on additional synthesis qubits. This is not the assumption under which the paper is written (and Azure Quantum Resource Estimator acts).

The paper assumes 2D nearest-neighbor connectivity between qubits, and a certain level of being able to apply operations in parallel. For example, T factories run in parallel (on completely separate sets of qubits) to prepare the T states that are then consumed during synthesis. But for most operations it's unclear whether they can be applied in parallel, and analyzing this would require the tool to do a complete layout of the logical qubits and all kinds of auxiliary qubits (which is computationally expensive, so it doesn't do that).

Instead, Azure Quantum Resource Estimator assumes that T gates are produced in parallel, and synthesis can be done in parallel using additional synthesis qubits (these can be allocated next to the T factories so they can consume T states in parallel), but after that getting the rotations from the synthesis qubits to the algorithm qubits is done sequentially, since the paths required for this are likely to overlap and interfere with each other.

Under these assumptions, doing synthesis directly on algorithm qubits as you show would require consuming each T gate sequentially, so the depth would actually be 6.

P.S. You have to remember that the resource estimates produced here are, well, estimates, not exact numbers supported by compiling the algorithm to a point where it's ready to run on a specific runtime on a specific device. These estimates are done to give fast order-of-magnitude evaluation of the required resources, so there are assumptions made to simplify the computation and make it faster. For example, the last sentence in that section of the paper says explicitly that several types of qubits involved in the synthesis and transport of the T gates is not counted towards the qubit number estimates. For another example, the tool doesn't do actual Clifford+T synthesis for each rotation gate to ascertain the number of T gates used in it, but uses a fixed number for each rotation (unless it's an equivalent of a single T or a Clifford gate).

$\endgroup$
7
  • $\begingroup$ Thanks for the answer. I added an image to clarify why I don't understand the contribution in $M_R$. Also, just to be sure, what you call synthesis is the decomposition of an arbitrary rotation on the gateset Clifford+T: am I correct? $\endgroup$ Dec 4, 2023 at 15:34
  • 1
    $\begingroup$ I've updated the answer to hopefully address your question in more detail $\endgroup$ Dec 5, 2023 at 19:01
  • $\begingroup$ Thank you for your update. What you say is extremely useful to me. Would it be a correct understanding to say that (i) "synthesis done on ancilla qubits" means that the gate is applied on ancilla qubit and teleported onto the data qubits? Hence, (ii) the data qubit just wait that the ancilla qubit synthesise the gate, and that the gate is teleported back? Do you agree with both (i) and (ii)? $\endgroup$ Dec 5, 2023 at 20:23
  • $\begingroup$ Is there a paper explaining the process in more details. Now I realize this is somehow explained in Fig 10 of Azure paper but the explanation is a bit quick: for instance I don't exactly get why the yellow box in Fig 10 b) actually does this kind of teleportation (if I was correct in my previous understanding). $\endgroup$ Dec 5, 2023 at 20:24
  • $\begingroup$ (i) and (ii), roughly yes (the terminology I've seen is "rotation magic states are prepared on synthesis qubits and then are consumed with an additional measurement" rather than calling it teleportation). This is not written down anywhere other than the paper you've seen and the documentation at learn.microsoft.com/en-us/azure/quantum/…. Once Azure Quantum Resource Estimator is released in open source, you'll be able to read the code, hopefully that will be helpful! $\endgroup$ Dec 5, 2023 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.