{"id":"d929348e-e2fd-4f79-bd99-215da11a99d2","arxiv_id":"2509.01912","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"SSHR uses parallelotopes (affine subspaces) in the Boolean hypercube to synthesize quantum oracles for <=8-bit functions and reports large CNOT reductions, but the provided construction does not uncompute its CNOTs.","lead":"This paper proposes a method, SSHR, that uses geometric shapes inside the Boolean hypercube to build small quantum circuits with fewer CNOT gates. A serious gap in the algorithm's circuit construction means the reported gains may not hold.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1 never uncomputes the CNOTs applied to the input register, so SSHR-generated circuits are not quantum oracles; the reported CNOT reductions are therefore for unverified circuits.","rationale":"The reader's weakest assumption is exactly the correctness of Algorithm 1 as an oracle block. A close reading of the pseudocode confirms the CNOTs are not uncomputed, and the MCT controls act on modified qubits. The paper offers no independent support: no formal verification, no reproducible code, and the theorem proof does not address uncomputation. If the concrete test is run and fails, the central claim collapses because the reported CNOT/T reductions are for circuits that do not implement the target function. The translated-parallelotope example strengthens the concern by showing an internal inconsistency between the ILP's output and the synthesis routine. Therefore no adjustment to the reader's REJECT verdict is needed, though the confidence might improve if the test were actually run.","tokens_in":14730,"tokens_out":8024,"duration_ms":85406,"concrete_test":"Implement Algorithm 1 for the 2-qubit function f(x)=1 iff x is 00 or 11 (the m=1 parallelotope with basis vector (1,1)), build the unitary of the produced circuit, and check whether every computational basis state |x>|y> is mapped to |x>|y xor f(x)>. For the input |10>|0>, the circuit leaves q1 flipped, so the input register is not restored; the test will fail. A wider check is to run the full SSHR-I on all 3-bit functions and compare each generated circuit's truth table on the output qubit against f(x) while verifying input qubits are unchanged.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The key assumption is that Algorithm 1 builds a valid oracle block. In the listing, lines 4-10 apply CNOT(st, st+i) to input qubits and store targets in list. Lines 11-17 only surround the MCT with X gates; the CNOTs are never undone. Thus after a block, every non-anchor qubit in a parallelotope block has been XORed with its block anchor, so |x> is not preserved. The MCT control condition is evaluated on these transformed qubits, so the output y is flipped according to a function of the transformed input, not the original x. This violates the oracle definition Of|x>|y>|0> = |x>|y xor f(x)>|0> given in Section I and II-B. The same flaw invalidates the claim in Section III that 'intermediate results are recovered after use' - no recovery operation is present. Additionally, the example in Section IV-D selects S2=[0110,1110], a translated copy of a 1D parallelotope. Eq. (1) defines parallelotopes as Minkowski sums of line segments from the origin, with no translation vector, so S2 is outside the stated definition; Algorithm 1 as written cannot represent it. The empirical gate counts in Tables IV-VII are therefore computed from circuits whose functional correctness has not been established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SSHR, a method for synthesizing quantum oracles for small Boolean functions (≤8 variables) by exploiting the spatial structure of parallelotopes in the Boolean hypercube. Two variants are presented: SSHR-H, a greedy heuristic, and SSHR-I, an ILP-based solver for a Weighted Parity Set Covering Problem. The central theoretical claim is Theorem 1, which states that if the on-set contains an m-dimensional parallelotope, the oracle can be implemented using one (n−m)-MCT gate via Algorithm 1. The paper reports substantial CNOT and T-count reductions compared to ESOP and XAG baselines.","tokens_in":14996,"tokens_out":8673,"duration_ms":93974,"significance":"The conceptual direction—using global geometric structure of Boolean functions to guide oracle synthesis—is appealing, and the ILP parity-set-cover formulation is a flexible way to optimize different gate metrics. If the construction were correct, the reported reductions (56% and 81% CNOT savings over ESOP and XAG for 5-bit functions) would be practically valuable for small-scale NISQ oracle implementations. However, the paper does not provide machine-checked proofs or reproducible code, and the central circuit construction is not validated. The significance of the empirical claims is therefore contingent on correcting the fundamental issues described below.","major_comments":[{"comment":"Algorithm 1 adds CNOTs in lines 4–10 but never reverses them. Thus the input register is not restored, contradicting the oracle definition in §II-B and the statement in §III that 'intermediate results... are recovered after use.' Concretely, for n=2 with α=(1,0), the block maps |x0,x1,y⟩ to |x0, x1⊕x0, y⊕¬(x1⊕x0)⟩ (where the X/MCT/X sequence toggles y when x1⊕x0=0), so y flips for x∈{00,11} rather than the intended vertices {00,10}. Hence Theorem 1 is false as stated, and the gate counts in Tables IV–VII are for circuits that do not compute the declared Boolean function.","section":"§III, Algorithm 1"},{"comment":"The example selects S2=[0110,1110], a translated 1D parallelotope. Equation (1) defines a parallelotope as a Minkowski sum of segments from the origin, with no translation vector. Theorem 1's proof assumes without loss of generality that the first vertex is (0,…,0), but NPN input negation/permutation cannot translate an arbitrary vertex to the origin. Consequently, S2 lies outside the stated definition, and Algorithm 1, which initializes st=0, cannot synthesize it. The example therefore claims validity for a structure the proposed algorithm does not handle.","section":"§IV-D, Eq. (1)"},{"comment":"The ILP formulation uses an undefined symbol B in constraints (C2)-(C3) and in the index set 'A − B'. Moreover, constraints (C4)-(C7) are not written out; the text merely lists '∀i∈S', '∀j∈U', etc. Without the exact constraint formulas and a definition of B, the WP-SCP model cannot be verified or reproduced, undermining the SSHR-I results in Tables VI–VII.","section":"§IV-B, Table III, constraints (C2)-(C3)"}],"minor_comments":[{"comment":"There are several typos: 'prallelotopes' in the abstract, 'Algoritm 1' in §IV-B, and 'embed ed' in §VI. The writing also contains awkward phrases such as 'we statute the synthesis problem' in §I.","section":"Throughout"},{"comment":"The captions and diagrams are difficult to follow. Fig. 4's caption is incomplete ('common control qubits ... qout :'), and Fig. 5(b) does not clearly label which gate corresponds to each selected parallelotope. Please add explicit labels and a step-by-step trace for the example.","section":"Fig. 4 and Fig. 5"},{"comment":"The random generation of 5-bit and 6-bit Boolean functions is not specified in enough detail (no seeds, no distribution description), which limits reproducibility. Also, the two-minute ILP timeout is mentioned, but the optimality gap or frequency of timeout is not reported.","section":"§V-A"},{"comment":"The dash for ESOP for n>6 is justified by saying ESOP is unable to generate circuits, but no runtime or memory evidence is provided. If ESOP was simply not run, that should be stated separately.","section":"§V-B, Table V"},{"comment":"The choice R=3/4 is argued heuristically, but no sensitivity analysis is presented. Since this parameter directly affects SSHR-H's behavior, a short study varying R would strengthen the paper.","section":"§V-B, parameter R"}],"recommendation":"reject","confidential_remarks":"The central flaw in Algorithm 1 is not a local presentation issue: the circuits produced by the paper's proposed method do not implement the intended oracle, and the reported experimental gains are therefore not meaningful. Even if the CNOTs were uncomputed, the translated-parallelotope issue and the incomplete ILP formulation would require substantial reworking. I recommend rejection, though I would be open to reconsidering a future version that fixes the circuit construction and re-evaluates the benchmarks."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nYou should know two things. The central synthesis algorithm in arXiv:2509.01912 does not appear to produce valid quantum oracles: Algorithm 1 applies CNOTs to the input register and never uncomputes them, so the input state isn't preserved. And the reported CNOT reductions are therefore computed from circuits whose correctness is unestablished.\n\nCredit where due: the idea of extracting parallelotope structures from the on-set and using them as building blocks is genuinely worth exploring. The ILP formulation of the synthesis task as weighted parity set cover is a clean and flexible way to use spatial correlations. The experimental coverage is decent: all 3- and 4-bit functions plus a random sample of 5- and 6-bit functions, with a consistent cost model for both the ILP objective and the evaluation.\n\nThe soft spot is load-bearing. The oracle definition in Sec. II requires |x> unchanged. Algorithm 1 adds CNOTs in lines 4-10, then X gates and an MCT, and X gates again. There is no inverse-CNOT stage. So after a block, the non-anchor qubits are left XORed with the anchor. In a simple 1D case the MCT still flips the output for the intended minterms, but the input register is left permuted. Concatenated blocks compose those permutations, and the final circuit evaluates f on a linearly transformed input, not on x. The claim in Sec. III that intermediate results are \"recovered after use\" is not supported by the listing. I independently checked this and the stress-test note is on target.\n\nSmaller issues: Eq. (1) defines parallelotopes as Minkowski sums of segments from the origin, but the Section IV-D example selects S2=[0110,1110], a translated line segment. Translated parallelotopes fall outside the definition, and Algorithm 1 cannot represent them. Also, the abstract credits \"our approach\" with the 56% and 81% CNOT gains, while Table IV shows SSHR-H uses more CNOTs than ESOP at every size; only SSHR-I delivers those reductions.\n\nWho this is for: people working on reversible logic synthesis and small-scale NISQ oracle compilation. If the uncomputation is fixed, the idea may still have value, though the CNOT savings will likely shrink substantially. As submitted, the core claim doesn't hold. Still, the novelty is real and the presentation is honest enough that I'd send it to a referee rather than desk-reject; the flaw is the kind a careful review should catch, and the authors deserve a chance to repair or reframe.\n\nRecommendation: reject as is, but engage with it if a revised version appears.","headline":"Clever idea, but the circuits don't implement the stated oracles because the input register is never restored.","tokens_in":15533,"tokens_out":7225,"would_cite":false,"duration_ms":78405,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"By viewing the on-set of a Boolean function as parallelotopes embedded in its hypercube, this paper constructs quantum oracle circuits with fewer CNOT gates than ESOP or XAG synthesis, reporting 56% and 81% reductions at five variables and","keywords":["quantum circuit synthesis","Boolean functions","parallelotope","Multi-Control Toffoli gates","CNOT gate optimization","weighted parity set cover","oracle synthesis","NPN equivalence"],"falsifier":"Run the paper's Section IV-D example through Algorithm 1: take the selected translated parallelotope S2=[0110,1110], apply the block to every 4-bit input with the target qubit in |0>, and check whether the target equals the Boolean function's value on all 16 inputs and whether all input qubits return to their starting values. A single mismatch refutes the correctness premise. The same exhaustive check can be automated for all 3- and 4-variable functions by synthesizing each with SSHR-I and simulating the resulting circuit as a permutation on (n+1)-qubit basis states.","tokens_in":14560,"feed_emoji":"🧊","tokens_out":15470,"duration_ms":155283,"temperature":0.7,"pith_summary":"A Boolean function's on-set, read as a subset of the n-dimensional hypercube, contains boxes (parallelotopes) generated by m orthogonal binary directions. This paper argues that each such box is a quantum-circuit atom: 2^m minterms can be implemented by a single (n−m)-controlled Toffoli gate plus a CNOT wiring pattern, with no auxiliary qubits needed to store intermediate results. Two algorithms consume these atoms: SSHR-H selects them greedily for fast synthesis, while SSHR-I formulates the whole task as a weighted parity set-cover problem solved by an ILP, requiring on-set minterms to be covered odd times and off-set minterms even times. The experimental claim is that the ILP variant lowers CNOT counts by 56% versus ESOP and 81% versus XAG for 5-bit functions, with consistent reductions in T-counts and ancillary qubits, and that the heuristic variant extends to 7- and 8-bit functions.","feed_headline":"Truth-table geometry cuts quantum oracle CNOTs by up to 81%","feed_subtitle":"New method mines Boolean functions for cube-like shapes, beating ESOP and XAG on up to 8 variables.","key_machinery":"The central object is the parallelotope: the Minkowski sum of m linearly independent line segments inside {0,1}^n. Lemma 1 requires the basis vectors to have disjoint 1-positions, which is what lets a single Multi-Control Toffoli gate test all 2^m vertices at once in Theorem 1. The second piece of machinery is the Weighted Parity Set-Covering Problem (WP-SCP): binary variables pick parallelotopes, parity constraints force odd/even coverage on on/off minterms, and a weighted objective counts CNOT and T-gate costs. This turns circuit synthesis into an integer program whose feasible region contains every ESOP decomposition.","core_discovery":"A Boolean function's on-set can be decomposed into parallelotopes, the boxes in its n-dimensional hypercube generated by m orthogonal binary vectors. The paper proves that 2^m minterms forming such a box cost one (n−m)-controlled MCT gate plus the CNOTs that wire it: basis-vector positions are made disjoint, CNOTs copy the pattern onto them, one MCT tests the common coordinates, and X gates supply the needed 0-controls. Synthesis then becomes parity selection—choose boxes so on-set minterms are covered odd times and off-set minterms even times—implemented greedily in SSHR-H or as an integer program in SSHR-I. Since every ESOP product term is a degenerate parallelotope, a feasible solution al","pith_inferences":["The parity set-cover model uses only odd/even coverage, so the same ILP machinery could be pointed at random functions beyond 8 variables; the reported two-minute solver timeout is the likely bottleneck and would need heuristic warm starts.","The claimed layer exchangeability is logical exchangeability under XOR, not a proof that CNOT wiring can be arbitrarily reordered; a direct simulation test would settle whether block-swapping changes the composed circuit's behavior.","The paper's own example includes translated boxes such as S2=[0110,1110], which do not contain the all-zero vertex; giving Algorithm 1 an explicit convention for translated boxes would let the method apply unchanged to functions not anchored at the origin."],"forward_implications":["If the reported numbers hold, small quantum oracles for functions up to 6 variables can be built with roughly half to one-fifth the CNOT gates of current ESOP and XAG flows, without clean ancillas during the core construction.","The parity set-cover formulation provides a formal feasibility guarantee, because every ESOP product term is itself a 0-dimensional parallelotope inside the search space.","The objective function can be switched between CNOT-count and T-count minimization, letting the same geometric decomposition target different hardware cost structures.","SSHR-H extends the approach to 7- and 8-variable functions, where the paper reports roughly 74% fewer CNOTs than XAG while ESOP no longer completes.","Because blocks are selected by parity rather than by sequential dependency, the composed circuit is logically layer-swappable, leaving room for later depth-oriented reordering."],"supporting_citations":[{"why":"Supplies the formal definition of a parallelotope as the Minkowski sum of line segments, the geometric object the whole synthesis method is built on.","marker":"[16]"},{"why":"Gives the ESOP-to-Toffoli cascade construction used as one of the two main baselines whose CNOT counts SSHR-I is compared against.","marker":"[7]"},{"why":"Provides the ESOP synthesis tool used in the experiments to generate the comparison circuits.","marker":"[29]"},{"why":"Introduces Xor-And-Inverter Graphs for quantum compilation, the second baseline method and the one SSHR-I reports the 81% reduction against.","marker":"[8]"},{"why":"Supplies the XAG-based low T-count oracle synthesis flow used as the experimental XAG baseline.","marker":"[30]"},{"why":"Provides the k-MCT gate decomposition costs used to translate circuit blocks into CNOT and T counts and to weight the ILP objective function.","marker":"[9]"}],"fun_headline_variants":["Parallelotope geometry cuts quantum CNOTs by up to 81%","Spatial structure in Boolean functions reduces CNOTs by 81%","Boxing Boolean on-sets lowers CNOT gate counts by 81%","Hypercube boxes slash CNOTs for small quantum circuits","Geometry of truth tables cuts CNOTs by 56-81%"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The method rests on the assumption that Algorithm 1 produces a valid oracle block for every selected parallelotope—flipping the target qubit exactly on those 2^m minterms and restoring every input qubit—but the paper gives no derivation that the CNOTs introduced in the first loop are undone, and translated parallelotopes such as S2=[0110,1110] are not covered by the stated Minkowski-sum definition.","fun_headline_variants_meta":{"raw":{"variants":["Parallelotope geometry cuts quantum CNOTs by up to 81%","Spatial structure in Boolean functions reduces CNOTs by 81%","Boxing Boolean on-sets lowers CNOT gate counts by 81%","Hypercube boxes slash CNOTs for small quantum circuits","Geometry of truth tables cuts CNOTs by 56-81%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000249,"raw_usage":{"total_tokens":1411,"prompt_tokens":794,"completion_tokens":617,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":538,"completion_tokens_details":{"reasoning_tokens":521}},"tokens_in":538,"tokens_out":617,"duration_ms":7175,"temperature":1.0,"reasoning_tokens":521,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:05:42.552283+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's Section IV-D example through Algorithm 1: take the selected translated parallelotope S2=[0110,1110], apply the block to every 4-bit input with the target qubit in |0>, and check whether the target equals the Boolean function's value on all 16 inputs and whether all input qubits return to their starting values. A single mismatch refutes the correctness premise. The same exhaustive check can be automated for all 3- and 4-variable functions by synthesizing each with SSHR-I and simulating the resulting circuit as a permutation on (n+1)-qubit basis states.","supporting_citations":[{"cited_title":"Determinants and the volumes of paral- lelotopes and zonotopes,","cited_arxiv_id":null,"evidence_quote":"Supplies the formal definition of a parallelotope as the Minkowski sum of line segments, the geometric object the whole synthesis method is built on."},{"cited_title":"Esop-based toffoli gate cascade generation,","cited_arxiv_id":null,"evidence_quote":"Gives the ESOP-to-Toffoli cascade construction used as one of the two main baselines whose CNOT counts SSHR-I is compared against."},{"cited_title":"Riener, “easy,” https://github.com/hriener/easy, 2024, version MIT-1- ov-file","cited_arxiv_id":null,"evidence_quote":"Provides the ESOP synthesis tool used in the experiments to generate the comparison circuits."},{"cited_title":"Xor-and-inverter graphs for quantum compilation,","cited_arxiv_id":null,"evidence_quote":"Introduces Xor-And-Inverter Graphs for quantum compilation, the second baseline method and the one SSHR-I reports the 81% reduction against."},{"cited_title":"The role of multiplicative complexity in compiling low t-count oracle circuits,","cited_arxiv_id":null,"evidence_quote":"Supplies the XAG-based low T-count oracle synthesis flow used as the experimental XAG baseline."},{"cited_title":"XOR-AND-XOR logic forms for autosymmetric functions and applica- tions to quantum computing,","cited_arxiv_id":null,"evidence_quote":"Provides the k-MCT gate decomposition costs used to translate circuit blocks into CNOT and T counts and to weight the ILP objective function."}],"review_version":1}