pith. sign in

arxiv: 2411.01880 · v2 · submitted 2024-11-04 · 🪐 quant-ph · cond-mat.mes-hall

Magic states are rarely the best resource to optimize: An analytical tool for qubit resource estimation in concatenated codes

Marco Fellous-Asiani , Hui Khoon Ng , Robert S. Whitney This is my paper

Pith reviewed 2026-05-23 17:53 UTC · model grok-4.3

classification 🪐 quant-ph cond-mat.mes-hall
keywords concatenated codesmagic statesresource estimationqubit overheadfault-tolerant quantum computingSteane codeerror correction gadgets
0
0 comments X

The pith

Magic operations are rarely the dominant qubit cost in concatenated error-correction schemes, making magic-specific optimizations yield only marginal gains.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a closed-form analytical tool that calculates the total qubit resources required by concatenated error-correction schemes at any number of levels. When applied to the 7-qubit Steane code using either standard or flag-qubit error-correction gadgets, the tool shows that the extra cost of magic-state injections for non-Clifford gates seldom accounts for the largest share of resources. Optimizations that lower the cost of every operation reduce overall qubit counts by several orders of magnitude, while optimizations aimed only at magic operations produce far smaller improvements. The authors conclude that this pattern is representative of most concatenated schemes.

Core claim

Using newly derived closed-form equations that remain simple for arbitrary concatenation depth, the authors calculate the qubit overhead for both error-correction gadgets and magic-state injections and find that magic operations do not dominate the resource budget in the 7-qubit Steane scheme; general optimizations therefore deliver substantially larger reductions than magic-only optimizations.

What carries the argument

The closed-form resource estimation equations that separately track the cost of standard error-correction gadgets and the additional cost of magic-state injections across any number of concatenation levels.

If this is right

  • Magic-specific optimizations produce only marginal reductions in total qubit resources.
  • Optimizations that affect all operations can lower qubit counts by a few orders of magnitude.
  • The same pattern of magic operations not being dominant appears in both Steane and flag-qubit gadget schemes.
  • The finding mirrors earlier observations for surface codes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Circuit designers may obtain larger efficiency gains by improving the cost of every gate rather than focusing on magic-state distillation.
  • The closed-form tool could be used to rank different concatenated schemes before numerical simulation.
  • Resource estimates that treat all logical operations equally may redirect attention away from magic-state research toward broader gadget improvements.

Load-bearing premise

The specific resource models and gadget costs measured for the 7-qubit Steane and flag-qubit schemes are representative of concatenated schemes in general.

What would settle it

A calculation for another concatenated code in which magic operations still consume the majority of qubit resources even after all general optimizations have been applied.

Figures

Figures reproduced from arXiv: 2411.01880 by Hui Khoon Ng, Marco Fellous-Asiani, Robert S. Whitney.

Figure 1
Figure 1. Figure 1: Plot of physical qubit costs for different error [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Ratio of resources R(K) for a circuit of inter￾est, Calgo, divided by the resources for the equivalent circuit Cnormal in which all level-K magic operations are replaced by normal ones; see Eq. (1). The solid lines are for a Calgo where 5% of the gates are magic operations (comparable to some real algorithms in Appendix A. The dashed lines are for a Calgo with only magic operations (an unrealistic worst-ca… view at source ↗
Figure 3
Figure 3. Figure 3: Analogy with a phase transition for the resource [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A transversal logical-qubit gate GL, with G1, G2, . . . ∈ Gphys as physical single-qubit gates. Each hori￾zontal line on the right-hand side represents a single physical qubit; the horizontal lines on the left-hand side represents a single logical qubit. are below the threshold. Our goal here is to estimate, for a given value of K, an upper bound — hopefully, a close-to-tight one — on the number of physica… view at source ↗
Figure 5
Figure 5. Figure 5: The method to prepare an arbitrary state [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The circuit for a generic EC gadget acting on a [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Magic-state implementation of a magic operation [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 10
Figure 10. Figure 10: Implementation of a T-gate on the single-qubit input |ψ⟩ via the use of the magic state [PITH_FULL_IMAGE:figures/full_fig_p023_10.png] view at source ↗
Figure 8
Figure 8. Figure 8: Fault-tolerant preparation of the logical (level [PITH_FULL_IMAGE:figures/full_fig_p023_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The Steane error-correction (EC) gadget for the [PITH_FULL_IMAGE:figures/full_fig_p023_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: Magic-state preparation circuits for the 7-qubit code with Steane EC gadgets. (a) The 1-prep-Rec of the state [PITH_FULL_IMAGE:figures/full_fig_p024_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Simplified sketch of the error-correction circuitry for 7-qubit code with the Steane approach, showing the aspects [PITH_FULL_IMAGE:figures/full_fig_p025_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Simplified sketch of the error-correction circuitry for 7-qubit code with the flag-qubit approach, showing the aspects [PITH_FULL_IMAGE:figures/full_fig_p029_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Plots of the toy-model in sec. VIII, where we vary [PITH_FULL_IMAGE:figures/full_fig_p031_14.png] view at source ↗
Figure 1
Figure 1. Figure 1: However, the switch from Steane to flag-qubit [PITH_FULL_IMAGE:figures/full_fig_p031_1.png] view at source ↗
Figure 15
Figure 15. Figure 15: Fault-tolerant preparation of the logical [PITH_FULL_IMAGE:figures/full_fig_p038_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Error correction gadget based on flag qubits. The top 7 lines represent the Steane encoded qubit. It requires 3 [PITH_FULL_IMAGE:figures/full_fig_p038_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Fault-tolerant preparation of the magic state [PITH_FULL_IMAGE:figures/full_fig_p039_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Non-fault-tolerant preparation of the state [PITH_FULL_IMAGE:figures/full_fig_p039_18.png] view at source ↗
read the original abstract

Concatenated error-correction schemes are well-understood routes to fault-tolerant quantum computing, and research on such schemes continues, including recent claims that they may be competitive with surface codes, and show potential when combined with high-rate Quantum Low Density Parity Check codes. However, there are few tools to evaluate the qubit resources required by concatenated schemes. We propose such a tool here. Its equations are closed-form and remain simple for an arbitrary number of levels of concatenation, making it ideal for comparing and minimizing the resource costs of such schemes. We use this tool to evaluate the resources for gate operations that require the injection of so-called ``magic states'', needed to complete the set of logical operations. It was expected that the complexity of such ``magic operations" would make them dominate the resource costs of a calculation, with numerous works proposing optimizations of these cost. Our work reveals that this expectation is often inaccurate: Magic operations are rarely the dominant cost of concatenated schemes, mirroring similar conclusions from past work for surface codes. Optimizations affecting all operations naturally have more impact than those on magic operations alone, yet we unexpected find that the former can reduce qubit resources by a few orders of magnitude while the latter give only marginal reductions. We show this in detail for a 7-qubit concatenated scheme with Steane error-correction gadgets or flag-qubits gadgets, and argue that our findings are representative of most concatenated schemes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a closed-form analytical tool for estimating qubit resources in concatenated quantum error-correcting codes with arbitrary concatenation levels. It applies the tool to the [[7,1,3]] Steane code under Steane error-correction gadgets and flag-qubit gadgets, showing that magic-state operations are rarely the dominant cost and that optimizations affecting all operations can reduce resources by orders of magnitude while magic-specific optimizations yield only marginal gains. The authors argue that these results are representative of most concatenated schemes.

Significance. If the tool and its conclusions hold, the work supplies a practical, closed-form method for resource counting that remains simple at high concatenation depth, a clear strength for comparing schemes. It also provides evidence that broad optimizations outperform magic-state-specific ones, mirroring surface-code findings and potentially redirecting research effort. The explicit closed-form equations for arbitrary L are a notable asset for reproducibility and parameter exploration.

major comments (2)
  1. [Abstract and Conclusion] Abstract and final section: the headline claim that magic operations are 'rarely the dominant cost' of concatenated schemes, and that the two examined cases are representative, rests on explicit calculations only for the [[7,1,3]] code with Steane and flag gadgets. The generalization is supported by qualitative argument alone; no additional explicit resource counts or structural proof are supplied showing that the magic-to-non-magic cost ratio remains sub-dominant for other base codes, gadget families, or concatenation depths.
  2. [Resource Model and Equations] Resource-model derivation (the closed-form equations): the abstract states that the tool uses closed-form equations, yet the manuscript does not include the explicit step-by-step derivations of the gadget overheads or the error-propagation assumptions used to obtain the qubit-count formulas. Without these or numerical validation benchmarks, it is unclear whether the central resource ratios are fully justified.
minor comments (2)
  1. [Introduction] Notation for concatenation level L and physical error rate p should be introduced once with a clear table of symbols.
  2. [Figures] Figure captions could explicitly state the concatenation depth and gadget type shown in each panel to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed report. We address each major comment below, clarifying our approach and indicating revisions where appropriate to improve transparency and rigor.

read point-by-point responses

  1. Referee: [Abstract and Conclusion] Abstract and final section: the headline claim that magic operations are 'rarely the dominant cost' of concatenated schemes, and that the two examined cases are representative, rests on explicit calculations only for the [[7,1,3]] code with Steane and flag gadgets. The generalization is supported by qualitative argument alone; no additional explicit resource counts or structural proof are supplied showing that the magic-to-non-magic cost ratio remains sub-dominant for other base codes, gadget families, or concatenation depths.

    Authors: Our explicit calculations are limited to the [[7,1,3]] Steane code under two gadget families, as stated. The claim of representativeness rests on the structural property that, in any concatenated scheme, the overwhelming majority of logical operations are Clifford gates realized through error-correction gadgets that incur no magic-state overhead; magic-state injection and distillation occur only for a small subset of non-Clifford gates. This imbalance in operation frequency and the localization of magic overhead are independent of the specific base code or gadget implementation, provided the concatenation follows the standard recursive structure. We will revise the abstract and conclusion to articulate this structural reasoning more explicitly, thereby strengthening the generalization without requiring additional explicit counts. revision: partial

  2. Referee: [Resource Model and Equations] Resource-model derivation (the closed-form equations): the abstract states that the tool uses closed-form equations, yet the manuscript does not include the explicit step-by-step derivations of the gadget overheads or the error-propagation assumptions used to obtain the qubit-count formulas. Without these or numerical validation benchmarks, it is unclear whether the central resource ratios are fully justified.

    Authors: We agree that the derivations of the closed-form expressions should be presented more explicitly. These expressions are obtained by solving the linear recurrence relations that accumulate qubit overhead across concatenation levels, using the per-gadget costs and the error-propagation rules for each operation type. In the revised manuscript we will add a dedicated appendix containing the full step-by-step derivation, the explicit assumptions on error propagation, and numerical validation benchmarks that compare the closed-form results against direct enumeration for small concatenation depths L. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation is self-contained from standard resource counting

full rationale

The paper introduces closed-form equations for qubit resource estimation in concatenated codes, derived directly from standard concatenation-level counting of physical qubits and operations. These are applied to explicit calculations for the [[7,1,3]] Steane code under Steane and flag-qubit gadgets, yielding the claim that magic operations are rarely dominant. No equation reduces by construction to a fitted parameter, self-defined quantity, or load-bearing self-citation; the representativeness argument is a qualitative extension from the two cases, not a definitional or fitted reduction. The central results follow from the paper's own explicit derivations without circular collapse to inputs.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard assumptions of quantum error correction (independent errors, perfect syndrome extraction in gadgets) plus the modeling choice that the 7-qubit code with Steane or flag gadgets is representative. No new particles or forces are postulated.

free parameters (2)
  • physical error rate p
    Input parameter to the resource equations; values are chosen to evaluate overheads but not fitted to produce the dominance conclusion.
  • concatenation level L
    Variable in the closed-form expressions; the tool is designed to handle arbitrary L without additional fitting.
axioms (1)
  • domain assumption Error propagation through concatenation levels follows the standard recursive overhead formulas for Steane and flag-qubit gadgets.
    Invoked to derive the closed-form resource counts for magic and non-magic operations.

pith-pipeline@v0.9.0 · 5796 in / 1343 out tokens · 32233 ms · 2026-05-23T17:53:05.334758+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

81 extracted references · 81 canonical work pages · 14 internal anchors

  1. [1]

    qubit’s types

    Definition of qubit’s type When we observe that a fault-tolerant scheme requires multiple types of normal qubits or multiple types of magic qubits, the scaling is not described by Eq. (2), which only has one type of each. That is when we need the general case, based on a matrix M of larger dimen- sions. However, while we have no simple way to say a priori...

    work page

  2. [2]

    Formalism for the general case Here we give details of how to generalize the scal- ing approach introduced in Sec. IV to cases where there are multiple types of normal and magic qubits (for in- stance because some normal gates require more qubits than other normal gates, or because there are different type of magic gates, each requiring a different number...

    work page

  3. [3]

    There rflag s is the time multiplicity for the ancillary states used in the flag EC gadget, whilerflag H is the time multiplicity for the |H⟩ magic-state

    Time multiplicities for flag-qubits We need to estimate the time multiplicity coefficients shown in Table II. There rflag s is the time multiplicity for the ancillary states used in the flag EC gadget, whilerflag H is the time multiplicity for the |H⟩ magic-state. To be more precise, we assume that the flag EC gadget uses a pool of 3 ancillary qubits that...

    work page

  4. [4]

    costs” (i.e. physical qubit costs) for different error-correction schemes, while assuming the “benefits

    Failure multiplicities for flag-qubits Here we explain the assumptions we used in order to to find the values of Nflag 0/+ and Nflag H given in Table I (they 38 Figure 15. Fault-tolerant preparation of the logical |+⟩: |+⟩-FT-Prep encoded in Steane code (top 7 qubits), with a verification based on flag qubits, from Refs [32] and [40]. The verification req...

    work page

  5. [5]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, A Quan- tum Approximate Optimization Algorithm, arXiv 10.48550/arXiv.1411.4028 (2014), 1411.4028

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1411.4028 2014

  6. [6]

    Amaro, C

    D. Amaro, C. Modica, M. Rosenkranz, M. Fioren- tini, M. Benedetti, and M. Lubasch, Filtering varia- tional quantum algorithms for combinatorial optimiza- tion, Quantum Sci. Technol. 7, 015021 (2022)

    work page 2022

  7. [7]

    Bauer, S

    B. Bauer, S. Bravyi, M. Motta, and G. K.-L. Chan, Quantum Algorithms for Quantum Chemistry and Quan- tum Materials Science, Chem. Rev. 120, 12685 (2020)

    work page 2020

  8. [8]

    Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. John- son, M. Kieferov´ a, I. D. Kivlichan, T. Menke, B. Per- opadre, N. P. D. Sawaya, S. Sim, L. Veis, and A. Aspuru- Guzik, Quantum Chemistry in the Age of Quantum Com- puting, Chem. Rev. 119, 10856 (2019)

    work page 2019

  9. [9]

    H. Ma, M. Govoni, and G. Galli, Quantum simulations of materials on near-term quantum computers, npj Com- put. Mater. 6, 1 (2020)

    work page 2020

  10. [10]

    P. W. Shor, Polynomial-Time Algorithms for Prime Fac- torization and Discrete Logarithms on a Quantum Com- puter, SIAM J. Comput. 10.1137/S0097539795293172 (2006)

    work page doi:10.1137/s0097539795293172 2006

  11. [11]

    H¨ aner, S

    T. H¨ aner, S. Jaques, M. Naehrig, M. Roetteler, and M. Soeken, Improved Quantum Circuits for Elliptic 41 Curve Discrete Logarithms, in Post-Quantum Cryptog- raphy (Springer, Cham, Switzerland, 2020) pp. 425–444

    work page 2020

  12. [12]

    Shor, Fault-tolerant quantum computation, in Pro- ceedings of 37th Conference on Foundations of Computer Science (1996) pp

    P. Shor, Fault-tolerant quantum computation, in Pro- ceedings of 37th Conference on Foundations of Computer Science (1996) pp. 56–65

    work page 1996

  13. [13]

    Knill, R

    E. Knill, R. Laflamme, and W. H. Zurek, Resilient quan- tum computation: error models and thresholds, Proceed- ings of the Royal Society of London. Series A: Mathemat- ical, Physical and Engineering Sciences 454, 365 (1998)

    work page 1998

  14. [14]

    Preskill, Reliable quantum computers, Proceedings of the Royal Society of London

    J. Preskill, Reliable quantum computers, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 385 (1998)

    work page 1998

  15. [15]

    Aharonov and M

    D. Aharonov and M. Ben-Or, Fault-tolerant quantum computation with constant error rate, SIAM Journal on Computing 38, 1207 (2008), https://doi.org/10.1137/S0097539799359385

    work page doi:10.1137/s0097539799359385 2008

  16. [16]

    Quantum accuracy threshold for concatenated distance-3 codes

    P. Aliferis, D. Gottesman, and J. Preskill, Quantum accu- racy threshold for concatenated distance-3 codes (2005), arXiv:quant-ph/0504218

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  17. [17]

    B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015)

    work page 2015

  18. [18]

    E. T. Campbell, B. M. Terhal, and C. Vuillot, Roads towards fault-tolerant universal quantum computation, Nature 549, 172 (2017)

    work page 2017

  19. [19]

    Roffe, Quantum error correction: an introductory guide, Contemp

    J. Roffe, Quantum error correction: an introductory guide, Contemp. Phys. 60, 226 (2019)

    work page 2019

  20. [20]

    A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012)

    work page 2012

  21. [21]

    Y. Liu, Z. Ma, L. Luo, C. Du, Y. Fei, H. Wang, Q. Duan, and J. Yang, Magic state distillation and cost analysis in fault-tolerant universal quantum computation, Quantum Science and Technology 8, 043001 (2023)

    work page 2023

  22. [22]

    Krishna and J.-P

    A. Krishna and J.-P. Tillich, Towards Low Overhead Magic State Distillation, Physical Review Letters 123, 070507 (2019)

    work page 2019

  23. [23]

    A Low-Overhead Hybrid Approach for Universal Fault-Tolerant Quantum Computation

    E. Nikahd, M. S. Zamani, and M. Sedighi, A Low- Overhead Hybrid Approach for Universal Fault-Tolerant Quantum Computation (2017), arXiv:1610.03309

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  24. [24]

    Magic state distillation with low overhead

    S. Bravyi and J. Haah, Magic state distillation with low overhead, Physical Review A 86, 052329 (2012), arXiv:1209.2426

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  25. [25]

    Webster, S

    P. Webster, S. D. Bartlett, and D. Poulin, Reducing the overhead for quantum computation when noise is biased, Physical Review A 92, 062309 (2015)

    work page 2015

  26. [26]

    Codes and Protocols for Distilling $T$, controlled-$S$, and Toffoli Gates

    J. Haah and M. B. Hastings, Codes and Protocols for Distilling T , controlled- S, and Toffoli Gates, Quantum 2, 71 (2018), arXiv:1709.02832

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  27. [27]

    M. B. Hastings and J. Haah, Distillation with Subloga- rithmic Overhead, Physical Review Letters 120, 050504 (2018)

    work page 2018

  28. [28]

    Goto, Step-by-step magic state encoding for efficient fault-tolerant quantum computation, Scientific Reports 4, 7501 (2014)

    H. Goto, Step-by-step magic state encoding for efficient fault-tolerant quantum computation, Scientific Reports 4, 7501 (2014)

    work page 2014

  29. [29]

    Kissinger and J

    A. Kissinger and J. van de Wetering, Reducing the num- ber of non-Clifford gates in quantum circuits, Phys. Rev. A 102, 022406 (2020)

    work page 2020

  30. [30]

    A. G. Fowler, S. J. Devitt, and C. Jones, Surface code implementation of block code state distillation, Scientific Reports 3, 1939 (2013)

    work page 1939

  31. [31]

    Li, A magic state’s fidelity can be superior to the op- erations that created it, New J

    Y. Li, A magic state’s fidelity can be superior to the op- erations that created it, New J. Phys. 17, 023037 (2015)

    work page 2015

  32. [32]

    Chamberland, T

    C. Chamberland, T. Jochym-O’Connor, and R. Laflamme, Overhead analysis of universal con- catenated quantum codes, Phys. Rev. A 95, 022313 (2017)

    work page 2017

  33. [33]

    O’Gorman and E

    J. O’Gorman and E. T. Campbell, Quantum computa- tion with realistic magic-state factories, Phys. Rev. A95, 032338 (2017)

    work page 2017

  34. [34]

    J. Haah, M. B. Hastings, D. Poulin, and D. Wecker, Magic State Distillation with Low Space Overhead and Optimal Asymptotic Input Count, Quantum 1, 31 (2017), arXiv:1703.07847

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  35. [35]

    E. T. Campbell and M. Howard, Magic state parity-checker with pre-distilled components (2018), arXiv:1709.02214

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  36. [37]

    Chamberland and K

    C. Chamberland and K. Noh, Very low overhead fault- tolerant magic state preparation using redundant ancilla encoding and flag qubits, npj Quantum Information 6, 91 (2020)

    work page 2020

  37. [38]

    Chamberland, T

    C. Chamberland, T. Jochym-O’Connor, and R. Laflamme, Thresholds for Universal Concate- nated Quantum Codes, Physical Review Letters 117, 010501 (2016)

    work page 2016

  38. [39]

    Using concatenated quantum codes for universal fault-tolerant quantum gates

    T. Jochym-O’Connor and R. Laflamme, Using concate- nated quantum codes for universal fault-tolerant quan- tum gates, Physical Review Letters 112, 010505 (2014), arXiv:1309.3310

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  39. [40]

    Litinski, Magic State Distillation: Not as Costly as You Think, Quantum 3, 205 (2019), 1905.06903v3

    D. Litinski, Magic State Distillation: Not as Costly as You Think, Quantum 3, 205 (2019), 1905.06903v3

    work page arXiv 2019

  40. [41]

    Magic state cultivation: growing T states as cheap as CNOT gates

    C. Gidney, N. Shutty, and C. Jones, Magic state cultiva- tion: growing T states as cheap as CNOT gates, arXiv 10.48550/arXiv.2409.17595 (2024), 2409.17595

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2409.17595 2024

  41. [42]

    How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits,

    C. Gidney and M. Eker˚ a, How to factor 2048 bit RSA in- tegers in 8 hours using 20 million noisy qubits, Quantum 5, 433 (2021), 1905.09749v3

    work page arXiv 2048

  42. [43]

    Ref. [24] also only considered resources in an example where both magic states and cnots are implemented via state injection; in our language, this means it considered all operations as magic operations. Our approach evalu- ates resources for both normal and magic operations

    work page

  43. [44]

    Quantum error correction with only two extra qubits

    R. Chao and B. W. Reichardt, Quantum error correction with only two extra qubits, Physical Review Letters121, 050502 (2018), arXiv:1705.02329

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  44. [45]

    B. W. Reichardt, Fault-tolerant quantum error correc- tion for Steane’s seven-qubit color code with few or no extra qubits, Quantum Science and Technology6, 015007 (2021), arXiv:1804.06995

    work page arXiv 2021

  45. [46]

    The verification is probabilistic because it is a probabilis- tic process with a finite chance of failing verification

    work page

  46. [47]

    As we were finishing this work, we became aware of a new proposal to further reduce the resources needed for error correction [78], but we have not yet analyzed it

    work page

  47. [48]

    This toy-model is intended to explore only the effect of the EC gadget’ size, so it does not capture other aspects of the flag-qubit scheme

    The flag-qubit scheme that we consider not only has a different size EC gadget from the Steane scheme, it also has other differences (such as slightly less-costly magic states). This toy-model is intended to explore only the effect of the EC gadget’ size, so it does not capture other aspects of the flag-qubit scheme

    work page

  48. [49]

    level- k

    To avoid any ambiguity, we explicitly state that we only use the term “level- k” to refer to the level- k circuit in which magic gates have not yet been replaced by state- injection gadgets. We only implement the state-injection as part of the protocol that writes level- k operations in terms of level-(k − 1) operations. 42

    work page

  49. [50]

    Fellous-Asiani, J

    M. Fellous-Asiani, J. H. Chai, R. S. Whitney, A. Auff` eves, and H. K. Ng, Limitations in Quantum Computing from Resource Constraints, PRX Quantum 2, 040335 (2021)

    work page 2021

  50. [51]

    Fellous-Asiani, J

    M. Fellous-Asiani, J. H. Chai, Y. Thonnart, H. K. Ng, R. S. Whitney, and A. Auff` eves, Optimizing Resource Efficiencies for Scalable Full-Stack Quantum Computers, PRX Quantum 4, 040319 (2023)

    work page 2023

  51. [52]

    Energetics of Trapped-Ion Quantum Computation

    F. G´ ois, M. Pezzutto, and Y. Omar, Towards En- ergetic Quantum Advantage in Trapped-Ion Quantum Computation, arXiv 10.48550/arXiv.2404.11572 (2024), 2404.11572

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2404.11572 2024

  52. [53]

    M. C. Volpato and P.-L. de Assis, Estimating the electri- cal energy cost of performing arbitrary state preparation using qubits and qudits in integrated photonic circuits, arXiv 10.48550/arXiv.2402.16603 (2024), 2402.16603

    work page doi:10.48550/arxiv.2402.16603 2024

  53. [54]

    In contrast, for a completely arbitrary algorithm, one may need to use our method to the evaluate the physi- cal qubit cost of every layer before discovering which one is the bottleneck layer, Lmax. There may even be some cases where the highest qubit cost is not during the cal- culation, but rather at the moment of preparation of the logical qubits that ...

    work page

  54. [55]

    time multiplicity

    An algorithm implementing Lmax at every step, requires more qubits than an algorithm implementing Lmax only once. This is because the latter would not need to be preparing ancillary states for future layers (or reading ancillary states from preceding layers) at the same time as carrying out Lmax. The extra resources required to implement Lmax at every ste...

    work page

  55. [56]

    This clearly overestimates the qubit cost of such a magic qubit

    We note that this treats an ancillary qubit that undergoes a single magic operation during its usage as if it experi- enced a magic operation at every time step. This clearly overestimates the qubit cost of such a magic qubit. How- ever, as we show that this cost is not so large, a better estimate would only reinforce this conclusion

    work page

  56. [57]

    (7) in the standard manner

    This can be found using Eq. (7) in the standard manner

    work page

  57. [58]

    Firstly, λnormal, λmagic, and b are positive numbers

    Monotonic growth with K is guaranteed by two observa- tions. Firstly, λnormal, λmagic, and b are positive numbers. Secondly, for the regime where λnormal > λ magic, we use b > λ normal, which holds for the reasons explained below Eq. (14)

    work page

  58. [59]

    Then the upper-bound for each one is the largest matrix element in the respective matrix, multiplied by the number of rows in that matrix

    As explained in Appendix B, λnormal, λmagic and b can become matrices when there are multiple types. Then the upper-bound for each one is the largest matrix element in the respective matrix, multiplied by the number of rows in that matrix

    work page

  59. [60]

    Here ⌈x⌉ is the ceiling function, so ⌈x⌉ is the smallest integer greater than x

    work page

  60. [61]

    In the case where τanc(k)/τL(k) is unbounded when k grows (which never occurs in the examples we treat later on), one can simply redefine r ≡ maxk∈[1,K]⌈τanc(k)/τL(k)⌉ so that the maximum is well- defined over the targeted concatenations levels the exper- imentalist wish to implement

    work page

  61. [62]

    Fault-tolerant magic state preparation with flag qubits

    C. Chamberland and A. W. Cross, Fault-tolerant magic state preparation with flag qubits, Quantum 3, 143 (2019), 1811.00566v2

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  62. [63]

    However, when errors are independent, such a prob- ability takes the form 1 − (1 − p)N, for which the upper bound N p is quite tight for the concrete values in Table I

    The upper-bound of N p does not require independent er- rors. However, when errors are independent, such a prob- ability takes the form 1 − (1 − p)N, for which the upper bound N p is quite tight for the concrete values in Table I

    work page

  63. [64]

    If there are multiple exRecs with different Ms, we sim- plify our analysis (while getting an upper bound) by re- placing all these Ms by whichever M is largest

    work page

  64. [65]

    This shows that even very large computations will not be large enough to be approximated by the law of large numbers

    These values are still significantly larger than that given by the law of large numbers, 1/(1 − N pthres). This shows that even very large computations will not be large enough to be approximated by the law of large numbers

    work page

  65. [66]

    Bluvstein, S

    D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kali- nowski, D. Hangleiter, J. P. Bonilla Ataides, N. Maskara, I. Cong, X. Gao, P. Sales Rodriguez, T. Karolyshyn, G. Semeghini, M. J. Gullans, M. Greiner, V. Vuleti´ c, and M. D. Lukin, Logical quantum processor based on reconfigurable atom arrays, Nature 626, ...

    work page 2024

  66. [67]

    Rigorously speaking, Nlevel-1 gates could be bigger than Qphys total(K−1)×DK−1×2DL. This is because, DK−1×2DL does not account for the duration required to prepare the ancillary level-( K − 1) states required to implement the level- K circuit (for instance the qubits required by the magic states). Their duration of preparation may be long enough that they...

    work page

  67. [68]

    This is because Fig

    We think it plausible to assume that practical quantum computers with not have concatenation level, K > 5. This is because Fig. 1 shows that at K = 5 all error- correction schemes considered here require millions of physical qubit for each qubit in the logical algorithm (with Steane scheme requiring billions). A large-scale quantum algorithm (like Shor co...

    work page 2048

  68. [69]

    This Z Aπ/4 can be injected and used to perform a T -gate, one would simply have to apply an additional logical Z in the block marked “S” in Fig

    The gadget in figure 11a will prepare Z Aπ/4 instead of Aπ/4 , whenever the logical X measurement of the repetition qubits in both gadgets indicated −1, and both Steane EC-gadgets detect no error. This Z Aπ/4 can be injected and used to perform a T -gate, one would simply have to apply an additional logical Z in the block marked “S” in Fig. 10. This addit...

    work page

  69. [70]

    1, which corre- sponds to a circuit without magic gates

    For this we start with the dashed curve for Steane code without shared state preparation in Fig. 1, which corre- sponds to a circuit without magic gates. We then multiply it by 17.6 (taken from Eq. 40) to arrive at the case where all gates are magic gates, and round to the nearest order of magnitude

    work page

  70. [71]

    Tansuwannont, B

    T. Tansuwannont, B. Pato, and K. R. Brown, Adaptive syndrome measurements for shor-style error correction, Quantum 7, 1075 (2023)

    work page 2023

  71. [72]

    B. Pato, T. Tansuwannont, S. Huang, and K. R. Brown, Optimization tools for distance-preserving flag fault-tolerant error correction, PRX Quantum 5, 020336 (2024)

    work page 2024

  72. [73]

    Fast versions of Shor's quantum factoring algorithm

    C. Zalka, Fast versions of Shor’s quantum factoring algo- rithm, arXiv 10.48550/arXiv.quant-ph/9806084 (1998), quant-ph/9806084

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.quant-ph/9806084 1998

  73. [74]

    Banegas, D

    G. Banegas, D. J. Bernstein, I. van Hoof, and T. Lange, Concrete quantum cryptanalysis of binary elliptic curves, TCHES , 451 (2021). 43

    work page 2021

  74. [75]

    Scherer, B

    A. Scherer, B. Valiron, S.-C. Mau, S. Alexander, E. van den Berg, and T. E. Chapuran, Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target, Quantum Inf. Process. 16, 60 (2017)

    work page 2017

  75. [76]

    Chakrabarti, R

    S. Chakrabarti, R. Krishnakumar, G. Mazzola, N. Stam- atopoulos, S. Woerner, and W. J. Zeng, A Threshold for Quantum Advantage in Derivative Pricing, Quantum 5, 463 (2021), 2012.03819v3

    work page arXiv 2021

  76. [77]

    Reiher, N

    M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quan- tum computers, Proc. Natl. Acad. Sci. U.S.A. 114, 7555 (2017)

    work page 2017

  77. [78]

    Gidney, Quantum block lookahead adders and the wait for magic states, arXiv 10.48550/arXiv.2012.01624 (2020), 2012.01624

    C. Gidney, Quantum block lookahead adders and the wait for magic states, arXiv 10.48550/arXiv.2012.01624 (2020), 2012.01624

    work page doi:10.48550/arxiv.2012.01624 2012

  78. [79]

    Flag fault-tolerant error correction with arbitrary distance codes

    C. Chamberland and M. E. Beverland, Flag fault-tolerant error correction with arbitrary distance codes, Quantum 2, 53 (2018), 1708.02246v3

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  79. [80]

    Chao and B

    R. Chao and B. W. Reichardt, Quantum Error Correc- tion with Only Two Extra Qubits, Phys. Rev. Lett. 121, 050502 (2018)

    work page 2018

  80. [81]

    Liou and C.-Y

    P.-H. Liou and C.-Y. Lai, Parallel syndrome extraction with shared flag qubits for Calderbank-Shor-Steane codes of distance three, Phys. Rev. A 107, 022614 (2023)

    work page 2023

Showing first 80 references.