{"id":"ad5d5a56-3231-42dc-b3a0-991496647144","arxiv_id":"2412.18309","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A QSVT-based quantum gradient descent algorithm is proposed that avoids coherent oracle access, but key construction steps and complexity claims are not adequately supported.","lead":"This paper proposes a quantum gradient descent algorithm built on quantum singular value transformation that needs only a classical description of the objective function, not a coherent oracle. The claimed benefits are logarithmic qubit count and logarithmic dependence on the number of variables, but the analysis has several gaps that undercut the main claims.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's coefficient-scaling step is invalid: Lemma 10 can only divide a block-encoded matrix by p>1, yet Algorithm 2 requires multiplying monomials by coefficients a_i that may exceed 1.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing defect: Lemma 10 only scales block-encoded matrices down, by A/p with p>1, while Algorithm 1's steps 3-4 require scaling up by coefficients a_i and powers i_m/M that can exceed 1. This is not a mere normalization convention: the assumption |f|<=1/2 on [-1/2,1/2]^n allows coefficients as large as 2^{d-1}, so the cited construction fails on valid inputs. Because the gradient block encoding of Lemma 3 is the core of Algorithm 2, the claimed running time and the claim of removing coherent oracle access are not established as written. I agree with the reader's rejection: the result should not be accepted without either a corrected scaling argument or an explicit restriction on coefficients. Other issues noted by the reader, such as the readout success probability and error accumulation, are secondary to this direct failure of the central construction.","tokens_in":18384,"tokens_out":17356,"duration_ms":162613,"concrete_test":"Take the valid instance n=1, f(x)=2x^2 on [-1/2,1/2], so a_1=2>1. Trace Algorithm 1 step 3: given the block encoding of x|0><0|, construct 2x|0><0| 'using Lemma 10'. Lemma 10 constructs A/p with p>1; the only p solving A/p=2A is p=1/2<1, which is outside the lemma. Then check whether Lemma 11 can be substituted: at x close to 1/2 the monomial's singular value is close to 1/2, and gamma=2 requires singular values <=(1-delta)/2<1/2, so the precondition fails. Thus no cited lemma implements this step, and Algorithm 2 cannot handle this input as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing flaw is in Algorithm 1, step 3 (and the analogous scaling in step 4). The algorithm invokes Lemma 10 to construct a block encoding of a_i times a monomial, but Lemma 10 only produces a block encoding of A/p for p>1. Under the paper's own assumptions, a_i is allowed to exceed 1: for example, f(x)=2x^2 on [-1/2,1/2] satisfies |f|≤1/2 with a_1=2. For such an input, no p>1 satisfies A/p=2A, so the cited lemma cannot perform the required scaling. This is load-bearing because the gradient block encoding in Lemma 3 is assembled by multiplying each monomial block encoding by its coefficient a_i and then by i_m/M; if a_i>1 (or i_m/M>1), the intermediate matrix either has no guaranteed block encoding or requires a different tool, such as singular-value amplification, whose preconditions are not shown. Consequently Algorithm 2 is not proven for generic polynomials satisfying the stated assumptions. A repair is plausible—combining all factors into one coefficient bounded by 1, or using Lemma 11 under a norm condition—but as written the central claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript develops a QSVT-based quantum gradient descent framework. For f(x)=Σ_{i=1}^K a_i f_i(x) with monomials f_i, |f|≤1/2 on [−1/2,1/2]^n, and a known gradient bound M, Algorithm 2 constructs a block encoding of the diagonal update matrix diag(x_{j,t} − η∂f/∂x_j) iteratively: Algorithm 1 assembles each monomial partial derivative from block encodings of single-coordinate operators (Lemma 2), products (Lemma 6), scalar multiplication (Lemma 10), linear combinations (Lemma 9), and amplification (Lemma 11); the claimed cost is O(log n (K 2^d v^2 log(1/ε))^T) depth with O(log n+log v+log K) qubits over T iterations. For separable f=Σ_i F(x_i), Algorithm 3 uses the polynomial-transformation lemma (Lemma 4) at per-iteration depth O(deg(P) log(1/ε)), for a total of O(log n (deg(P) log(1/ε))^T) with O(log n) qubits. Section IV discusses initial-state preparation, extraction of |x_T⟩ by postselection, and comparisons with Rebentrost et al. [31] and with classical gradient descent. The technical toolkit (Definition 1, Lemmas 5–11) is collected in Appendix A with citations to Gilyén et al. [22] and Rattew–Rebentrost [32].","tokens_in":18637,"tokens_out":42358,"duration_ms":358275,"significance":"If made rigorous, the framework would be a valuable addition to the QSVT literature: gradient descent with O(log n) qubits, polynomial classes broader than [31]'s homogeneous even-degree case, and no coherent oracle access. The central idea of representing the iterate as a diagonal block-encoded operator built from a classically prepared initial state, then assembling monomial gradients from product and linear-combination lemmas, is transparent, falsifiable, and potentially generalizable to other iterative methods. I find no circularity: the argument depends on established external lemmas, and the author's earlier works [27–29] are not used in the main construction. At the same time, the paper as written contains several load-bearing gaps — the unproven scalar multiplications in Algorithm 1, an invalid norm bound on individual monomial gradients, an internally inconsistent complexity formula, and an incorrect postselection-probability estimate — so the significance is conditional on a substantive revision.","major_comments":[{"comment":"The construction of the gradient block encoding is not valid as written. Steps 3–4 invoke Lemma 10 to multiply a block-encoded monomial by the coefficient a_1 and by i_1/M, but Lemma 10 only produces a block encoding of A/p for p>1 (implemented via RY(theta) with cos(theta/2)=1/p), and no lemma in the paper scales an encoding up by a factor c>1. Such factors are allowed by the assumptions: f(x)=2x^2 on [-1/2,1/2] satisfies |f|≤1/2 with a_1=2, and with M=2 (sup|∇f|=2) the combined factor a_1 i_1/M equals 2; in general a_i can be as large as 2^(d−1). Moreover, the norm check at Eq. (28) infers |∂f_i/∂x_j|≤M for each monomial term from |∇f|≤M, which is the reverse of the triangle inequality and is false under cancellation: for f = A x_1 − A x_1 one has |f|=0 and |∇f|=0≤M for any M>0, while ∂f_1/∂x_1 = A, so the operator (1/M)(∂f_1/∂x_1)|0⟩⟨0| has norm A/M, which can exceed 1 and then admits no block encoding. Thus Lemma 3 and Algorithm 2 are not established for generic polynomials satisfying the stated assumptions. A repair would require merging the two scalings into a single factor a_i i_m/M implemented by singular-value amplification with verified norm preconditions and a strictly larger M, plus a bound on individual monomial partial derivatives; none of this appears in the manuscript.","section":"Algorithm 1, steps 3–4; Eq. (28); Lemma 10 (Appendix A)"},{"comment":"The total-depth formulas O(log n (K 2^d v^2 log(1/epsilon))^T) and O(log n (deg(P) log(1/epsilon))^T) do not follow from the iteration-by-iteration description. Each iteration is a circuit of depth O(log n K 2^d v^2 log(1/epsilon)) (Algorithm 2 steps 1–3), and step 4 says to repeat that circuit T times, feeding the previous output as input; sequential composition yields O(T log n K 2^d v^2 log(1/epsilon)). No mechanism in the text (compounding amplification costs, error reduction, or otherwise) produces a factor of the form (base)^T, yet the 'Potential improvement' paragraph explicitly relies on exponential dependence on T. The authors must either correct the total complexity to the additive form or supply the missing derivation if an exponential-in-T depth is really intended; the comparisons with classical O(ndKvT) and with Ref. [31] are affected in either case. In addition, the per-iteration factors 2^d and v^2 in Lemma 3 are not traced: monomial products cost O(d) applications of block encodings and the amplifications in Eqs. (26)–(27) cost O(v log(v/epsilon)) per monomial, which does not obviously yield 2^d v^2 log(1/epsilon).","section":"Algorithm 2, step 4; Algorithm 3, step 6; Section IV"},{"comment":"The claim that postselecting on the |0> ancilla in Eq. (47) yields |x_T> with 'reasonable' O(1) success probability because each x_{i,T} is O(1) is incorrect and is contradicted by the paper's own norm bound. The success probability is (1/n) Σ_i x_{i,T}^2 = ||x_T||^2/n, and the 'Initial condition' paragraph establishes ||x_T|| ≤ |x_0| + eta M T ≤ 1/2, so the probability is at most 1/(4n); it vanishes with n and can be much smaller for sparse solutions (a solution concentrated on one coordinate gives probability 1/(4n)). If delivering the state |x_T> is part of the claimed output, amplitude amplification with O(sqrt(n)) overhead is required, which changes the claimed logarithmic-in-n running time; alternatively the output claim should be restricted to the block encoding.","section":"Section IV, 'Obtaining quantum state corresponding to solutions'"},{"comment":"The instruction to 'use either Lemma 11, or Lemma 10 to insert the hyperparameter eta' into (1/M) diag(P(x_{j,0})) is not justified for a general eta. Lemma 10 scales only down (p>1), and Lemma 11 amplifies singular values by gamma>1 only when the input singular values are below (1−delta)/gamma. For eta M > 1, which is not excluded (eta is a free hyperparameter and M is an upper bound on |∇f|), neither lemma's precondition is shown to hold; an admissible range for eta (e.g., eta < 1/(2M) with strict inequality) must be stated and verified together with the convergence constraint |x_0| + eta M T ≤ 1/2 from Section IV. As written, step 3 of Algorithm 3 is unproven.","section":"Algorithm 3, step 3"}],"minor_comments":[{"comment":"The choice q = log_2(1/(1/2 − eta M T)^2) only guarantees that the largest entry 1/sqrt(2^q) of the diagonal initial matrix equals 1/2 − eta M T, whereas the quantity that must be bounded is the Euclidean norm |x_0| = sqrt(n/2^q) of the coordinate vector; the correct relation is 2^q ≥ n/(1/2 − eta M T)^2, which still costs only O(log n) qubits.","section":"Section IV, 'Initial condition'"},{"comment":"With eta fixed to 1/(2MK) in step 3, the initial-condition requirement becomes |x_0| ≤ 1/2 − T/(2K), so the algorithm can only run for T < K iterations; if a larger T is intended, eta must be chosen smaller, and this trade-off is not discussed.","section":"Algorithm 2, step 3 and Section IV"},{"comment":"Each iteration operates on an ε-approximate block encoding, so after T iterations the accumulated error is O(Tε); the final 'ε-approximated' claim requires per-iteration precision ε/T (or an explicit error budget), which should be reflected in the stated log(1/ε) factors.","section":"Algorithm 2, step 4; Algorithm 3, step 6"},{"comment":"The citation for Lemma 9 appears as '[22?]' with a literal question mark; the reference needs to be resolved.","section":"Appendix A, Lemma 9"},{"comment":"The partial derivative of f_1 is written with the coefficient a_1, although f_1 is defined in Eqs. (4)–(5) as a monomial without a coefficient; the notation should be reconciled so that a_1 is introduced by the sum in Eq. (14).","section":"Eq. (18)"},{"comment":"The expression '1/2 v(f_1)U_1' is ambiguous: it is intended as (1/2)·v(f_1)·U_1, not 1/(2v(f_1))·U_1; please add parentheses.","section":"Eqs. (26)–(27)"},{"comment":"The passage asserting that polynomial approximability of F(x) to error ε with degree O(log(1/ε)) transfers to its derivative ∂F/∂x_i requires a smoothness hypothesis and an error-transfer argument; the derivative of a degree-d approximant can have approximation error that grows with d.","section":"Section III.B"},{"comment":"Typographical slips include 'homonogeous', 'capitulate', 'produce' for 'procedure', 'matirx', and 'an ϵ-closed approximated' in Algorithm 2 step 3; the manuscript needs a careful proofreading pass.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a brief, informal QSVT application. The referee's main technical concerns are the unproven scalar multiplications in Algorithm 1, the invalid inference at Eq. (28) that individual monomial gradients are bounded by M, the internally inconsistent (base)^T complexity formula, and the wrong postselection-probability estimate in Section IV. All of these are, in principle, repairable within the paper's framework, which is why I recommend major revision rather than rejection, but the revision must contain complete proofs of Algorithms 2 and 3 rather than clarifications. The author's self-citations [27–29] appear only in the introduction and are not used by the construction; that is acceptable, but it would help to say so explicitly. The number of typographical slips, the unresolved citation in Lemma 9, and the informal style suggest the paper needs a careful polishing pass before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Briefly: the core idea is reasonable, but the main construction has a concrete, load-bearing bug. Algorithm 1, step 3 (and the analogous step 4) uses Lemma 10 to scale a block-encoded matrix by the coefficient a_i. Lemma 10 only produces A/p for p > 1, i.e., it shrinks a matrix. Under the paper's own assumptions, a_i can easily exceed 1—for example, f(x)=2x^2 on [-1/2,1/2] satisfies |f| ≤ 1/2. There is no p > 1 that gives A/p = a_i A, and negative coefficients are also not handled. This breaks the construction of the gradient operator for generic polynomials. The fix is straightforward in principle—normalize by a global coefficient bound and absorb that factor into the learning rate—but it is not in the paper.\n\nWhat is genuinely new: the paper builds quantum gradient descent entirely from diagonal block encodings, eliminating the coherent oracle assumption of Rebentrost et al. The treatment of sums of monomials and the special case of separable sums of univariate functions are sensible directions. The second algorithm, for separable functions, is a nice complement and avoids the worst scaling of the generic case.\n\nOther soft spots, in proportion. The error analysis is incomplete: each iteration uses an epsilon-approximate encoding, and the paper never states how epsilon must scale with the number of iterations T to keep the final error under control. A naive accumulation argument would multiply the claimed complexity by a polynomial factor in T. The success-probability discussion in Section IV is also handwavy. The formula (1/n) Σ x_i^2 is correct, but the claim that it is O(1) implicitly assumes all components are of order 1; that is not guaranteed by the algorithm. The proposed uniform-superposition initialization restricts the starting vector to all-equal components, which is a serious practical limitation for a gradient method. The self-citations are fine; the construction does not depend on them.\n\nFor a reader: the idea is worth thinking about, and the flaws are identifiable and likely repairable. But as written, the main claim is unsupported. I would not cite it in its current form, but I would send it to peer review, with clear instructions for the referees to check the scaling step and error accumulation carefully.","headline":"The QSVT-based idea is genuinely fresh, but the main algorithm has a concrete, load-bearing bug in the coefficient scaling step, so the central claim is not established as written.","tokens_in":19173,"tokens_out":4763,"would_cite":false,"duration_ms":43852,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"By encoding the gradient as a diagonal matrix, quantum gradient descent can be run from classical polynomial data alone, with no coherent oracle access.","keywords":["quantum gradient descent","quantum singular value transformation","block encoding","polynomial optimization","coherent oracle access","diagonal matrix encoding","singular value amplification","convex optimization"],"falsifier":"Run Algorithm 1 on the monomial $2x^2$ over $[-1/2,1/2]$. Step 3 must turn a block encoding of $x\\,|0\\rangle\\langle 0|$ into one of $2x\\,|0\\rangle\\langle 0|$; the only scaling tools supplied are Lemma 10, which divides by $p>1$, and Lemma 11, which requires singular values below $(1-\\delta)/\\gamma$. With $x$ ranging up to $1/2$, no value of $\\delta\\in(0,1/2)$ and $\\gamma=2$ satisfies that threshold for all encodings, so either a different construction is needed or the generic-coefficient claim fails; finding that construction, or proving none exists, settles the question.","tokens_in":18140,"feed_emoji":"📉","tokens_out":17950,"duration_ms":160994,"temperature":0.7,"pith_summary":"This paper sets out to show that quantum gradient descent does not need coherent oracle access—a quantum black box that loads classical data into superposition—to optimize a polynomial. It constructs circuits that take only a classical description of the function, a shallow unitary preparing the initial point, and standard block-encoding tools, and that output an updated solution vector in quantum form. If the construction is right, the two algorithms scale as $O(\\log n\\,(K^2 d v^2 \\log(1/\\epsilon))^T)$ and $O(\\log n\\,(\\deg(P)\\log(1/\\epsilon))^T)$, using between $O(\\log n)$ and $O(\\log n+\\log v+\\log K)$ qubits. That would mean the earlier quantum gradient descent's reliance on an oracle for a matrix specifying the function can be dropped, with exponentially fewer qubits, and that coherent access is not a prerequisite for this kind of quantum optimization speedup.","feed_headline":"Run quantum gradient descent from classical inputs alone","feed_subtitle":"Two algorithms need only logarithmic qubits in the variable count and no coherent oracle, unlike earlier methods.","key_machinery":"The central object is the block-encoded diagonal gradient operator, built monomial by monomial. A block encoding represents a matrix as the top-left block of a larger unitary. Starting from a unitary $U_0$ that prepares the current point, a state-preparation lemma gives an exact block encoding of $X=\\mathrm{diag}(x_1,\\dots,x_n)$; a derived single-entry lemma extracts $x_j |k\\rangle\\langle k|$ at any diagonal location. Products and powers of these entries assemble each monomial's partial derivative, linear combinations assemble the full gradient, and the singular-value amplification lemma strips prefactors such as $1/v(f_i)$ and $1/2$. For the separable class, the polynomial-transformation lemma is the second workhorse: it maps $X$ to $\\mathrm{diag}(P(x_1),\\dots,P(x_n))$ in $\\deg(P)$ applications of the encoding, so polynomial approximation of a univariate derivative supplies the whole update.","core_discovery":"The central claim, stated on the paper's own terms, is that the gradient of any polynomial can be carried through gradient descent as a block-encoded diagonal matrix—block encoding meaning the matrix sits in the top-left corner of a larger unitary. Beginning with the amplitude state $|x\\rangle=\\sum_j x_j |j\\rangle$, the paper obtains an exact block encoding of $X=\\mathrm{diag}(x_1,\\dots,x_n)$, then isolates entries $x_j |k\\rangle\\langle k|$, forms powers and products to build each monomial's partial derivative, combines them into $\\mathrm{diag}(\\partial f/\\partial x_1,\\dots,\\partial f/\\partial x_n)$, and applies singular-value amplification to normalize prefactors. Repeating the update $X_{t+1}=X_t-\\eta\\,\\mathrm{diag}(\\nabla f(X_t))$ for $T$ steps yields a block encoding of the final diagonal solution matrix, from which the state $|x_T\\rangle$ is read out by measuring an ancilla and keeping the success branch. For the separable class $f(x)=\\sum_i F(x_i)$, a polynomial-transformation lemma applies a degree-$\\deg(P)$ polynomial entrywise, reducing the qubit count to $O(\\log n)$. The paper concludes that this removes the coherent-oracle assumption of the prior work and handles a broader class of functions than homogeneous even-degree polynomials.","pith_inferences":["The same block-encoding construction could likely be reused for other classical-data optimization problems—least squares, Lasso, or tensor decompositions—wherever the data enter through explicit polynomial expressions; this transfer is not claimed in the paper.","A natural next step would be to approximate the whole descent map $x \\mapsto x-\\eta\\nabla f(x)$ as one polynomial in $X$ and apply it with QSVT once, avoiding the T-fold repetition that dominates the cost.","An unstated but simple safeguard for the monomial case would be to rescale the objective so every coefficient lies between 0 and 1 and absorb the normalization into the gradient bound; the paper does not discuss this normalization.","The output readout can be tested on a few-qubit example by comparing the amplitudes of the final block-encoded state with a classical gradient descent trajectory; the paper's update rule predicts they match to within the chosen error tolerance."],"forward_implications":["If the central claim is correct, optimizing high-dimensional polynomial objectives needs only logarithmically many qubits in the variable count, with each iteration costing a factor that is polynomial in the monomial parameters and the inverse error tolerance.","The earlier coherent-oracle bottleneck disappears: classical knowledge of the monomial coefficients and a cheap unitary for the initial point are enough to run the descent.","The separable-function algorithm covers sums of single-variable functions whose derivatives are well approximated by polynomials, and uses the smallest qubit count of the two.","In the homogeneous-polynomial setting, the paper's comparison predicts an exponential improvement in error tolerance and in the polynomial degree factor over the old method, at the price of a squared term in the number of monomials.","For strongly convex objectives, the iteration count depends only logarithmically on the desired accuracy, so the exponential-in-iterations prefactor becomes polynomial in the accuracy."],"supporting_citations":[{"why":"Supplies the QSVT toolkit—block-encoding definitions, polynomial transformation, product and linear-combination lemmas, and singular-value amplification—on which both algorithms are built.","marker":"[22]"},{"why":"The prior quantum gradient descent algorithm for homogeneous even-degree polynomials that this work generalizes and compares against; removing its oracle-access assumption is the paper's stated motivation.","marker":"[31]"},{"why":"Provides the lemma that converts a state-preparation unitary into an exact block encoding of the diagonal matrix X, the entry point for encoding the current point.","marker":"[32]"},{"why":"Supplies the tensor-product block-encoding construction used to combine operators inside the circuits.","marker":"[36]"},{"why":"Gives the convex and strongly convex iteration bounds used to translate the exponential dependence on the iteration count into a statement about the desired accuracy.","marker":"[33–35]"}],"fun_headline_variants":["Quantum gradient descent from classical data alone","No oracle needed: quantum gradient descent on classical inputs","Classical in, quantum out: gradient descent without coherent access","Quantum gradient descent skips coherent oracle entirely","Log-qubit gradient descent: quantum advantage without oracle"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction depends on being able to multiply a block-encoded monomial by arbitrary real coefficients, including coefficients larger than one, using the scaling tools the paper provides.","fun_headline_variants_meta":{"raw":{"variants":["Quantum gradient descent from classical data alone","No oracle needed: quantum gradient descent on classical inputs","Classical in, quantum out: gradient descent without coherent access","Quantum gradient descent skips coherent oracle entirely","Log-qubit gradient descent: quantum advantage without oracle"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000771,"raw_usage":{"total_tokens":3458,"prompt_tokens":1030,"completion_tokens":2428,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":646,"completion_tokens_details":{"reasoning_tokens":2355}},"tokens_in":646,"tokens_out":2428,"duration_ms":15813,"temperature":1.0,"reasoning_tokens":2355,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:51:09.058767+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on the monomial $2x^2$ over $[-1/2,1/2]$. Step 3 must turn a block encoding of $x\\,|0\\rangle\\langle 0|$ into one of $2x\\,|0\\rangle\\langle 0|$; the only scaling tools supplied are Lemma 10, which divides by $p>1$, and Lemma 11, which requires singular values below $(1-\\delta)/\\gamma$. With $x$ ranging up to $1/2$, no value of $\\delta\\in(0,1/2)$ and $\\gamma=2$ satisfies that threshold for all encodings, so either a different construction is needed or the generic-coefficient claim fails; finding that construction, or proving none exists, settles the question.","supporting_citations":[],"review_version":1}