{"id":"10e90c4c-e3df-4bf1-b21d-91897cc3fa62","arxiv_id":"2505.17944","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A simulated-annealing qubit-ordering step makes parity twine and SWAP network encodings beat Qiskit's transpiler for QAOA circuits above a connectivity threshold, and parity twine runs up to 20 qubits on IBM hardware.","lead":"A qubit-ordering heuristic makes parity twine and SWAP network encodings beat standard QAOA transpilers once a problem's connectivity passes a threshold, cutting depth by up to 85 percent at 120 qubits. On IBM hardware the parity twine method solves 20-qubit instances where the SWAP network approach stops at 15 qubits.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The unproved 'reverse direction' rule for multi-layer PTC (Sec. II-C) is load-bearing: all p>1 hardware and noise results depend on it, yet no circuit identity or derivation is supplied.","rationale":"I read the paper as making two connected claims: (i) single-layer PTC+SA/SWAP+SA reduce two-qubit gates and depth vs Qiskit-T above an edge-density threshold, and (ii) this translates to better multi-layer QAOA performance on hardware. The first is supported by Table I and the availability of the problem instances and results in the linked repository; I see no need to challenge those numbers. The second depends entirely on the alternating forward/backward pass rule in Sec. II-C. That rule is asserted in one sentence and is not obvious: a truncated PTC circuit with interleaved RZ rotations is not a time-reversal-symmetric black box, and the logical mixer cannot simply be ignored. This is exactly the reader's weakest assumption, so my agreement is 'agree'. I also considered the small number of random instances (3 per edge-density point) and the depth-metric comparison across different hardware topologies; both are legitimate caveats, but they affect confidence in thresholds rather than the correctness of the multi-layer construction. If the alternating rule fails, the hardware advantage up to 20 qubits and the p=50 noise comparison are invalidated; if it holds, the paper's central claims remain plausible. Hence the reader's CONDITIONAL verdict is appropriate and unchanged.","tokens_in":13271,"tokens_out":9250,"duration_ms":82945,"concrete_test":"For a 5-qubit non-fully-connected WMC graph, construct the exact p=2 circuit prescribed by Sec. II-C: PTC truncated at t=2 for layer 1, then the second layer in the reverse direction, using LR-QAOA parameters from Eq. (4). In a statevector simulator, compare the full unitary (after the decoding convention used for measurement) with the target LR-QAOA unitary U_C(γ2)U_B(β2)U_C(γ1)U_B(β1), quantifying distance by fidelity or diamond norm. If the distance is not numerically zero, the alternating rule is not valid as stated; if the authors intend a different construction, the paper must specify it so the test can be rerun.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section II-C and Fig. 3(b) state that for a non-fully connected graph the PTC circuit can be truncated at t=2 for the first QAOA layer, and that 'subsequent layers can then proceed in the reverse direction, effectively alternating forward and backward passes as the QAOA p increases.' No derivation, circuit identity, or numerical validation is given for this rule. This matters because it is the only bridge from the single-layer transpilation counts (Table I, Figs. 4-6) to the central multi-layer claims: the ibm_fez experiments with p=3..20 (Fig. 8) and the depolarizing-noise simulation at p=50 (Fig. 7). Reversing a partial parity-encoding circuit with interleaved RZ rotations does not in general implement another independent cost-Hamiltonian layer: the CNOTs transform the diagonal RZ gates under conjugation, so the effective interactions in the reverse pass differ unless a specific commutation/angle relation holds. The paper does not state how the mixer is interleaved or how the reversed RZ angles are chosen. If the rule is false or requires extra uncompute/reset gates, the multi-layer QPU and noise results break, even though the single-layer resource-reduction claims could still stand. This is the most load-bearing assumption in the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a simulated-annealing-based qubit-order optimization for two connectivity-aware encodings of QAOA circuits on a linear chain: the SWAP network and parity twine chains (PTC). It benchmarks PTC+SA and SWAP+SA against Qiskit-T, Qiskit-P, Qiskit-AI, and TKET on weighted MaxCut instances with varying edge density, reporting resource tables for 20, 60, and 120 qubits, a depolarizing-noise simulation for 8 qubits at p=50, and ibm_fez hardware experiments for up to 22–25 qubits. The central claim is that above a connectivity threshold, these encodings reduce two-qubit gate count and depth relative to Qiskit-T, e.g., an 85% depth reduction and 28% gate reduction for a 120-qubit instance at 25% connectivity, and that PTC extends LR-QAOA to larger qubit counts than SWAP networks on real hardware.","tokens_in":13640,"tokens_out":12238,"duration_ms":129590,"significance":"If the central claims hold, the work is a practically valuable contribution to QAOA transpilation. The SA-based ordering heuristic is simple and scales to 120 qubits, and the paper provides a public repository with instances and results, which aids reproducibility. The claim that PTC and SWAP encodings can outperform a general-purpose transpiler above density thresholds is useful for practitioners. However, the validation is incomplete: the multi-layer extension relies on an unproved alternating-pass rule, and the depth metric in Table I is inconsistent with the paper's own formulas. The single-layer resource-reduction results are credible enough to warrant revision rather than rejection.","major_comments":[{"comment":"The paper states that for a non-fully connected graph the PTC circuit can be truncated at t=2 for the first QAOA layer and that 'subsequent layers can then proceed in the reverse direction.' This alternating-pass rule is the only stated mechanism for extending the single-layer encoding to the p>1 circuits used in the depolarizing-noise simulation (Fig. 7, p=50) and the ibm_fez experiments (Fig. 8, p=3..20). No derivation, circuit identity, or numerical validation is provided to show that a reversed truncated pass, with interleaved RZ rotations and mixers, implements another independent cost-Hamiltonian layer; CNOT conjugation of the diagonal RZ gates generally changes the effective two-qubit interactions. Please supply a formal argument or a statevector-level check for p=2 and state explicitly how the mixer and the reversed RZ angles are scheduled. Without this, the multi-layer hardware and noise claims are unsupported, although the single-layer resource comparisons could still stand.","section":"II-C, Fig. 3(b), Figs. 7–8"},{"comment":"The depth formulas in Sec. II state d=2Nq+2 for PTC and d=3Nq-2 for SWAP networks, and Ng=Nq^2-1 for PTC. Table I at Ed=1.0 reports substantially larger depths for the SA-optimized encodings (e.g., Nq=20: PTC+SA depth 66 vs 42, SWAP+SA depth 77 vs 58; Nq=120: 366 vs 242 and 477 vs 358). Please clarify whether Table I counts native-gate depth, includes final uncompute/measurement-order restoration, or includes single-qubit rotations, and correct either the table or the formulas. Since the abstract's depth-reduction percentages are computed from Table I, this inconsistency is load-bearing and must be resolved.","section":"II-A, II-B, Table I"},{"comment":"The quantitative thresholds quoted in the abstract and conclusions (e.g., Ed≈0.35 for Nq=20 and Ed≈0.13 for Nq=120) are based on only three randomly generated graphs per data point. The error bars in Fig. 6 are standard deviations over these three instances, and no confidence intervals or significance tests are reported. Given the visible variance, the crossing points should be presented as ranges or supported by more instances, and the text should avoid presenting them as precise thresholds. The qualitative trend is not in question, but the specific threshold values are not statistically established.","section":"III-A, Fig. 6, Table I"}],"minor_comments":[{"comment":"The stopping temperature T_s is mentioned in the SA description but never given a value; only T0, delta, and max_iter are specified.","section":"II-C"},{"comment":"'Qiskit-P allows implemention' should read 'implementation.'","section":"II-D"},{"comment":"The expression U_{ij}^{2Q}ρU_{ij}^{2Q} should presumably be U_{ij}^{2Q}ρU_{ij}^{2Q†} unless the gate is assumed Hermitian.","section":"II-F, Eq. (8)"},{"comment":"The 'minimum possible depth' d_min used for the ratios in Fig. 4 is not defined in the text; please define it explicitly.","section":"III-A, Fig. 4"},{"comment":"The formula for the effective approximation ratio r_eff appears only in the inset and is not defined in the text; please add a definition.","section":"III-C, Fig. 8(b)"},{"comment":"The paragraphs introducing r and p_gs do not specify the sample count used for the noiseless simulation in Fig. 8(a), which would help interpret the comparison with the random sampler.","section":"II-E"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope and the repository link is a clear strength. The main reason for major revision is the unproved alternating-pass rule for multi-layer QAOA and the unexplained discrepancy between the stated depth formulas and Table I. I do not see a novelty-disclosure issue; the reuse of the authors' own LR-QAOA schedules is transparent. If the alternating-pass rule cannot be substantiated, the multi-layer claims should be removed or clearly qualified."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Single-layer resource comparisons are solid and the SA qubit-ordering heuristic is a real, if incremental, improvement. The thing to check before trusting the p>1 hardware and noise results is the unproved 'reverse direction' rule in Sec. II-C; if that rule is wrong, the multi-layer claims collapse, though the single-layer numbers stand independently.\n\nThe paper does a competent job benchmarking PTC and SWAP network encodings against Qiskit-T, Qiskit-P, Qiskit-AI, and TKET on random graphs with varying edge density, and it clearly shows the crossover thresholds where parity-based encodings beat the transpilers. The SA cost function tailored to trailing removable interactions is new relative to [20], and the systematic threshold map across Nq and Ed is useful. The first hardware run of PTC on ibm_fez is a legitimate data point. Code and data are linked, so the resource counts are reproducible.\n\nTwo soft spots. First, the reversal rule: Sec. II-C says subsequent layers proceed in the reverse direction after truncating at t=2, with no derivation. The CNOTs in a PTC layer conjugate the RZ rotations; reversing the pass changes which interactions are effectively implemented unless a specific angle relation holds. The paper doesn't provide that. Since the ibm_fez experiments with p=3..20 and the p=50 noise simulation both depend on it, this is load-bearing. It could be a correct identity, but it needs a proof or at least a numerical check on the full unitary. Second, Table I reports PTC+SA depth 66 for Nq=20, Ed=1.0, while the paper's own formula gives 2Nq+2=42; SWAP+SA depth 77 vs 58. Maybe the reported depths include something extra, but the discrepancy is unexplained and makes the exact numbers harder to trust. Minor: only three random graphs per point, so the error bars are thin, but the trends are consistent.\n\nFor whom: practitioners choosing a transpilation strategy for QAOA on fixed superconducting layouts, and people working on parity encodings. It deserves a serious referee; the single-layer results and the threshold map are citable regardless of the reversal-rule outcome. My recommendation: send it to review, but the referee should push for a derivation or validation of the reverse-pass rule before the multi-layer conclusions are accepted.","headline":"Solid single-layer benchmarking with a useful SA heuristic, but the multi-layer claims rest on an unproved reverse-pass rule that needs to be fixed before the hardware results can be trusted.","tokens_in":14109,"tokens_out":2353,"would_cite":true,"duration_ms":19158,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that parity twine chains and SWAP networks, when paired with simulated-annealing qubit ordering, outperform standard transpilers for QAOA circuits once problem edge density exceeds a threshold that shrinks as qubit count…","keywords":["parity twine chain","SWAP network","QAOA","simulated annealing","qubit mapping","transpilation","weighted MaxCut","LR-QAOA"],"falsifier":"Run a noiseless statevector simulation of a 6–8 qubit non-fully connected weighted MaxCut instance for $p=3$ and $p=4$ using the alternating forward/backward PTC or SWAP construction and compare the output distribution against the exact QAOA unitary evolution; any discrepancy would falsify the truncation rule.","tokens_in":13123,"feed_emoji":"🧵","tokens_out":7427,"duration_ms":68190,"temperature":0.7,"pith_summary":"The paper aims to show that parity twine chains (PTC) and SWAP networks, two encodings that map fully connected circuits onto a line of qubits, can be made competitive for sparsely connected QAOA problems by optimizing the initial qubit order with simulated annealing. Above an edge-density threshold that falls as the system grows, the optimized encodings beat standard transpilers in both two-qubit gate count and circuit depth, with an 85% depth reduction and 28% gate reduction at 120 qubits and 25% connectivity. The authors also demonstrate on the ibm_fez device that PTC finds optimal solutions for fully connected weighted MaxCut problems up to 20 qubits, versus 15 qubits with SWAP networks.","feed_headline":"QAOA encodings beat Qiskit beyond a shrinking density threshold","feed_subtitle":"Above a crossover density that falls as qubits grow, the method cuts depth 85% and gates 28% at 120 qubits.","key_machinery":"Parity twine chains (PTC) are the central object: a CNOT-based encoding that folds the parities of several logical qubits onto a single physical qubit, so that a two-qubit ZZ interaction becomes a local single-qubit RZ rotation. A simulated-annealing step relabels the qubits' initial order so that the parities appearing at the end of the encoding correspond to edges missing from the problem graph and can be dropped; the same relabeling is applied to SWAP networks, where the dropped operations are SWAP gates belonging to missing edges. The paper's resource identities are $N_g = N_q^2 - 1$ and $d = 2N_q + 2$ for PTC per layer on a 1D chain, versus $N_g = \\frac{3}{2}N_q^2 - \\frac{5}{2}N_q + 1$ and $d = 3N_q - 2$ for SWAP networks.","core_discovery":"The central claim is that PTC and SWAP encodings, when their initial qubit order is chosen by simulated annealing, outperform Qiskit's optimization-level-3 transpiler for QAOA instances once the problem graph's edge density exceeds a threshold that decreases with qubit count: roughly $E_d = 0.35$ at 20 qubits and $E_d = 0.13$ at 120 qubits. Above the threshold the PTC+SA construction yields both fewer two-qubit gates and smaller circuit depth; at 120 qubits with $E_d = 0.248$ it reports an 85% reduction in depth and a 28% reduction in two-qubit gates relative to Qiskit-T. The paper further claims this is the first demonstration of these encodings beating standard transpilers in reduced-connectivity scenarios, and validates PTC on real hardware, finding optimal solutions up to 20 qubits whereas SWAP networks stop at 15.","pith_inferences":["If the alternating forward/backward layer rule holds, the annealed qubit ordering amortizes over all $p$ layers, meaning the reported per-layer resource counts understate the encodings' advantage for deep QAOA circuits.","The simulated-annealing cost function is a generic graph-relabeling heuristic that could transfer to other parity-based encodings or to T- and H-shaped hardware topologies, a direction the paper mentions but does not demonstrate.","The systematic fall of the crossing threshold with qubit count suggests a scaling law for when structured encodings beat general transpilers; fitting such a law to more sizes and hardware graphs would sharpen practical guidance.","A testable extension is to check whether the threshold depends only on edge density or also on graph structure, for instance by comparing random regular graphs with Erdős–Rényi graphs of the same density."],"forward_implications":["For QAOA on linear-chain hardware with non-trivial connectivity, PTC+SA and SWAP+SA become the preferred transpilation strategy above the density threshold, with the threshold shrinking as system size increases.","The PTC+SA construction reduces circuit depth relative to all tested transpilers across almost the entire edge-density range, even in regimes where it uses more two-qubit gates.","Under a depolarizing noise model, PTC improves success probability over SWAP networks by up to 5.65 percentage points at a moderate error strength, while approximation ratios remain comparable.","On the ibm_fez device, PTC extends the size at which optimal solutions to fully connected weighted MaxCut are found from 15 to 20 qubits, and extends distinguishability from a random sampler from 20 to 22 qubits."],"supporting_citations":[{"why":"It supplies the parity twine chain encoding that the paper optimizes.","marker":"[12]"},{"why":"It provides the temporal parity encoding that PTC generalizes.","marker":"[13]"},{"why":"It gives the optimal SWAP network layer counts and topology analysis used as baseline.","marker":"[11]"},{"why":"It reports the SWAP network scaling formulas for QAOA that the paper compares against.","marker":"[10]"},{"why":"It supplies the simulated annealing heuristic used to optimize qubit order.","marker":"[23]"},{"why":"It defines the LR-QAOA protocol used in the noise simulations.","marker":"[17]"},{"why":"It provides the LR-QAOA benchmarking protocol and random-sampler confidence intervals for the hardware experiments.","marker":"[18]"},{"why":"It is the Qiskit SDK whose level-3 transpiler is the main baseline.","marker":"[24]"},{"why":"It is the AI Routing Pass baseline that the encodings are compared with.","marker":"[26]"},{"why":"It is the TKET transpiler baseline used for comparison.","marker":"[27]"}],"fun_headline_variants":["Annealed qubit order beats Qiskit in QAOA beyond density cutoff","QAOA depth cut 85% at 120 qubits via annealed encodings","First demonstration: PTC and SWAP encodings top Qiskit in sparse QAOA","Threshold drops with qubits: annealing wins QAOA transpilation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The multi-layer hardware claims assume that, for a non-fully connected graph, truncating the first QAOA layer at $t=2$ and alternating forward/backward passes over subsequent layers reproduces $p$ independent cost-Hamiltonian evolutions without correction circuits, an assumption the paper states but does not derive.","fun_headline_variants_meta":{"raw":{"variants":["Annealed qubit order beats Qiskit in QAOA beyond density cutoff","QAOA depth cut 85% at 120 qubits via annealed encodings","First demonstration: PTC and SWAP encodings top Qiskit in sparse QAOA","Threshold drops with qubits: annealing wins QAOA transpilation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000296,"raw_usage":{"total_tokens":1749,"prompt_tokens":1007,"completion_tokens":742,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":623,"completion_tokens_details":{"reasoning_tokens":655}},"tokens_in":623,"tokens_out":742,"duration_ms":4803,"temperature":1.0,"reasoning_tokens":655,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:37:47.294052+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a noiseless statevector simulation of a 6–8 qubit non-fully connected weighted MaxCut instance for $p=3$ and $p=4$ using the alternating forward/backward PTC or SWAP construction and compare the output distribution against the exact QAOA unitary evolution; any discrepancy would falsify the truncation rule.","supporting_citations":[{"cited_title":"Connectivity-aware synthesis of quantum algorithms,","cited_arxiv_id":null,"evidence_quote":"It supplies the parity twine chain encoding that the paper optimizes."},{"cited_title":"Algorithm-oriented qubit mapping for variational quantum algorithms,","cited_arxiv_id":null,"evidence_quote":"It gives the optimal SWAP network layer counts and topology analysis used as baseline."},{"cited_title":"Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware,","cited_arxiv_id":null,"evidence_quote":"It reports the SWAP network scaling formulas for QAOA that the paper compares against."},{"cited_title":"Evaluating the performance of quantum process units at large width and depth,","cited_arxiv_id":null,"evidence_quote":"It provides the LR-QAOA benchmarking protocol and random-sampler confidence intervals for the hardware experiments."},{"cited_title":"Qiskit: An Open-Source Quantum SDK,","cited_arxiv_id":null,"evidence_quote":"It is the Qiskit SDK whose level-3 transpiler is the main baseline."},{"cited_title":"AI-powered transpiler passes,","cited_arxiv_id":null,"evidence_quote":"It is the AI Routing Pass baseline that the encodings are compared with."},{"cited_title":"Tket documentation,","cited_arxiv_id":null,"evidence_quote":"It is the TKET transpiler baseline used for comparison."}],"review_version":1}