Beverland et al. Model#

In this notebook, we reproduce the physical resource estimates in “Assessing requirements to scale to practical quantum advantage” by Beverland et al, Appendix F.

The paper describes the formulas used for estimating cost in the various appendices. The final estimation procedure is put together in Appendix E and we reproduce the values found in Appendix F.

The Azure cost model has 5 inputs:

  1. The physical assumptions about the hardware (e.g. error rate, the latency of Clifford and measurement operations, etc).

  2. A summary of the circuit/algorithm to execute (e.g. number of T gates, etc).

  3. The magic state factory (e.g. number of qubits consumed by it, its error rate, etc).

  4. Cost model of Approximating rotations using T operations up to error \(\epsilon\).

  5. The quantum error correction scheme.

We take a look at each of these and then reproduce the results of Appendix F.

The Inputs#

Physical Parameters#

These are assumptions about the quantum hardware and are:

  • t_gate_ns: Execution time of Clifford gates.

  • t_meas_ns: Execution time of Measurement operations.

  • physical_error: Physical error rate (\(p\)).

In Qualtran these are represented by the PhysicalParameters dataclass. Since the total execution time depends only on the cycle time, we combine the Beverland gate time estimates to get a cycle time.

from qualtran.surface_code import PhysicalParameters

beverland_phys_params = PhysicalParameters.make_beverland_et_al('superconducting', optimistic_err_rate=True)
beverland_phys_params

PhysicalParameters(physical_error=0.0001, cycle_time_us=0.4)

# Compare and contrast with the Gidney and Fowler assumptions
PhysicalParameters.make_gidney_fowler()

PhysicalParameters(physical_error=0.001, cycle_time_us=1.0)

Algorithm Summary#

This is a summary of the circuit or algorithm to execute. This summary is several simple counts:

  • n_algo_qubits is the number of algorithm qubits.

  • n_logical_gates captures the number of gates, including

    • measurement is the number of Clifford measurements (\(M_R\)).

    • t is the number of T gates (\(M_T\)).

    • toffoli is the number of Toffoli gates (\(M_{Tof}\)).

    • rotation is the number of rotations (\(M_R\)).

  • n_rotation_layers is the number of rotation layers (\(D_R\)).

Note: The symbol in parentheses corresponds to the notation in the paper

In Qualtran the algorithm specs are represented by the data class qualtran.surface_code.AlgorithmSummary.

from qualtran.resource_counting import GateCounts
from qualtran.surface_code import AlgorithmSummary

AlgorithmSummary(n_algo_qubits=1, n_logical_gates=GateCounts(t=1))

AlgorithmSummary(n_algo_qubits=1, n_logical_gates=GateCounts(t=1, toffoli=0, cswap=0, and_bloq=0, clifford=0, rotation=0, measurement=0), n_rotation_layers=None)

Magic State Factory#

The magic state factory in our case is a T-state factory. The paper describes 15-to-1 factories in Appendix C, but only the overall summary in Table VII in terms of physical qubit count and generation time is used in estimation in Appendix F.

Rotation Approximation Model#

This is a model that approximates the number of T gates needed to implement a rotation up to error \(\epsilon\). In the paper they use the approximation model from Kliuchnikov et al. The formula for the number of T gates used to approximate an angle up to error \(\epsilon\) is given by:

\[ a \log_2{\frac{1}{\epsilon}} + b \]

Where \(a\) and \(b\) are constants that depend on the gate set and the approximation protocol. Table 1 of Kliuchnikov et al gives estimates for those constants for different combinations of gate sets and protocols.

Though Beverland et al includes slightly different coefficient values, the rotation approximation model used by Azure cost model is using \(a=0.53\) and \(b=4.86\) from Table 1 of Kliuchnikov et al.

from qualtran.surface_code.rotation_cost_model import BeverlandEtAlRotationCost

BeverlandEtAlRotationCost

RotationLogarithmicModel(slope=0.53, overhead=5.3, gateset='Clifford+T')

Quantum Error Correction Scheme#

The quantum error correction scheme determines three things:

  1. The logical error rate given a code distance and physical error rate: \(P(d)\).

  2. The number of physical qubits needed per logical qubit: \(n(d)\).

  3. The duration of a logical time step: \(\tau(d)\).

Table V of the paper lists how these are related to the QEC scheme.

In the paper, they use gate-based QEC which has \(P(d), n(d), \tau(d)\) as:

\[\begin{split} P(d) = 0.03 \left ( \frac{p}{0.01} \right) ^ \frac{d+1}{2}\\ n(d) = 2 d^2\\ \tau(d) = \textrm{\{single cycle time\}} \cdot d\\ \end{split}\]

The error detection circuit time depends on several factors physical factors including the time to apply a Clifford, measurement and reset operations as well as classical processing.

In Table V they don’t take into account the classical processing part and assume that a reset takes the same time as a measurement leading to the formula:

\[ \textrm{\{single cycle time\}} = 4t_\textrm{gate} + 2t_\textrm{meas} \]

Other authors (e.g. Fowler, Gidney) assume that the entire process takes a specific time (e.g. \(1\mu s\)).

from qualtran.surface_code import QECScheme

qec = QECScheme.make_beverland_et_al()
qec

QECScheme(error_rate_scaler=0.03, error_rate_threshold=0.01)

Resource Estimation#

Now we move to reproduce the results in Appendix F.

Quantum Dynamics#

The algorithm specs of this circuit are given as:

  • number of algorithm qubits: \(100\)

  • number of rotation gates: \(30{,}100\)

  • number of measurements: \(1.4 \times 10^5\)

  • no T or Toffoli gates

  • depth of rotation circuit: \(501\)

with an error budget \(\epsilon\) of \(0.001\)

qd_alg = AlgorithmSummary(
    n_algo_qubits = 100,
    n_logical_gates = GateCounts(
        rotation=30_100,
        # Note in the paper the number of measurements
        # has an extra zero which we assume to be a typo.
        measurement=1.4e5,
    ),
    n_rotation_layers = 501
)

The first step is to calculate the total number of logical qubits (accounting for routing). The paper uses the fast data block layout from Litinski 2018. This data block is represented in Qualtran as FastDataBlock.

from qualtran.surface_code import FastDataBlock

logical_qubits = FastDataBlock.get_n_tiles(n_algo_qubits=qd_alg.n_algo_qubits)
print('Q =', logical_qubits)

Q = 230

from qualtran.surface_code import beverland_et_al_model

# Calculate the minimum number of logical time steps (Eq D3)
error_budget = 0.001
c_min = beverland_et_al_model.minimum_time_steps(
    error_budget=error_budget,
    alg=qd_alg,
    rotation_model=BeverlandEtAlRotationCost,
)
print('C_min = %e' % c_min)

C_min = 1.801200e+05

# And the number of needed T operations (Eq D4)
t_operations = beverland_et_al_model.t_states(
    error_budget=error_budget,
    alg=qd_alg,
    rotation_model=BeverlandEtAlRotationCost
)
print('M = %e' % t_operations)

M = 6.020000e+05

Comparing our esimates of \(Q = 230, C_{min} = 1.8 \times 10^5, M = 9 \times 10^5\) to the paper estimates of \(Q = 230, C_{min} = 1.5 \times 10^5, M = 2.4 \times 10^6\). We find a match for \(Q\) and \(C_{min}\) however we are off by 4x for the number of T gates \(M\).

D4 gives the formula for \(M\) as

\[M = M_T + 4 M_{Tof} + M_R \lceil A \log_2{M_R/\epsilon_{syn}} + B\rceil\]

Since \(M_T = M_{Tof} = 0\), the only contribution to \(M\) comes from rotations where \(M_R = 30100, \epsilon_{syn} = \frac{10^{-3}}{3} , A = 0.53, B = 4.86\) which give our value of \(6.02e5\).

Next, we estimate the code distance \(d\). \(d\) satisfies

\[ P(d) = a \left ( \frac{p}{p^*} \right )^\frac{d+1}{2} \]
subject ot the constraint on the logical error rate of \(Q \cdot C \cdot P(d) = \frac{\epsilon}{3}\). Where \(p\) is the physical error rate. \(a\) and \(p^*\) are constants determined by the QEC scheme.

d = beverland_et_al_model.code_distance(
    error_budget=error_budget,
    time_steps=c_min,
    alg=qd_alg,
    qec_scheme=qec,
    physical_error=beverland_phys_params.physical_error,
)
print(f'{d=}')

d=9

Matching the paper’s code distance of \(d = 9\). This leads to a total run time (Eq. E3) of 0.65s which is close to the time in the paper of 0.55s

t_s = d * beverland_phys_params.cycle_time_us * 1e-6 * c_min
print(f'algorithm run time of {t_s:g} seconds')

algorithm run time of 0.648432 seconds

Next, we examine the magic state factories. In the paper, for the quantum dynamics example, we are given \(199\) factories each producing one T state every \(46.8 \mu s\) at an error rate of \(5.6\times 10^{-11}\) while consuming \(3{,}240\) physical qubits.

num_factories = 199
factory_qubits = 3_240

# Leading to a total number of physical qubits (from E6)
distillation_qubits = num_factories * factory_qubits
q = distillation_qubits + logical_qubits * qec.physical_qubits(d)
print('total number of physical qubits:', q)
print('percentage of distillation qubits: {}%'.format(round(distillation_qubits / q * 100, 1)))

total number of physical qubits: 682020
percentage of distillation qubits: 94.5%

Our estimate of 0.68M physical qubits with 94.5% of them being consumed by the T states factories match the numbers in the paper.

Quantum Chemistry#

The algorithm specs of this circuit are given as:

  • number of algorithm qubits: \(1318\)

  • number of rotation gates: \(2.06 \times 10^8\)

  • number of measurements: \(1.37 \times 10^9\)

  • number of T gates: \(5.53 \times 10^7\)

  • number of Toffoli gates: \(1.35 \times 10^{11}\)

  • depth of rotation circuit: \(2.05 \times 10^8\)

with an error budget of 0.01

chem_alg = AlgorithmSummary(
    n_algo_qubits=1318,
    n_logical_gates=GateCounts(
        rotation=2.06e8,
        measurement=1.37e9,
        toffoli=1.35e11,
        t=5.53e7,
    ),
    n_rotation_layers=2.05e8,
)
chem_alg

AlgorithmSummary(n_algo_qubits=1318, n_logical_gates=GateCounts(t=55300000.0, toffoli=135000000000.0, cswap=0, and_bloq=0, clifford=0, rotation=206000000.0, measurement=1370000000.0), n_rotation_layers=205000000.0)

logical_qubits = FastDataBlock.get_n_tiles(n_algo_qubits=chem_alg.n_algo_qubits)

print('Q =', logical_qubits)

Q = 2740

# Calculate the minimum number of logical time steps (Eq D3)
error_budget = 0.01
c_min = beverland_et_al_model.minimum_time_steps(
    error_budget=error_budget, alg=chem_alg, rotation_model=BeverlandEtAlRotationCost
)
print('C_min = %g' % c_min)

C_min = 4.11756e+11

# And the number of needed T operations (Eq D4)
t_operations = beverland_et_al_model.t_states(
    error_budget=error_budget, alg=chem_alg, rotation_model=BeverlandEtAlRotationCost
)
print('M = %g' % t_operations)

M = 5.45205e+11

Note that our estimates match nicely to the paper estimates of

\[\begin{split}Q = 2740\\ C_{min} = 4.10 \times 10^{11}\\ M = 5.44 \times 10^{11}\end{split}\]

Next, we estimate the code distance.

d = beverland_et_al_model.code_distance(
    error_budget=error_budget,
    time_steps=c_min,
    alg=chem_alg,
    qec_scheme=qec,
    physical_error=beverland_phys_params.physical_error,
)
print(f'{d=}')

d=17

Again we match the code distance from the paper of \(d = 17\). This leads to a total run time (Eq. E3) of

total_seconds = beverland_phys_params.cycle_time_us * d * 1e-6 * c_min
total_days = total_seconds / 3600 / 24
print(f'algorithm run time of {total_days:g} days')

algorithm run time of 32.4067 days

We get a run time estimate of 32.4 days. In the paper, it says the run time is 1 month and 1 day.

Next we examine the magic state factories. In the paper, for the quantum chemistry example, we are given \(17\) factories each producing one T state every \(83.2\mu s\) at an error rate of \(2.13e-15\) while consuming \(16,000\) qubits.

num_factories = 17
factory_qubits = 16_000

# Leading to a total number of physical qubits (from E6)
distillation_qubits = num_factories * factory_qubits
q = distillation_qubits + logical_qubits * qec.physical_qubits(d)
print('total number of physical qubits: %g M' % round(q * 1e-6, 2))
print('percentage of distillation qubits: {}%'.format(round(distillation_qubits / q * 100, 1)))

total number of physical qubits: 1.86 M
percentage of distillation qubits: 14.7%

Our estimate of 1.86M physical qubits matches the paper’s estimate.

Shor Factoring#

The algorithm specs of this circuit are given as:

  • number of algorithm qubits: \(12{,}581\)

  • number of rotation gates: \(12\)

  • number of measurements: \(1.08 \times 10^9\)

  • number of T gates: 12

  • number of Toffoli gates: \(3.73 \times 10^{10}\)

  • depth of rotation circuit: \(12\)

with an error budget of \(1/3\)

shor_alg = AlgorithmSummary(
    n_algo_qubits=12581,
    n_logical_gates=GateCounts(
        rotation=12,
        measurement=1.08e9,
        # Note in the paper the number of Toffoli operations is 3.73e10.
        # However we assume that the exponent has a typo and that the number is 3.73e9.
        toffoli=3.73e9,
        t=12,
    ),
    n_rotation_layers=12,
)

logical_qubits = FastDataBlock.get_n_tiles(n_algo_qubits=shor_alg.n_algo_qubits)

print('Q =', logical_qubits)

Q = 25481

# Calculate the minimum number of logical time steps (Eq D3)
error_budget = 1 / 3
c_min = beverland_et_al_model.minimum_time_steps(
    error_budget=error_budget, alg=shor_alg, rotation_model=BeverlandEtAlRotationCost
)
print('C_min = %e' % c_min)

C_min = 1.227000e+10

# And the number of needed T operations (Eq D4)
t_operations = beverland_et_al_model.t_states(
    error_budget=error_budget, alg=shor_alg, rotation_model=BeverlandEtAlRotationCost
)
print('M = %e' % t_operations)

M = 1.492000e+10

Our estimates of \(Q = 25481, C_{min} = 1.23 \cdot 10^{10}, M = 1.49 \cdot 10^{10}\) match the estimates of the paper.

d = beverland_et_al_model.code_distance(
    error_budget=error_budget,
    time_steps=c_min,
    alg=shor_alg,
    qec_scheme=qec,
    physical_error=beverland_phys_params.physical_error,
)
print(f'{d=}')

d=13

Matching the code distance of \(d = 13\) in the paper.

total_seconds = beverland_phys_params.cycle_time_us * d * 1e-6 * c_min
total_hours = total_seconds / 3600
h = int(total_hours)
m = (total_hours - h) * 60
'algorithm run time of %d hours %d' % (h, m)

'algorithm run time of 17 hours 43'

Our estimate runtime of 17h43m matches with the estimate of the paper.

Next we examine the magic state factories. In the paper, for the quantum chemistry example, we are given \(18\) factories each producing one T state every \(72.8 \mu s\) at an error rate of \(5.51e-13\) while consuming \(5,760\) qubits.

num_factories = 18
factory_qubits = 5760

# Leading to a total number of physical qubits (from E6)
distillation_qubits = num_factories * factory_qubits
q = distillation_qubits + logical_qubits * qec.physical_qubits(d)
print('total number of physical qubits: %g M' % round(q * 1e-6, 2))
print('percentage of distillation qubits: {}%'.format(round(distillation_qubits / q * 100, 1)))

total number of physical qubits: 8.72 M
percentage of distillation qubits: 1.2%

Our estimate of 8.72M physical qubits matches the paper’s estimate.