{"id":"0540d1dc-de94-42ad-b479-7104bae28113","arxiv_id":"1908.08862","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The paper derives QAOA parameters from the infinite regular tree limit using tensor networks, so quantum hardware is only needed to sample the final state.","lead":"This paper proposes a method to choose QAOA control parameters using only classical tensor-network simulations of an infinite tree graph, removing the per-instance quantum-classical training loop. If it works, QAOA would only need the quantum processor for the final sampling, reducing QPU overhead.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Numerical evidence is gathered in the regime where Eq. (9) cannot hold: N=10–20 with p up to 8, so the central transfer claim is not actually tested.","rationale":"The reader identifies the concentration/local-tree-limit transfer as the weakest assumption. My stress-test sharpens this: the experiments are run in the regime where the local-tree approximation provably fails, because the reverse causal cone is not a proper subgraph for the small N and large p used. This means the numerical support does not test the mechanism that the theory claims. However, this is a limitation in the evidence, not a demonstrated falsehood of the central idea. For random regular graphs with fixed p and N growing, the infinite-tree limit is plausibly correct, and the method could still work. The paper should therefore remain conditional: the core claim is not rejected, but the supporting numerics need to be redone in the asymptotic regime, ideally with variance statistics and stronger baselines. I do not see grounds to change the reader's CONDITIONAL verdict.","tokens_in":13326,"tokens_out":14844,"duration_ms":166983,"concrete_test":"Fix p=3 on random 3-regular graphs and use the locality of QAOA to compute, for each edge, the exact correlation from its p-neighborhood subgraph. Evaluate the mean residual energy at the tree-optimal parameters for N=50,100,200,400 and verify it converges to the infinite-tree value; then, at the same sizes, optimize the full per-edge objective with 100 random starts of Adam/BFGS and determine whether tree parameters achieve the same energy. If the tree value is not attained or the gap does not vanish as N grows, the transfer claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Eq. (9) defines the tree limit as the per-edge QAOA objective for instances that are large compared with the reverse causal cone: for each edge, the p-neighborhood is a tree and is a proper subgraph. For a random d-regular graph this requires N to grow faster than the causal-cone tree, which has ~2^{p+2} vertices for d=3. The paper's Max-Cut benchmarks use N=10–20 and p up to 8 (Sec. 3.1, Fig. 4); at p=8 the causal cone has 1022 vertices, far exceeding the entire instance, so every edge's p-neighborhood is the whole (cyclic) graph, not a tree. Thus Fig. 4 cannot validate the local-tree-limit mechanism; it tests an extrapolation that the paper's own 'large compared to the number of blocks' condition explicitly excludes. The same issue applies to the 2D spin-glass benchmark, where the square lattice is not locally tree-like at any size. If tree-QAOA only works because of an additional, unproven concentration/transfer property, the paper provides no data in the regime where that property is supposed to follow from Eq. (9); if it is intended to work when the causal cone covers the graph, that is a different claim requiring separate support. The strongest statement in the paper—'comparable or even better' than per-instance training—is therefore resting on experiments in exactly the regime where the central approximation is not valid.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes tree-QAOA, a classical method for determining QAOA parameters for a problem class without calling the QPU for parameter updates. The central idea is to compute the per-edge energy expectation value on an infinite regular tree of the relevant degree via tensor-network contraction (Eq. (9)), optimize the QAOA angles on this tree classically, and then reuse those angles for all finite instances of the same degree. The method is tested on Max-Cut on 3-regular graphs and on spin glasses on square grids, and the resulting residual energies are compared against per-instance training with L-BFGS-B and Adam. The authors also study robustness to gate errors and translate the tree-optimized QAOA angles into a quantum-annealing schedule that is compared with a linear ramp.","tokens_in":13628,"tokens_out":7360,"duration_ms":76326,"significance":"If the central claim is established, the paper addresses a significant practical bottleneck of QAOA on NISQ devices: eliminating the QPU calls used for the variational parameter-update loop. The reverse-causal-cone derivation leading to Eq. (9) is conceptually sound, and the tensor-network contraction on a tree is a valid and potentially scalable way to evaluate the infinite-tree objective, with an exponential-in-depth but polynomial-in-system-size cost. The concrete falsifiable prediction that classically computed tree parameters transfer to finite instances of the same degree is of broad interest. However, the numerical validation currently does not test this prediction in the regime where Eq. (9) is supposed to hold, so the central claim is not yet established.","major_comments":[{"comment":"The numerical experiments are performed in a regime that violates the paper's own condition for the tree limit. For p=8 the tree-QAOA circuit contains 2^{10}-2=1022 qubits, while the test instances have N=10-20, so the p-neighborhood of every edge is the entire cyclic graph rather than a proper tree subgraph. Consequently Fig. 4(a) and (b) cannot validate the local-tree-limit mechanism; they test an extrapolation that Eq. (9) explicitly excludes. The authors should either simulate instances with N much larger than 2^{p+2} in the valid regime or provide and validate a separate concentration/transfer argument that justifies the extrapolation.","section":"Sec. 3.1, Fig. 4, Eq. (9)"},{"comment":"The spin-glass benchmarks on square grids use a problem graph that is not locally tree-like at any scale, because the grid contains 4-cycles. Replacing the grid by a degree-4 tree therefore is not justified by Eq. (9). The observation that tree-QAOA still performs 'much better than random guessing' on the small grids is an empirical heuristic result, not evidence for the tree-limit mechanism. The paper should either clearly separate this as a robustness test of the heuristic or provide an alternative theoretical rationale for why the tree approximation applies to non-tree locally cyclic graphs.","section":"Sec. 3.2"},{"comment":"No error bars, variances, or confidence intervals are reported for the M=100 averages. Since the vanilla QAOA training is performed with a single random initialization per instance, the claim that 'tree-QAOA performs comparable or even better' than per-instance training is not statistically supported. Please report the standard error or the full distribution of residual energies, and state the number of random restarts used for the optimizers.","section":"Sec. 3.1, Figs. 4 and 5"},{"comment":"The annealing-schedule result is not fully supported as presented. The polynomial fit is described as degree 6 but the coefficients are not given, no error bars are shown for the averaged ground-state population, and the comparison is only made for 10-spin instances over a limited range of total annealing times. Moreover, the connection between optimal discrete QAOA angles and a continuous annealing schedule is heuristic and would need at least a specification of the fit and a broader numerical study to establish the claimed 'applicability beyond QAOA'.","section":"Sec. 5, Fig. 7"}],"minor_comments":[{"comment":"The phrase 'eliminate the classical outer learning loop' is overstated because the tree parameters are still found by classical optimization (L-BFGS-B) in Sec. 3.1. Please clarify that the QPU is removed from the update loop, not that all optimization is eliminated.","section":"Abstract, Sec. 2.3"},{"comment":"The claim that the optimization landscape for the infinite-size instance 'is much easier to navigate' is made without quantitative support. Consider showing a comparison of the landscapes or labeling this as an informal observation.","section":"Sec. 2.2"},{"comment":"The sentence describing the initialization of parameters for p>1 is grammatically unclear: 'we use the found parameters of p−1 blocks together new parameters which we add such that both {γi} and {βi} form a linear schedule.' Please rephrase for clarity.","section":"Sec. 3.1"},{"comment":"The numerical values of the tree-QAOA parameters and the polynomial coefficients used to construct the annealing schedule are not provided, so the annealing experiment cannot be reproduced. Please include them in a table or supplementary material.","section":"Sec. 5"},{"comment":"The caption does not state that the plotted values are averages over M=100 instances, nor the number of optimizer runs per instance. Please add this information to the caption.","section":"Fig. 4(a)"},{"comment":"When Eq. (9) is introduced, the text should more explicitly connect it to the concentration result of Ref. [23], clarifying the distinction between concentration of the objective value and concentration of the optimal parameters.","section":"Sec. 2.2"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a relevant question and the tree-limit derivation is appealing, but the main numerical evidence is gathered in precisely the regime where the paper's own Eq. (9) cannot hold. The authors should be encouraged to test the method in the valid large-N regime, or to reframe the work as an empirical heuristic whose theoretical justification is a separate open problem. I would recommend major revision rather than rejection, as the core approach may be salvageable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the core idea—computing QAOA parameters from the infinite regular tree via tensor networks—is new and clean, but the numerical evidence does not actually test the tree-limit mechanism because it uses instances small enough that the reverse causal cone is the whole graph. Read the results as an extrapolation, not a validation.\n\nThe genuinely new piece is the tree-QAOA construction: for a fixed degree, the per-edge energy in the infinite-size limit is evaluated by contracting a tensor network of treewidth 1, and the optimal parameters are then transferred to finite instances. That is a reasonable extension of the concentration results from Brandao et al. and Zhou et al., and the derivation in Eqs. (7)-(9) is correct. The annealing-schedule interpolation in Sec. 5 is a nice extra and seems to improve on a linear ramp, at least on 10-spin instances.\n\nWhere it gets soft: the central theoretical claim (Eq. 9) requires the instance to be large compared to the reverse causal cone. For 3-regular Max-Cut with N=12 and p≥3, that cone already contains more vertices than the whole graph, so every edge sees cycles, not a tree. The paper's own Fig. 4 is exactly in that regime, so it cannot validate the tree-limit approximation. The 2D spin-glass benchmarks are even further from the assumption. The performance may still transfer for other reasons (parameter concentration is known), but the paper doesn't isolate that. The comparison is also under-powered: no error bars or variance across the 100 instances, and the vanilla QAOA baselines use a single random start. A hyperparameter-tuned optimizer might beat tree-QAOA at every p. Finally, no code or data is released, which makes it hard to check the contraction and optimization details.\n\nThe paper is not careless in its claims—the conclusion says the large-size advantage 'remains an open question'—but the abstract's 'comparable or even better' is not supported by evidence in the regime where the method is supposed to work. I'd like to see either a move to larger simulated instances (or a clear acknowledgment that the small-N results are an extrapolation), error bars, and a baseline using Brandao-style parameter transfer.\n\nOverall: worth a serious referee, because the idea is good and the theory is right, but the numerical section needs rework before publication.","headline":"The tree-QAOA idea is new and the theory is sound, but the numerical evidence is gathered in the regime where the tree-limit approximation cannot hold, so the transfer claim rests on extrapolation.","tokens_in":14151,"tokens_out":2777,"would_cite":false,"duration_ms":27594,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The optimal parameters for QAOA on a problem class can be found by classically simulating the infinite regular tree of the corresponding graph degree, so the quantum processor is needed only to sample from the final state.","keywords":["Quantum Approximate Optimization Algorithm","QAOA","tensor networks","parameter concentration","Max-Cut","spin glasses","quantum annealing","variational quantum algorithms"],"falsifier":"Take a fixed-degree random graph family and a fixed depth $p$, and check whether the spread of per-instance optimal QAOA parameters shrinks as the system size grows while the per-edge energy approaches the infinite-tree correlation function of Eq. (9). Concretely, on 3-regular Max-Cut with $p=8$, compare the residual energy delivered by tree-QAOA parameters against full per-instance training on instances with $N\\geq 100$ qubits; a systematic gap in favor of instance-trained parameters would falsify the claim that the QPU is unnecessary for parameter updates.","tokens_in":13122,"feed_emoji":"⚛️","tokens_out":10106,"duration_ms":89015,"temperature":0.7,"pith_summary":"This paper tries to eliminate the classical outer learning loop of the Quantum Approximate Optimization Algorithm (QAOA) by showing that its variational parameters can be inferred classically from the topology of the problem graph. The central observation is that optimal QAOA parameters concentrate for a given problem class and depend on local graph degree rather than instance size. The authors therefore optimize the parameters on an infinite regular tree with the same degree, using tensor-network contraction that costs polynomially in qubit number and exponentially in circuit depth. These tree-optimal parameters are then applied to finite instances, and the quantum processor is used only to sample from the output state. If this works, QAOA loses its main per-instance training cost, which would make it substantially more practical on near-term devices.","feed_headline":"Simulate a tree to train QAOA without a QPU","feed_subtitle":"Tree-computed parameters match or beat per-instance QAOA training on Max-Cut and spin-glass tests.","key_machinery":"The reverse causal cone of a correlation function: for the expectation value of an edge operator, only gates within $p$ layers of that edge can contribute, and on large random fixed-degree graphs this support is typically a tree of the same degree as the problem graph. Tree-QAOA evaluates the infinite-tree correlation function by building a tensor network in the superoperator picture, decomposing each two-qubit $\\sigma_z\\sigma_z$ gate into rank-3 tensors, and contracting along the qubit lines. Since a tree has treewidth 1, the contraction complexity scales with the exponential of the treewidth times the number of blocks, i.e. exponentially in $p$ but only polynomially in the number of qubits.","core_discovery":"The paper claims that for QAOA on a problem class with fixed local structure, the per-edge energy of any large instance is governed by the infinite regular tree of the corresponding vertex degree. Concretely, the paper defines tree-QAOA: classically optimize the parameters of a QAOA circuit placed on this infinite tree, using a tensor network whose contraction cost scales polynomially in the number of qubits and exponentially in the number of QAOA blocks $p$. The same parameters are then used for all finite instances of the class, with the QPU reduced to preparing and sampling the final state. Numerically, for Max-Cut on 3-regular graphs and spin glasses on square grids, tree-QAOA attains residual energies comparable to or better than vanilla QAOA trained instance by instance, and the parameters remain useful under analog control noise.","pith_inferences":["If the tree limit holds beyond the tested sizes, QAOA for any bounded-local-structure problem class could ship with precomputed parameter tables, removing the variational loop from deployment entirely.","The gap between tree-optimal and per-instance-optimal residual energy could serve as a diagnostic: a problem class where instance optima do not approach the tree optimum is likely to resist parameter transfer, so tree-QAOA could be validated on small classical simulations before trusting it on a QPU.","The annealing-schedule transfer suggests that schedules for analog annealers could be designed from local tree structure without knowing the spectral gap; testing on other spin-glass families with planted hard instances would show whether this is generic.","Because the paper reports the tree optimization landscape as noticeably less rugged than the finite-instance landscape, tree parameters could initialize per-instance variational training and potentially avoid poor local optima."],"forward_implications":["For a fixed problem class, one classical tree optimization replaces per-instance QPU training; the quantum processor is only needed to sample from the prepared QAOA state.","The classical preprocessing cost is polynomial in qubit number and exponential in circuit depth, so the method is aimed at shallow NISQ circuits where the training loop would otherwise dominate.","On the tested Max-Cut and spin-glass instances, tree parameters match or beat instance-trained QAOA, and the paper expects the advantage to become more pronounced on larger instances.","Tree-QAOA parameters remain useful under analog control errors up to roughly 20 percent disorder, staying well above random guessing.","Interpolating the tree-QAOA parameters into a smooth annealing schedule improves ground-state population over a linear ramp in small quantum-annealing simulations."],"supporting_citations":[{"why":"Defines QAOA and introduces the reverse causal cone that the tree simulation exploits.","marker":"[7]"},{"why":"Establishes concentration of QAOA objective values for fixed control parameters, motivating parameter reuse across instances.","marker":"[23]"},{"why":"Shows tensor-network contraction cost scales with the treewidth of the circuit graph, underpinning the claimed classical scaling.","marker":"[26]"},{"why":"Supplies the density-matrix superoperator formulation used to turn the tree correlation function into a contractable tensor network.","marker":"[25]"},{"why":"Reports exponential residual-energy scaling in depth and special-purpose parameter initialization, forming the baseline tree-QAOA is compared against.","marker":"[12]"},{"why":"Provides the contraction-order heuristic used to contract the tree tensor networks efficiently.","marker":"[29]"},{"why":"Implements the quasi-Newton optimizer used to find tree parameters and as a trained-QAOA baseline.","marker":"[27]"},{"why":"Implements the adaptive-moment optimizer used as the second trained-QAOA baseline.","marker":"[28]"}],"fun_headline_variants":["Train QAOA classically on an infinite tree, skip the QPU","No QPU needed to train QAOA: tree tensor networks pick parameters","Tree-shaped QAOA training beats per-instance quantum tuning","Classical tree calculations replace QAOA's quantum training loop","QAOA parameters from an infinite tree, no quantum processing unit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"A single set of QAOA parameters found on the infinite regular tree works well for all finite instances of the same problem class, because optimal parameters concentrate and the tree's energy landscape approximates large finite instances.","fun_headline_variants_meta":{"raw":{"variants":["Train QAOA classically on an infinite tree, skip the QPU","No QPU needed to train QAOA: tree tensor networks pick parameters","Tree-shaped QAOA training beats per-instance quantum tuning","Classical tree calculations replace QAOA's quantum training loop","QAOA parameters from an infinite tree, no quantum processing unit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000207,"raw_usage":{"total_tokens":1351,"prompt_tokens":848,"completion_tokens":503,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":464,"completion_tokens_details":{"reasoning_tokens":415}},"tokens_in":464,"tokens_out":503,"duration_ms":5439,"temperature":1.0,"reasoning_tokens":415,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:27:12.889158+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a fixed-degree random graph family and a fixed depth $p$, and check whether the spread of per-instance optimal QAOA parameters shrinks as the system size grows while the per-edge energy approaches the infinite-tree correlation function of Eq. (9). Concretely, on 3-regular Max-Cut with $p=8$, compare the residual energy delivered by tree-QAOA parameters against full per-instance training on instances with $N\\geq 100$ qubits; a systematic gap in favor of instance-trained parameters would falsify the claim that the QPU is unnecessary for parameter updates.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines QAOA and introduces the reverse causal cone that the tree simulation exploits."},{"cited_title":"Optimizing quantum heuristics with meta-learning","cited_arxiv_id":"1908.03185","evidence_quote":"Shows tensor-network contraction cost scales with the treewidth of the circuit graph, underpinning the claimed classical scaling."},{"cited_title":"Ising formulations of many np problems","cited_arxiv_id":null,"evidence_quote":"Provides the contraction-order heuristic used to contract the tree tensor networks efficiently."}],"review_version":1}