{"id":"ce8f96f5-73fb-4f9e-8b18-5f182928ff1a","arxiv_id":"2508.02822","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"A quantum algorithm that block-encodes the solution to the Sylvester equation with near-linear condition-number complexity and logarithmic dimension and error dependence.","lead":"This paper presents a quantum algorithm to solve the linear matrix equation AX+XB=C, the Sylvester equation, by storing the solution in a block-encoded form. It matters because this could enable exponential speedups for extracting properties of the solution in control theory and physics applications.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Block-encoding construction presumes known normalization factor x; abstract gives no evidence x is efficiently computable, leaving claimed complexity and BQP-completeness unverified.","rationale":"The reader's weakest assumption correctly identifies the normalization factor x as a load-bearing prerequisite. My concern sharpens this: x is not merely a practical detail but a potential hidden cost that could invalidate the asymptotic complexity claims, and it is central to the BQP-completeness argument. Since the full text is unavailable, this cannot be resolved by reading the abstract alone. The verdict of UNVERDICTED remains appropriate: the paper's soundness is indeterminate until the derivation and definitions are inspected. I do not see grounds to move to ACCEPT or REJECT from the abstract alone. The concrete test I propose is the minimal check that would settle whether the concern lands.","tokens_in":661,"tokens_out":1932,"duration_ms":23646,"concrete_test":"In the full manuscript, locate the theorem stating the query and gate complexity of the block-encoding of X/x. Verify whether the theorem's assumptions include a classical or quantum oracle for x, or whether x is computed inside the algorithm. Independently re-derive the complexity including the cost of computing x; if the cost is non-negligible (e.g., requires solving the Sylvester equation), the headline complexity claim fails. Additionally, compute the condition number for the specific BQP-complete instances used in the reduction to confirm it is polynomially bounded; if it is exponential, the claimed efficient solution of BQP-complete problems does not follow.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that a quantum circuit block-encodes X/x with near-linear complexity in a condition number depending on A and B, and logarithmic in dimension and error. This presumes that the rescaling factor x is known or efficiently computable. If x is not supplied as an oracle and instead must be computed from A, B, and C, the cost of doing so may dominate the claimed complexity—especially if computing x is as hard as solving the Sylvester equation itself. The BQP-completeness claim amplifies this: solving a BQP-complete problem through this circuit would require x to encode a computationally hard quantity, yet the abstract does not state how x is obtained. Without a derivation showing that x can be computed efficiently (or that the complexity statement includes the cost of computing x), the central complexity bounds are unsupported. The condition number is also undefined in the abstract; if it can be exponentially large for the BQP-complete instances, the near-linear dependence would negate efficiency.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a quantum algorithm for solving the Sylvester equation AX+XB=C by constructing a block-encoding of the normalized solution matrix X/x. It asserts query and gate complexities that are almost linear in a condition number depending on A and B, and logarithmic in dimension and inverse error. It further claims that the resulting circuits can solve BQP-complete problems efficiently, and discusses applications, the Riccati equation, and open problems. This review is based solely on the abstract, as the full text was not available.","tokens_in":813,"tokens_out":1340,"duration_ms":15871,"significance":"If the complexity claims are correct, the algorithm would be a meaningful contribution to quantum linear algebra for matrix equations, potentially enabling exponential speedups for extracting certain properties of solutions. The connection to BQP-completeness is intriguing and, if substantiated, would demonstrate strong expressiveness. However, the significance is currently contingent on unresolved details, most importantly the cost of obtaining the normalization factor x and the precise definition and magnitude of the condition number. The paper would be strengthened by explicit, verifiable derivations of these points; the abstract alone does not establish the central complexity bound.","major_comments":[{"comment":"The abstract states that the solution matrix is produced as a block-encoding of X/x, where x is 'a rescaling factor needed for normalization,' but it does not state how x is obtained. If x must be computed from A, B, and C as part of the algorithm, its cost could dominate the claimed complexity—especially if computing x is as hard as solving the Sylvester equation itself. The authors should either specify an efficient oracle or procedure for x, or include its cost in the complexity statement.","section":"Abstract"},{"comment":"The claimed complexity is 'almost linear in a condition number that depends on A and B,' but the condition number is not defined. If this quantity is not bounded for the BQP-complete instances constructed later, the claimed efficiency may not follow. The abstract should define the condition number explicitly (for example, in terms of the spectra of A and B or the properties of the Sylvester operator) and state whether it remains polynomially bounded in the relevant instances.","section":"Abstract"},{"comment":"The abstract says the algorithm 'can solve BQP-complete problems efficiently.' This is a strong claim that needs careful qualification: it should specify the input model, how the problem is encoded into A, B, and C, and whether 'efficiently' means polynomial-time in the problem size and in the relevant error/condition parameters. Without this context, the claim is too broad to assess, especially given that the block-encoding model requires oracles whose implementation cost is not accounted for.","section":"Abstract"}],"minor_comments":[{"comment":"The phrase 'exponentially faster than would be possible from preparing X as a quantum state' is imprecise; it should clarify whether the speedup is in query complexity, gate complexity, or both, and under what oracle model this comparison is made.","section":"Abstract"},{"comment":"The term 'almost linear' is informal and should be replaced with a precise bound, such as O(κ^{1+o(1)}) or O(κ log^c κ), to allow verification.","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"This review is based on the abstract only, as the full manuscript was not provided. The central claims cannot be verified without the full proof and complexity derivations. The most critical gap is the treatment of the normalization factor x and the condition number; the BQP-completeness claim also requires a precise input model. I would be in a position to give a firmer recommendation after reviewing the full text."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a plausible extension of block-encoding quantum linear algebra to Sylvester equations, and the BQP-completeness connection is interesting. The abstract alone isn't enough to verify the complexity claims, but the paper warrants a serious referee.\n\nWhat's new: previous block-encoding work focused on linear systems Ax=b. Tackling the Sylvester equation AX+XB=C directly, and block-encoding the solution matrix, is a genuine step. The claimed complexities—near-linear in a condition number, logarithmic in dimension and error—are in line with the standard for quantum linear algebra. The BQP-completeness claim suggests the algorithm captures a broad class of problems, which is notable if the details hold.\n\nSoft spots: the abstract doesn't define the condition number or say how the normalization factor x is obtained. If x must be computed separately, the cost could dominate the query complexity; the stress-test note is right to flag this. Also, for BQP-complete instances, the condition number might be exponential, which would weaken the efficiency claim. These are exactly the kind of details referees should probe. That said, the authors (Somma, Low, Berry, Babbush) have a strong record in block-encoding and quantum signal processing, and the full paper will almost certainly address these points. The abstract is also honest in stating it's an 'approach' and discussing extensions and open problems.\n\nBottom line: I can't give a verdict from the abstract, but this deserves peer review. It's a solid subfield contribution if correct, and the BQP-completeness result would make it more than incremental. If you're running a reading group on quantum algorithms, I'd wait for the full text but keep it on the list.","headline":"Plausible and potentially important block-encoding result for Sylvester equations; referees should check the normalization factor and condition number details.","tokens_in":1295,"tokens_out":1850,"would_cite":false,"duration_ms":20428,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A quantum circuit solves the Sylvester matrix equation with near-linear cost in the condition number.","keywords":["Sylvester equation","quantum algorithm","block-encoding","linear matrix equation","quantum complexity","BQP-complete","condition number","Riccati equation"],"falsifier":"Exhibit a family of Sylvester equations with constant condition number but where every quantum block-encoding of $A$ and $B$ requires a number of elementary gates that grows polynomially with matrix dimension, so the construction's resource count exceeds the claimed polylogarithmic dimension dependence. Alternatively, show that computing the normalization factor $x$ from the inputs requires reading all entries of $C$, which would erase the exponential readout advantage for property estimation.","tokens_in":480,"feed_emoji":"🧮","tokens_out":4688,"duration_ms":53000,"temperature":0.7,"pith_summary":"This paper proposes a quantum algorithm that solves the linear matrix equation $AX+XB=C$ for complex matrices $A$, $B$, and $C$, with $X$ unknown. The solution is delivered as a block-encoding of a normalized matrix $X/x$, rather than as a quantum state, so that quantities such as individual entries or inner products of $X$ can be estimated exponentially faster in the precision than state-preparation approaches would allow. The resource count is almost linear in a problem-dependent condition number and logarithmic in both the matrix dimension and the target error. The authors argue the algorithm is powerful enough to solve BQP-complete problems, and they point to applications in control theory and physics as well as a natural extension to Riccati equations.","feed_headline":"Quantum solver for AX+XB=C runs near-linearly in condition number","feed_subtitle":"Block-encoding the solution lets entries of X be read out exponentially faster than state preparation.","key_machinery":"The central object is the block-encoding of the normalized solution matrix $X/x$: a unitary operator whose top-left block equals $X/x$ up to a known scale, so that overlap measurements recover entries and linear functionals of $X$. The argument builds this block-encoding from assumed block-encodings of $A$, $B$, and $C$ using quantum linear-algebra compilations, and the cost is governed by a condition number that depends on $A$ and $B$ rather than on the matrix dimension, which is why the complexity depends only polylogarithmically on the size. The block-encoding is the load-bearing data structure: it converts the linear matrix equation into a form where quantum linear-algebra subroutines apply, and it makes property extraction the final readout.","core_discovery":"The central claim is that the Sylvester equation, the continuous-time matrix equation $AX+XB=C$, can be solved by a quantum circuit that block-encodes the solution $X$ scaled by a normalization factor $x$. The block-encoding is a representation of a matrix inside a unitary that allows access to its entries through quantum measurements, and the authors show how to construct it with query and gate complexities scaling almost linearly in a condition number depending only on $A$ and $B$, and logarithmically in the dimension and inverse error. Because the output is a block-encoding rather than a state vector, the algorithm can evaluate properties of $X$ that are costly to extract from a prepared quantum state. The paper also shows that the resulting circuits can solve BQP-complete problems, which it reads as evidence that the approach captures substantial computational power.","pith_inferences":["If block-encodings of $A$ and $B$ can be built with size polylogarithmic in dimension, the same near-linear-in-condition-number complexity likely transfers to Lyapunov and discrete Sylvester equations, since they share the same generator structure.","The BQP-completeness statement suggests that the algorithm's cost is likely optimal up to polylogarithmic factors for a large family of instances, unless quantum complexity classes collapse.","A practical bottleneck will be computing the normalization factor $x$; if $x$ is not available in advance, the algorithm must estimate it, and that estimation cost is not counted in the stated complexity.","A testable extension is to apply the method to small discretized control-theory examples and compare the block-encoding readout precision against classical solves, checking the predicted logarithmic-in-dimension scaling."],"forward_implications":["For any observable or individual entry of $X$, the corresponding quantity can be estimated exponentially faster in the error than by preparing $X$ as a quantum state and sampling it.","The algorithm solves BQP-complete problems efficiently, meaning its expressive power matches the full power of quantum computation on the relevant class of instances.","Because the complexity is logarithmic in dimension, the method scales to very large Sylvester equations provided the condition number stays manageable.","The techniques extend toward solving the related Riccati equation, opening a path to quantum algorithms for nonlinear matrix equations."],"supporting_citations":[],"fun_headline_variants":["Quantum block-encoding solves Sylvester equation near-linearly","Near-linear condition time for quantum Sylvester solver","Exponential readout speedup from Sylvester block-encoding","Sylvester equation: quantum algorithm with almost linear queries","Quantum Sylvester solver achieves BQP-complete power efficiently"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm assumes the matrices $A$, $B$, and $C$ are available through efficient block-encoding oracles and that the normalization factor $x$ is known or cheap to compute; if either fails, the claimed near-linear-in-condition-number and logarithmic-in-dimension costs do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Quantum block-encoding solves Sylvester equation near-linearly","Near-linear condition time for quantum Sylvester solver","Exponential readout speedup from Sylvester block-encoding","Sylvester equation: quantum algorithm with almost linear queries","Quantum Sylvester solver achieves BQP-complete power efficiently"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000282,"raw_usage":{"total_tokens":1625,"prompt_tokens":856,"completion_tokens":769,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":472,"completion_tokens_details":{"reasoning_tokens":689}},"tokens_in":472,"tokens_out":769,"duration_ms":9520,"temperature":1.0,"reasoning_tokens":689,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T04:50:18.886676+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a family of Sylvester equations with constant condition number but where every quantum block-encoding of $A$ and $B$ requires a number of elementary gates that grows polynomially with matrix dimension, so the construction's resource count exceeds the claimed polylogarithmic dimension dependence. Alternatively, show that computing the normalization factor $x$ from the inputs requires reading all entries of $C$, which would erase the exponential readout advantage for property estimation.","supporting_citations":[],"review_version":1}