Pith. sign in

REVIEW 4 major objections 5 minor 17 references

Quantum Solution Framework for Finite-Horizon LQG Control via Block Encodings and QSVT

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper claims that finite-horizon discrete-time LQG control can be solved by a quantum algorithm whose cost is polylogarithmic in system dimension and linear in the time horizon.

desk verdict A sensible composition of known block-encoding/QSVT primitives for LQG, but the headline polylog total-runtime claim rests on an unanalyzed normalization assumption and ignores data I/O; per-component complexity is sound. read the letter →

arxiv 2507.09841 v1 pith:B7YYWPFB submitted 2025-07-14 quant-ph

Nahid Binandeh Dehaghani , Rafal Wisniewski , A. Pedro Aguiar This is my paper · ORCID
classification quant-ph MSC 81P6893E2093E11
keywords quantumLQGcontrolblockencodingQSVTRiccatirecursionKalmanfilterlinearalgebrafinite-horizonoptimalspeedup
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 tries to establish that the classical LQG control pipeline—a backward Riccati recursion for control gains and a forward Kalman filter for state estimates—can be re-expressed entirely in quantum linear algebra. If correct, the per-step cost that classically scales as $O(n^3)$ in the system dimension $n$ would become polylogarithmic in $n$, with only a linear dependence on the horizon $T$. The reason to care is that LQG is the workhorse of optimal feedback control under Gaussian noise, and large-scale or real-time settings hit the cubic wall. The authors' speedup claim is conditional: it requires efficient block encodings of all matrices, bounded condition numbers for the inverted matrices, and access to fault-tolerant quantum hardware.

What carries the argument

The machinery is the block encoding of a matrix $A$ as the top-left block $(A/\alpha)$ of a larger unitary, together with Quantum Singular Value Transformation (QSVT), the technique that applies a polynomial to the singular values of a block-encoded matrix. Block-encoded addition via linear combination of unitaries and block-encoded multiplication via composition of two unitaries let the algorithm carry out the Riccati and Kalman recurrences symbolically. QSVT supplies the inverse: an odd polynomial approximating $x^{-1}$ to degree $O(\kappa \log(1/\varepsilon'))$, so an inverse costs $O(\mathrm{polylog}(n/\varepsilon) \cdot \kappa \log(1/\varepsilon'))$ rather than $O(n^3)$. The normalization factor $\alpha$ is the parameter that decides whether the speedup survives: runtime scales linearly in $\alpha$, and the paper sets $\alpha = 1$ for simplicity while noting $\alpha$ may scale with matrix norms.

What would settle it

Track the quantities $\|P_k\|$ and $\|R_k\|$ (or the condition numbers of $B^\top P_{k+1}B + N$ and $\Gamma + C R_k C^\top$) along the Riccati and Kalman recursions for a family of discrete-time LQG instances with unstable or marginally stable dynamics. If any of these grows faster than polylogarithmically in $k$ or $n$, the $O(T\,\mathrm{polylog}(n))$ runtime bound in Proposition 8 fails for those instances, since QSVT inversion costs scale linearly in $\alpha$ and $\kappa$.

Watch

Extended reading notes

Core claim

The central claim is that block-encoded quantum arithmetic plus QSVT-based matrix inversion can implement both halves of the LQG solution—the discrete-time Riccati recursion and the Kalman filter—and compose them into an end-to-end quantum LQG controller. Each iteration is built from block-encoded additions, multiplications, and one matrix inversion; the inversion uses QSVT with a polynomial of degree $O(\kappa \log(1/\varepsilon'))$. Summing the $T$ backward steps and $T$ forward steps yields the total complexity $O(T \cdot \mathrm{polylog}(n/\varepsilon) \cdot \kappa \cdot \log(1/\varepsilon'))$ with $\kappa = \max(\kappa_R, \kappa_V)$, which is the paper's Proposition 8. The authors state this is an asymptotic quantum speedup over the classical $O(T n^3)$ dense-matrix cost.

Load-bearing premise

The argument stands or falls on the assumption that every matrix used in the recursion, including the newly computed Riccati and covariance matrices, can be loaded into the quantum routine at polylogarithmic cost with a normalization factor that stays constant across all $T$ steps, and that each matrix inversion involves a condition number that stays bounded.

Editorial extensions

If this is right

  • If Proposition 8 holds, the per-step quantum cost for LQG is polylogarithmic in $n$, so the horizon $T$, not the dimension, sets the linear growth of the runtime.
  • The same block-encoded pipeline covers both halves of LQG, so control gain synthesis and state estimation share one representation and one set of quantum primitives.
  • The quantum Kalman filter becomes the forward half of a complete LQG solver rather than a standalone estimation routine.
  • The total complexity $O(T \cdot \mathrm{polylog}(n/\varepsilon) \cdot \kappa \cdot \log(1/\varepsilon'))$ gives a precise target: any classical algorithm beating it for large $n$ would need to exploit structure beyond dense matrix operations.

Reading between the lines

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

  • The paper leaves the evolution of the normalization factor $\alpha$ and the condition numbers $\kappa_R, \kappa_V$ unanalyzed across the recursion. If the Riccati matrix or the covariance grows in norm over the horizon, QSVT inversion costs grow with it, so the claimed polylog-in-$n$ scaling may be overtaken by a factor that depends on the dynamics rather than on $n$.
  • A concrete check suggested by the structure: simulate the classical Riccati and Kalman recursions on families of unstable or marginally stable systems and record the norms and condition numbers at each step. If any grows faster than polylogarithmically in $n$ or $k$, the runtime formula in Proposition 8 is not achieved for those instances.
  • The error analysis is per-operation and the authors explicitly defer cumulative error propagation. A natural extension is to budget the approximation errors $\varepsilon_R, \varepsilon_V$ across $T$ steps so that the final control inputs remain within a specified tolerance, which the current complexity statement does not address.
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 / 5 minor

Summary. The paper proposes a quantum algorithm for the finite-horizon discrete-time LQG control problem. It reformulates the backward Riccati recursion and the forward Kalman filter using block-encoded matrix arithmetic and QSVT-based matrix inversion, and it states complexity bounds for the resulting pipeline. The headline claim, in the abstract and in Proposition 8, is an end-to-end runtime of O(T polylog(n/epsilon) kappa log(1/epsilon')), which the paper contrasts with the classical O(T n^3) cost.

Significance. If the advertised end-to-end runtime were actually established, the result would be a significant theoretical contribution: it would give a quantum LQG solver with near-logarithmic dependence on the system dimension. The paper deserves credit for assembling standard QSVT and block-encoding primitives into a coherent pipeline and for stating its per-subroutine complexity assumptions explicitly. The proof strategy is not circular and no fitted parameters appear. However, the central end-to-end claim is not supported by the analysis: the normalization of block encodings is not tracked through the recursion, the cost of extracting classical control inputs is omitted, and the conclusion itself concedes that no error propagation analysis has been done. These are load-bearing omissions rather than presentation issues.

major comments (4)
  1. [§I, §III-B, §V-A-d, Proposition 8] The complexity analysis assumes alpha = 1, but the paper's own block-encoding construction, Proposition 3, yields a block encoding with normalization alpha = ||A||_F. For a dense n x n matrix with O(1) entries this is Theta(sqrt(n)), not O(1). QSVT is applied to the normalized matrix A/alpha, so the effective condition number and all matrix-product normalizations inherit an alpha-dependence; Proposition 5 multiplies the normalizations of successive block encodings. Section V-A-d and Proposition 8 omit this alpha-dependence entirely. Consequently, the stated bound O(T polylog(n/epsilon) kappa log(1/epsilon')) does not follow from the assumptions in the paper.
  2. [§IV-A, §IV-B-c, §IV-C, Algorithms 2-4] The matrices P_k and R_k are not given data; they are outputs of the recursion. The algorithm must therefore construct their block encodings from arithmetic on previous block encodings, and the normalization factors multiply at each step. The text says intermediate block encodings are 'rescaled as needed' and that amplitude amplification can be applied, but no algorithm or cost is given for this rescaling, and no bound is provided on ||P_k||, ||R_k||, kappa_R, or kappa_V over the T steps. For an unstable A or a large terminal cost these quantities can grow with T, so the linear-in-T factor in Proposition 8 is not justified.
  3. [§IV-C, Algorithm 4 Phase III, §V] The final step of Algorithm 4 outputs classical control inputs u_k = K_k mu_k by measurement. The complexity analysis in Section V stops before readout. Reconstructing T classical vectors of dimension m from quantum states requires tomography or repeated sampling with a cost that depends polynomially on m and on 1/epsilon; for m = O(n) this would remove the polylogarithmic scaling in n. If the intended output is only a quantum state of controls rather than classical control inputs, the abstract's wording that the algorithm 'delivers control inputs and estimated states' must be qualified.
  4. [§VI] The conclusion explicitly states that no error propagation analysis has been performed. Each QSVT inversion and each block-encoded arithmetic operation introduces approximation error, and these errors feed into the next Riccati and Kalman steps. A rigorous total-complexity statement with final accuracy epsilon' requires per-step error budgets and a proof that the Riccati and Kalman recursions remain stable under the accumulated perturbations; neither is provided. This is not a minor caveat: it is necessary for the correctness of the total runtime claim.
minor comments (5)
  1. [§III, introductory paragraph] The word 'relevent' should be 'relevant'.
  2. [§V-C] The text 'explained in Section 3' should refer to a numbered section or subsection (for example, Section IV-B), since no section labeled 'Section 3' exists.
  3. [Algorithms 2-4] The notation suppresses normalization factors in expressions such as U_1^{-1}, U_K_k, and U_{P_k}; because block-encoded matrices are scaled by different alpha factors, this notation should be defined explicitly to avoid ambiguity.
  4. [Proposition 8] The use of epsilon' = min(epsilon'_R, epsilon'_V) should be justified: the relationship between the per-subroutine tolerances and the final error tolerance, including the accumulated error over T steps, is not stated.
  5. [References] Reference [12] is an arXiv preprint; if a peer-reviewed version exists, it should be cited instead of or in addition to the preprint.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the runtime bound is composed from external QSVT and block-encoding theorems, with no fitted parameters and no load-bearing self-citations; the unverified alpha = O(1) normalization is a soundness caveat, not a circular step.

full rationale

The paper's claimed derivation chain is a compositional application of external results. Block encoding (Prop. 3, attributed to [7], [11]) yields an (||A||_F, s, epsilon)-encoding with O(polylog(mn/epsilon)) preparation time; arithmetic composition (Props. 4-5, from [7], [8]) combines encodings; QSVT inversion (Sec. III-D, from [7], [17]) supplies the O(kappa log(1/epsilon')) polynomial degree; Propositions 6-8 concatenate these per time step to obtain O(T polylog(n/epsilon) kappa log(1/epsilon')). No parameter is fitted to data, no conclusion is defined in terms of a premise containing it, and none of the cited building blocks are authored by the present authors (the closest is [12], Shi-Zhang-Zhang), so no self-citation chain is load-bearing. The polylog-n claim is explicitly conditional on the stated assumption that all matrices admit block encodings with normalization alpha = O(1) and bounded condition numbers (Section I and the Block-Encoding Assumption in Section IV). Whether that assumption is satisfiable - dense matrices give ||A||_F = Theta(sqrt(n)) under the paper's own Prop. 3, and Prop. 5 multiplies normalizations in the R_k recursion - is a genuine soundness/correctness concern, and the Conclusion concedes that no error-propagation analysis has been performed. However, an unsupported or implausible precondition is not circularity under the review rules, because the runtime formula does not reduce to its inputs by construction. Accordingly the circularity score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard QSVT results plus strong assumptions about data access, conditioning, normalization, and readout that are not analyzed. No constants are fitted to empirical data; the only hand-chosen quantity is the block-encoding normalization alpha, set to 1.

free parameters (1)
  • Block-encoding normalization alpha = assumed 1
    QSVT and multiplication runtimes grow linearly in alpha; the paper sets alpha = 1 for simplicity and does not track growth of the normalization for recursively updated matrices P_k and R_k.
assumptions (4)
  • domain assumption Efficient block encodings exist for all matrices via quantum-accessible data structures in O(polylog(n/epsilon)) time
    Invoked in Prop. 3 and Section V; not proven for the recursively updated dense matrices in the Riccati and Kalman recursions.
  • standard math QSVT polynomial approximation for matrix inversion is valid with degree O(kappa log(1/epsilon'))
    Taken from ref [7]; used in Sections III.D, V.
  • domain assumption Fault-tolerant quantum hardware and quantum random access memory are available
    Stated in the Assumptions and Scope paragraph of the introduction.
  • ad hoc to paper Output measurement extracts classical control inputs without affecting the asymptotic runtime bound
    Step 9 of Algorithm 4 and the final extraction note assume readout is cheap; no cost analysis is given for reading O(n) or O(n^2) amplitudes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Solution Framework for Finite-Horizon LQG Control via Block Encodings and QSVT." pith.science (2026). https://pith.science/paper/B7YYWPFB

@misc{pith2026250709841,
  author       = {Pith},
  title        = {Pith review of: Quantum Solution Framework for Finite-Horizon LQG Control via Block Encodings and QSVT},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/B7YYWPFB}},
  note         = {Machine review of arXiv:2507.09841}
}
abstract

We present a quantum algorithm for solving the finite-horizon discrete-time Linear Quadratic Gaussian (LQG) control problem, which integrates optimal control and state estimation in the presence of stochastic disturbances and noise. Classical approaches to LQG require solving a backward Riccati recursion and a forward Kalman filter, both requiring computationally expensive matrix operations with overall time complexity $\mathcal{O}(T n^3)$, where $n$ is the system dimension and $T$ is the time horizon. While efficient classical solvers exist, especially for small to medium-sized systems, their computational complexity grows rapidly with system dimension. To address this, we reformulate the full LQG pipeline using quantum linear algebra primitives, including block-encoded matrix representations and quantum singular value transformation (QSVT) techniques for matrix inversion and multiplication. We formally analyze the time complexity of each algorithmic component. Under standard assumptions on matrix condition numbers and encoding precision, the total runtime of the quantum LQG algorithm scales polylogarithmically with the system dimension $n$ and linearly with the time horizon $T$, offering an asymptotic quantum speedup over classical methods.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 11 canonical work pages

  1. [1]

    B. D. Anderson and J. B. Moore, Optimal control: linear quadratic methods. Courier Corporation, 2007

    2007

  2. [2]

    Risk-sensitive optimal control,

    P. Whittle, “Risk-sensitive optimal control,” Wiley, 1990

    work page 1990

  3. [3]

    Simon, Optimal state estimation: Kalman, H infinity, and nonlinear approaches

    D. Simon, Optimal state estimation: Kalman, H infinity, and nonlinear approaches. John Wiley & Sons, 2006

    2006

  4. [4]

    The role and use of the stochastic linear-quadratic- gaussian problem in control system design,

    M. Athans, “The role and use of the stochastic linear-quadratic- gaussian problem in control system design,” IEEE transactions on automatic control, vol. 16, no. 6, pp. 529–552, 1971

    work page 1971

  5. [5]

    Formulas for discrete time lqr, lqg, leqg and minimax lqg optimal control problems,

    A. Shaiju and I. R. Petersen, “Formulas for discrete time lqr, lqg, leqg and minimax lqg optimal control problems,” IFAC Proceedings Volumes, vol. 41, no. 2, pp. 8773–8778, 2008

    work page 2008

  6. [6]

    Quantum algorithm for linear systems of equations,

    A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum algorithm for linear systems of equations,” Physical review letters, vol. 103, no. 15, p. 150502, 2009

    2009

  7. [7]

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

    A. Gily ´en, Y . Su, G. H. Low, and N. 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 , 2019, pp. 193–204

    work page 2019

  8. [8]

    Lecture notes on quantum algorithms for scientific computa- tion,

    L. Lin, “Lecture notes on quantum algorithms for scientific computa- tion,” arXiv preprint arXiv:2201.08309 , 2022

    arXiv 2022

Show all 17 references
  1. [9]

    Block-encoding struc- tured matrices for data input in quantum computing,

    C. S ¨underhauf, E. Campbell, and J. Camps, “Block-encoding struc- tured matrices for data input in quantum computing,” Quantum, vol. 8, p. 1226, 2024

    2024

  2. [10]

    Quantum resources required to block-encode a matrix of classical data,

    B. D. Clader, A. M. Dalzell, N. Stamatopoulos, G. Salton, M. Berta, and W. J. Zeng, “Quantum resources required to block-encode a matrix of classical data,” IEEE Transactions on Quantum Engineering, vol. 3, pp. 1–23, 2022

    2022

  3. [11]

    The power of block- encoded matrix powers: improved regression techniques via faster hamiltonian simulation,

    S. Chakraborty, A. Gily ´en, and S. Jeffery, “The power of block- encoded matrix powers: improved regression techniques via faster hamiltonian simulation,” arXiv preprint arXiv:1804.01973 , 2018

    2018 arXiv

  4. [12]

    A quantum algorithm for the kalman filter using block encoding,

    H. Shi, G. Zhang, and M. Zhang, “A quantum algorithm for the kalman filter using block encoding,” arXiv preprint arXiv:2404.04554 , 2024

    2024 arXiv

  5. [13]

    Differentiable quantum computing for large-scale linear control,

    C. Clayton, J. Leng, G. Yang, Y .-L. Qiao, M. Lin, and X. Wu, “Differentiable quantum computing for large-scale linear control,” Advances in Neural Information Processing Systems , vol. 37, pp. 37 176–37 212, 2024

    2024

  6. [14]

    Quantum algorithms to simulate quadratic classical hamil- tonians and optimal control,

    H. Krovi, “Quantum algorithms to simulate quadratic classical hamil- tonians and optimal control,” arXiv preprint arXiv:2404.07303, 2024

    2024 arXiv

  7. [15]

    Fable: Fast approximate quantum circuits for block-encodings,

    D. Camps and R. Van Beeumen, “Fable: Fast approximate quantum circuits for block-encodings,” in 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) . IEEE, 2022, pp. 104–113

    2022

  8. [16]

    Explicit quantum circuits for block encodings of certain sparse matrices,

    D. Camps, L. Lin, R. Van Beeumen, and C. Yang, “Explicit quantum circuits for block encodings of certain sparse matrices,” SIAM Journal on Matrix Analysis and Applications , vol. 45, no. 1, pp. 801–827, 2024

    2024

  9. [17]

    Grand unification of quantum algorithms,

    J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, “Grand unification of quantum algorithms,” PRX quantum , vol. 2, no. 4, p. 040203, 2021

    2021

Pith tools

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