Physical qubit estimates when using surface codes

Question

I've been trying to recreate physical qubit requirements to attack elliptic curve cryptography for the good people over at cryptography stack exchange. I don't want to get too deep into the arcana of surface codes, but still provide a useful reference estimate. I'm using a paper by Aggarwal et al where their estimator is given in Table III of appendix A. Ignoring the cost of state factories for the time being, they claim that the required code distance to successfully execute $n_C$ Clifford gates with gate probability $p_g$ is $$d_C:=\min_{d\in\mathbb N}(80p_g)^{\frac{d+1}2}\ge\frac 1{n_c}$$ which feel to be the right shape with 80 presumably some sort of code-dependent constant. However, they then go on to say that the required number of physical qubits will be $$3.125\times n_L\times d_C$$ where $n_L$ is the number of logical qubits. Is this a misprint? I had thought that the number of physical qubits grows roughly quadratically with the code distance.

Trying to recreate their calculations in their Section B with $p_g=5\times 10^{-4}$ and $20\times 1.16\times 10^{11}$ Clifford gates gives a code distance $d_C=17$ which gives a circuit estimate of 53 times by the number of logical qubits (rather than the 735.3 quoted in section B).

Running their estimator for the number of physical qubits required for state factories comes out as 36750 which should be a second order effect.

Answer 1

I'm using a paper by Aggarwal et al

The implementation details of these algorithms have improved substantially since 2017. For example, you'll find much better logical gate counts (but not physical estimates) in "Improved quantum circuits for elliptic curve discrete logarithms".

I had thought that the number of physical qubits grows roughly quadratically with the code distance.

Yes, it should be growing quadratically.

The number should probably be $3.125d^2n$ instead of $3.125dn$. In 2017 the usual surface code qubit was a pair of square holes within a 2d field of holes using a horizontal and vertical pitch of $1.25d$. That's where the magic number "3.125" comes from: $2 \cdot 1.25^2 = 3.125$.

Since then, the field has switched from holes-on-an-open-field-of-surface-code to boxes-of-surface-code. Now a logical qubit is $2(d+1)^2$ physical qubits.