Pith. sign in

REVIEW 3 major objections 5 minor 31 references

Dead Gate Elimination

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Pith's one-line read This paper proves that quantum-circuit gates acting on qubits whose measurement outcomes are unused can be safely deleted, without altering the probability distribution of the outcomes that later classical computations depend on.

desk verdict Sound formal framework, unsound algorithm as written: Theorem 3's SWAP rule requires relabeling and Algorithm 1 forgets it. read the letter →

arxiv 2504.12729 v2 pith:AKHBN6QL submitted 2025-04-17 quant-ph cs.PLcs.SE

classification quant-phcs.PLcs.SE MSC 81P68 PACS 03.67.-a03.67.Lx
keywords deadgateeliminationquantumcircuitoptimizationhybridquantum-classicalprogramsdiscardedmeasurementoutcomesvariationaleigensolverphaseestimationequivalencerelativetovalidfrontier
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper introduces dead-gate elimination, a circuit simplification for hybrid quantum-classical programs in which some measurement outcomes never feed into the later classical computation. It proves that any single-qubit gate acting on a qubit whose outcome is discarded, any controlled version of such a gate, and certain SWAP gates can be removed while leaving the probability distribution of the contributing outcomes unchanged. The proof proceeds through an equivalence relation on circuits relative to a set of dead qubits, and the accompanying Algorithm 1 repeatedly removes such gates from the circuit frontier in quadratic worst-case time. The authors demonstrate the technique on a VQE example, a QPE example, and random hybrid programs, reporting nontrivial gate reductions even after standard transpilation.

What carries the argument

The load-bearing object is the equivalence relation $\equiv_D$ between circuits relative to a fixed set $D$ of dead qubits: two circuits are equivalent when they give the same probabilities for every measurement outcome on the valid qubits (Definition 5), with an extended version (Definition 7) that allows dead labels to move, for instance through a SWAP. The proof of Theorem 2 performs the calculation that carries the argument: when a controlled gate acts on a dead target qubit, each contribution to a valid-outcome amplitude is multiplied by $|\alpha|^2+|\beta|^2=1$ for the dead qubit's basis states, so all probabilities on valid qubits are unchanged. Algorithm 1 repeatedly inspects the frontier, meaning the gates whose outputs feed nothing else, and deletes any gate matching one of the three rules.

What would settle it

Exhaustively generate all circuits with up to four or five qubits from a universal gate set, mark every possible subset of qubits as dead, and compare, by exact state-vector simulation, the probability distribution on the valid qubits before and after each deletion Algorithm 1 performs; any mismatch between the two distributions would refute the claim. To be a proper test the comparison must include controlled gates whose control lines sit on valid qubits and whose targets are dead.

Watch

Extended reading notes

Core claim

The discovery is a formal criterion for deadness: a gate is dead when deleting it leaves the probability distribution of the measurement outcomes that later classical code actually uses untouched. Three removal rules are proved. First, a single-qubit gate acting on a dead qubit can always be deleted. Second, a gate acting on a dead qubit can also be deleted when it is controlled by any number of other qubits. Third, a SWAP gate can be deleted even when it moves a value from a dead qubit to a valid one, provided the dead label travels with the value. Algorithm 1 applies the rules from the circuit's frontier until no more gates are removable, and Theorem 4 bounds the running time by $O(|C.\text{gates}()|^2)$.

Load-bearing premise

The set of dead qubits is assumed to be known and marked in advance; the paper does not itself analyze the classical host program to find which measurement outcomes are unused.

Editorial extensions

If this is right

  • In any hybrid program where a subset of measured outcomes provably never influences later classical code, the executed circuit can be replaced by a strictly smaller one with identical behavior for that host computation.
  • The simplification composes with standard transpilation: the random-circuit experiments start from circuits already optimized by a transpiler and still remove gates.
  • The benefit scales with the proportion of discarded outcomes, not their absolute number, so programs that ignore a large fraction of measurements benefit most.
  • Unmeasured ancilla qubits can be treated as implicitly measured and discarded, extending the optimization to circuits with ancillas.
  • For iterative algorithms like VQE, per-iteration gate savings accumulate over the many iterations the algorithm runs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension the paper leaves open is a static analysis that derives dead-qubit labels from the classical host language, since the examples mark them by hand; combining a liveness-style dataflow analysis with Algorithm 1 would make the optimization fully automatic.
  • The extended equivalence used for SWAP removal suggests the dead-qubit set should be tracked as a moving label through the circuit; a compiler could integrate this with qubit routing rather than treating routing as a prior phase.
  • Applying the same criterion to mid-circuit measurements is not straightforward, because measurement has side effects even on dead qubits; the paper itself flags dynamic circuits as future work.
  • The safety proof is distributional: it preserves the joint distribution on valid outcomes but not the full state, so downstream uses that rely on entanglement structure rather than measurement statistics would need a different guarantee.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The manuscript introduces a circuit simplification method for hybrid quantum-classical programs in which some measurement outcomes are discarded because they do not influence subsequent classical computation. It defines dead qubits, dead gates, and an equivalence relation that compares circuits only on valid measurement outcomes. The paper proves three removal rules: single-qubit gates on dead qubits and controlled gates on dead qubits can be removed (Theorems 1 and 2), and a SWAP between a dead and a valid qubit can be removed provided the dead/valid labels are also swapped (Theorem 3). It then presents Algorithm 1 for iteratively removing dead gates from a circuit, with a claimed O(|gates|^2) complexity bound, and evaluates the method on a VQE instance, a QPE instance, and random hybrid programs. The linear-algebra proofs are mostly clear, but the algorithm as written does not implement the label-swapping required by Theorem 3, so the central algorithmic claim is not yet established.

Significance. The dead-gate formalism is a useful and clearly stated idea, and Theorems 1 and 2 are proved correctly from the Born rule. The experiments show that even circuits already processed by standard transpilers admit non-trivial gate reductions when some outcomes are non-contributory. If the algorithm is repaired to track the relabeling required by Theorem 3, and if the origin of the dead-qubit labels is made explicit, the contribution would be a practical and well-motivated optimization for hybrid quantum programs. At present, however, the paper's headline claim that 'removal of dead gates has no influence on the probability distribution of the measurement outcomes that contribute' is not supported by the pseudocode as written. The flaw is local and fixable, so the work is conditionally significant rather than fundamentally unsound.

major comments (3)
  1. [Section 3, Algorithm 1 and Theorem 3 (Eq. (7), Remark 2)] Algorithm 1 removes a SWAP by executing only Copt ← Copt − g and never updates the dead/valid labeling that Theorem 3 requires. Theorem 3 states C ≡_{{qi}}^{{qj}} C′, meaning that after removing the SWAP the dead label must move from qi to qj. Since Algorithm 1 never records or applies this relabeling, it can make later removal decisions against the wrong dead set and can return a circuit that is not equivalent to C under the original contributory measurement outcomes. A concrete counterexample is: q0 is dead, q1 is valid, the initial state is |00>, and the circuit applies H to q0 followed by SWAP(q0,q1). The original valid measurement on q1 is 50/50, but Algorithm 1 removes the SWAP and leaves the marker on q0, so a host program reading q1 obtains outcome 0 deterministically. Remark 2 mentions adapting the qubit mapping, but that adaptation is not part of Algorithm 1's data structures, loop condition, or complexity statement. The paper must revise the algorithm to carry the relabeling explicitly, and Theorem 4 must be restated for the revised data structures.
  2. [Section 3, Definitions 4-6 and Section 1] The dead-qubit set D is assumed to be known and marked, but the paper provides no static analysis that derives these labels from the classical host program; the labels in Example 1, the VQE instance, and the QPE instance are inferred by hand. Every removal decision depends on D, so an incorrect label can cause a non-dead gate to be removed and can change an outcome that the subsequent computation actually uses. The correctness guarantee is therefore conditional on a given, correctly marked set of discarded outcomes. Please either provide the analysis that produces these labels from the host program or state this scope condition prominently and discuss how the labels are obtained in practice.
  3. [Section 3, Theorem 4] The complexity proof for Algorithm 1 counts only gate removals and does not account for the data structures needed by the fixed algorithm, in particular the frontier update rule and the label map required by Theorem 3. Once the relabeling is added, the O(|C.gates()|^2) bound may still hold, but the proof must specify how the frontier is recomputed and how the dead-set comparison for Theorem 3 is performed. As written, the proof applies to a simplified version of the algorithm that does not match the correctness argument.
minor comments (5)
  1. [Throughout] There are many typos: 'In addtion' in Section 1, 'syne rgy' and 'subset s' in the Abstract, 'asympotic' in Section 3, and 'mini seconds' in Figure 8(b). These should be corrected.
  2. [Section 3, Definition 7] The extended equivalence definition is notationally heavy; a short running example would greatly help the reader understand the substitution [e1/f1, ...] before Theorem 3 is introduced.
  3. [Section 3, Algorithm 1] The pseudocode does not state how frontier() is recomputed after a removal or how gate dependencies are maintained; please specify the update rule or cite a standard circuit representation that makes it precise.
  4. [Section 4, Random circuits] The paper does not specify how the dead-qubit set is chosen for each random circuit (e.g., uniformly at random, fixed positions, or by some program-dependent rule); please clarify to make the experiments reproducible.
  5. [Figure 6 and Example 5] The QPE diagram uses symbols r and QFT^†_f without definitions, and Example 5's circuit-diagram formatting appears garbled, making the claimed inequivalence difficult to verify; please redraw and explain both.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's theorems are direct Born-rule calculations, and the dead-gate definition is a criterion, not a reused conclusion.

full rationale

The paper's central derivation is Theorem 2, which proves by a direct summation over amplitude moduli that removing a single-qubit gate on a dead qubit leaves probabilities of all valid-outcome strings unchanged. This is a self-contained calculation from the Born rule and the definition of subsystem measurement probabilities; it does not assume the conclusion. Theorem 1 is explicitly a special case of Theorem 2, and Theorem 3 follows directly from the definition of SWAP and the extended equivalence in Definition 7. The definition of a dead gate (Definition 6) is an equivalence criterion: a gate is dead exactly when removing it preserves the valid-outcome distribution. That the abstract states that removing dead gates has no influence is therefore partly analytic, but the paper's actual contribution is the identification theorems showing which gate patterns satisfy that criterion, so the derivation chain is not circular. No parameters are fitted, no data are predicted from fitted values, and no load-bearing result is imported from the authors' prior work; the references to the authors' earlier static-analysis papers appear only as background in Section 5. The externally provided set of dead qubits is an assumption about the host classical program, not a reuse of the paper's own conclusion. The possible mismatch between Theorem 3's required qubit relabeling and Algorithm 1's pseudocode is a soundness/correctness concern about the algorithm's implementation, not a circularity in the derivation.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The theoretical derivation uses only standard quantum-mechanical probability rules plus two explicit domain restrictions. The crucial non-mathematical input is the pre-marked dead-qubit set D, which the paper assumes rather than computes. No free parameters are fitted and no new physical entities are introduced.

assumptions (3)
  • standard math The Born rule: probability of a measurement outcome on a subsystem is obtained by summing squared amplitudes over the unmeasured degrees of freedom.
    Used throughout Theorem 2's proof to compare probabilities on the valid qubits.
  • domain assumption The circuit contains no mid-circuit measurements or resets.
    Stated at the start of Section 3; the method does not cover dynamic circuits, as acknowledged in the conclusion.
  • domain assumption A set D of dead qubits is given and correctly marks every measurement outcome that does not contribute to the classical computation.
    Section 3: 'we assume that for the outcomes we collect by measuring all qubits, a subset of them has no contribution ... We explicitly mark such measurement outcomes as discarded.' The correctness proof inherits this labeling.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dead Gate Elimination." pith.science (2026). https://pith.science/paper/AKHBN6QL

@misc{pith2026250412729,
  author       = {Pith},
  title        = {Pith review of: Dead Gate Elimination},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AKHBN6QL}},
  note         = {Machine review of arXiv:2504.12729}
}
read the original abstract

Hybrid quantum algorithms combine the strengths of quantum and classical computing. Many quantum algorithms, such as the variational quantum eigensolver (VQE), leverage this synergy. However, quantum circuits are executed in full, even when only subsets of measurement outcomes contribute to subsequent classical computations. In this manuscript, we propose a novel circuit optimization technique that identifies and removes dead gates. We prove that the removal of dead gates has no influence on the probability distribution of the measurement outcomes that contribute to the subsequent calculation result. We implemented and evaluated our optimization on a VQE instance, a quantum phase estimation (QPE) instance, and hybrid programs embedded with random circuits of varying circuit width, confirming its capability to remove a non-trivial number of dead gates in real-world algorithms. The effect of our optimization scales up as more measurement outcomes are identified as non-contributory, resulting in a proportionally greater reduction of dead gates.

Figures

Figures reproduced from arXiv: 2504.12729 by the authors.

Figure 1
Figure 1. An example of a hybrid program, where a quantum circui [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. A 3-qubit circuit. The measurement outcome of the top qubit is discarded. q0 U3 q1 q2 W1 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Simplification of the circuit in Fig. 2. The probabili [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: An instance of VQE algorithm. q0 U4( −→γ ) q1 q2 RZ (θ5) RY (θ6) q3 RZ (θ7) RY (θ8) [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: A simplified Ansatz, A2, that can replace A1 in [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: An instance of QPE, where U consists of Hadamard gates and a sequence of controlled oracles to prepare the state ready for the inverse quantum Fourier transform (QFT [7,22]), QFT† f is the front part of the inverse QFT, measurement outcomes oi ∈ {0, 1} for all i, and ⌊…
Figure 7
Figure 7. Figure 7: A simplified QPE circuit to replace the circuit in Fig. [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: (a) Gate reduction obtained by performing our optimi [PITH_FULL_IMAGE:figures/full_fig_p013_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 11 canonical work pages

  1. [1]

    Quantum 7, 989 (Apr 2023)

    Abedi, E., Beigi, S., Taghavi, L.: Quantum lazy training. Quantum 7, 989 (Apr 2023). https://doi.org/10.22331/q-2023-04-27-989 , http://dx.doi.org/10.22331/q-2023-04-27-989

  2. [3]

    Bouland, A., van Dam, W., Joorati, H., Kerenidis, I., Prak ash, A.: Prospects and challenges of quantum finance (2020), https://arxiv.org/abs/2011.06492

  3. [4]

    In: 2022 IEEE International Confer - ence on Quantum Computing and Engineering (QCE)

    Chen, T.F., Jiang, J.H.R., Hsieh, M.H.: Partial equivale nce check- ing of quantum circuits. In: 2022 IEEE International Confer - ence on Quantum Computing and Engineering (QCE). p. 594–604 . IEEE (Sep 2022). https://doi.org/10.1109/qce53715.2022.00082, http://dx.doi.org/10.1109/QCE53715.2022.00082

  4. [5]

    In: 2024 International Conference on Quantum Computing and Enginee ring (9 2024)

    Chen, Y., Fulginiti, I., Mendl, C.B.: Probabilistic Circ uit Model. In: 2024 International Conference on Quantum Computing and Enginee ring (9 2024). https://doi.org/10.1109/QCE60285.2024.10379

  5. [6]

    In: Hermenegildo, M.V., Morales, J.F

    Chen, Y., Stade, Y.: Quantum constant propagation. In: Hermenegildo, M.V., Morales, J.F. (eds.) Static Analy- sis. pp. 164–189. Springer Nature Switzerland, Cham (2023) , https://link.springer.com/chapter/10.1007/978-3-031-44245-2_9

  6. [7]

    Coppersmith, D.: An approximate fourier transform usefu l in quantum factoring (2002), https://arxiv.org/abs/quant-ph/0201067

  7. [8]

    Journal of Artificial Intelligenc e and Technol- ogy 2(1), 9–15 (Dec 2021)

    De Luca, G.: A survey of nisq era hybrid quantum-classical ma- chine learning research. Journal of Artificial Intelligenc e and Technol- ogy 2(1), 9–15 (Dec 2021). https://doi.org/10.37965/jait.2021.12002, https://ojs.istp-press.com/jait/article/view/60

  8. [9]

    Quantum computing, phase estimation and applications

    Dobšíček, M.: Quantum computing, phase estimation and ap plications. arXiv preprint arXiv:0803.0909 (2008)

Show all 31 references
  1. [10]

    Elsharkawy, A., To, X.T.M., Seitz, P., Chen, Y., Stade, Y ., Geiger, M., Huang, Q., Guo, X., Ansari, M.A., Mendl, C.B., Kranzlmüller, D., Sc hulz, M.: Integration of quantum accelerators with high performance computing – a review of quantum programming tools (2023), https://ar...

  2. [12]

    Materials Theory 6(1), 2 (2022)

    Fedorov, D.A., Peng, B., Govind, N., Alexeev, Y.: Vqe met hod: a short survey and recent developments. Materials Theory 6(1), 2 (2022)

  3. [13]

    Jojo, J., Khandelwal, A., Chandra, M.G.: Quantum algori thms for tensor-svd (2024), https://arxiv.org/abs/2405.19485

  4. [14]

    OUP Oxford (2006)

    Kaye, P., Laflamme, R., Mosca, M.: An introduction to quan tum computing. OUP Oxford (2006)

  5. [15]

    arXiv preprint quant-ph/9511026 (1995)

    Kitaev, A.Y.: Quantum measurements and the abelian stab ilizer problem. arXiv preprint quant-ph/9511026 (1995)

  6. [16]

    Li, P., Liu, J., Gonzales, A., Saleem, Z.H., Zhou, H., Hov land, P.: Qutracer: Miti- gating quantum gate and measurement errors by tracing subse ts of qubits (2024), https://arxiv.org/abs/2404.19712

  7. [18]

    In: 2018 IEEE Inter- national Conference on Rebooting Computing (ICRC)

    McCaskey, A., Dumitrescu, E., Liakh, D., Humble, T.: Hyb rid program- ming for near-term quantum computing systems. In: 2018 IEEE Inter- national Conference on Rebooting Computing (ICRC). pp. 1–1 2 (2018). https://doi.org/10.1109/ICRC.2018.8638598

  8. [19]

    In: 2018 IEEE interna tional conference on rebooting computing (ICRC)

    McCaskey, A., Dumitrescu, E., Liakh, D., Humble, T.: Hyb rid programming for near-term quantum computing systems. In: 2018 IEEE interna tional conference on rebooting computing (ICRC). pp. 1–12. IEEE (2018)

  9. [20]

    New J ournal of Physics 18(2), 023023 (feb 2016)

    McClean, J.R., Romero, J., Babbush, R., Aspuru-Guzik, A .: The theory of variational hybrid quantum-classical algorithms. New J ournal of Physics 18(2), 023023 (feb 2016). https://doi.org/10.1088/1367-2630/18/2/023023, https://dx.doi.org/10.1088/1367-2630/18/2/023023

  10. [21]

    Morgan kaufmann (1997)

    Muchnick, S.: Advanced compiler design implementation . Morgan kaufmann (1997)

  11. [22]

    Cambridge University Pres s, 1 edn

    Nielsen, M.A., Chuang, I.L.: Quantum Computation and Qu antum Informa- tion: 10th Anniversary Edition. Cambridge University Pres s, 1 edn. (Jun 2012). https://doi.org/10.1017/CBO9780511976667

  12. [23]

    Proceedings of the ACM on Software Engineering 1(FSE), 2144–2166 (2024)

    Paltenghi, M., Pradel, M.: Analyzing quantum programs w ith lintq: A static analy- sis framework for qiskit. Proceedings of the ACM on Software Engineering 1(FSE), 2144–2166 (2024)

  13. [24]

    Nature communications 5(1), 4213 (2014)

    Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.H., Zhou , X.Q., Love, P.J., Aspuru-Guzik, A., O’brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nature communications 5(1), 4213 (2014)

  14. [25]

    https://doi.org/10.5281/zenodo.2573505

    Qiskit contributors: Qiskit: An open-source framework for quantum computing (2023). https://doi.org/10.5281/zenodo.2573505

  15. [26]

    Quetschlich, N., Forster, T., Osterwind, A., Helms, D., Wille, R.: Towards equivalence checking of classical circuits using quantum c omputing (2024), https://arxiv.org/abs/2408.14539

  16. [27]

    ACM Computing Surveys (CSUR) 32(3), 300–335 (2000)

    Rieffel, E., Polak, W.: An introduction to quantum comput ing for non-physicists. ACM Computing Surveys (CSUR) 32(3), 300–335 (2000)

  17. [28]

    Rohe, T., Grätz, S., Kölle, M., Zielinski, S., Stein, J., Linnhoff-Popien, C.: From problem to solution: A general pipeline to solve optimisati on problems on quantum hardware (2024), https://arxiv.org/abs/2406.19876

  18. [29]

    Quantum Science and Tec hnology 4(1), 014008 (oct 2018)

    Romero, J., Babbush, R., McClean, J.R., Hempel, C., Love , P.J., Aspuru- Guzik, A.: Strategies for quantum computing molecular ener gies using the unitary coupled cluster ansatz. Quantum Science and Tec hnology 4(1), 014008 (oct 2018). https://doi.org/10.1088/2058-9565/aad3e4,...

  19. [30]

    Springer (2012)

    Seidl, H., Wilhelm, R., Hack, S.: Compiler Design: Analy sis and Transformation. Springer (2012)

  20. [31]

    SIAM Journal on Comp ut- ing 26(5), 1484–1509 (1997)

    Shor, P.W.: Polynomial-time algorithms for prime facto rization and dis- crete logarithms on a quantum computer. SIAM Journal on Comp ut- ing 26(5), 1484–1509 (1997). https://doi.org/10.1137/S0097539795293172, https://doi.org/10.1137/S0097539795293172

  21. [32]

    In: 2023 IEEE International Conference o n Quantum Comput- ing and Engineering (QCE)

    Veshchezerova, M., Somov, M., Bertsche, D., Limmer, S., Schmitt, S., Perelshtein, M., Joshi Tripathi, A.: A Hybrid Quantum-Classical Approac h to the Electric Mobility Problem . In: 2023 IEEE International Conference o n Quantum Comput- ing and Engineering (QCE). pp. 636–641. ...

  22. [33]

    In: 2023 IEEE/ACM 4th International Workshop on Quantum Software En gineering (Q- SE)

    Xia, S., Zhao, J.: Static entanglement analysis of quant um programs. In: 2023 IEEE/ACM 4th International Workshop on Quantum Software En gineering (Q- SE). pp. 42–49 (2023). https://doi.org/10.1109/Q-SE59154.2023.00013 16 Y. Chen, et al

  23. [34]

    In: 2023 IEEE/ACM 4th International Wo rkshop on Quantum Software Engineering (Q-SE)

    Zhao, P., Wu, X., Li, Z., Zhao, J.: Qchecker: Detecting bu gs in quantum programs via static analysis. In: 2023 IEEE/ACM 4th International Wo rkshop on Quantum Software Engineering (Q-SE). pp. 50–57. IEEE (2023)

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.