{"id":"d0550d81-e8ef-4b5a-8a47-808f3541e07f","arxiv_id":"2506.13720","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"POPQC parallelizes local quantum-circuit optimization with O(n log n) work and O(r log n) span and proves local optimality with respect to an external oracle.","lead":"POPQC is a parallel algorithm for optimizing quantum circuits by repeatedly optimizing small non-overlapping segments in parallel, guided by bookmarks called fingers. On standard benchmarks it reports speedups of many orders of magnitude over sequential optimizers while keeping output quality about the same.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Local-optimality proof depends on an unverified 'well-behaved oracle' property that VOQC/Quartz almost certainly do not satisfy, so Theorem 7's guarantee is not established for the implemented system.","rationale":"The reader's weakest assumption identifies exactly the well-behaved oracle property, and the stress-test agrees that this is the most load-bearing point of the paper. The entire local-optimality argument in Lemma 6 and Theorem 7 hinges on the claim that after the oracle processes a 2Ω-segment, every Ω-subsegment of the result is itself optimal. This is not a benign technical assumption: it is a strong heredity property that heuristic optimizers such as VOQC are not designed to satisfy. VOQC is a one-shot rule-based pass; it may leave a segment unchanged while a subsegment would be reduced if processed separately. If that occurs, the algorithm removes a finger that should have been kept, and the invariant 'every unoptimized Ω-segment contains a finger' is broken. The final circuit may then contain Ω-segments that the oracle would reduce, contradicting the abstract's unqualified claim. The complexity theorems, the index-tree data structure, and the empirical speedups are not affected by this concern, so the paper still has substantial value; the condition is that the local-optimality claim must be either verified for the actual oracles or explicitly scoped to well-behaved oracles. The proposed concrete test is straightforward because the implementation and oracles are available, and it would settle whether the concern lands in practice. A secondary indexing inconsistency in the pseudocode (mixing logical and physical finger positions) is worth noting but does not change the verdict, since the well-behaved oracle issue is more fundamental and already warrants the conditional acceptance.","tokens_in":23175,"tokens_out":10151,"duration_ms":101495,"concrete_test":"Re-run VOQC on every Ω-segment (Ω=200) of a sample of the final circuits reported in Table 1 (e.g., BoolSat 34, BWT 29, HHL 13, StateVec 8). If any Ω-segment is reduced by VOQC in isolation, the returned circuit is not locally optimal in the paper's sense, and Theorem 7 fails for the implemented oracle. As a complementary check of the well-behaved assumption itself, generate random circuits over VOQC's gate set, run VOQC once on each, then run VOQC on every Ω-length subsegment of the output; if any subsegment shrinks, the oracle is not well-behaved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 6, just before Lemma 6, the paper defines an oracle as well-behaved if, after it optimizes a circuit, every segment of its output is itself optimal with respect to the oracle. Lemma 6 then uses this property in both cases: when the oracle makes no change to a 2Ω-segment, the finger is removed because all Ω-subsegments inside are 'locally optimal by the well-behaved property'; when the oracle does change the segment, all fully contained Ω-segments of the output are similarly declared optimal. Theorem 7 is then stated without qualification: 'The POPQC algorithm produces a locally optimal circuit with respect to a given oracle function.' The abstract repeats this unconditionally. No argument, experiment, or reference is given that VOQC or Quartz—the two oracles used in Section 7—satisfy this property. VOQC applies a fixed sequence of rewrite passes once; it is not a complete optimizer. A 2Ω-segment can be left unchanged while some Ω-subsegment of it would be reduced by VOQC if invoked on that subsegment, or by a different pass order. If that happens, the finger is removed even though an unoptimized Ω-segment remains, and the invariant fails. The local-optimality guarantee is the paper's central correctness claim; the complexity bounds in Theorem 4 do not depend on this assumption and are not in question. The missing hypothesis should be either verified for the implemented oracles or made explicit and tested.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces POPQC, a parallel algorithm for local optimization of quantum circuits. The algorithm maintains a set of 'fingers' marking potentially unoptimized Ω-segments, and in each round it selects non-interfering fingers and optimizes the surrounding 2Ω-segments in parallel using an external oracle optimizer. The circuit is stored in a sparse array with an index tree that supports logarithmic-time queries for live gates. The authors prove work O(n(Ω lg n + W)) and span O(r(lg n + S)), where r is the number of rounds, and claim that the returned circuit is locally optimal, meaning every Ω-segment is optimal with respect to the oracle. They implement the algorithm in Rust using VOQC and Quartz as oracles and report large speedups over sequential baselines on a 64-core machine, with code available on GitHub.","tokens_in":23595,"tokens_out":10280,"duration_ms":96599,"significance":"If the central claims hold, POPQC is a significant contribution: it is, to my knowledge, the first parallel quantum circuit optimizer with provable near-linear work and a formal (if weak) quality guarantee, backed by a large and thoughtfully designed experimental evaluation. The potential-function argument for bounding the number of oracle calls is clean, and the index-tree data structure is a useful ingredient beyond this specific application. The paper ships its code and evaluates against multiple optimizers and benchmark families, which strengthens confidence in the practical claims. However, the local-optimality theorem rests on an unstated and unverified 'well-behaved oracle' assumption, and the pseudocode contains inconsistencies between the described 2Ω-segments and the actual indices used; these issues directly affect the paper's central correctness claim and must be resolved before the guarantee can be accepted.","major_comments":[{"comment":"The local-optimality guarantee is not established for the implemented system. Lemma 6 and Theorem 7 rely on the assumption that the oracle is 'well-behaved' (Section 6, before Lemma 6): for any A' = oracle(A), every segment of A' must already be optimal with respect to the oracle. The paper gives no proof that VOQC or Quartz, the two oracles used in Section 7, have this property, and Section 7.4 itself reports that POPQC finds optimizations that a single VOQC run misses, which is exactly the kind of behavior the well-behaved property rules out. Since the abstract states the optimality guarantee unconditionally, the authors should either verify the property (for instance, by exhaustively checking oracle outputs on all segments for the benchmark circuits), or explicitly state and empirically test the assumption as part of Theorem 7 and adjust the abstract accordingly.","section":"Section 6 (well-behaved oracle; Theorem 7)"},{"comment":"The pseudocode optimizes a segment of 2Ω+1 gates, not 2Ω gates: the index range i ∈ [-Ω, Ω] contains 2Ω+1 values. The surrounding text, Lemma 6, Theorem 4, and Figure 2 all describe 2Ω-segments. This off-by-one changes the size of the segment submitted to the oracle and affects the non-interference condition, the oracle work bound W, and the invariant argument in Lemma 6. Please make the pseudocode and the prose consistent (for example, use i ∈ [-Ω, Ω-1]) and adjust the analysis if the intended segment is indeed 2Ω+1 gates.","section":"Algorithm 3, line 4"},{"comment":"The definition of a finger is inconsistent between the initial state and subsequent rounds. Algorithm 2 initializes F with array indices (0, Ω, 2Ω, ...), while Algorithm 3 line 7 adds new fingers at Circuit.before(C, f) − Ω and Circuit.before(C, f) + Ω, which are gate-count positions rather than array indices. In the next round, Algorithm 4 line 3 calls Circuit.before(C, F[i]) on those values, but Circuit.before is defined only for an array index (Section 3). No mapping from gate-count positions back to array indices is provided, so the pseudocode as written is not a well-defined algorithm and the proofs, which treat all fingers uniformly, do not cover the described code.","section":"Algorithms 2–4, finger representation"}],"minor_comments":[{"comment":"The parmap iterates over i ∈ {0, ..., |F|}, which includes i = |F| and accesses F[|F|] out of bounds; the upper limit should be |F|−1.","section":"Algorithm 4, line 2"},{"comment":"The function padWithTombstone is used but never defined; its semantics should be described, including how the optimized segment is mapped back onto the original 2Ω positions.","section":"Algorithm 3, line 8"},{"comment":"The introduction attributes QMA-hardness of global circuit optimization to reference [38], but [38] is the Nam et al. optimizer paper; the background section correctly cites [25] (Janzing et al.) for this fact, so the citation in Section 1 appears to be wrong.","section":"Section 2.3 and Introduction"},{"comment":"The figure uses the label 'CNOT1,2' without defining the gate-index convention, which makes the example hard to follow.","section":"Figure 1"},{"comment":"The abstract says 'a Ω-deep circuit' where 'an Ω-segment' is intended, and Appendix A.3 contains a typo, 'accroding' for 'according'.","section":"Abstract and Appendix A.3"}],"recommendation":"major_revision","confidential_remarks":"The complexity results and the experimental contribution are solid, but the paper's headline guarantee is currently stated too strongly: Theorem 7 and the abstract claim unconditional local optimality, while the proof depends on the well-behaved oracle assumption that is not verified for the actual oracles. The off-by-one and finger-representation issues in the pseudocode also need to be fixed before the paper can be considered publishable. I would like to see a revision that either proves or empirically validates the well-behaved property for VOQC and Quartz, or explicitly reformulates the guarantee as conditional and tests how often the condition holds."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is a real algorithmic step: the finger invariant plus index tree turns the sequential OAC idea into a parallel algorithm with O(n log n) work and O(r log n) span, and the experiments show it actually scales on 64 cores and beats the sequential baselines by orders of magnitude. Code is on GitHub. That part deserves to be taken seriously.\n\nSecond, the central correctness claim is softer than the abstract lets on. The local-optimality theorem (Thm 7) depends on the oracle being 'well-behaved': after the oracle optimizes any segment, every subsegment of the output is itself optimal with respect to the oracle. The paper defines this property in Section 6 but never shows VOQC or Quartz satisfy it. A fixed-pass rewrite system like VOQC almost certainly does not: a 2Ω-segment can be left unchanged while an Ω-subsegment of it would shrink if the oracle were invoked on that subsegment in a different context. So the proof of Lemma 6 — and with it the unconditional 'produces a locally optimal circuit' statement in the abstract — doesn't go through for the implemented oracles. The complexity bounds don't depend on this assumption, so the algorithmic contribution stands; it's the quality guarantee that is conditional.\n\nMinor things: Algorithm 3 line 4 builds a segment of 2Ω+1 gates, not 2Ω; the text and figures say 2Ω. That's a small inconsistency, but since Ω is constant it doesn't affect asymptotics. Also, the gate-reduction averages in Table 1 exclude the rows where VOQC hit the 24-hour timeout; that's disclosed but it does tilt the 'no quality degradation' claim.\n\nWho's this for: anyone working on quantum circuit compilation or parallel algorithms for circuits. The paper deserves a serious referee; the authors need to either prove the well-behaved property for a realistic class of oracles, or weaken/caveat the theorem and validate the invariant empirically (e.g., check after termination whether any Ω-segment actually improves when re-optimized). I'd send it to review, with a clear request for those changes.","headline":"A genuinely useful parallel circuit optimizer with the right complexity bounds, but the local-optimality guarantee is conditional on a strong oracle property the paper never verifies.","tokens_in":24010,"tokens_out":2291,"would_cite":true,"duration_ms":21520,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W10","68Q12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces POPQC, a parallel algorithm that provably optimizes quantum circuits to local optimality in near-linear work and logarithmic span, and demonstrates orders-of-magnitude speedups over sequential optimizers.","keywords":["quantum circuit optimization","parallel algorithms","local optimality","work-span analysis","oracle optimizer","index tree","finger scheduling","quantum computing"],"falsifier":"Take a 2 $\\Omega$-segment from a benchmark circuit, optimize it with VOQC, then cut a subsegment from the middle of the output and run VOQC on it; if that subsegment shrinks, the oracle is not well-behaved and POPQC's local-optimality guarantee does not apply.","tokens_in":22978,"feed_emoji":"⚛️","tokens_out":6114,"duration_ms":54440,"temperature":0.7,"pith_summary":"The paper claims that quantum circuit optimization, previously a sequential and superlinear affair, can be made parallel without sacrificing quality. It presents POPQC, an algorithm that maintains \"fingers\" into the circuit, optimizes non-interfering segments concurrently in rounds, and provably terminates with a locally optimal circuit. For constant segment size $\\Omega$, the algorithm requires O(n log n) work and O(r log n) span, with at most O(n) calls to an external oracle optimizer. The practical significance is that large circuits that stymie existing optimizers for 24 hours or more can be optimized in seconds on a 64-core machine, with essentially the same gate reduction. A sympathetic reader would care because this is a provably efficient parallel approach to a task central to near-term quantum computing.","feed_headline":"Parallel optimizer tames quantum circuits in near-linear time","feed_subtitle":"POPQC provably optimizes every Omega-segment in parallel, beating sequential optimizers by orders of magnitude.","key_machinery":"The central mechanism is the finger set indexed into a sparse circuit representation. A finger is an index in the gate array near which the algorithm presumes optimization is needed; two fingers are non-interfering if at least 2 $\\Omega$ gates separate them, so their segments can be optimized in parallel. The circuit is stored as a gate array with tombstones plus a balanced index tree whose leaves are weighted 1 for a live gate and 0 for a tombstone; the tree answers \"how many live gates before position i\" and \"what is the i-th live gate\" in logarithmic work, letting the algorithm locate segments and apply updates without rescanning. The paper defines a well-behaved oracle as one whose optimized output has every subsegment already optimal, which is the property enabling the finger invariant to survive round after round.","core_discovery":"The central discovery is that local optimality - the property that every $\\Omega$-gate segment of the circuit is optimal with respect to a given oracle - can be attained by a parallel, work-efficient algorithm. Instead of the sequential cut-optimize-meld-compress scheme of prior work, the algorithm keeps a set of finger indices, selects a constant fraction of non-interfering fingers per round, optimizes the 2-$\\Omega$ segments around them in parallel, and updates fingers only at segment boundaries where the oracle made changes. The invariant that every unoptimized $\\Omega$-segment contains a finger is preserved across rounds; when no fingers remain, every $\\Omega$-segment has been checked by the oracle, yielding local optimality. The proof of efficiency rests on a potential function showing O(n) total oracle calls, a finger-count bound of O($\\Omega$ n), and an index-tree data structure for the circuit that supports each access and update in O(log n) work.","pith_inferences":["If the well-behaved property can be verified or enforced for a given oracle, POPQC's local-optimality guarantee becomes a compositional certificate: each segment's optimality is independent, so the output can be checked segment-by-segment in parallel, a natural testable quality metric for large circuits.","The index-tree representation may be reusable beyond this algorithm, for example as a runtime scheduler for streaming circuit transformations or for coarse-grained parallel compilation passes that must maintain a compact view of a sparse gate list.","The finger-invariant idea generalizes: any optimization task with a local, checkable optimality notion and a well-behaved local repair routine could be parallelized in the same rounds-of-parallel-repair pattern, not just quantum circuit optimization.","The observed small number of rounds suggests that real quantum circuits have limited long-range interaction under this optimizer; if that locality is structural, then the empirical round count could be formalized for natural circuit classes, dropping the r factor from the span bound."],"forward_implications":["For any circuit of n gates and constant Omega, POPQC terminates in O(n log n) total work and O(r log n) span, making near-linear-time optimization achievable in principle.","The output circuit is locally optimal: no Omega-segment can be further improved by the oracle, a formal quality guarantee stronger than heuristic single-pass optimization.","The algorithm makes only O(n) oracle calls, so the cost is dominated by the oracle work; in practice, over 90% of the time is spent inside the oracle.","A single-processor run of POPQC already outperforms the best sequential local optimizer, and with 64 threads it beats the VOQC baseline by orders of magnitude, with gate-reduction quality within about half a percent.","The same algorithm works with different oracles and cost functions; using Quartz with a depth-aware cost, it reduces circuit depth by up to 20% even when gate-count-only optimization finds nothing."],"supporting_citations":[{"why":"Supplies the preceding local-optimality approach, the oracle abstraction, and optimization baseline the paper compares against.","marker":"[8]"},{"why":"Provides VOQC, the verified rule-based optimizer used as the main oracle and baseline in the evaluation.","marker":"[22]"},{"why":"Provides Quartz, the search-based optimizer used as an alternative oracle for depth-aware optimization.","marker":"[59]"},{"why":"Supplies the work-span model and parallel-map primitive used for the complexity analysis.","marker":"[1]"},{"why":"Establishes QMA-hardness of global circuit optimization, motivating the local-optimality relaxation.","marker":"[25]"},{"why":"Gives an earlier rule-based optimizer treated as a state-of-the-art sequential baseline.","marker":"[38]"}],"fun_headline_variants":["Parallel optimizer zeros in on quantum circuit local optimality","Quantum circuit optimizer goes parallel, provably near-linear","Parallel local optimizer for quantum circuits: fast and proven","Near-linear work, parallel span: quantum circuit optimization","Parallel quantum circuit optimization: local optimality achieved"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The local-optimality guarantee collapses if the oracle optimizer is not \"well-behaved\" - meaning that after it optimizes a segment, some subsegment of that output could still be improved by the oracle itself.","fun_headline_variants_meta":{"raw":{"variants":["Parallel optimizer zeros in on quantum circuit local optimality","Quantum circuit optimizer goes parallel, provably near-linear","Parallel local optimizer for quantum circuits: fast and proven","Near-linear work, parallel span: quantum circuit optimization","Parallel quantum circuit optimization: local optimality achieved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000278,"raw_usage":{"total_tokens":1686,"prompt_tokens":1007,"completion_tokens":679,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":623,"completion_tokens_details":{"reasoning_tokens":604}},"tokens_in":623,"tokens_out":679,"duration_ms":6498,"temperature":1.0,"reasoning_tokens":604,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:56:51.521324+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a 2 $\\Omega$-segment from a benchmark circuit, optimize it with VOQC, then cut a subsegment from the middle of the output and run VOQC on it; if that subsegment shrinks, the oracle is not well-behaved and POPQC's local-optimality guarantee does not apply.","supporting_citations":[{"cited_title":"Local Optimization of Quantum Circuits (Extended Version)","cited_arxiv_id":"2502.19526","evidence_quote":"Supplies the preceding local-optimality approach, the oracle abstraction, and optimization baseline the paper compares against."},{"cited_title":"A verified optimizer for quantum circuits","cited_arxiv_id":null,"evidence_quote":"Provides VOQC, the verified rule-based optimizer used as the main oracle and baseline in the evaluation."},{"cited_title":"Acar, and Zhihao Jia","cited_arxiv_id":null,"evidence_quote":"Provides Quartz, the search-based optimizer used as an alternative oracle for depth-aware optimization."},{"cited_title":"Acar and Guy E","cited_arxiv_id":null,"evidence_quote":"Supplies the work-span model and parallel-map primitive used for the complexity analysis."},{"cited_title":"Identity check is qma- complete, 2003","cited_arxiv_id":null,"evidence_quote":"Establishes QMA-hardness of global circuit optimization, motivating the local-optimality relaxation."},{"cited_title":"Ross, Yuan Su, Andrew M","cited_arxiv_id":null,"evidence_quote":"Gives an earlier rule-based optimizer treated as a state-of-the-art sequential baseline."}],"review_version":2}