Pith. sign in

REVIEW 4 major objections 8 minor 51 references

Simple Quantum Gradient Descent Without Coherent Oracle Access

T0 review · 4 major / 8 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read By encoding the gradient as a diagonal matrix, quantum gradient descent can be run from classical polynomial data alone, with no coherent oracle access.

desk verdict 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. read the letter →

arxiv 2412.18309 v2 pith:V6B3B4AU submitted 2024-12-24 quant-ph

Nhat A. Nghiem This is my paper · ORCID
classification quant-ph MSC 81P6868Q12 PACS 03.67.Lx
keywords quantumgradientdescentsingularvaluetransformationblockencodingpolynomialoptimizationcoherentoracleaccessdiagonalmatrixamplificationconvex
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 8 minor

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].

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 (4)
  1. [Algorithm 1, steps 3–4; Eq. (28); Lemma 10 (Appendix A)] 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.
  2. [Algorithm 2, step 4; Algorithm 3, step 6; Section IV] 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).
  3. [Section IV, 'Obtaining quantum state corresponding to solutions'] 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.
  4. [Algorithm 3, step 3] 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.
minor comments (8)
  1. [Section IV, 'Initial condition'] 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.
  2. [Algorithm 2, step 3 and Section IV] 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.
  3. [Algorithm 2, step 4; Algorithm 3, step 6] 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.
  4. [Appendix A, Lemma 9] The citation for Lemma 9 appears as '[22?]' with a literal question mark; the reference needs to be resolved.
  5. [Eq. (18)] 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).
  6. [Eqs. (26)–(27)] 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.
  7. [Section III.B] 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.
  8. [Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation is built on external QSVT lemmas and does not reduce its predictions to fitted inputs or self-citations.

full rationale

The paper's central claim—constructing a quantum gradient descent algorithm from classical polynomial data using QSVT—is not circular. The construction relies on external, independently established tools: Lemma 1 and Lemma 4 are from Gilyén et al. [22], Lemma 1 is attributed to Rattew and Rebentrost [32], and the amplification and block-encoding lemmas are standard QSVT results. The author's self-citations [27,28,29] appear only in the introduction as background on eigenvalue estimation and are not used in the derivation of Algorithms 1-3. No parameter is fitted to data and then renamed as a prediction; the gradient operator is explicitly assembled from monomial block encodings using the stated lemmas. The objective function and initial point are inputs, and the output block encoding is derived by explicit circuit constructions rather than by assumption. The identified coefficient-scaling defect in Algorithm 1 (Lemma 10 only scales matrices down by p > 1, while the algorithm may need to multiply by coefficients a_i > 1) is a correctness gap, not a circularity: it does not make the conclusion equivalent to an input or to a self-citation. Therefore the appropriate circularity score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

No new physical entities are introduced. The key assumptions are structural restrictions on the objective function, the (unsupported) coefficient scaling step, the polynomial approximation of derivatives, and the O(1) depth of the initial state preparation. The most fragile is the coefficient scaling axiom, which is not justified by the cited lemma.

free parameters (3)
  • Learning rate eta = 1/(2MK) in Algorithm 2; user-chosen in Algorithm 3
    Selected by hand; it controls the update step and is constrained by the norm bound |x0| + eta M T <= 1/2. In Algorithm 2 eta is fixed by K and M, which restricts the number of iterations T < K.
  • Gradient norm bound M = assumed known
    An input upper bound on |grad f| over the domain; used to normalize gradient entries and to set eta. The algorithm requires this bound to be known precisely.
  • Polynomial approximation degree deg(P) = chosen by user
    In Algorithm 3, the derivative is replaced by a polynomial approximation of degree deg(P). The paper claims deg(P) = O(log(1/epsilon)) for many functions, but this depends on the function's analyticity and is not proven in general.
assumptions (5)
  • domain assumption The objective function admits the stated structure (sum of monomials with known coefficients, or sum of univariate functions).
    Section III assumes f = sum_i a_i f_i or f = sum_i F(x_i). This restricts the applicability of the algorithms.
  • ad hoc to paper Arbitrary coefficients a_i can be inserted into the block encoding using Lemma 10.
    Algorithm 1 steps 3-4 apply Lemma 10 twice to multiply by a_i and by i_1/M, but Lemma 10 only constructs A/p for p > 1, i.e., it scales down. No mechanism for scaling up by a_i > 1 is provided.
  • domain assumption The derivative of each univariate function can be approximated by a polynomial of degree O(log(1/epsilon)).
    Section III.B relies on polynomial approximation of F'(x_i) to additive error epsilon with degree O(log(1/epsilon)). This holds only for analytic functions with suitable domain of analyticity, and is stated without proof or conditions.
  • domain assumption The initial state-preparation unitary U0 has O(1) depth.
    Algorithm 2 and 3 assume U0 has O(1) depth. The paper gives one example (uniform superposition) but arbitrary initial points may require more expensive preparation.
  • standard math Standard QSVT and block-encoding lemmas from Gilyen et al. and Rattew-Rebentrost are correct.
    The construction relies on Lemmas 1, 4, 5, 6, 7, 8, 9, 10, 11 from the QSVT literature.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Simple Quantum Gradient Descent Without Coherent Oracle Access." pith.science (2026). https://pith.science/paper/V6B3B4AU

@misc{pith2026241218309,
  author       = {Pith},
  title        = {Pith review of: Simple Quantum Gradient Descent Without Coherent Oracle Access},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V6B3B4AU}},
  note         = {Machine review of arXiv:2412.18309}
}
read the original abstract

The gradient descent method aims at finding local minima of a given multivariate function by moving along the direction of its gradient, and hence, the algorithm typically involves computing all partial derivatives of a given function, before updating the solution iteratively. In the work of Rebentrost et al. [New Journal of Physics, 21(7):073023, 2019], the authors translated the iterative optimization algorithm into a quantum setting, with some assumptions regarding certain structure of the given function, with oracle or black-box access to some matrix that specifies the structure. Here, we develop an alternative quantum framework for the gradient descent problem, based on the seminal quantum singular value transformation framework. We show that given only classical information of function of interest, it is possible to construct a quantum gradient descent algorithm with a running time logarithmical in the number of variables. In particular, our framework consumes exponentially less qubits than the prior quantum gradient descent algorithm and removes the need for any coherent oracle access to classical information. Thus, our work provides another example demonstrating the power of quantum singular value transformation framework, and in particular, it adds another instance revealing that quantum coherent access is not necessary for quantum computational advantage.

Figures

Figures reproduced from arXiv: 2412.18309 by the authors.

Figure 1
Figure 1. FIG. 1: Simple illustration for the gradient descent method. It begins at some initially random points [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 20 canonical work pages

  1. [31]

    Quantum algorithms for supervised and unsupervised machine learning

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv:1307.0411, 2013

    arXiv 2013

  2. [22]

    Efficient quantum algorithms for simulating sparse hamiltonians

    Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Communications in Mathematical Physics, 270(2):359–371, 2007

    2007

  3. [32]

    Quantum principal component analysis

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631– 633, 2014

    2014

  4. [1]

    If im = 0, then we simply ignore it and only proceed with those operators with im > 0

    First, for each block encoding of the operator xm |0⟩ ⟨0| (for m = 1, 2, ..., n) such that im ≥ 1, we can use lemma 6 to construct the block encoding of xim m |0⟩ ⟨0| for each m = 2, ..., n. If im = 0, then we simply ignore it and only proceed with those operators with im > 0. For m = 1, we construct the block encoding of xi1−1 1 |0⟩ ⟨0| instead. If i1 = ...

    work page

  5. [2]

    Use lemma 6 again to construct the block encoding of xi1−1 1 xi2 2 ...xin n |0⟩ ⟨0|

    work page

  6. [3]

    Use lemma 10 to construct the block encoding of a1xi1−1 1 xi2 2 ...xin n |0⟩ ⟨0|

    work page

  7. [4]

    where we remind that in the last line, M is the upper bound of the norm of gradient of f within the domain D

    Use lemma 10 again to construct the block encoding of a1 i1 M xi1−1 1 xi2 2 ...xin n |0⟩ ⟨0|. where we remind that in the last line, M is the upper bound of the norm of gradient of f within the domain D. According to Eqn. 16, the output of the above algorithm is 1 M ∂f1(x1,...,xn) ∂x1 |0⟩ ⟨0|, which is assumed to be non-zero among v(f1) non-zero gradient ...

    work page

  8. [5]

    0 0 0 · · ·xn,0   The time complexity, or quantum circuit depth of this step is O(log(n)) and spatial complexity is O(log(n))

    Use U0 and lemma 1 to construct the block encoding of   x1,0 0 · · ·0 0 x2,0 · · ·0 0 0 . . . 0 0 0 · · ·xn,0   The time complexity, or quantum circuit depth of this step is O(log(n)) and spatial complexity is O(log(n))

    work page

Show all 51 references
  1. [6]

    With the above (block encoding of) operator as input, use algorithm 1 and the procedure from lemma 3 with the above input to construct the ϵ-approximated block encoding of: 1 2M K   ∂f (x1,0,x2,0,...,xn,0) ∂x1,0 0 0 0 0 ∂f (x1,0,x2,0,...,xn,0) ∂x2,0 0 0 0 0 . . . 0 0 0 ...

  2. [7]

    0 0 0 · · ·xn,0   − 1 2M K   ∂f (x1,0,x2,0,...,xn,0) ∂x1,0 0 0 0 0 ∂f (x1,0,x2,0,...,xn,0) ∂x2,0 0 0 0 0

    Use lemma 9 with minus sign instead of plus sign, to construct the ϵ-approximated block encoding of 1 2   x1,0 0 · · ·0 0 x2,0 · · ·0 0 0 . . . 0 0 0 · · ·xn,0   − 1 2M K   ∂f (x1,0,x2,0,...,xn,0) ∂x1,0 0 0 0 0 ∂f (x1,0,x2,0,...,xn,0) ∂x2,0 0 0 0 0 . . . 0 0 0...

  3. [8]

    Eventually, we obtain an ϵ-approximated block encoding of   x1,T 0 · · ·0 0 x2,T · · ·0 0 0

    Iterate the following procedure T times: use the ϵ-approximated block encoding of the above operator and repeat from step (2). Eventually, we obtain an ϵ-approximated block encoding of   x1,T 0 · · ·0 0 x2,T · · ·0 0 0 . . . 0 0 0 · · ·xn,T   The total time complexit...

  4. [9]

    0 0 0 · · ·xn,0   The time complexity, or quantum circuit depth of this step is O(log(n)) and spatial complexity is O(log(n))

    Use U0 and Lemma 1 to construct the block encoding of   x1,0 0 · · ·0 0 x2,0 · · ·0 0 0 . . . 0 0 0 · · ·xn,0   The time complexity, or quantum circuit depth of this step is O(log(n)) and spatial complexity is O(log(n))

  5. [10]

    0 0 0 · · ·xn,0   − →1 M   P x1,0 0 · · · 0 0 P x2,0 · · · 0 0 0

    Use Lemma 4 and transform the above block-encoded operator into:   x1,0 0 · · ·0 0 x2,0 · · ·0 0 0 . . . 0 0 0 · · ·xn,0   − →1 M   P x1,0 0 · · · 0 0 P x2,0 · · · 0 0 0 . . . 0 0 0 · · · P xn,0   (36) The complexity of this step is O deg(P) log(n)

  6. [11]

    0 0 0 · · · P xn,0   − →η   P x1,0 0 · · · 0 0 P x2,0 · · · 0 0 0

    Use either Lemma 11, or Lemma 10 to insert the hyperparameter η to the above operator, i.e., we obtain the transformation: 1 M   P x1,0 0 · · · 0 0 P x2,0 · · · 0 0 0 . . . 0 0 0 · · · P xn,0   − →η   P x1,0 0 · · · 0 0 P x2,0 · · · 0 0 0 . . . 0 0 0 · · · P xn,...

  7. [12]

    0 0 0 · · ·xn,0   − η   P x1,0 0 · · · 0 0 P x2,0 · · · 0 0 0

    Use Lemma 9 to construct the block encoding of: 1 2     x1,0 0 · · ·0 0 x2,0 · · ·0 0 0 . . . 0 0 0 · · ·xn,0   − η   P x1,0 0 · · · 0 0 P x2,0 · · · 0 0 0 . . . 0 0 0 · · · P xn,0     = 1 2   x1,1 0 · · ·0 0 x2,1 · · ·0 0 0 . . . 0 0 0 · · ·...

  8. [13]

    Then we obtain an ϵ-approximated block encoding of:   x1,1 0 · · ·0 0 x2,1 · · ·0 0 0

    Use Lemma 11 and remove the factor 1 /2 in the above operator. Then we obtain an ϵ-approximated block encoding of:   x1,1 0 · · ·0 0 x2,1 · · ·0 0 0 . . . 0 0 0 · · ·xn,1   The complexity of this step is O deg(P) log(n) log 1 ϵ 11

  9. [14]

    0 0 0 · · ·xn,T   The total time complexity is O log(n) deg(P) log 1 ϵ T and spatial complexity is O log n IV

    Use the above operator and repeat from the beginning, e.g., Step 1-5, we then obtain an ϵ-approximated block encoding of   x1,T 0 · · ·0 0 x2,T · · ·0 0 0 . . . 0 0 0 · · ·xn,T   The total time complexity is O log(n) deg(P) log 1 ϵ T and spatial complexity is O log n...

  10. [15]

    Thus, this method is a nice complement to the Ref

    Although the method of [31] is only applicable to a homogeneous polynomial of even degree, the algorithm 3 13 introduced above can deal with polynomial of various kinds, and can go even beyond the polynomial domain. Thus, this method is a nice complement to the Ref. [31] (and ...

  11. [16]

    Simulating physics with computers

    Richard P Feynman. Simulating physics with computers. In Feynman and computation, pages 133–153. CRC Press, 2018

    2018

  12. [17]

    Quantum theory, the church–turing principle and the universal quantum computer

    David Deutsch. Quantum theory, the church–turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818):97–117, 1985

    1985

  13. [18]

    Rapid solution of problems by quantum computation

    David Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553–558, 1992

    1907

  14. [19]

    Universal quantum simulators

    Seth Lloyd. Universal quantum simulators. Science, 273(5278):1073–1078, 1996

    1996

  15. [20]

    Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

    Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332, 1999

    1999

  16. [21]

    A fast quantum mechanical algorithm for database search

    Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996

    1996

  17. [23]

    Black-box hamiltonian simulation and unitary implementation

    Dominic W Berry and Andrew M Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Information and Computation, 12:29–62, 2009

    2009

  18. [24]

    High-order quantum algorithm for solving linear differential equations

    Dominic W Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathe- matical and Theoretical, 47(10):105301, 2014

    2014

  19. [25]

    Hamiltonian simulation with nearly optimal dependence on all parameters

    Dominic W Berry, Andrew M Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th annual symposium on foundations of computer science, pages 792–809. IEEE, 2015

    2015

  20. [26]

    Optimal hamiltonian simulation by quantum signal processing

    Guang Hao Low and Isaac L Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical review letters, 118(1):010501, 2017

    2017

  21. [27]

    Hamiltonian simulation by qubitization

    Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019

    2019

  22. [28]

    Quantum simulation of real-space dynamics

    Andrew M Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang. Quantum simulation of real-space dynamics. Quantum, 6:860, 2022. 14

    2022

  23. [29]

    Quantum algorithm for linear systems of equations

    Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009

    2009

  24. [30]

    Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

    Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920–1950, 2017

    1920

  25. [33]

    Quantum algorithms for topological and geometric analysis of data

    Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. Quantum algorithms for topological and geometric analysis of data. Nature communications, 7(1):1–7, 2016

    2016

  26. [34]

    Quantum embeddings for machine learning

    Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran. Quantum embeddings for machine learning. arXiv preprint arXiv:2001.03622, 2020

    2001 arXiv

  27. [35]

    Quantum algorithm for data fitting

    Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data fitting. Physical review letters, 109(5):050505, 2012

    2012

  28. [36]

    Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning

    Nathan Wiebe, Ashish Kapoor, and Krysta Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. arXiv preprint arXiv:1401.2142, 2014

    2014 arXiv

  29. [37]

    Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    Andr´ as Gily´ en, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019

    2019

  30. [38]

    On the relationship between continuous-and discrete-time quantum walk

    Andrew M Childs. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathe- matical Physics, 294(2):581–603, 2010

    2010

  31. [39]

    Quantum walk algorithm for element distinctness

    Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007

    2007

  32. [40]

    Lecture notes on quantum algorithms

    Andrew M Childs. Lecture notes on quantum algorithms. Lecture notes at University of Maryland, 2017

    2017

  33. [41]

    Quantum support vector machine for big data classification.Physical review letters, 113(13):130503, 2014

    Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification.Physical review letters, 113(13):130503, 2014

    2014

  34. [42]

    Quantum algorithm for estimating eigenvalue

    Nhat A Nghiem and Tzu-Chieh Wei. Quantum algorithm for estimating eigenvalue. arXiv preprint arXiv:2211.06179, 2022

    2022 arXiv

  35. [43]

    Improved quantum algorithms for eigenvalues finding and gradient descent

    Nhat A Nghiem and Tzu-Chieh Wei. Improved quantum algorithms for eigenvalues finding and gradient descent. arXiv preprint arXiv:2312.14786, 2023

    2023 arXiv

  36. [44]

    Improved quantum power method and numerical integration using quantum singular value transformation

    Nhat A Nghiem, Hiroki Sukeno, Shuyu Zhang, and Tzu-Chieh Wei. Improved quantum power method and numerical integration using quantum singular value transformation. arXiv preprint arXiv:2407.11744, 2024

    2024 arXiv

  37. [45]

    Quantum algorithm for petz recovery channels and pretty good measurements

    Andr´ as Gily´ en, Seth Lloyd, Iman Marvian, Yihui Quek, and Mark M Wilde. Quantum algorithm for petz recovery channels and pretty good measurements. Physical Review Letters, 128(22):220502, 2022

    2022

  38. [46]

    Quantum gradient descent and newton’s method for constrained polynomial optimization

    Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd. Quantum gradient descent and newton’s method for constrained polynomial optimization. New Journal of Physics, 21(7):073023, 2019

    2019

  39. [47]

    Non-linear transformations of quantum amplitudes: Exponential improvement, generalization, and applications

    Arthur G Rattew and Patrick Rebentrost. Non-linear transformations of quantum amplitudes: Exponential improvement, generalization, and applications. arXiv preprint arXiv:2309.09839, 2023

    2023 arXiv

  40. [48]

    A method for solving the convex programming problem with convergence rate o (1/k2)

    Yurii Nesterov. A method for solving the convex programming problem with convergence rate o (1/k2). In Dokl akad nauk Sssr, volume 269, page 543, 1983

    1983

  41. [49]

    Introductory lectures on convex optimization: A basic course, volume 87

    Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013

    2013

  42. [50]

    Convex optimization

    Stephen Boyd. Convex optimization. Cambridge UP, 2004

    2004

  43. [51]

    Approximate quantum circuit synthesis using block encodings

    Daan Camps and Roel Van Beeumen. Approximate quantum circuit synthesis using block encodings. Physical Review A, 102(5):052411, 2020. 15 Appendix A: Preliminaries Here, we summarize the main recipes of our work, which mostly derived in the seminal QSVT work [22]. We keep the s...

    2020

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.