{"id":"3e7f30f4-1079-4ef0-aee7-d37c50d55f71","arxiv_id":"2504.17965","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A quantized Fisher-Yates shuffle builds five quantum circuits for uniform permutation superpositions with O(n log n) qubits and up to O(n^2 log^2 n) gates, though the headline says O(n^2 log n).","lead":"This paper turns the classical card-shuffle algorithm into quantum circuits that create equal superpositions of all ways to reorder n items. The goal is a resource-efficient building block for quantum encryption, error correction, and optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised O(n^2 log n) gate/depth bound is contradicted by the paper's own Table I and Eqs. (12)-(16), which give O(n^2 log^2 n) for the binary-encoded algorithms; the one-hot route to O(n^2 log n) is only sketched and changes qubit counts.","rationale":"The reader's conditional verdict is appropriate, but my primary concern differs from the stated weakest assumption. The borrowed-ancilla decomposition is a real unproven step, yet the specific availability argument in Section IV.4 is standard and likely repairable with a more careful accounting of idle subregisters and gate-level restorations. The more decisive issue is that the paper's own quantitative analysis in Section IV.5 and Table I contradicts the abstract and conclusion's headline O(n^2 log n) complexity. This is not an external standard the paper merely fails to meet; it is an internal inconsistency in the central resource-optimality claim. A conditional verdict remains correct because the algorithmic constructions and the correctness proof for Algorithm 5 are coherent, and the resource claims can likely be repaired by either demoting the advertised bound or fully specifying the one-hot variants and their qubit costs. The concrete test is deliberately algebraic and uses only the paper's own formulas, so it settles the mismatch without relying on the authors' code.","tokens_in":17442,"tokens_out":22585,"duration_ms":235934,"concrete_test":"Evaluate the leading term of Eq. (12) using the paper's own G(C^m X) = 4(m-2)(6G(CX)+7G(RZ)+2G(H)) and G(U_i) from Eq. (22). The algebraic check should show that the sum over i of i * ceil(log n) * |i|_bin is Theta(n^2 log^2 n); if it does, the abstract's O(n^2 log n) bound cannot hold for Algorithms 3-7. Then compile the one-hot variant A_oh described in Section IV.5 into a complete, proven algorithm and verify explicitly that it keeps O(n log n) qubits and O(n^2 log n) gates; the paper should state unambiguously that this variant, rather than Table I, supports the advertised resource claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central resource claim in the abstract and conclusion is that the construction requires only O(n log n) qubits and O(n^2 log n) gates and circuit depth. That claim is not what the paper's own analysis establishes. Equations (12)-(16) and Table I state G(A), G(\\tilde A) in O(n^2 log^2 n), G(B), G(\\tilde B) in O((m + log n) n^2 log n), and G(C) in O(m n^2 log n). The dominant term is the sum over i of i * log n * |i|_bin, which is Theta(n^2 log^2 n); no constant-factor rewriting of the stated G(C^m X) = O(m) removes the second log factor. To reach O(n^2 log n), Section IV.5 switches to one-hot controls, but that is a separate construction: A_oh and B_oh are not the pseudocode Algorithms 3-7, and for the entangling versions \\tilde A_oh, \\tilde B_oh, C_oh the ancilla cost rises to O(n^2) qubits in Table II. Thus the abstract's simultaneous O(n log n) qubits and O(n^2 log n) gates is only achieved by A_oh (and by B_oh if m is treated as constant), not by the suite as stated. This is an internal inconsistency, not merely a typo: the conclusion repeats the O(n^2 log n) bound without the qubit tradeoff, and the optimality conjecture is framed around it. The borrowed-ancilla decomposition flagged in the reader's verdict is a genuine proof gap, but it is a standard technique and the availability argument appears plausibly sufficient; the unsupported advertised complexity is the more immediate obstacle to accepting the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a quantisation of the classical Fisher–Yates shuffle as a family of five quantum circuits (Algorithms 3–7) for preparing uniform superpositions over permutations of composite registers. Two disentangling versions, A and B, uncompute the ancilla after each iteration; two entangling versions, \\tilde A and \\tilde B, keep ancilla subregisters entangled with the permutation history; and a light entangling version, C, omits the permutation register. The authors prove correctness of the disentangling shuffle (Theorem 2, Appendix A) by induction using Lemma 1, then derive the other four variants by restriction. The resource analysis in Section IV gives qubit counts in Eqs. (7)–(11), gate counts in Eqs. (12)–(16), and cycle counts in Eqs. (17)–(21), with the asymptotics summarized in Table I and, for the one-hot encoding, Table II. The abstract and Section V claim that the construction requires O(n log n) qubits and O(n^2 log n) gates and depth; the derivation in Section IV.5 and Table I instead give O(n^2 log^2 n) for A and \\tilde A, with the one-hot variants in Table II achieving O(n^2 log n) only for A_oh and with extra qubit costs for the entangling versions.","tokens_in":17754,"tokens_out":12543,"duration_ms":122542,"significance":"If the resource claims are corrected, the paper makes a solid contribution. The proof of Theorem 2 is an explicit induction with no circularity, and the framework genuinely unifies earlier constructions (Barenco et al., Chiew et al., Adhikari, Bai–Shang) under one principle. The computed O(n^2 log^2 n) gate bound for A and \\tilde A at O(n log n) qubits, if valid, still improves on the O(n^3 log^2 n) of Chiew et al. and the O(n^{5/2} log n) of Bai–Shang, so the main qualitative resource improvement survives the correction. The open-source Qiskit implementation is a further strength supporting reproducibility. The advertised simultaneous O(n log n) qubit and O(n^2 log n) gate/depth claim is, however, not what the paper's own analysis establishes, and this inconsistency affects the central optimality statement.","major_comments":[{"comment":"The abstract and Section V state that the construction requires only O(n log n) qubits and O(n^2 log n) gates and circuit depth, but Section IV.5 and Table I state G(A), G(\\tilde A) \\in O(n^2 log^2 n), G(B), G(\\tilde B) \\in O((m+log n)n^2 log n), and G(C) \\in O(mn^2 log n), with the corresponding depth bounds in Eqs. (17)–(21). The O(n^2 log n) figure is achieved only by the one-hot-encoded variant A_oh in Table II, and by B_oh only if m is treated as constant; for \\tilde A_oh, \\tilde B_oh and C_oh the one-hot encoding raises the qubit count to O(n^2) in the ancilla. Because the abstract and the optimality conjecture in Section V are framed around this simultaneous resource claim, the authors must either revise these passages to state the actual O(n^2 log^2 n) scaling of the main suite or explicitly restrict the headline claim to the one-hot state-preparation variant.","section":"Abstract; Section V; Section IV.5; Table I"},{"comment":"The gate counts rely on the assertion that 'we may always borrow qubits from a data/permutation subregister which is currently not swapped or does not control the uncomputation step' to obtain G(C^m X) \\in O(m). This assertion is not proved, and it is load-bearing for Table I and for Eqs. (12)–(21). One must verify that enough borrowable qubits are available for every i and j, including the last iteration i = n-1, the uncomputation cascade in Algorithms 3 and 5, and the entangling variants where ancilla subregisters remain occupied; one must also ensure that the borrowed qubits are returned to their original states. Please either give a rigorous availability argument or incorporate the necessary ancilla overhead into the qubit counts of Eqs. (7)–(11).","section":"Section IV.4, Eqs. (12)–(21)"},{"comment":"The asymptotic conclusion in Section IV.5 correctly states G(A), G(\\tilde A) \\in O(n^2 log^2 n), but the same paragraph's comparison to prior work and the following paragraph's one-hot discussion mix two different constructions. The reader is left to infer that the abstract's O(n^2 log n) gate/depth claim refers to the one-hot variants of Table II; this should be made explicit, and the optimality conjecture should be formulated separately for the binary-encoded suite (O(n^2 log^2 n)) and for the one-hot state-preparation variant (O(n^2 log n)).","section":"Section IV.5, paragraph after Eq. (23)"},{"comment":"The exact gate-count formulas include a term \\Delta(i) G(X) inside the sum over i for the permutation-register initialization, but the initialization in lines 1–3 of Algorithms 3–6 is a one-time cost of \\sum_{k=1}^{n-1} \\Delta(k) G(X), not a cost incurred in every iteration. The asymptotic results are unaffected because the overcount is O(n log n), but Eqs. (12)–(15) are not exact as written and are inconsistent with the cycle-count treatment in Eq. (17), where the initialization appears once as C(X).","section":"Eqs. (12)–(15)"}],"minor_comments":[{"comment":"The pseudocode for Algorithm 7 includes lines 1–3 that apply X^{0\\to k} to a register Hp:k, even though the light shuffle C is defined on Hd \\otimes Ha without the permutation register Hp; these lines should be removed to match the construction described in Section III and the caption.","section":"Algorithm 7, Figure 4"},{"comment":"The sentence 'Since \\tau_{j,i} leaves 0 \\le k < 0 with k \\not= j invariant' contains a typo; it should read '0 \\le k < i, k \\not= j' (or the intended range).","section":"Appendix A, proof of Theorem 2"},{"comment":"For m=2 the paper gives the Toffoli decomposition as six CX plus nine single-qubit gates, while for m \\ge 3 it states G(C^m X) = 4(m-2)(6G(CX)+7G(RZ)+2G(H)); the relationship between the single-qubit-gate count in the m=2 case and the G(RZ), G(H) factors in the general formula should be clarified so the total counts are directly comparable.","section":"Section IV.4, paragraph on C^m X decomposition"},{"comment":"The open-source implementation is cited as 'QuantumFisherYates (2025)' without a URL or repository identifier; please include the repository address so the code can be located.","section":"Reference [42]"},{"comment":"The paper alternates between the notations 'log^2(n)' and 'log(n)^2'; using a single convention would improve readability.","section":"Throughout Section IV"}],"recommendation":"major_revision","confidential_remarks":"The correctness core of the paper is sound and the resource bounds are mostly derived transparently; the immediate obstacle is the unsupported O(n^2 log n) headline claim in the abstract and conclusion, which contradicts the paper's own Table I and Section IV.5. The borrowed-ancilla argument is a genuine gap but appears fixable with an explicit availability proof. I recommend major revision rather than rejection because the corrected O(n^2 log^2 n) scaling still positions the binary-encoded suite favorably against prior O(n log n)-qubit constructions, and the one-hot variant A_oh does deliver the advertised O(n^2 log n) gate count for state preparation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the core construction is sound, the paper is honest about recovering Barenco et al. as a special case, and the explicit resource formulas are a genuine service to the subfield. But the abstract and conclusion claim O(n log n) qubits and O(n^2 log n) gates/depth, which is not what the paper's own analysis establishes. Section IV.5 and Table I give O(n^2 log^2 n) for A and ãA, O((m+log n)n^2 log n) for B and ãB, and O(m n^2 log n) for C under binary-encoded controls. The O(n^2 log n) figure only appears in the one-hot variants of Table II, and those cost extra ancillas, up to O(n^2) for the entangling versions. This is an internal inconsistency, not a typo: the conclusion repeats it and the optimality conjecture leans on it. The fix is straightforward—correct the headline or restructure the presentation around the one-hot route with the qubit tradeoff made explicit.\n\nThe correctness proof for Algorithm 5 (Theorem 2) is a real induction and the corollaries follow. The five-way separation into disentangling/entangling state preparation, disentangling/entangling shuffle, and light entangling shuffle is well organized, and the use of Shukla–Vedula's binary encoding is clean. The literature comparison to Chiew et al., Bai–Shang, and Bärtschi–Eidenbenz looks fair.\n\nTwo softer issues. First, Algorithm 7's pseudocode still contains lines applying X gates to Hp:k, but the light shuffle has no permutation register; that is a leftover from the other algorithms and should be deleted. Second, Section IV.4 asserts that a C^m X gate can always be decomposed in O(m) gates by borrowing qubits from subregisters that are not currently swapped. That is a standard technique, but the claim is not proved and the last iteration (i = n−1) has no untouched subregisters, so the exact gate counts in Eqs. (12)–(21) are not fully justified as written. The asymptotic bounds may survive because an exponential fallback at the last iteration is still dominated by the stated big-Os, but the paper should say so. Also, reference [42] is a bare name with no URL or hash, which is unhelpful for a reproducibility claim.\n\nMy take: this deserves a serious referee, but not acceptance without revision. The construction and the correct parts of the resource analysis are worth keeping; the headline complexity claim has to be fixed first. A corrected version will be a useful reference for anyone working on permutation-state preparation or symmetrization circuits.","headline":"A useful, mostly correct family of permutation-superposition circuits with a systematic resource comparison, undercut by an overstated headline complexity that contradicts its own tables.","tokens_in":18357,"tokens_out":5422,"would_cite":true,"duration_ms":59802,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"The quantum Fisher-Yates shuffle prepares uniform superpositions of permutations with O(n log n) qubits and O(n^2 log n) gates, unifying previous constructions.","keywords":["quantum Fisher-Yates shuffle","uniform superposition of permutations","quantum state preparation","controlled swap gates","permutation circuits","resource analysis","quantum optimisation","reversible classical algorithms"],"falsifier":"For a fixed small $n$ (say $n=5$), write out the exact sequence of multi-controlled gates in one iteration of Algorithm 3 and check whether, at each gate, enough subregisters of $H_p$ are untouched to serve as borrowed ancillas. A concrete failure mode would be an iteration in which the controlled swaps and the uncomputation cascade together touch all $n$ permutation subregisters, leaving no borrowable qubit; counting the resulting native CX gates after decomposing every $C^mX$ with no extra ancillas would then give a gate count above the claimed $O(n^2\\log^2 n)$.","tokens_in":17158,"feed_emoji":"🔀","tokens_out":11532,"duration_ms":101838,"temperature":0.7,"pith_summary":"The paper claims that the classical Fisher–Yates shuffle, the standard linear-time method for sampling a uniform random permutation, can be quantised directly: each random choice of $j$ becomes a uniform superposition, and each swap becomes a controlled swap. From this single idea the authors derive five quantum circuits that prepare uniform superpositions of permutations, or uniformly permuted data with the permutation recorded, on composite registers. The construction uses only $O(n\\log n)$ qubits and, in the paper's resource analysis, $O(n^2\\log^2 n)$ gates for the binary-encoded state-preparation variants, with the abstract and conclusion reporting $O(n^2\\log n)$ gates and depth. A sympathetic reader would care because these states are the starting point for permutation-symmetric quantum error-correcting codes, quantum encryption protocols, and Grover/QAOA approaches to scheduling and routing problems.","feed_headline":"Fisher-Yates shuffle cuts permutation-state cost to O(n^2 log n)","feed_subtitle":"Five circuit variants prepare uniform superpositions of n-element permutations with the best-known qubit and gate counts.","key_machinery":"The load-bearing object is the controlled subregister swap, executed in superposition. In iteration $i$, the ancilla (or a fresh ancilla subregister) is placed in $\\frac{1}{\\sqrt{i+1}}\\sum_{j=0}^i |j\\rangle_a$ by the ancilla-free circuit $U_i$ of [41]; then, for each $j$, a multi-controlled SWAP exchanges subregisters $j$ and $i$ of the permutation and/or data register, conditioned on $|j\\rangle_a$. The combinatorial identity that carries the correctness proof is Lemma 1, which states that $(j,\\sigma)\\mapsto \\tau_{j,i}\\tilde\\sigma$ is a bijection from $\\{0,\\ldots,i\\}\\times S_i$ to $S_{i+1}$; this is the uniqueness of the monotone factorisation, and it ensures the loop builds each permutation exactly once. Disentangling variants add a cascade of controlled bit flips that use the state of the permutation register to uncompute the ancilla, which is what lets a single $\\lceil\\log_2 n\\rceil$-qubit ancilla be reused.","core_discovery":"The paper's central claim is that the classical Fisher–Yates shuffle can be promoted to a quantum circuit by keeping the loop structure and replacing each random choice of an exchange index $j$ with a uniform superposition $\\frac{1}{\\sqrt{i+1}}\\sum_{j=0}^i |j\\rangle_a$ in an ancilla register, then swapping subregisters $j$ and $i$ only when the ancilla holds $|j\\rangle$. This yields five unitaries — $A$, $\\tilde A$, $B$, $\\tilde B$, and $C$ — defined by Eqs. (2)–(6), covering disentangled and entangling state preparation, disentangled and entangling shuffles, and a 'light' shuffle that records the permutation only in the ancilla. The correctness proof rests on Lemma 1, the bijection $(j,\\sigma)\\mapsto \\tau_{j,i}\\tilde\\sigma$ between $\\{0,\\dots,i\\}\\times S_i$ and $S_{i+1}$, which guarantees that every permutation is generated exactly once; Theorem 2 proves Algorithm 5 implements $B$, and the other four algorithms follow as corollaries. The resource analysis reports $O(n\\log n)$ qubits throughout, with gate/cycle counts of $O(n^2\\log^2 n)$ for $A$ and $\\tilde A$, $O((m+\\log n)n^2\\log n)$ for $B$ and $\\tilde B$, and $O(m n^2 \\log n)$ for $C$ in the binary encoding, and the conclusion states the overall complexity as $O(n^2 \\log n)$ gates and depth.","pith_inferences":["The same 'replace a random choice by a superposition, then control the operation on the sampled value' recipe should apply to any classical algorithm whose random choices are uniform and whose operations are invertible, so uniform superpositions over other combinatorial families (matchings, spanning trees, linear extensions) could be built from their classical samplers.","The paper's resource comparison depends on a borrowed-ancilla decomposition that is asserted but not proven for every iteration; if that assumption fails, the one-hot encoding from Table II provides a fallback that increases qubits to $O(n^2)$ but restores the $O(n^2\\log n)$ gate scale, so the practical trade-off is likely to be hardware-dependent.","A direct way to test the claimed uncomputation is to run the disentangling variants on small $n$ and measure the ancilla register after the circuit; entanglement there would pinpoint the iteration where coherent control of the swap or the uncomputation cascade fails.","The open question the paper leaves—which symmetric-group representations admit iterative uncomputation—suggests that not every permutation-based state preparation can be done with a clean ancilla; the entangled variants are the safe choice when the representation's action cannot be inverted from the data state alone."],"forward_implications":["Using the disentangling state-preparation circuit, any quantum algorithm that needs a uniform superposition over all $n!$ permutations can start from $O(n\\log n)$ qubits and, in the binary encoding, $O(n^2\\log^2 n)$ gates rather than the $O(n^3)$-scale gate counts of earlier constructions at comparable qubit cost.","The three shuffling variants give a direct way to superpose outcomes of permutation-dependent data processing: run the light shuffle on data only, the entangling shuffle with the permutation stored in a separate register, or the disentangling shuffle with clean ancillas.","Because each iteration only needs a uniform superposition over the first $i+1$ basis states, the same circuit template can be stopped after $i$ iterations to prepare a uniform superposition over $S_{i+1}$, giving a coherent way to generate smaller permutation groups.","The one-hot encoded variants trade $\\Theta(n)$ or $\\Theta(n^2)$ ancilla qubits for one fewer $\\log n$ factor in gate/cycle count, letting a user choose the best point on the trade-off for a given hardware.","If the resource analysis holds, these circuits become natural subroutines for permutation-symmetric error-correcting encodings, quantum permutation-pad cryptography, and Grover/QAOA solvers for TSP and scheduling problems."],"supporting_citations":[{"why":"Original statement of the Fisher-Yates shuffle, the classical algorithm being quantised.","marker":"[39]"},{"why":"Durstenfeld's O(n) version that fixes the loop structure of Algorithms 1 and 2.","marker":"[38]"},{"why":"Ancilla-free uniform-superposition circuit U_i used in every iteration to prepare the sum over |0> ... |i>.","marker":"[41]"},{"why":"Provides the multi-controlled X gate decompositions whose O(m) cost is used in the gate and cycle counts.","marker":"[40]"},{"why":"Standard textbook decompositions for controlled SWAP and Toffoli gates used in the resource formulas.","marker":"[43]"},{"why":"The earlier permutation-superposition construction that the current framework recovers as a special case with one-hot controls.","marker":"[1]"},{"why":"Mixed-radix permutation-state construction used as a main comparator; the paper argues its gate count is worse by a log factor.","marker":"[30]"},{"why":"Recent insertion-based construction at O(n log n) qubits whose gate count the paper claims to improve.","marker":"[15]"},{"why":"Permutation-matrix construction requiring O(n^2) qubits but O(n^2) cycles, the only major method not a special case.","marker":"[18]"}],"fun_headline_variants":["Quantum Fisher-Yates shuffle unifies five circuit variants","Best-known resource counts for permutation-state preparation","O(n log n) qubits and O(n^2 log n) gates for quantum shuffle","Classical Fisher-Yates quantized for uniform permutation superpositions","Simple quantum shuffle matches best-known complexity bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole resource-optimality comparison rests on the assumption that every multi-controlled X gate used in the circuits can be decomposed with $O(m)$ gates using only qubits borrowed from registers that are not being acted on, without adding qubits to the counts in Eqs. (7)–(11); if any iteration lacks a borrowable subregister, the $O(n^2\\log^2 n)$ gate bound and the comparison with prior algorithms break down.","fun_headline_variants_meta":{"raw":{"variants":["Quantum Fisher-Yates shuffle unifies five circuit variants","Best-known resource counts for permutation-state preparation","O(n log n) qubits and O(n^2 log n) gates for quantum shuffle","Classical Fisher-Yates quantized for uniform permutation superpositions","Simple quantum shuffle matches best-known complexity bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000997,"raw_usage":{"total_tokens":4279,"prompt_tokens":1058,"completion_tokens":3221,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":3138}},"tokens_in":674,"tokens_out":3221,"duration_ms":23271,"temperature":1.0,"reasoning_tokens":3138,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:29:08.954402+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed small $n$ (say $n=5$), write out the exact sequence of multi-controlled gates in one iteration of Algorithm 3 and check whether, at each gate, enough subregisters of $H_p$ are untouched to serve as borrowed ancillas. A concrete failure mode would be an iteration in which the controlled swaps and the uncomputation cascade together touch all $n$ permutation subregisters, leaving no borrowable qubit; counting the resulting native CX gates after decomposing every $C^mX$ with no extra ancillas would then give a gate count above the claimed $O(n^2\\log^2 n)$.","supporting_citations":[{"cited_title":"Sedgewick, ACM Comput","cited_arxiv_id":null,"evidence_quote":"Original statement of the Fisher-Yates shuffle, the classical algorithm being quantised."},{"cited_title":"Chiew, K","cited_arxiv_id":null,"evidence_quote":"Durstenfeld's O(n) version that fixes the loop structure of Algorithms 1 and 2."},{"cited_title":"Marsh and J","cited_arxiv_id":null,"evidence_quote":"Ancilla-free uniform-superposition circuit U_i used in every iteration to prepare the sum over |0> ... |i>."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the multi-controlled X gate decompositions whose O(m) cost is used in the gate and cycle counts."},{"cited_title":"Steinhaus, One hundred problems in elementary math- ematics (Courier Corporation, New York, 1979)","cited_arxiv_id":null,"evidence_quote":"Standard textbook decompositions for controlled SWAP and Toffoli gates used in the resource formulas."},{"cited_title":"Since the ancilla register’s state is uncomputed after each itera- tion (lines 10-12), we can reuse it’s qubits for the sub- sequent one","cited_arxiv_id":null,"evidence_quote":"The earlier permutation-superposition construction that the current framework recovers as a special case with one-hot controls."},{"cited_title":"Symmetry-based quantum algorithms for open-shop scheduling with hard constraints","cited_arxiv_id":"2211.05822","evidence_quote":"Mixed-radix permutation-state construction used as a main comparator; the paper argues its gate count is worse by a log factor."},{"cited_title":"Kuang and M","cited_arxiv_id":null,"evidence_quote":"Recent insertion-based construction at O(n log n) qubits whose gate count the paper claims to improve."},{"cited_title":"Majenz, G","cited_arxiv_id":null,"evidence_quote":"Permutation-matrix construction requiring O(n^2) qubits but O(n^2) cycles, the only major method not a special case."}],"review_version":1}