REVIEW 4 major objections 6 minor 31 references
Medusa claims that a small number of tuned flag qubits can make an N-qubit adder-like circuit fail as rarely as an N-1-qubit circuit.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
2026-08-03 21:09 UTC pith:NZTM523B
load-bearing objection The heuristic and simulations are plausible, but Algorithm 1's binary search is described upside down and the reported m values are not reproducible from the paper as written. the 4 major comments →
Medusa: Detecting and Removing Failures for Scalable Quantum Computing
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Starting from CNOT-only circuits in ICM form, Medusa attaches unique X- and Z-flags so that errors are caught before they spread, post-selects runs where no flag fired, and defines the post-selected failure rate as missed failures divided by accepted runs. The key numerical discovery is that even a modest improvement in flag reliability---captured by an error multiplier m below 1---lowers the whole circuit's failure rate, and for adder-like topologies the required m is reachable with moderate-distance surface codes. Concretely, the paper demonstrates that an N-qubit adder-like circuit can be tuned, using about 5 log2 N flags, to reach the failure rate of an N-1-qubit circuit. This means the
What carries the argument
The central mechanism is the flag qubit combined with an error multiplier m. A flag is a qubit connected by two CNOTs around a stretch of circuit; its final measurement reveals whether an error occurred in that stretch. The error multiplier m scales the base depolarizing noise p_ncs down to p_f = m * p_ncs for the gates touching the flags. Medusa ranks unique flags by weight (the number of CNOTs they surround), simulates noisy flagged circuits against stabilizer truth tables to compute the post-selected failure rate, and binary-searches m so the circuit reaches a target failure rate such as the flagless failure rate of an (N-1)-qubit circuit. The m=0 perfect-flag simulation gives an upper bo
Load-bearing premise
The central premise is that only the gates touching the flags need protection--flag error rates can be set to m times the data error rate while the CNOTs linking flags to data are left out of the resource count; if those links must be error-corrected, the reported costs are too low.
What would settle it
Rerun the paper's simulations with noisy initialization and measurement, or include the flag-to-data CNOTs in the resource estimate, and check whether an N-qubit circuit with the predicted m still reaches the failure rate of the N-1 circuit.
If this is right
- For adder-like circuits, an N-qubit implementation can be tuned to the failure rate of an N-1-qubit implementation using a logarithmic number of flags, so error-correction cost need not track circuit size as steeply.
- Smaller circuits require relatively more flag error correction than larger circuits to gain one qubit's worth of failure-rate improvement, since the required m is smaller for small N.
- The perfect-flag simulation gives a numerical upper bound: for a chosen flag set, no amount of flag error correction can beat that failure rate.
- A slight improvement in local flag fault-tolerance reduces the entire circuit's failure rate, supporting partial error correction instead of fully protected syndrome extraction.
- The reported physical-qubit counts are lower bounds, because they exclude error correction of the CNOTs connecting flags to data qubits.
Where Pith is reading between the lines
- If the connecting CNOTs between flags and data qubits must themselves be error corrected, the reported surface-code footprints would likely rise; the qualitative benefit may survive, but the cost break-even point would shift.
- The same stabilizer-truth-table and binary-search recipe could transfer to other structured circuit families whose gate count scales with qubit number, such as QFT-like or QRAM-like circuits, though the required m values would need fresh simulation.
- The one-step 'N behaves like N-1' result suggests a recursive strategy: repeated Medusa-style flagging could climb down several circuit sizes, trading full QEC for layers of protected flags, provided error accumulation across nested flags is checked.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces Medusa, an automated compilation method that inserts flag qubits into ICM-form quantum circuits to lower their post-selected failure rate (FR). The method uses a weight-based heuristic for placing unique flags, Stim-based noisy simulation to estimate FR, and a binary-search procedure over an 'error multiplier' m that scales the noise on gates touching the flags. The central benchmark shows that for adder-like circuits, an N-qubit circuit can be tuned to match the FR of an (N−1)-qubit circuit; the required m is then mapped to surface-code distances and physical qubit counts. The authors conclude that partially error-corrected flags offer a cost-effective way to reduce logical failure rates in structured circuits.
Significance. The idea of exploiting circuit structure to reduce QEC overhead is timely and potentially valuable for early fault-tolerant computation. The paper contributes a concrete flag-insertion heuristic, uses a reproducible simulator (Stim), and provides explicit resource estimates. If the results hold, the approach could inform practical compilation choices. However, the central numerical result—the m values in Fig. 4d—is not reproducible from the described Algorithm 1, and the resource estimates are explicitly incomplete because they omit the cost of protecting the flag–data CNOTs. These issues must be resolved before the quantitative claims can be accepted. The qualitative conclusion that better-protected flags lower FR is plausible and supported by Fig. 5, but the paper's current form overstates the reliability of its headline numbers.
major comments (4)
- [Sec. 2.4 / Algorithm 1] The binary-search update is inverted relative to the monotonicity of FR(m). Since p_f = m·p_ncs and Fig. 5 shows FR decreases as m decreases, FR is increasing in m. Therefore, when FR > FR_target the algorithm should decrease m by setting b←m. The pseudocode instead sets a←m, driving m upward; this cannot produce the interior m values reported in Fig. 4d. The accompanying text also reverses the terminology: m=0 (perfect flags) gives the lowest FR, hence is a lower bound on FR, not the 'upper bound' as stated. As written, the paper does not specify a procedure that yields the published m values.
- [Sec. 3.1 / Algorithm 1] The stopping tolerance ε=0.0005 is comparable to the binomial standard error of the FR estimate from 10^6 simulation runs (max sqrt(0.25/1e6)=0.0005). No error bars or confidence intervals are provided in Fig. 4d. The binary search may therefore be chasing sampling noise rather than a genuine threshold, and the reported m–N curves may not be reproducible. Please report repeated trials, confidence intervals, or increase the sample size / relax ε so that the tuning is statistically meaningful.
- [Sec. 3.4] The resource estimates in Fig. 4f explicitly exclude the qubits needed to error-correct the two-qubit gates between the flags and the data qubits, and the authors label the estimate a 'lower bound.' This omission is load-bearing for the cost-benefit conclusion, because the entire tuning mechanism relies on those connecting CNOTs having error rate p_f. If protecting these CNOTs is necessary or expensive, the reported qubit counts could be substantially too low. The paper should either quantify this overhead or substantially soften the claim that partially protected flags are 'cost-effective.'
- [Algorithm 1] The inner while-loop does not reset the binary-search bounds a and b when the number of flags f is incremented. Since adding a flag changes FR, a previously converged m is no longer valid for the new circuit, and carrying over the interval may cause the search to exit prematurely or oscillate. The exact search procedure over f needs to be specified precisely for the reported results to be reproducible.
minor comments (6)
- [Abstract / Sec. 1.3] The phrase 'numerically upper bound the failure rate' is misleading: perfect flags give the lowest possible FR for a given heuristic, i.e., a lower bound on the achievable failure rate, not an upper bound. Please correct the terminology.
- [Fig. 1 caption] Typo: 'wether' should be 'whether'.
- [Sec. 3.1] The paper uses at most 100 random input strings per circuit. For circuits with more than 100 qubits, this is a small sample of the input space; please discuss how representative this is for the stabilizer-based FR estimate.
- [Sec. 2.4] The statement that 'a and b are lower bounded by a threshold value that limits the depth of binary search' is vague, and the pseudocode contains no such threshold. Please clarify the termination criterion.
- [Sec. 3.3] The benchmark circuits are 'adder-like' after removing T and H gates from real adders. The paper is transparent about this, but the abstract's phrasing 'large-scale implementations' may overstate relevance to quantum algorithms that require T gates. Consider clarifying this limitation in the conclusion as well.
- [Sec. 2.2] There is no comparison of the weight-based flag selection to random placement or to a fixed number of flags. A baseline would strengthen the claim that the heuristic's ranking is effective.
Circularity Check
No significant circularity: Medusa's m-tuning result is an explicit inversion to an externally defined target, not a prediction reduced from its inputs.
full rationale
Medusa's central numerical claim is that an error multiplier m can be found so that FR_m(N) matches FR(N-1); this is an explicit target-inversion procedure, stated in Sec. 3.3 as "we wish to tune the value of m such that an N-circuit reaches a target FR_tar equivalent to the failure rate of a N-1 circuit" and implemented by the binary search in Alg. 1. Showing that such an m exists is a construction/feasibility statement, not a prediction extracted from the fitted value, so the fitted-input-called-prediction pattern does not apply. The perfect-flag m=0 simulation is a benchmark, and the target is defined by the flagless N-1 circuit rather than by the perfect-flag bound, so there is no definitional collapse. Self-citations [25,31] supply the ICM compilation formalism, but they are background and do not carry the failure-rate result; the numerical FR values come from independent Stim simulations, and the surface-code resource mapping uses an external formula from [24]. The paper explicitly labels the resource estimates as a lower bound because connecting-CNOT error correction is excluded (Sec. 3.4), which is a stated limitation rather than a hidden circular step. The Sec. 2.4 labels calling m=0 the 'upper bound' and m=1 the 'lower bound' appear reversed relative to Fig. 5, and the branch logic in Alg. 1 looks inverted relative to FR(m) monotonicity; these are reproducibility/correctness concerns, not circularity. No load-bearing step reduces to its own inputs.
Axiom & Free-Parameter Ledger
free parameters (3)
- error multiplier m =
varies with N and p_ncs; see Fig. 4d
- number of flags = 5 log2(N) =
coefficient 5
- epsilon (binary search tolerance) =
0.0005
axioms (5)
- domain assumption Arbitrary computations can be pre-compiled to ICM circuits (CNOT-only) without loss of generality.
- domain assumption Noise model: only CNOT gates are depolarizing with rate p_ncs; qubit initialization and measurement are noiseless.
- domain assumption Flags can be protected by surface codes so that gates touching them have error rate p_f = m*p_ncs, without error-correcting the connecting CNOTs.
- domain assumption Surface code logical error rate formula p_f = 0.08*(p_ncs/0.0053)^{0.58d-0.27} from [24] is correct for the regimes used.
- domain assumption Randomly selected 100 input strings are representative for failure-rate estimation.
read the original abstract
Quantum circuits will experience failures that lead to computational errors. We introduce Medusa, an automated compilation method for lowering a circuit's failure rate. Medusa uses flags to predict the absence of high-weight errors. Our method can numerically upper bound the failure rate of a circuit in the presence of flags, and fine tune the fault-tolerance of the flags in order to reach this bound. We assume the flags can have an increased fault-tolerance as a result of applying surface QECs to the gates interacting with them. We use circuit level depolarizing noise to evaluate the effectiveness of these flags in revealing the absence of the high-weight stabilizers. Medusa reduces the cost of quantum-error-correction (QEC) because the underlying circuit has a lower failure rate. We benchmark our approach using structured quantum circuits representative of ripple-carry adders. In particular, our flag scheme demonstrates that for adder-like circuits, the failure rate of large-scale implementations can be lowered to fit the failure rates of smaller-scale circuits. We show numerically that a slight improvement in the local fault-tolerance of the flag-qubits can lead to a reduction in the overall failure rate of the entire quantum circuit.
Figures
Reference graph
Works this paper leans on
-
[1]
Physical Review A—Atomic, Molecular, and Optical Physics 70, 5 (2004), 052328
Aaronson, S., and Gottesman, D.Improved simulation of stabilizer circuits. Physical Review A—Atomic, Molecular, and Optical Physics 70, 5 (2004), 052328
2004
-
[2]
M.Automated flag qubit insertion for reliable quantum circuit output
Acharya, N., and Saeed, S. M.Automated flag qubit insertion for reliable quantum circuit output. In2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)(2021), IEEE, pp. 431–436
2021
-
[3]
In25th International Conference on Theory and Applications of Satisfiability Testing(2022)
Berent, L., Burgholzer, L., and Wille, R.Towards a sat encoding for quan- tum circuits. In25th International Conference on Theory and Applications of Satisfiability Testing(2022)
2022
-
[4]
G., and Feld, S
Bhatnagar, D., Steinberg, M., Elkouss, D., Almudever, C. G., and Feld, S. Low-depth flag-style syndrome extraction for small quantum error-correction codes. In2023 IEEE International Conference on Quantum Computing and Engi- neering (QCE)(2023), vol. 1, IEEE, pp. 63–69
2023
-
[5]
A., Li, S
Bluvstein, D., Geim, A. A., Li, S. H., Evered, S. J., Bonilla Ataides, J. P., Baranes, G., Gu, A., Manovitz, T., Xu, M., Kalinowski, M., et al.A fault- tolerant neutral-atom architecture for universal quantum computation.Nature (2025), 1–3
2025
-
[6]
Bombin, H., Litinski, D., Nickerson, N., Pastawski, F., and Roberts, S.Unify- ing flavors of fault tolerance with the zx calculus.Quantum 8(2024), 1379
2024
-
[7]
J., Browne, D
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., and V an den Nest, M. Measurement-based quantum computation.Nature Physics 5, 1 (2009), 19–26
2009
-
[8]
InProceedings of the 26th Asia and South Pacific Medusa: Detecting and Removing Failures for Scalable Quantum Computing Design Automation Conference(2021), pp
Burgholzer, L., Kueng, R., and Wille, R.Random stimuli generation for the verification of quantum circuits. InProceedings of the 26th Asia and South Pacific Medusa: Detecting and Removing Failures for Scalable Quantum Computing Design Automation Conference(2021), pp. 767–772
2021
-
[9]
W.Fault-tolerant magic state preparation with flag qubits.Quantum 3(2019), 143
Chamberland, C., and Cross, A. W.Fault-tolerant magic state preparation with flag qubits.Quantum 3(2019), 143
2019
-
[10]
W.Fault-tolerant quantum computation with few qubits.npj Quantum Information 4, 1 (2018), 42
Chao, R., and Reichardt, B. W.Fault-tolerant quantum computation with few qubits.npj Quantum Information 4, 1 (2018), 42
2018
-
[11]
W.Quantum error correction with only two extra qubits.Physical review letters 121, 5 (2018), 050502
Chao, R., and Reichardt, B. W.Quantum error correction with only two extra qubits.Physical review letters 121, 5 (2018), 050502
2018
-
[12]
W.Flag fault-tolerant error correction for any stabilizer code.PRX Quantum 1, 1 (2020), 010302
Chao, R., and Reichardt, B. W.Flag fault-tolerant error correction for any stabilizer code.PRX Quantum 1, 1 (2020), 010302
2020
-
[13]
In2024 15th International Conference on Information and Communication Technology Convergence (ICTC)(2024), IEEE, pp
Cho, E., and Cha, G.Accelerated flag qubit allocation for fault-tolerant quan- tum error correction. In2024 15th International Conference on Information and Communication Technology Convergence (ICTC)(2024), IEEE, pp. 673–676
2024
-
[14]
M., and Brown, K
Debroy, D. M., and Brown, K. R.Extended flag gadgets for low-overhead circuit verification.Physical Review A 102, 5 (2020), 052409
2020
-
[15]
Physical Review Letters 134, 9 (2025), 090603
Delfosse, N., and Tham, E.Low-cost noise reduction for clifford circuits. Physical Review Letters 134, 9 (2025), 090603
2025
-
[16]
[17]Gidney, C.Stim: a fast stabilizer circuit simulator.Quantum 5(2021), 497
Eisert, J., and Preskill, J.Mind the gaps: The fraught road to quantum advan- tage.arXiv preprint arXiv:2510.19928(2025). [17]Gidney, C.Stim: a fast stabilizer circuit simulator.Quantum 5(2021), 497
Pith/arXiv arXiv 2025
-
[18]
Gidney, C., and Ekerå, M.How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits.Quantum 5(2021), 433
2048
-
[19]
P., Khattar, T., Yuan, C., Peduri, A., Yosri, N., Malone, F
Harrigan, M. P., Khattar, T., Yuan, C., Peduri, A., Yosri, N., Malone, F. D., Babbush, R., and Rubin, N. C.Expressing and analyzing quantum algorithms with qualtran.arXiv preprint arXiv:2409.04643(2024)
Pith/arXiv arXiv 2024
-
[20]
Henriet, L., Beguin, L., Signoles, A., Lahaye, T., Browaeys, A., Reymond, G.-O., and Jurczak, C.Quantum computing with neutral atoms.Quantum 4 (2020), 327
2020
-
[21]
G.Qram: A survey and critique.arXiv preprint arXiv:2305.10310(2023)
Jaqes, S., and Rattew, A. G.Qram: A survey and critique.arXiv preprint arXiv:2305.10310(2023)
arXiv 2023
-
[22]
A., and Brun, T
Lidar, D. A., and Brun, T. A.Quantum error correction. Cambridge university press, 2013
2013
-
[23]
Liou, P.-H., and Lai, C.-Y.Reducing quantum error correction overhead with ver- satile flag-sharing syndrome extraction circuits.IEEE Transactions on Quantum Engineering(2025)
2025
-
[24]
R., and Devitt, S.Compare the pair: Rotated versus unrotated surface codes at equal logical error rates.Physical Review Research 7, 3 (2025), 033074
O’Rourke, A. R., and Devitt, S.Compare the pair: Rotated versus unrotated surface codes at equal logical error rates.Physical Review Research 7, 3 (2025), 033074
2025
-
[25]
J.Fault-tolerant, high-level quantum circuits: form, compilation and description.Quantum Science and Technology 2, 2 (2017), 025003
Paler, A., Polian, I., Nemoto, K., and Devitt, S. J.Fault-tolerant, high-level quantum circuits: form, compilation and description.Quantum Science and Technology 2, 2 (2017), 025003
2017
-
[26]
[27]Preskill, J.Beyond nisq: The megaquop machine, 2025
Peham, T., Schmid, L., Berent, L., Müller, M., and Wille, R.Automated synthesis of fault-tolerant state preparation circuits for quantum error-correction codes.PRX Quantum 6, 2 (2025), 020330. [27]Preskill, J.Beyond nisq: The megaquop machine, 2025
2025
-
[28]
Ransford, A., Allman, M., Arkinstall, J., Campora III, J., Cooper, S. F., De- laney, R. D., Dreiling, J. M., Estey, B., Figgatt, C., Hall, A., et al.Helios: A 98-qubit trapped-ion quantum computer.arXiv preprint arXiv:2511.05465(2025)
Pith/arXiv arXiv 2025
-
[29]
InProceedings of the 28th Asia and South Pacific Design Automation Conference(2023), pp
Schneider, S., Burgholzer, L., and Wille, R.A sat encoding for optimal clifford circuit synthesis. InProceedings of the 28th Asia and South Pacific Design Automation Conference(2023), pp. 190–195
2023
-
[30]
Shaik, I., and van de Pol, J.Cnot-optimal clifford synthesis as sat.arXiv preprint arXiv:2504.00634(2025)
Pith/arXiv arXiv 2025
-
[31]
K., Paler, A., Gavriel, J., Myers, C
Vijayan, M. K., Paler, A., Gavriel, J., Myers, C. R., Rohde, P. P., and Devitt, S. J. Compilation of algorithm-specific graph states for quantum circuits.Quantum Science and Technology 9, 2 (2024), 025005
2024
-
[32]
Zen, R., Olle, J., Colmenarez, L., Puviani, M., Müller, M., and Marqardt, F.Quantum circuit discovery for fault-tolerant logical state preparation with reinforcement learning.arXiv preprint arXiv:2402.17761(2024)
arXiv 2024
-
[33]
D.Algorithmic fault tolerance for fast quantum computing.arXivorg(2024)
Zhou, H., Zhao, C., Cain, M., Bluvstein, D., Duckering, C., Hu, H.-Y., W ang, S.-T., Kubica, A., and Lukin, M. D.Algorithmic fault tolerance for fast quantum computing.arXivorg(2024)
2024
This paper was first reviewed by deepseek-v4-flash on August 3, 2026.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.