{"id":"d33f657d-8f1d-4767-8a1f-b43c8f6895d2","arxiv_id":"2412.17309","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A QAOA simulation study of graph similarity through edge overlap finds that a compact encoding with many infeasible states causes QAOA to underperform random sampling as graphs grow.","lead":"This 2018 honours dissertation describes Qolab, a C simulator for the Quantum Approximate Optimisation Algorithm, and applies a compact permutation encoding to graph similarity via edge overlap. A generalist would read it for an empirical map of QAOA costs and optimizer behavior, though the paper's own larger-scale results show QAOA falling below random sampling.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Key evidence for the Section 1.5 claim is uninterpretable: the 'Quantum / Classical Expectation' metric is defined with contradictory sign conventions, and Section 4.4.1 interprets the negative values as failure, directly contradicting the stated hypothesis.","rationale":"The reader's verdict is REJECT, and my analysis supports that verdict without moving it. The reader's weakest_assumption concerns the infeasible tail and the classical optimizer's ability to concentrate probability on feasible permutations. That is a real mechanism, but the more fundamental and immediate problem is that the paper's primary evidence for the Section 1.5 hypothesis is internally contradictory. The Section 4.1 definition of the Classical Comparison metric says both that a negative value indicates QAOA is better and that higher is better, which cannot both be true. The plots consistently show negative values on larger graphs, and Section 4.4.1 explicitly treats those negative values as a deficiency. Under the natural reading, this is a direct refutation of the central claim for all optimizers tested; under the literal definition, the same plots would support the claim. Because the paper never resolves this ambiguity, the reported empirical evidence cannot be used to evaluate the hypothesis. A re-analysis with an explicit sign convention and a direct fixed-budget sampling comparison would settle the matter. This does not require new experiments: the raw data and plotting code are linked in Appendix F. My agreement with the reader is partial because I identify the metric contradiction as the decisive flaw, while the tail issue is important but secondary. The conclusion remains REJECT, so the reader's verdict is unchanged.","tokens_in":37543,"tokens_out":5828,"duration_ms":56299,"concrete_test":"Recompute the QAOA-versus-random comparison from the archived raw data (bitbucket.org/qaoa_uwa/results) with an explicit sign convention: δ = (E_QAOA - E_random)/E_random, with δ > 0 meaning QAOA beats random. Report δ with error bars per graph size, optimizer, and p. Separately, for a fixed sample budget (e.g., 1,000 measurements from the final QAOA state and from uniform sampling), count the number of sampled permutations that are feasible and match or exceed the known optimal edge overlap. If δ ≤ 0 for V ≥ 8 across all optimizers, or if the fixed-budget success count does not exceed random sampling, the Section 1.5 claim is refuted by the paper's own data.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Section 1.5) is that, for a fixed number of samples, QAOA produces more correct maximal-edge-overlap solutions than naive random sampling. The decisive reported evidence is the 'Quantum / Classical Expectation' metric. Section 4.1 defines it as: 'A negative value indicates better likelihood of a better solution from the QAOA. Higher is better.' These two clauses cannot both hold: if negative means QAOA is better, then higher (less negative) is not better; if higher is better, then negative is worse. The plots in Figures 4.2-4.6 show negative values for larger graphs, and Section 4.4.1 states that 'for all algorithms tested the effect of infeasible solutions results in a lower expectation value versus classical sampling in the larger test cases indicating either more optimisation time is required or a more nuanced problem encoding.' That sentence treats lower-than-random expectation as a failure. Thus the paper's own interpretation of the same metric refutes the Section 1.5 hypothesis, while the formal definition would, if taken literally, claim the opposite. The ambiguity is not cosmetic: it decides whether the central claim is supported or refuted. The tail-mapping issue (Section 3.2.4) is a plausible mechanism, but the immediate load-bearing problem is that the paper does not state, unambiguously, whether its headline comparison is positive or negative for QAOA on the larger instances.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an honours-thesis-style study applying the Quantum Approximate Optimisation Algorithm (QAOA) to graph similarity, specifically to the problem of maximal edge overlap between two directed or undirected unweighted graphs under vertex relabelling. The authors introduce Qolab, a C-based simulation package for QAOA, and propose a compact encoding of permutation problems that uses q = ceil(log2(V!)) qubits rather than a unary V^2 encoding. The stated unifying hypothesis (Section 1.5) is that, for a fixed number of samples, QAOA will produce more correct maximal-edge-overlap solutions than naive random sampling. The paper reports experiments with eight classical optimisers at six decomposition levels, on graphs generated by Erdős–Rényi models with several deformation types, and concludes that the QAOA suffers from infeasible solutions in larger test cases.","tokens_in":37807,"tokens_out":4097,"duration_ms":42594,"significance":"If the central hypothesis were supported, the paper would offer two useful contributions: a general-purpose QAOA simulation tool with a reproducible benchmark suite, and a memory-efficient encoding for permutation-based optimisation problems. The manuscript does make some genuine assets explicit: the source code and result data are promised at public repositories, the study covers a broad sweep of classical optimisers (eight methods at six values of p), and the correctness of the QAOA expectation is checked against brute-force optimal values in Section 4.1. However, the paper's own reported results contradict the unifying hypothesis for larger graphs, and the primary comparison metric is defined with contradictory sign conventions. The contribution is therefore not established by the evidence presented, and the significance of the claimed result is currently undermined.","major_comments":[{"comment":"The definition of the 'Quantum / Classical Expectation' metric contains two mutually exclusive clauses: 'A negative value indicates better likelihood of a better solution from the QAOA. Higher is better.' These cannot both hold. If negative means QAOA is better, then higher (less negative) is not better; if higher is better, then negative is worse. The plots in Figures 4.2–4.6 show negative values for larger graphs, and Section 4.4.1 explicitly interprets those negative values as failure ('a lower expectation value versus classical sampling'). This contradiction is load-bearing because the metric is the main evidence for or against the Section 1.5 hypothesis. The paper must state an unambiguous sign convention and then re-interpret the figures consistently.","section":"Section 4.1, 'Classical Comparison' metric"},{"comment":"Section 4.4.1 states: 'for all algorithms tested the effect of infeasible solutions results in a lower expectation value versus classical sampling in the larger test cases.' This is a direct admission that the central hypothesis of Section 1.5 (QAOA outperforms random sampling) is not supported on larger graphs for any of the eight optimisers tested. If the 'negative is better' reading of the metric is instead adopted, then the same sentence would be inconsistent with the reported sign of the values. Either way, the paper does not present an unambiguous positive result, and the hypothesis as stated is not established. This is not a presentation issue but a fundamental problem with the claimed conclusion.","section":"Section 4.4.1 and Section 1.5"},{"comment":"The encoding maps all 2^q − V! infeasible bit-strings to cost zero, and the QAOA starts from a uniform superposition over all 2^q states. As the paper itself notes and as Table B.1 shows, the tail fraction can be substantial (e.g., for V=8, 2^q/V! ≈ 1.63). The paper attributes the degraded expectation values on larger graphs to the 'effect of infeasible solutions,' which is a plausible mechanism, but no evidence is provided that the classical optimiser can overcome this tail within the evaluation budget. Since the Section 1.5 hypothesis depends precisely on the QAOA concentrating probability on feasible permutations, the paper needs either a dedicated analysis of the tail's influence or a revised hypothesis that accounts for the reported negative results.","section":"Section 3.2.4, tail mapping and Section 4.4.1"},{"comment":"The claims of 'O(V^3) operations' for the state-preparation encoding and 'O(n^2 log n) operations and O(n log n) qubits' for the edge-overlap circuit are asserted by citation to [1] and [18] rather than derived in this manuscript. Because the claimed 'significant quantum memory savings at the cost of additional operations' is one of the paper's two headline contributions, the resource trade-off should be either derived or stated with the precise conditions under which the cited bounds apply. As written, the reader cannot verify the resource count without going to the cited works, and the paper's own Appendix E, which is used to justify the Chebyshev truncation for U_B, is informal.","section":"Sections 3.2.2 and 3.2.4, resource claims"}],"minor_comments":[{"comment":"The figures do not include error bars, confidence intervals, or any measure of trial-to-trial variance; given that results are aggregated over different deformation types and multiple random instances, the absence of dispersion information makes it difficult to assess the reliability of the reported averages.","section":"Figures 4.2–4.6 and Appendix F"},{"comment":"The text in Section 4.5 refers to 'Figure 4.5' for the undirected Subplex results, but the displayed figure caption is 'Figure 4.6: Final performance for the Subplex algorithm (undirected graphs)'. Similar numbering inconsistencies appear across the results chapter and should be corrected.","section":"Section 4.5 and figures"},{"comment":"The sentence 'This requires the generation of all q! bit-strings' is confusing: the simulation enumerates all 2^q computational basis states, not q! bit-strings. The subsequent sentence about reducing 'generations of the q! permutations' to the 2^{ceil(log2(v!))} state-space needs to be clarified.","section":"Section 3.4.1"},{"comment":"The Chebyshev expansion is written with 'inf' instead of an infinity symbol, and the summation index n is not defined in the displayed formula; the truncation criterion in Eq. (3.7.8) should also state explicitly that n runs from 1 to the truncation order.","section":"Equation (3.7.3)"},{"comment":"The proof of λ_{min,max} = ±q is informal: it uses a real-symmetric-matrix argument with a typo ('R3' instead of R^n), invokes Perron–Frobenius without stating the non-negativity conditions precisely, and the final observation 'for a negative v, λ = −q' does not constitute a proof for all vectors. The paper also contains typos such as 'Schr¨ oidgner' in Section 1.4.1 and 'na ¨ ıve' elsewhere.","section":"Appendix E"}],"recommendation":"reject","confidential_remarks":"The arXiv manuscript appears to be an unrevised honours dissertation. The central hypothesis is contradicted by the paper's own results, and the primary metric is defined with contradictory sign conventions; these are load-bearing issues that cannot be resolved by minor editing. The negative result on larger graphs is not framed as a negative result, but rather as a failure condition within the original hypothesis, leaving no coherent positive claim. The reviewer also notes that the paper's promised code and data would be valuable if made available, but they do not compensate for the central evidential contradiction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a 2018 honours thesis posted to arXiv in 2024. It applies QAOA to graph similarity via edge overlap, uses a compact permutation encoding (credited to Chiew et al.), and presents Qolab, a distributed simulator. The advertised claim is that QAOA beats random sampling for a fixed number of samples. The paper's own results on larger graphs contradict that, and the metric that would decide the question is defined with contradictory sign conventions.\n\nWhat is genuinely useful: the encoding itself—ceil(log2(V!)) qubits with the tail mapped to zero—is a sensible way to cut qubit count for permutation problems, and the authors are upfront about the infeasible-solution cost. Qolab looks real: state-vector distribution, Lehmer-code permutation generation, Chebyshev-based matrix exponential, and NLopt integration. The optimizer comparison across eight methods and six depths is thorough for a student project. Correctness is checked against brute force, and test cases are generated by graph deformations, which is more careful than many QAOA papers.\n\nWhere it falls down: the central hypothesis is not supported. Section 4.4.1 explicitly says that on larger graphs, all optimizers yield a lower expectation value than classical random sampling. That is the opposite of what the abstract promises. Worse, the \"Quantum/Classical Expectation\" metric in Section 4.1 says \"A negative value indicates better likelihood of a better solution from the QAOA. Higher is better.\" Both clauses cannot be true. The plots show negative values on larger graphs, and the text treats them as failure. This ambiguity decides whether the main result is positive or negative. Additionally, the so-called novel encoding is credited to Chiew et al., so the contribution is the application, not the encoding itself. Resource counts are cited rather than derived, and Appendix E's spectral proof is informal, though the result is correct.\n\nIn proportion: the math and data are transparent enough to see what happened, and the writing is clear, but the paper overclaims. A reader cannot tell from the metric definition which direction the evidence points. If the authors reframed the work as an honest negative result about QAOA with tail-heavy encodings, it could be useful. As it stands, the abstract and conclusion are not supported by the data.\n\nRecommendation: I would not publish this as is, but I would send it to peer review if the authors are willing to fix the metric definition and reframe the contribution. The simulator and the empirical optimizer data deserve referee attention, and the negative result, once stated clearly, is worth reporting.","headline":"A careful QAOA-for-graph-similarity study whose own larger-graph results refute its central claim, made worse by a metric defined with contradictory sign conventions.","tokens_in":38353,"tokens_out":3182,"would_cite":false,"duration_ms":31411,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C60","68Q12","81P68"],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"A compact qubit encoding lets QAOA beat random sampling on small graph-similarity problems, but the zero-cost infeasible tail erodes the advantage on larger instances.","keywords":["quantum approximate optimisation algorithm","graph similarity","edge overlap","permutation encoding","combinatorial optimisation","quantum simulation","infeasible solutions","parameter optimisation"],"falsifier":"Run the exact simulation on randomly deformed graph pairs of increasing vertex count with a fixed evaluation budget, and compare the QAOA expectation value with the expectation of uniform random sampling under the same cost function. The paper's Section 4.4.1 already reports a negative quantum-versus-classical ratio on the larger directed test cases; any negative ratio at a given graph size falsifies the unifying hypothesis for that size, and a consistently positive ratio across the tested range would confirm it.","tokens_in":37272,"feed_emoji":"⚛️","tokens_out":14307,"duration_ms":127830,"temperature":0.7,"pith_summary":"This paper tries to establish the Quantum Approximate Optimisation Algorithm (QAOA) as a practical tool for whole-graph similarity, measured by maximal edge overlap between two unlabelled directed or undirected graphs. Its route is a compact permutation encoding that uses $\\lceil\\log_2(V!)\\rceil$ qubits instead of $V^2$, plus a custom simulator, Qolab, that tests all components of the algorithm from desktop to cluster scale. The unifying hypothesis is that, for a fixed number of samples, QAOA produces more correct solutions than random sampling. The data support that hypothesis on small graphs and on undirected graphs, while showing the advantage disappears on larger directed instances, and the paper attributes that pattern to the large tail of infeasible zero-cost bit-strings. A working version of this encoding would give near-term quantum computers a memory-efficient route into permutation problems; the measured degradation points instead to where the next encoding or optimiser improvements must go.","feed_headline":"QAOA beats random sampling on small graph puzzles","feed_subtitle":"The qubit-saving trick works on small graphs, then the zero-cost impostors take over.","key_machinery":"The load-bearing mechanism is the permutation-index encoding: rather than labelling each candidate vertex mapping with $V^2$ unary qubits, the paper orders all $V!$ permutations and stores only the index of a permutation in $q=\\lceil\\log_2(V!)\\rceil$ qubits. The diagonal cost Hamiltonian $\\hat C$ gives each index its edge-overlap value, and the unused tail of $2^q-V!$ bit-strings is set to zero. The mixing Hamiltonian $\\hat B=\\sum_i\\sigma^x_i$ makes the search walk over all bit-strings, and $\\hat U_B$ is applied through a polynomial expansion of the matrix exponential rather than a full dense exponentiation. Everything that matters for the result follows from that tail: it is what saves memory, and it is what makes the cost landscape hard for the classical optimiser.","core_discovery":"The paper's central claim is that graph similarity by maximal edge overlap can be mapped to QAOA with only $q=\\lceil\\log_2(V!)\\rceil$ qubits, and that on small instances the algorithm measurably improves over naive random sampling for a fixed sample count. The unused bit-strings are assigned zero cost, so the algorithm starts from a uniform superposition in which most amplitude sits on infeasible solutions; nevertheless, the reported experiments show QAOA escaping that local minimum and improving with Trotter depth, with undirected graphs performing better than directed ones. At larger graph sizes the improvement reverses: the paper reports that the QAOA expectation value falls below random sampling for all eight classical optimisers tested, which it treats as evidence that the feasible/infeasible mix makes the optimisation problem harder, not as a final refutation of the approach.","pith_inferences":["The comparison baseline is random sampling only; comparing QAOA on this encoding against classical heuristic graph-matching would clarify whether the small-instance advantage is real or an artefact of a weak baseline.","The paper's alternate cost function that penalises infeasible states made things worse, which suggests a subtle nonlinearity: a soft, tuned penalty or a separate feasible-mixing operator might outperform both tested extremes.","The tail proportion oscillates with $V$ (for example, $2^q/V!$ is 0.65 at $V=8$ and 0.15 at $V=10$ in the paper's Table B.1), so picking graph sizes whose factorial sits close to a power of two could give QAOA an easier landscape and a cleaner test of the algorithm.","The exact state-vector simulation ceiling of 22 qubits is a memory bound, so adapting the encoding to a restricted mixer or approximate simulation scheme would show whether the trend continues or reverses at larger sizes."],"forward_implications":["Small instances and undirected pairs establish a baseline where QAOA with this encoding is a valid laboratory for comparing mixers, cost Hamiltonians, and classical optimisers.","Increased Trotter depth $p$ buys better solutions at roughly double the evaluation count, so any real device must budget quantum evaluations against solution quality.","The zero-cost tail creates a landscape in which all infeasible strings look optimal; any future encoding that shrinks or penalises that tail should directly improve the measured quantum-versus-classical ratio.","Because the simulator is problem-agnostic apart from the cost function, the same package can be used to validate QAOA on other NP-optimisation problems without building a new simulation stack."],"supporting_citations":[{"why":"Defines the QAOA framework that the paper applies and extends.","marker":"[31]"},{"why":"Provides the alternative permutation-problem QAOA mappings that motivate the compact encoding.","marker":"[38]"},{"why":"Supplies the walk-mask restricted QAOA variant that Qolab supports alongside the canonical mixer.","marker":"[61]"},{"why":"Shows how to encode edge-overlap values on $\\mathcal{O}(n\\log n)$ qubits, the basis of the paper's compact permutation encoding.","marker":"[18]"},{"why":"Provides the efficient ancilla-free diagonal-unitary construction used to realise $\\hat U_C$.","marker":"[87]"},{"why":"Supplies the classical optimisation methodology for hybrid quantum-classical algorithms that the eight optimisers are compared against.","marker":"[37]"},{"why":"Provides the continuous-time-quantum-walk simulation techniques and polynomial expansion behind the $\\hat U_B$ implementation.","marker":"[49]"},{"why":"Supplies the method for preparing a superposition over $n$ elements with $O(n^3)$ operations, used in the permutation mapping.","marker":"[1]"}],"fun_headline_variants":["QAOA beats random on small graphs, fails on larger ones","Qubit-saving QAOA shines on small graphs, flips on big","QAOA graph similarity: small win, but zero-cost impostors","QAOA improves on small graphs, then random wins","Graph similarity QAOA: small gains, big reversal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The classical optimiser can concentrate enough probability on feasible permutations within its evaluation budget even though the search starts uniformly over a space in which nearly all bit-strings are infeasible zero-cost strings.","fun_headline_variants_meta":{"raw":{"variants":["QAOA beats random on small graphs, fails on larger ones","Qubit-saving QAOA shines on small graphs, flips on big","QAOA graph similarity: small win, but zero-cost impostors","QAOA improves on small graphs, then random wins","Graph similarity QAOA: small gains, big reversal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000241,"raw_usage":{"total_tokens":1543,"prompt_tokens":985,"completion_tokens":558,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":472}},"tokens_in":601,"tokens_out":558,"duration_ms":5081,"temperature":1.0,"reasoning_tokens":472,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:36:28.253011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the exact simulation on randomly deformed graph pairs of increasing vertex count with a fixed evaluation budget, and compare the QAOA expectation value with the expectation of uniform random sampling under the same cost function. The paper's Section 4.4.1 already reports a negative quantum-versus-classical ratio on the larger directed test cases; any negative ratio at a given graph size falsifies the unifying hypothesis for that size, and a consistently positive ratio across the tested range would confirm it.","supporting_citations":[{"cited_title":"Quantum Algorithms for Scientific Computing and Approxi- mate Optimization","cited_arxiv_id":null,"evidence_quote":"Provides the alternative permutation-problem QAOA mappings that motivate the compact encoding."},{"cited_title":"A quantum walk assisted approximate algorithm for bounded NP optimisation problems","cited_arxiv_id":"1804.08227","evidence_quote":"Supplies the walk-mask restricted QAOA variant that Qolab supports alongside the canonical mixer."},{"cited_title":"Efficient quantum circuits for diagonal unitaries with- out ancillas","cited_arxiv_id":null,"evidence_quote":"Provides the efficient ancilla-free diagonal-unitary construction used to realise $\\hat U_C$."},{"cited_title":"pyCTQW: A continuous-time quantum walk simulator on distributed memory computers","cited_arxiv_id":null,"evidence_quote":"Provides the continuous-time-quantum-walk simulation techniques and polynomial expansion behind the $\\hat U_B$ implementation."}],"review_version":1}