{"id":"7932457c-ca79-49e3-a470-fdcc06ba1776","arxiv_id":"2504.12729","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A circuit optimization that removes gates on qubits whose measurement results are unused, with a proof that the distribution of the remaining outcomes is unchanged.","lead":"The paper presents a way to shrink quantum circuits by cutting out gates whose measurement results are not used by the rest of a hybrid quantum-classical program. It proves the cut is safe for the outcomes that matter, and tests it on VQE, quantum phase estimation, and random circuits.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 omits the measurement relabeling that Theorem 3 requires, so removing a dead/valid SWAP can change the value read by the classical program.","rationale":"The reader's CONDITIONAL verdict already mentions that the SWAP relabeling is under-specified, but the reader's chosen weakest assumption is the external derivation of dead-qubit labels. I think the more load-bearing issue is internal to Algorithm 1: Theorem 3's extended equivalence is only meaningful with a simultaneous relabeling of which qubit is dead/valid, and the algorithm never performs or outputs that relabeling. This is a concrete correctness gap, not merely a scope limitation, because a direct implementation of the pseudocode can change the value consumed by the classical program. The 2-qubit H+SWAP example settles the point. The underlying Theorems 1-3 appear correct, and the gap is fixable by making the relabeling an explicit part of the algorithm and its data structures, so the paper does not warrant rejection; a conditional acceptance with this required revision is the right outcome. The reader's verdict is already CONDITIONAL, so I do not move it.","tokens_in":11743,"tokens_out":7824,"duration_ms":93215,"concrete_test":"Implement Algorithm 1 exactly as written (with gate removal only, no relabeling) and run it on the 2-qubit circuit H(q0); SWAP(q0,q1), with q0 marked discarded and q1 valid. Compare the empirical distribution of q1 on the original circuit with q1 on the optimized circuit; they will differ (50/50 vs deterministic 0). Then repeat with a version that swaps the dead/valid markers whenever Theorem 3 is applied; the distributions on the relabeled valid qubit should match. If the corrected version passes, the paper needs to specify that relabeling inside Algorithm 1; if it fails, Theorem 3's application is unsound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3 is mathematically correct, but Algorithm 1 as written applies it unsoundly. The theorem states that a SWAP between a dead qubit qi and a valid qubit qj can be removed only if the dead/valid labels are also swapped: after removal, the formerly dead qubit qi carries the valid outcome. The pseudocode only performs Copt ← Copt − g and never records or applies this relabeling. Consequently, the 'discarded' markers remain on the original physical qubits, and a later removal decision may be checked against the wrong dead set; the final Copt is not guaranteed equivalent to C under the original set of contributory measurement outcomes. A concrete counterexample to the unmodified algorithm: initial state |00>, q0 is dead and q1 is valid, circuit applies H to q0 then SWAP(q0,q1). The original valid measurement on q1 is 50/50. Algorithm 1 removes the SWAP as dead and returns H on q0 with the marker still on q0, so the program still reads q1 and gets outcome 0 with probability 1. The paper's Remark 2 mentions adapting the qubit mapping, but that adaptation is not part of Algorithm 1, its data structures, or its stated complexity bound. Thus the central claim 'removal of dead gates has no influence on the probability distribution of the measurement outcomes that contribute' is not established for the algorithm as specified; it holds only if the transformation includes an explicit measurement-relabeling step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12057,"tokens_out":5290,"duration_ms":59389,"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":[{"comment":"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.","section":"Section 3, Algorithm 1 and Theorem 3 (Eq. (7), Remark 2)"},{"comment":"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.","section":"Section 3, Definitions 4-6 and Section 1"},{"comment":"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.","section":"Section 3, Theorem 4"}],"minor_comments":[{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"Section 3, Definition 7"},{"comment":"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.","section":"Section 3, Algorithm 1"},{"comment":"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.","section":"Section 4, Random circuits"},{"comment":"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.","section":"Figure 6 and Example 5"}],"recommendation":"major_revision","confidential_remarks":"The main problem is confined to the mismatch between Theorem 3 and Algorithm 1; the mathematical content of the theorems is sound, and the proposed fix is local. I would not reject the paper, because the underlying idea is correct and experimentally promising. In revision, please re-check the Section 4 examples for cases where a SWAP removal changes the physical qubit carrying a valid outcome; the current examples appear to avoid such cases, which is why the bug does not surface in the evaluation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives a clean formalization of when gates can be removed from a circuit when some measurement outcomes are unused. Theorems 1 and 2 are correct: single-qubit and controlled gates acting only on dead qubits are removable. The more interesting piece is Theorem 3, a SWAP rule that permutes dead/valid labels. That rule is valid at the level of the extended equivalence in Definition 7. The proofs are direct, the dead-gate definition is independent of the proof, and the paper positions itself honestly against QuTracer and partial equivalence checking. The demo implementation is a plus.\n\nBut the algorithm the paper actually ships, Algorithm 1, does not implement Theorem 3's relabeling. The pseudocode only does Copt <- Copt - g; it never records that the dead and valid labels have swapped. A concrete failure: q0 dead, q1 valid, H on q0 then SWAP(q0,q1). The original valid outcome on q1 is 50/50. Algorithm 1 removes the SWAP, leaves the dead marker on q0, and the program still reads q1, which now returns a deterministic 0. Remark 2 says the qubit mapping should be adapted, but that adaptation is not part of the algorithm, its data structures, or its complexity bound. So the central claim that removing dead gates has no influence on contributory outcomes is not established for the algorithm as specified. That is a major flaw, not a stylistic one.\n\nIn proportion: the dead-qubit set D is assumed given rather than derived from the host program. The paper says this explicitly and the examples mark D by hand, so it is an acknowledged open problem, not a hidden circularity. The random-circuit evaluation reports mean gate reduction without error bars and the artifact is not versioned, so the numbers are suggestive rather than a rigorous benchmark. Those are minor compared to the algorithm bug.\n\nWho this is for: people working on quantum circuit compilation or hybrid quantum-classical optimization. The formal equivalence framework is worth reading; the algorithm as published should not be used without adding an explicit qubit-mapping update. I would send this to peer review, but with the expectation of a major revision that rewrites Algorithm 1 and reruns the experiments with a correct implementation.","headline":"Sound formal framework, unsound algorithm as written: Theorem 3's SWAP rule requires relabeling and Algorithm 1 forgets it.","tokens_in":12538,"tokens_out":2704,"would_cite":false,"duration_ms":29632,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":["03.67.-a","03.67.Lx"],"model":"deepseek-v4-flash","headline":"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.","keywords":["dead gate elimination","quantum circuit optimization","hybrid quantum-classical programs","discarded measurement outcomes","variational quantum eigensolver","quantum phase estimation","equivalence relative to valid outcomes","circuit frontier"],"falsifier":"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.","tokens_in":11587,"feed_emoji":"⚛️","tokens_out":6286,"duration_ms":60811,"temperature":0.7,"pith_summary":"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.","feed_headline":"Dead gates can be stripped from quantum circuits safely","feed_subtitle":"New proof shows gates on unused qubit measurements can vanish without changing later calculation results.","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the prior notion of partial equivalence checking: comparing probability distributions for a given outcome set, which the paper turns into a simplification criterion rather than a verification check.","marker":"[4]"},{"why":"QuTracer is the closest prior optimizer that removes gates not affecting a subset of measured qubits; the paper positions its own formal framework and SWAP handling against it.","marker":"[16]"},{"why":"Establishes that a measurement outcome depends only on its causal light cone, the insight the paper says prior work did not systematically exploit.","marker":"[1]"},{"why":"Defines hybrid programs, the execution model in which discarded measurement outcomes arise.","marker":"[19]"},{"why":"Provides the classical compiler notion of dead variables and liveness analysis that inspired the dead gate concept.","marker":"[21, 30]"},{"why":"Supplies the VQE algorithm used as the first evaluation instance.","marker":"[12]"},{"why":"Supplies the quantum phase estimation references used in the QPE evaluation instance.","marker":"[9,15,22]"}],"fun_headline_variants":["Quantum circuits shed dead gates without altering results","Dead gate removal proven safe for hybrid quantum algorithms","Eliminating dead gates: a quantum circuit shortcut","New proof enables safe deletion of dead quantum gates","Dead gates vanish safely in quantum circuits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum circuits shed dead gates without altering results","Dead gate removal proven safe for hybrid quantum algorithms","Eliminating dead gates: a quantum circuit shortcut","New proof enables safe deletion of dead quantum gates","Dead gates vanish safely in quantum circuits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000199,"raw_usage":{"total_tokens":1315,"prompt_tokens":834,"completion_tokens":481,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":450,"completion_tokens_details":{"reasoning_tokens":412}},"tokens_in":450,"tokens_out":481,"duration_ms":4980,"temperature":1.0,"reasoning_tokens":412,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T12:24:57.050915+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"QuTracer: Mitigating Quantum Gate and Measurement Errors by Tracing Subsets of Qubits","cited_arxiv_id":"2404.19712","evidence_quote":"QuTracer is the closest prior optimizer that removes gates not affecting a subset of measured qubits; the paper positions its own formal framework and SWAP handling against it."},{"cited_title":"In: 2018 IEEE interna tional conference on rebooting computing (ICRC)","cited_arxiv_id":null,"evidence_quote":"Defines hybrid programs, the execution model in which discarded measurement outcomes arise."},{"cited_title":"Materials Theory 6(1), 2 (2022)","cited_arxiv_id":null,"evidence_quote":"Supplies the VQE algorithm used as the first evaluation instance."}],"review_version":1}