{"id":"1b141e1e-dd35-4411-8013-2dd37757e646","arxiv_id":"2507.09841","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"A proposal to solve finite-horizon LQG control with block-encoded quantum linear algebra, claiming O(T polylog(n)) runtime under strong assumptions about data access, conditioning, and ignoring output readout.","lead":"This paper proposes a quantum algorithm that rewrites the two iterative steps of linear-quadratic-Gaussian control, the backward Riccati recursion and the forward Kalman filter, as quantum circuits using block encodings and QSVT. It claims the runtime grows polylogarithmically with system dimension and linearly with time horizon, against the classical O(T n^3) cost.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The polylog(n) runtime claim rests on an unproven normalization assumption: Proposition 3 block-encodes dense matrices with α=||A||_F=Θ(√n), while Section V sets α=1; condition numbers of recursively generated Riccati/Kalman matrices are never tracked.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: the block-encoding normalization α and condition numbers of matrices generated inside the Riccati and Kalman recursions are assumed to be O(1) and bounded, but never analyzed. This is reinforced by Proposition 3, which gives α=||A||_F for dense matrices, making the α=1 shortcut inconsistent with the paper's own encoding construction before the recursion even begins. The repeated multiplications in Algorithms 2 and 3 compound normalizations, and the paper explicitly states that no error propagation analysis has been performed. Since the central claim is the polylogarithmic-in-n, linear-in-T total runtime, and that claim depends on these uncontrolled quantities, the REJECT verdict stands. A re-scoped version with explicit bounds on all input and generated matrices, plus readout costs, could be conditionally acceptable, but the current manuscript does not provide that.","tokens_in":13052,"tokens_out":10548,"duration_ms":128505,"concrete_test":"Take a dense n×n matrix A with O(1) entries and construct its block encoding via Proposition 3. The normalization is α=||A||_F=Θ(√n), not 1, so the Section V cost O(T_U κ log(1/ε′)) must be multiplied by α; this already removes 'polylog n' for the advertised dense-matrix regime. Then run the Kalman covariance recursion (12) for a scalar unstable mode with A=1.5, C=0, Σ=1, R_0=1, T=50; R_k grows as 2.25^k. Since each step of Algorithm 3 block-encodes R_k, the effective normalization of the covariance data grows exponentially in T, contradicting the α=O(1) assumption even when κ(V_k)=1. These two checks would settle whether the missing normalization and conditioning analysis is a real gap in Proposition 8.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 8 states total time O(T·polylog(n/ε)·κ·log(1/ε′)) for the full LQG pipeline, with κ=max(κ_R,κ_V). This formula only follows if every QSVT inversion and block-encoded product has normalization α=O(1) and bounded condition number. Neither is established. The paper's own block-encoding construction, Proposition 3, produces an (||A||_F, s, ε)-block encoding; for a dense n×n matrix with O(1) entries this gives α=Θ(√n), not α=1. Section I says α=1 is taken 'for simplicity', and Section V's inversion cost O(T_U·κ·log(1/ε′)) drops the α-dependence of QSVT, whose query complexity is linear in α. The difficulty compounds in the recursion: P_k and R_k are outputs of the algorithm, not given data, and Proposition 5 multiplies normalizations of successive block encodings. There is no analysis bounding ||P_k||, ||R_k||, κ_R, or κ_V over T steps; for an unstable A with large terminal cost or for a non-detectable Kalman setup these quantities can grow with T, making the per-step cost exponential in T. The Conclusion itself concedes that no error propagation analysis has been done. The consequence is not a minor constant: the claimed polylog(n) and linear-in-T scalings in the abstract and Proposition 8 are unsupported by the stated assumptions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13336,"tokens_out":9184,"duration_ms":114963,"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":[{"comment":"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.","section":"§I, §III-B, §V-A-d, Proposition 8"},{"comment":"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.","section":"§IV-A, §IV-B-c, §IV-C, Algorithms 2-4"},{"comment":"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.","section":"§IV-C, Algorithm 4 Phase III, §V"},{"comment":"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.","section":"§VI"}],"minor_comments":[{"comment":"The word 'relevent' should be 'relevant'.","section":"§III, introductory paragraph"},{"comment":"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.","section":"§V-C"},{"comment":"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.","section":"Algorithms 2-4"},{"comment":"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.","section":"Proposition 8"},{"comment":"Reference [12] is an arXiv preprint; if a peer-reviewed version exists, it should be cited instead of or in addition to the preprint.","section":"References"}],"recommendation":"reject","confidential_remarks":"The paper is essentially an application of known QSVT and block-encoding primitives to the LQG recursions. The advertised end-to-end speedup is the main contribution, and it is not established because normalization factors, condition-number evolution, and classical readout costs are not analyzed. These are not minor local gaps; they are structural to the claim. A resubmission would need to either track alpha and kappa through the recursions and include readout costs, or explicitly restrict the statement to an input/output model in which all of these costs are polylogarithmic. As it stands, the central claim is unsupported by the paper's own constructions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague —\n\nQuick take: this is a competent assembly of known quantum linear algebra primitives — the quantum Kalman filter from Shi et al. and QSVT-based inversion and multiplication — applied to finite-horizon LQG. The per-subroutine complexity estimates are standard and mostly correct as circuit-depth statements. What the paper does not do is back the end-to-end claim in the abstract and Proposition 8 that total runtime scales polylogarithmically in n and linearly in T.\n\nThe main gap is the normalization factor α. Proposition 3 block-encodes a matrix with α = ||A||_F, which for dense O(1)-entry matrices is Θ(√n). The text says \"for simplicity\" it often takes α=1, and Section V's inversion cost drops the α-dependence. QSVT query complexity is linear in α, so this is not a constant. The recursion creates P_k and R_k as outputs, not given data, and their norms and condition numbers are never bounded. Proposition 5 multiplies normalizations, so a single product can inflate α. Nothing rules out α or κ growing with T for an unstable A or large terminal cost. If they grow, the per-step cost stops being polylog(n), and the linear-in-T scaling is no longer meaningful.\n\nThere are also unaccounted I/O costs. The algorithm assumes matrices live in quantum-accessible data structures; loading dense matrices is a real cost not analyzed. The control inputs u_k are classical outputs; extracting them by measurement costs something, and the paper doesn't say what. The total runtime claim is therefore a circuit-depth estimate under optimistic assumptions, not an end-to-end runtime.\n\nCredit where due: the paper is transparent about its limitations, saying in the conclusion that no error propagation analysis has been done. The citations are appropriate, and the composition is not silly. The flaw is in the interpretation of the complexity formula as a full runtime guarantee.\n\nCould this be rescued? Yes, by re-scoping as a circuit-depth bound under explicit assumptions on α and κ, with I/O costs stated separately. As written, the headline claim is unsupported.\n\nThis is a paper someone in the quantum control area might want to read as an example of block-encoding complexity pitfalls, but I wouldn't cite it for its main claims. It deserves a serious referee only if the venue wants algorithm sketches with this level of analysis; otherwise a desk reject with a rewrite invitation is fair. My own verdict is reject as stated.","headline":"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.","tokens_in":13899,"tokens_out":3760,"would_cite":false,"duration_ms":40503,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","93E20","93E11"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["quantum LQG control","block encoding","QSVT","Riccati recursion","Kalman filter","quantum linear algebra","finite-horizon optimal control","quantum speedup"],"falsifier":"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$.","tokens_in":12827,"feed_emoji":"⚛️","tokens_out":7195,"duration_ms":73926,"temperature":0.7,"pith_summary":"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.","feed_headline":"Quantum LQG controller claims polylog scaling in system size","feed_subtitle":"Block encodings and QSVT aim to replace classical cubic scaling with a horizon-linear, dimension-polylogarithmic cost.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Originates the quantum linear-systems speedup that the block-encoding pipeline inherits and extends to matrix arithmetic.","marker":"[6]"},{"why":"Supplies QSVT, the polynomial transformation used for matrix inversion and the engine of the complexity analysis.","marker":"[7]"},{"why":"Provides the block-encoding definitions and the addition/multiplication rules used in the Riccati and Kalman recursions.","marker":"[8]"},{"why":"Quantifies the resources required to block-encode classical data, backing the assumption of polylogarithmic encoding cost.","marker":"[10]"},{"why":"Establishes block-encoded matrix powers and faster Hamiltonian simulation that underpin the arithmetic subroutines.","marker":"[11]"},{"why":"Gives the quantum Kalman filter via block encoding that the forward pass adapts and integrates into the LQG loop.","marker":"[12]"}],"fun_headline_variants":["Quantum LQG control with polylog dimension scaling","QSVT quantum solver for LQG control","Polylog quantum speedup for LQG control","Quantum LQG via block encodings and QSVT","Fast quantum LQG: polylog scaling in n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum LQG control with polylog dimension scaling","QSVT quantum solver for LQG control","Polylog quantum speedup for LQG control","Quantum LQG via block encodings and QSVT","Fast quantum LQG: polylog scaling in n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000225,"raw_usage":{"total_tokens":1461,"prompt_tokens":937,"completion_tokens":524,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":447}},"tokens_in":553,"tokens_out":524,"duration_ms":4524,"temperature":1.0,"reasoning_tokens":447,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:46:40.299925+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics,","cited_arxiv_id":null,"evidence_quote":"Supplies QSVT, the polynomial transformation used for matrix inversion and the engine of the complexity analysis."},{"cited_title":"Quantum resources required to block-encode a matrix of classical data,","cited_arxiv_id":null,"evidence_quote":"Quantifies the resources required to block-encode classical data, backing the assumption of polylogarithmic encoding cost."},{"cited_title":"A quantum algorithm for the Kalman filter using block encoding","cited_arxiv_id":"2404.04554","evidence_quote":"Gives the quantum Kalman filter via block encoding that the forward pass adapts and integrates into the LQG loop."}],"review_version":1}