{"id":"233e20f2-018f-4140-9551-7e60b51a1282","arxiv_id":"2509.08276","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"FeynmanDD maps Feynman path integral sums onto classical decision diagrams, so quantum circuit amplitudes, probabilities, and equivalence checks become BDD counting tasks that run very fast on structured circuits.","lead":"FeynmanDD is a new classical algorithm that rewrites a quantum circuit as a sum of powers and then as a binary decision diagram, turning amplitude computation and sampling into counting problems. In benchmarks it runs much faster and uses far less memory than existing decision-diagram simulators on several circuit families, and it also performs exact equivalence checking.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Linear-network complexity is deferred, so the headline speedups rest on an unproven BDD-size bound; a scaling test would settle it.","rationale":"The reader's weakest assumption—that the linear-network complexity analysis is deferred and that BDD size under the fixed qubit order is not formally guaranteed—is exactly the load-bearing point. The paper's own text (Section 7.3 and the Introduction) admits the formal characterization is future work. The experimental results, while impressive, are limited to n<=40 for the constructed family and n=25 for the supremacy-style circuits, so they do not establish scaling behavior. My proposed test directly probes whether the BDD size stays polynomial for the family the authors intend to claim as a provable advantage. If it does, the concern is resolved; if not, the central performance claims are fragile. I see no internal inconsistency in the SOP framework or the counting reduction; the gap is purely the missing size bound and the associated construction cost. Therefore the verdict remains CONDITIONAL, unchanged from the reader's assessment.","tokens_in":21328,"tokens_out":7315,"duration_ms":86307,"concrete_test":"Run FeynmanDD on the linear-network family of Eq. (2) for n = 40, 80, 160, 320 with fixed k=7 (or k=ceil(log n)), using the qubit order, and record MTBDD node count and total runtime. If B(f) and runtime grow polynomially in n, the deferred complexity claim is supported; if they grow exponentially, the claimed advantage for this family fails. As a secondary check, re-run the cz/5x5_10 amplitude benchmark with gate-order and tensor-order variable orderings; if runtime or BDD size changes by orders of magnitude, the reported speedup is ordering-sensitive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central efficiency claim—amplitude simulation runs in time linear in B(f), yielding extreme speedups on Google supremacy and linear-network circuits—rests on the unproven premise that B(f) stays polynomially small under the fixed qubit order for these families. Section 5 explicitly states variable ordering 'significantly impacts the BDD size' and that the tensor-contraction bound is 'very loose' for linear-network circuits. Section 7.3 introduces the linear-network family and says 'A more comprehensive analysis of this circuit family will be presented in subsequent work'; the Introduction likewise defers 'a characterization of the complexity of the FeynmanDD method.' Without that characterization, the 0.05 s vs timeout for cz/5x5_10 (Table 2) and the linear-network results (Table 6) are unexplained empirical observations: they could reflect genuine circuit structure, or they could be artifacts of the fixed qubit order that vanish on neighboring families or orderings. Additionally, Section 5's binary synthesis method is justified only by 'numerical simulations suggest'; no bound is given for MTBDD construction time relative to final BDD size, so the 'linear in B(f)' statement in Section 6.1 covers counting, not necessarily the full simulation pipeline.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FeynmanDD, a decision-diagram method for exact simulation and equivalence checking of quantum circuits over discrete gate sets. The method derives a sum-of-powers (SOP) representation of an amplitude or trace, converts the associated multilinear polynomial over Z_r into an MTBDD, and evaluates the amplitude by counting how many assignments map to each residue. Sections 3--4 give the SOP calculus for gate sets Z, T, and the Google-supremacy set G, including contraction and substitution operations. Section 5 describes a binary synthesis construction and variable-ordering heuristics. Section 6 gives formulas for amplitudes, probabilities, sampling, and equivalence checking via tr(U_C0^dag U_C1). Section 7 reports speedups over DDSIM, SliQSim, and WCFLOBDD on Google-supremacy, GHZ, BV, and especially 'linear-network' circuits; Section 8 compares equivalence checking with MQT-QCEC. The paper states that amplitude simulation is linear in B(f), where B(f) is the MTBDD size, but explicitly defers a formal complexity characterization of the linear-network family to future work.","tokens_in":21658,"tokens_out":6144,"duration_ms":75473,"significance":"If the claimed runtime bounds held with polynomial B(f) for the tested families, FeynmanDD would be a genuinely interesting bridge between BDD counting and Feynman-path simulation: it would enable exact single-amplitude computation, exact sampling, and exact equivalence checking with very small memory on structured circuits. The SOP framework is flexible, the counting formulation is exact, and the paper gives clear Theorems 1--2 and explicit formulas in Section 6. These are strengths. However, the submitted manuscript does not prove that B(f) stays small for the headline families, and the only justification for the MTBDD-building phase is empirical ('numerical simulations suggest'). The significance is therefore conditional on the deferred complexity analysis and on the reproducibility of the experimental results. No machine-checked proofs or released code accompany the paper, so the empirical claims are not independently verifiable at this stage.","major_comments":[{"comment":"The claim 'our simulation algorithm achieves runtime linear in B(f)' is only established for the counting phase. The BDD construction, which Section 5 calls 'the most computationally expensive step', is justified by 'Numerical simulations suggest' for the binary synthesis method, with no bound on its time relative to B(f); variable ordering can change B(f) exponentially. Therefore the full pipeline's runtime is not shown to be linear in B(f). Please either provide a construction-time bound or restrict the claim to the counting stage and report construction versus counting times in the experiments.","section":"§6.1 and §5"},{"comment":"The formal complexity of the method, and specifically of the linear-network family, is explicitly deferred: §1 says 'In a follow-up work, we will provide a characterization of the complexity', and §7.3 says 'A more comprehensive analysis of this circuit family will be presented in subsequent work.' Yet the linear-network circuits are 'purposefully' designed so that the number of forward signals is bounded by k+1. As submitted there is no theorem showing B(f) is polynomial for this family, so the extreme speedups in Table 6 are unexplained empirically; they could depend on the fixed qubit ordering. A scaling experiment in n and k with several orderings, or an actual theorem, is needed to support the claimed advantage over tensor-network and Clifford methods.","section":"§1, §7.3"},{"comment":"The experimental protocol fixes the 'qubit order' variable ordering for all circuits. Section 5 states that variable ordering 'may significantly impact the final size' and exhibits an ordering that makes the Hadamard-chain BDD blow up exponentially. For the Google-supremacy results (Tables 2--3), no evidence is given that the speedups are robust with respect to variable ordering or circuit variation (e.g., neighboring grid sizes). Without this, the 0.01--0.2 s amplitude times could be artifacts of a single favorable ordering rather than a property of the circuits. Report results for at least two orderings, or provide a size analysis of B(f) for these circuits.","section":"§5 and §7"},{"comment":"No code, data, or detailed benchmark-generation scripts are released. Given that the performance claims rely entirely on the experimental tables, the absence of artifacts prevents independent reproduction. I ask the authors to release the FeynmanDD implementation, the exact circuit instances (including random seeds for GRCS and linear-network circuits), and the scripts used for the DDSIM/SliQSim/WCFLOBDD comparisons.","section":"§7 (experimental setup)"}],"minor_comments":[{"comment":"The symbol m is used for the number of circuit gates earlier and for the bit length of the counting result in Section 6.1. Use different symbols (e.g., M for gate count, ℓ for bit length) to avoid confusion.","section":"§6.1"},{"comment":"The counting-identity paragraph contains a garbled phrase: 'when a variable x appears exactly twice in the terms having form r/2 x x0 and r/2 x x1'. Please rewrite the condition precisely (which monomials, which coefficients, and what simplification follows).","section":"§5"},{"comment":"Typographical errors: 'meausred' for 'measured' in the captions of Tables 4 and 5. Also, the notation in Table 3's caption '(x)' should be explained more clearly in the table text.","section":"Tables 4--5"},{"comment":"The equivalence criterion is stated as 'equivalent (up to a global phase)' when the trace has unit norm. Please spell out the argument briefly (all eigenvalues of a unitary are on the unit circle, so modulus 2^n forces them to coincide), and clarify the distinction between 'equal as unitaries' and 'equal up to a global phase'.","section":"§6.2"}],"recommendation":"major_revision","confidential_remarks":"This is a promising systems-style contribution, but the current text overstates what is proved: the 'linear in B(f)' claim applies only to counting, and the advertised 'provable efficiency advantages over tensor networks' are deferred to a follow-up. The purpose-built linear-network benchmark needs a scaling study or a theorem before the main performance claims can be taken as robust. If the authors can supply the missing runtime breakdown, an ordering-robustness experiment, and release code/data, I would be willing to accept a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is a genuine new twist on an old idea: represent the Feynman path sum of a circuit as a multilinear polynomial over Z_r, encode that polynomial as a classical MTBDD, and use BDD counting to extract amplitudes. The SOP representation itself is known (Montanaro, Dawson et al.), and counting with BDDs is textbook, but the combination is new and, as far as I can tell, correctly executed. The extension to sampling via conditional probabilities and to equivalence checking via trace computation is natural and works in the benchmarks.\n\nWhat the paper does well: the writing is clear, the math is straightforward, and the experimental section is broad. It reports dramatic speedups on Google supremacy circuits (0.04 s vs timeout on 25 qubits for amplitude) and on their own linear-network family. It also reports failures on large RevLib circuits, which is a good sign—they are not hiding the rough edges.\n\nThe soft spots are real but not fatal. First, the headline claim \"runtime linear in B(f)\" is only about the counting step. The cost of building the MTBDD is justified by \"numerical simulations suggest,\" with no bound on construction time relative to final BDD size. Second, the linear-network circuits are purpose-built to keep the BDD small, and the authors admit the tensor-contraction bound is very loose for those circuits. They explicitly defer a complexity characterization to a follow-up, so the central efficiency claim rests on an unproven premise. Third, all experiments use a fixed qubit order; BDD size is notoriously order-sensitive. Fourth, no code or data is released, so the numbers are not independently checkable.\n\nNone of this undermines the math as presented. The paper is honest about the missing pieces. But the gap between the empirical speedups and the theoretical understanding is large enough that I would not yet cite it as proof that FeynmanDD beats tensor networks or Schrödinger methods in general. It is a promising method with a solid core, waiting for the follow-up complexity analysis and a released implementation.\n\nWho is it for: anyone working on classical simulation of quantum circuits, decision diagrams, or quantum verification. It deserves a serious referee, not a desk reject. I would send it to peer review, and in the report ask for code/data and at least a partial complexity bound for the construction step, plus a sensitivity analysis over variable orderings.\n\nRegards.","headline":"A real new combination of Feynman path sums and classical BDD counting, with impressive but not yet fully explained speedups; the deferred complexity analysis and missing code keep it conditional.","tokens_in":22047,"tokens_out":3079,"would_cite":true,"duration_ms":35535,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"FeynmanDD computes quantum amplitudes by counting solutions on a decision diagram.","keywords":["FeynmanDD","binary decision diagrams","multi-terminal BDD","sum-of-powers representation","quantum circuit simulation","amplitude computation","equivalence checking","variable ordering"],"falsifier":"Instrument the implementation to record the MTBDD node count B(f) and runtime for amplitudes on the published benchmark circuits; if runtime is not proportional to B(f) up to the counting bit length, the claimed linear-in-B(f) guarantee is not what the implementation delivers. Alternatively, run it on random layers of CCZ gates and check whether the diagram size and runtime grow exponentially with qubit count despite trying each ordering heuristic the paper suggests; that would demarcate the method's practical boundary.","tokens_in":21309,"feed_emoji":"🧮","tokens_out":7842,"duration_ms":91632,"temperature":0.7,"pith_summary":"FeynmanDD is a new classical simulation method that turns quantum circuit analysis into a counting problem. The paper shows that, for circuits built from discrete gate sets, the Feynman-path-integral expression for an amplitude can be written as a sum of powers of a root of unity, with the exponent a low-degree multilinear polynomial. That polynomial is compiled into a multi-terminal binary decision diagram, and the amplitude is recovered by counting how many assignments send the polynomial to each residue. The paper proves the evaluation runs in time linear in the diagram size, and reports that for structured families such as GHZ, BV, linear-network, and supremacy-benchmark circuits, the diagrams stay small enough to beat standard simulators by orders of magnitude. A reader should care because this opens a new route to classically simulating and verifying quantum circuits that exploits repetition in the circuit's algebraic form rather than in its state vector.","feed_headline":"Decision diagrams turn amplitude simulation into counting","feed_subtitle":"FeynmanDD maps circuits to sum-of-powers forms and beats standard simulators on large structured benchmarks.","key_machinery":"The load-bearing object is the sum-of-powers form: a circuit gate is encoded as a power ω^{ℓ(x)} of a root of unity, so the whole circuit becomes a uniformly normalized sum over internal wire values, with the exponent a multilinear polynomial. The companion machinery is the multi-terminal binary decision diagram, a rooted directed acyclic graph whose leaves hold residue values, built for the exponent polynomial. Once the MTBDD exists, evaluation of the sum-of-powers form is a residue-counting problem: count assignments yielding each residue and combine with the roots of unity, in time linear in the diagram size. Two ordering choices carry the method: the order in which polynomial terms are a","core_discovery":"The central claim is that one can map a quantum circuit to a sum-of-powers representation of the target amplitude—an expression 1/√R Σ_y ω^{f(x,y)} where ω is a root of unity and f is a multilinear polynomial of degree at most three—and then treat the circuit-analysis task as a counting problem over f. Given an MTBDD for f with B(f) nodes, FeynmanDD computes any amplitude exactly in O(mB(f)) time, where m is the counting bit length; the same machinery handles acceptance probabilities and, by forming the trace of U†V, equivalence checking. The paper constructs sum-of-powers forms for three universal gate sets—the H/Z/CZ/CCZ set, the Clifford+T set, and the supremacy-benchmark gate set—and pro","pith_inferences":["Editorial inference: if polynomially sized sum-of-powers BDDs exist for a broad class of circuits, the method effectively characterizes a new classical-simulability region defined by low XOR-treewidth of the path-sum polynomial, rather than by stabilizer rank or tensor-network cutwidth.","Editorial inference: the variable-ordering bottleneck suggests a direct test: run FeynmanDD on random constant-depth IQP circuits with many CCZ gates under sifting and tensor-order heuristics; if diagrams blow up polynomially with qubit count, the practical reach extends well beyond the tested families.","Editorial inference: the trace-based equivalence check could be combined with circuit optimizers to validate whole compiled programs exactly; a concrete extension is to benchmark on large Clifford+T circuits produced by rotation synthesis, where the paper only sketches the expected BDD behavior."],"forward_implications":["Single-amplitude simulation becomes as easy as the diagram is small: any circuit whose sum-of-powers polynomial admits a polynomially sized MTBDD is simulable in polynomial time, independent of entanglement structure.","Sampling by sequential conditional probabilities is available on the same diagram, with a quadratic cost in diagram size, so structured circuits can be sampled without storing the full state.","Equivalence checking can be done exactly via the trace criterion, using the same counting engine, and the paper reports fast checks on large GHZ and BV circuits.","Adding a new gate set requires only a configuration-file entry for the gate's power form, not a new data structure, so the method extends to other discrete universal sets.","The existence of a circuit family where FeynmanDD is efficient while tensor-network and Clifford methods are provably costly suggests BDD counting captures structure those methods miss."],"supporting_citations":[{"why":"defines multi-terminal binary decision diagrams (ADDs), the data structure FeynmanDD uses to represent residue-valued functions.","marker":"[9]"},{"why":"supplies the counting algorithm whose cost is linear in BDD size and the Figure-23 linear-network construction used to build a hard-for-tensor-network test family.","marker":"[31]"},{"why":"provides tensor contraction and substitution operations that the sum-of-powers framework adapts to manipulate circuit amplitudes.","marker":"[36]"},{"why":"introduces the quantum-circuits-and-low-degree-polynomials framework and the degree-3 polynomial family used in the linear-network experiments.","marker":"[39]"},{"why":"supplies the sifting dynamic-variable-ordering heuristic that keeps MTBDD sizes small in several experiments.","marker":"[45]"},{"why":"is the prior bit-slicing BDD simulator used as the main BDD-based baseline in the simulation benchmarks.","marker":"[50]"},{"why":"documents BDD counting complexity and the NP-hardness of variable ordering, grounding the complexity statements about B(f).","marker":"[58]"},{"why":"provides the supremacy-benchmark circuit families and gate sets used in the large-scale simulation experiments.","marker":"[8]"}],"fun_headline_variants":["Quantum amplitudes via counting on decision diagrams","Simulate circuits by counting, not summing","FeynmanDD: Quantum analysis becomes a counting task","Decision diagrams make amplitude simulation a count","Turn quantum circuit analysis into a counting problem"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The method's speed collapses if the circuit's exponent polynomial cannot be squeezed into a small decision diagram; the paper's experiments depend on variable-ordering heuristics to keep the diagram small, and it defers a formal characterization of when that is possible.","fun_headline_variants_meta":{"raw":{"variants":["Quantum amplitudes via counting on decision diagrams","Simulate circuits by counting, not summing","FeynmanDD: Quantum analysis becomes a counting task","Decision diagrams make amplitude simulation a count","Turn quantum circuit analysis into a counting problem"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000166,"raw_usage":{"total_tokens":1040,"prompt_tokens":644,"completion_tokens":396,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":388,"completion_tokens_details":{"reasoning_tokens":329}},"tokens_in":388,"tokens_out":396,"duration_ms":5625,"temperature":1.0,"reasoning_tokens":329,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T20:52:06.721243+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument the implementation to record the MTBDD node count B(f) and runtime for amplitudes on the published benchmark circuits; if runtime is not proportional to B(f) up to the counting bit length, the claimed linear-in-B(f) guarantee is not what the implementation delivers. Alternatively, run it on random layers of CCZ gates and check whether the diagram size and runtime grow exponentially with qubit count despite trying each ordering heuristic the paper suggests; that would demarcate the method's practical boundary.","supporting_citations":[],"review_version":1}