acceptodds
Under review as a conference paper at ICLR 2027

Same System, Fewer Measurements: Structured Variational Quantum Linear Solvers

Abstract

We introduce StructVQLS, a structure-based quantum linear solver exploiting recurring relations in widely used partial differential equation (PDE) discretizations for more accurate solutions with fewer measurements. On a heat system, GPU circuit-simulator experiments achieve 61.7% lower mean equation residual than merged exact Pauli at 512M measurements per run. Stable 1% residual is reached with StructVQLS, but not with Pauli within this budget in the evaluated cohort. In separate nonsymmetric convection-diffusion experiments, native sampling gives 50.6-60.9% lower mean residual than merged Pauli across two advection weights. Separate measurement emulation achieves 75% fewer measurements with lower final residual than merged Pauli in observed cross-budget comparisons. StructVQLS integrates exact operator completion, residual-preserving distributed coordination and weighted gradient estimation. Fixed stencil relations give grid-independent operator counts; coefficient weights control gradient noise. Common operator structure thus improves measurement efficiency.

Primary area:
applications to physical sciences (physics, chemistry, biology, etc.)
Keywords:
variational quantum algorithms, quantum linear solvers, structured operator decomposition, distributed optimization, finite-shot trainability, parabolic partial differential equations, CUDA-Q

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_HDfiOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper has a clear focus: replaces the Pauli LCU decomposition of a PDE discretisation with an LCU built from the stencil relations themselves. The key object is the Hermitian dilation of a partial signed permutation: for K relations the construction gives 2K+1 signed-permutation terms and K+1 unsigned skeletons independent of grid size, which specialises to 4d+1 terms for a d-dimensional Dirichlet heat operator. On top of this the paper adds a fixed-lift identity, a row-block residual decomposition for the distributed setting, a finite-shot variance and allocation analysis, and a control-variate estimator that reuses the previous update's shot counts. Experiments are circuit-simulator runs on heat and upwind convection-diffusion systems up to N = 32768 (15 qubits), plus a much larger emulation campaign.

Critical strengths
  1. I think the directed case is a real gap in the prior art. Previously people decompose σx ⊗ A, which is the same operator as D(A) only when A is symmetric. The paper's use of [[0, A], [Aᵀ, 0]] is the correct generalisation to nonsymmetric A, and I confirmed that the leading structural decomposition work for this operator class contains no treatment of advection, upwinding, or directed operators at all. Extending completion to partial signed permutations with unequal forward and backward weights is a defensible contribution.

  2. From the paper, the reporting discipline is better than the norm. The arithmetic is clean and reasonable.

Critical weaknesses
  1. The contribution claim is not adequately separated from prior art, and the closest competitor is never benchmarked. This is my main concern. The paper "Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians" already decompose σx ⊗ A for the d-dimensional Poisson problem into 4d+1 Hermitian, one-sparse, self-inverse operators, and they note the extension to sparse matrices with constant diagonals. Corollary 2 of this paper recovers that same count for the same case. The paper says so in one clause of Related Work, but Contribution (1) in the introduction reads as if the completion construction is new. The same applies to the completion machinery itself: Gnanasekaran & Surana introduce unitary completion for exactly this class of structured sparse matrices and, in §VII of the 2026 paper, explicitly analyse unitary completion against unitary dilation for partial-isometry terms. Their decomposition gives 2 log₂ n_x + 1 terms for the 1D Poisson equation and polylogarithmic scaling for heat and higher-dimensional systems. The paper cites this line of work in one sentence ("Sigma-basis methods provide compact operator access") and never compares constructions, term counts, coefficient norms, or shots-to-target. Since the thesis is that structured LCUs are measurement-efficient, the Sigma-basis decomposition is the comparison that matters most and it is absent. Contribution (1) is therefore not established as new in its current framing.

  2. I feel the experiments do not isolate the mechanism the paper claims. On the native N = 32768 heat study, StructVQLS and the direct-square control are statistically indistinguishable: S − D = −0.000142, interval [−0.003841, 0.003557], while both differ from merged Pauli. The direct-square arm is not a Pauli baseline; it compiles A² out of the same stencil relations (Eq. 15, 33 terms) and is a second short-coefficient-mass structured representation. So the gap against merged Pauli is evidence that a structured representation beats Pauli at matched shot budgets, which prior work already argues, and is not evidence for the 9-term linear completion specifically. The six-source study agrees (S-minus-D intervals span zero at all three sizes), and in the common-depth control at N = 32768 the direct-square arm is numerically better than StructVQLS (.01015 ± .0012 against .01226 ± .0029). The upwind studies and the cross-budget "75% fewer measurements" claim run S against M only, with no structured-square control. Until a factorised comparison exists that varies representation (Pauli / structured square / structured linear) against allocation on at least one nonsymmetric case, the reader cannot tell which ingredient produces the result.

  3. Several load-bearing objects are used before definition ("merged exact Pauli", "charged", "selected tasks", "native", S/(4C) efficiency, Q_local(9,1) = 222). The r versus R distinction is easy to lose across sections. Figure 5's headline percentages ("S error: 48.3% lower E") are computed from the two displayed hand-picked samples, while the cohort statistics in Section 4.3 are different numbers; the caption flags this, but the figure invites the wrong reading. The abstract places the native upwind figures and the emulated cross-budget figure in adjacent sentences, and the native/emulated distinction is load-bearing.

Questions for authors
  1. What exactly is new in Theorem 1 relative to "Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians" beyond the partial-signed-permutation and directed-interface cases? Please state the delta in the related work rather than leaving it to a single clause.

  2. Why is there no comparison against the Sigma-basis decomposition, which targets the same operator class and reports 2 log₂ n_x + 1 terms for the 1D Poisson case? For at least one shared system, please report term counts, coefficient ℓ1 mass, per-coordinate variances, and shots-to-target for both constructions.

7 comments

I clarify a typo in the summary part that native runs reach N = 32768 is on the heat system experiment, and the reported upwind native runs are at N = 256.

Please focus on Weaknesses 1 first and give clarification to existing works.

The full information of the two papers I mentioned in the Weakness 1 are as follows:

  1. Li, Hui-Min, Zhi-Xi Wang, and Shao-Ming Fei. "Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians." Physical Review A 108.3 (2023): 032418.

  2. Gnanasekaran, Abeynaya, and Amit Surana. "Efficient quantum access model for sparse structured matrices using linear combination of “things”." Physical Review A 113.2 (2026): 022437.

In the response, please focus on explaining the difference between the proposed solution and the methods in above two papers. Thanks!

AuthorsOpenReview ↗

Response to Reviewer HDfi: Contributions beyond Li and Sigma

Thank you for clarifying the comparisons with Li et al. and the Sigma construction, and for asking us to isolate the measurement mechanism and improve the presentation. Section and table references are to the revised manuscript.

1. Added value beyond Li and Sigma (Sections 2-3, 4.5).

StructVQLS (S) carries reusable directed relations through residual-preserving learning to lower measurement noise and gate cost.

Li et al. (2023) establish the symmetric Poisson 4d+1 count (paper). We extend it to partial signed-permutation relations: truncated stencils and directed interfaces with unequal forward/backward weights. For K distinct nonidentity unsigned supports and nonzero real coefficients, completion gives 2K+1 Hermitian involutions sharing K+1 permutation skeletons. The fixed lift D(A)=[[0,A],[A^T,0]] preserves the original residual and derivatives for nonsymmetric solves with reusable circuits.

Gnanasekaran and Surana (2026) provide general Sigma matrix access and completion, including nonsymmetric matrices (paper). We organize measurements around fixed spatial relations and carry them through quadratic, RHS, scale and coordination gradients, coefficient-aware allocation and distributed execution. On fixed-coefficient heat systems, S retains nine terms and coefficient mass 3; Sigma grows from 9 to 17 terms and mass 4 to 6. Sigma/S initial full-gradient variance rises from 2.61 to 10.44.

Section 2 credits Hogancamp et al. for first-derivative operators and Shen et al. for block-local coordination. D=structured direct square; M=merged Pauli.

2. Sigma: lower gradient noise (Section 4.5; K.2, Tables 34-36).

We supply all four requested metrics using Sigma's recursive construction (V.1), tensor-sum extension and projected measurements (VI.1): four paired starts/size, shared ansatz/optimizer, 512 updates, 1M shots/full gradient. CPU emulation has no reuse; rejected projections are charged zero-valued observations.

NTerms S / SigmaMass S/SigmaInitial variance S/SigmaFinal raw residual S/Sigma
169 / 93 / 40.0060433 / 0.01577600.023424 / 0.024882
649 / 133 / 50.0060156 / 0.03438650.027899 / 0.027968
2569 / 173 / 60.0060018 / 0.06263040.021228 / 0.021842

Variance is the mean initial full-gradient covariance trace. N=256 coordinate variances:

CoordinateSSigma
theta_00.00072551730.0071616319
theta_10.00072551740.0071616526
theta_20.00072544370.0070601333
theta_30.00072552360.0071616395
theta_40.00072552370.0071616725
theta_50.00072544090.0070584295
theta_60.00072552370.0071619339
log scale0.00092334090.0127032766

Paired endpoint 95% CIs for Sigma-S: [-0.001734, 0.004651], [-0.000890, 0.001028] and [-0.000792, 0.002020]. Stable 1% hits are 0/4 for both at every size; each path costs 512M shots (2.048B/method/size). Stability requires five passing checks ten updates apart and a passing endpoint. The measured benefit is lower gradient noise at the same objective and budget.

3. Nonsymmetric allocation (Section 4.5; Tables 37-38).

S improves on M under both policies: N=64, beta=.2 convection-diffusion, four paired starts, depth-three ansatz, 512 Adam updates, 1M shots/gradient. Coordinate allocation uses coefficients or a charged 5% pilot plus 95% fresh samples; within-coordinate rules are fixed. D represents A^T A with unequal boundary corrections.

AllocationS final raw residualD final raw residualM final raw residual
Coefficient0.0679580.0675450.094304
Charged pilot0.0694940.0688930.095303

S-M 95% CIs: [-0.048615, -0.004076] and [-0.047900, -0.003718]; S-D: [-0.000514, 0.001339] and [-0.001276, 0.002477]. Pilot-minus-coefficient interaction CIs: [-0.002333, 0.002710] for S-D and [-0.004641, 0.005714] for S-M. Both allocation policies retain the S-M gain in the 24-path control.

S/D both retain short heat coefficient masses: linear 3/3, quadratic 4.875/5.0. Eight paired native starts give S/D/M means 0.008505/0.008617/0.025050 and S-D interval [-0.002008, 0.001785]. At n=15, S uses 7.4%/9.8% lower expected CX than D on all-to-all/linear connectivity at rho=1: an additional circuit-cost benefit over D.

4. Definitions and presentation.

We clarified definitions in Sections 1, 3.3 and 4: merged exact Pauli, charged shots (pilots/fresh counts; past counts once), selected tasks and native GPU circuit-simulator sampling versus emulation. Section 3.2 defines Q_local(L,Delta), including Q_local(9,1)=222; Appendix F.1 defines S/(4C) using shots and summed maximum worker loads. Discretization r_k, raw residual r and aligned R are distinguished. Figure 5 (p. 8) uses each source's first registered start, labels percentages "example," and Section 4.3 reports cohort statistics.

Reviewer_nLBfOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes StructVQLS, a variational quantum linear solver for structured PDE operators. For operators described by fixed local relations, it constructs an exact signed-permutation decomposition of a Hermitian dilation, with a term count independent of grid size. The analysis covers residual-preserving lifts, an exact decomposition of the distributed row objective, and coefficient-dependent measurement-allocation and gradient-variance bounds. Experiments use GPU-based quantum-circuit sampling and measurement emulation on heat and nonsymmetric convection–diffusion systems. The main empirical finding is a lower original-system residual than the merged exact-Pauli baseline at matched measurement budgets in the reported experiments. Performance relative to the direct-square control is generally comparable.

Critical strengths

The main technical idea is the completion in Theorem 1. KK signed-permutation relations give a Hermitian operator with 2K+12K+1 terms, at any system size, while the Pauli decomposition keeps growing (Fig. 1). Theorem 3 shows that the lift preserves residuals and all parameter derivatives, and Theorem 4 gives the distributed objective exactly. At the largest tested scale (N=32768N{=}32768), StructVQLS reaches a mean residual of 0.0090 against 0.0236 for merged Pauli at matched budget, and 3 of 4 paired runs stabilize below 1% residual while merged Pauli reaches none (p. 7). What's more, Table 30 shows that the gain carries over to nonsymmetric operators.

Critical weaknesses

What the experiments show is better shot efficiency than the chosen merged-Pauli estimator. They do not show a lower total resource cost. In the normalized-objective study (Table 19), structured grouping needs about 46.8M CX gates per million-shot update, against 16.9M for both real ordered Pauli and ME grouping. Success rates in the 100-start cohort are similar (Table 18), and in the three-start native follow-up S reaches the target less often than ME (1/3 vs. 2/3, p. 30). Table 16 favors S, but on different, unnormalized circuits, so the conclusion depends on the compiler and the objective. There is no experiment on real hardware, and some emulated runs use 101810^{18}–102210^{22} shots. The baselines also leave out recent block-encoding work (arXiv:2608.19655), constant-term high-entanglement decompositions (Quantum Inf. Process., 2025), and a tridiagonal VQLS study on real hardware (arXiv:2412.04938). A broader efficiency claim would need these comparisons.

The dimension-independent variance bound is also more limited than the headline claim suggests. Appendix A.4 (p. 16) notes that keeping the coefficients fixed under backward-Euler refinement requires the time step to shrink with h2h^2. At a fixed physical time step, the coefficient mass and the variance envelope grow. The native headline comparisons also use only four paired starts per setting. Under a common protocol (Table 8), the advantage of S over D is not consistent across sizes, and at N=32768N = 32768 D has the lower mean residual. In Appendix E (p. 25), simply returning the prepared right-hand side comes close to the exact-gradient result for the smooth source. The right-hand-side baseline also achieves a lower residual than S at 2M shots for all three sizes (e.g. .03971 vs. .04536 at N=32768N = 32768).

Questions for authors
  1. Could you report for each representation the total CX count and wall time needed to reach a matched residual including failed restarts?
  2. How do accuracy and variance scale at a fixed physical time step rather than with fixed stencil coefficients?
  3. With more independent starts how does StructVQLS compare with block encoding, the high-entanglement decomposition, and the RHS-only baseline?
4 comments
AuthorsOpenReview ↗

Response to Reviewer nLBf: Matched comparisons, resource costs and fixed-time accuracy

Thank you for highlighting total resource costs, statistical robustness, the HED/BE and RHS-only comparisons, and accuracy at a fixed physical time step. Section and table references are to the revised manuscript.

StructVQLS (S) lowers cost MSE versus block encoding (BE) by 43-47%/59-60% at epsilon_2=1e-5/1e-4. D=direct square; M=merged Pauli.

1. Expanded starts and RHS-only (Section 4.1, Tables 32-33).

Heat: GPU circuit-simulator sampling, 512 updates, 1M shots/gradient, count reuse.

CohortS/D/M mean raw residualS/D/M stable 1% hits
New four pairs0.007980 / 0.008061 / 0.0265173/4 / 3/4 / 0/4
Combined eight pairs0.008505 / 0.008617 / 0.0250506/8 / 5/8 / 0/8

Combined 95% CIs: S-M [-.021805,-.011285]; S-D [-.002008,.001785]. Stable hits require five passing checks ten updates apart and a passing endpoint.

Appendix E's different ansatz (256 updates, 2M shots/gradient) gives S means 0.05660/0.04892/0.04536 versus RHS-only 0.05647/0.04579/0.03971. All 24 expanded native endpoints beat RHS-only, 0.039713, confirming improvement over the input.

2. HED and BE (Section 4.5).

S lowers gradient variance versus HED with shared N=64 heat matrix, residual objective, ansatz/optimizer, four starts, 512M shots/path. CPU-emulated HED/S means: .027832/.027899, paired 95% CI [-.001512,.001379], 0/4 stable 1% hits each. HED lowers CX; S lowers variance (K.5, Table 40).

At 1M attempts, S lowers expected CX from BE's 7.098B to .540B, all-to-all (499-626 versus 7098 CX/circuit). We adapt Dsouza et al.'s BE to A/3 at eight states. Both estimate

CG=1−∣u∣2/v,u=⟨b∣A∣ψ⟩,v=∣Aψ∣2C_G=1-|u|^2/v,\qquad u=\langle b|A|\psi\rangle,\quad v=\\|A\psi\\|^2

b is normalized. BE shares joint/marginal counts; S independently estimates real/imaginary overlap and norm with square-bias correction. 1M attempts cover the complete cost, including rejections. Moments include covariance/ratio bias, conditional on defined estimates; negligible failure tails.

Noisy precision (K.7, Tables 43-44, Figure 10). One-GPU density-matrix simulation adds depolarization after each CX/u gate, epsilon_1=epsilon_2/10, on the eight states.

CX noise epsilon_2S/BE MSE, 1M attemptsS/BE MSE, matched CX
1e-614.90-15.9512.16-14.33
1e-50.534-0.5700.533-0.567
1e-40.398-0.4080.398-0.408

State ranges; matched CX: BE 76,076 attempts, S 1M. MSE=(gate bias+sampling bias)^2+variance. Both have large bias at 1e-4. Both budgets show a crossover: BE's lower variance wins noiselessly and at 1e-6; S's lower gate bias gives better precision at the two higher levels.

Four paired BE/S CPU runs optimize F=rho^2 v-2 rho Re(u)+1 with learned scale: 512 Adam updates, 1M attempts/gradient, ideal gates. S/BE residuals: .027899/.027405, BE-S 95% CI [-.001457,.000469], 0/4 stable 1% hits each. Raw-gradient overlap uses 61,963 CX versus 7098 for source-objective C_G (K.6).

Section 2 adds Tosti Balducci et al. (2024) on tridiagonal term/depth tradeoffs and hardware results.

3. Costs including failed starts (Table 1; K.4).

All 67,232 n=15 circuits include preparation, controls and workspace/readout. At rho=1, S lowers expected CX versus M by 51.6%/48.9% on all-to-all/linear connectivity. Normalized local cost (Section 4.6): S uses 46.80M versus 16.92M CX per update for merged-equivalent (ME) grouping; native hits 1/3 versus 2/3. ME differs from raw-objective M.

Table 39 includes failures: hits charged to stable-window endpoints, non-hits to 512M shots; final confirmation makes it retrospective:

MethodHitsHit/censor shotsShots per observed successSummed update seconds
S6/83.034B505.67M8,758.2
D5/83.006B601.20M9,283.4
M0/84.096BUndefined718,914.6

Each completes 4.096B shots. Fresh-count hit/censor CX: 11.169/11.945/31.132T all-to-all and 47.465/52.125/125.358T linear (S/D/M). With process overhead: 8832.4/9355.9/720032.7 simulator seconds, summed across starts; excludes queue idle, validation and offline compilation.

4. Fixed physical time (Sections 3.3, 4.3; K.8, Tables 45-46).

At N=256, S lowers gradient variance (M/S=4.231) and reaches 5% continuum error in 3/4 starts versus M's 0/4 at equal 8.192B emulated shots/path. S/M errors are 4.968%/5.147% (SD .032%/.094%); exact-gradient mean 4.705%. Raising shots/gradient 1M to 4M lifts S hits 1/4 to 3/4; M stays 0/4.

Four paired starts: Delta t=1/400, T=1/100, four 512-update solves; each method propagates its field as classical RHS. 1M/4M shots/gradient cost 2.048B/8.192B shots/path. Shared-state M/S variance: .990/1.851/4.231 at N=16/64/256. All outcomes/discrete errors: Tables 45-46.

Fixed physical Delta t gives lambda_1=mu+4 sum_k kappa_k Delta t/h_k^2=O(h^-2). Bounded other scales/parameter count give a sufficient O(h^-8)/B variance envelope. Time T needs T/Delta t solves; fixed r needs O(h^-2).

Thank you for the additional experiments. However, my concern about the novelty remains, and the scope of the new experiments is limited. While I believe the work has publication value, I am not yet convinced that its contribution meets the bar for ICLR. I therefore maintain my score.

AuthorsOpenReview ↗

Training to a certified 1% solution at fixed time step

Thank you for clarifying that novelty and the scope of the evidence remain your concerns. Your original review asked whether the measurement savings survive the cost of training to a common accuracy, including unsuccessful starts. We tested that question directly in a strong-transport extension of StructVQLS.

End-to-end cost with the original circuit family. We kept the same eight-layer circuit at every training round and at output. Both trainers started from the same four states on a 16-cell problem at fixed time step 0.02 and flow strength 30,000. We required both a certified relative field error and an original-system relative residual of at most 1%, followed by delivery of one physical solution state. The new trainer succeeded on 4/4 starts. Our previous sector-coordinate trainer succeeded on 2/4 within 30 epochs. On the two starts where both succeeded, total logical CX fell from 2.60 trillion to 1.06 billion (2,457-fold), and single-thread circuit-simulator time from 594 s to 2.15 s (276-fold). This includes circuit preparation, fitting, checks and output retries. Charging all four starts, including both failures, gives 8.60 trillion CX for two returns versus 2.50 billion for four.

What changes in training. After removing the known Fourier phase from the operator, we measure the remaining coupling between frequency groups. Recording both the probe sign and the measured frequency gives the entire complex response of a group in two measurement batches, one per quadrature. That response supplies a target for the next circuit fit. Row-wise quantum Jacobi updates already exist (arXiv:2412.03939). The distinction is how measurement noise enters the physical field. On a fixed grid with a transported source and nonzero diffusion within the transport kernel, the whole-vector row estimator needs shots growing at least linearly with flow strength to maintain a fixed relative RMS error in one step from the solution. Under the sector contraction condition, our grouped estimator has a flow-independent sufficient shot budget for that step. In the four-start circuit test, the whole-vector row probe certified 0/4; splitting the same row measurement by frequency group certified 4/4.

Scope at 64 cells. With the same time step, uniform shot allocation certified neither start, although both final fields were within 1% on independent checking. We then allocated the same per-round CX ceiling according to each group's contribution to physical variance and its compiled cost per shot. Both starts certified, in 4.99 s and 7.71 s. Across the same 96 finite-shot emulation paths at this size (two flows, two sources, two initializations and 12 seeds), certification changed from 0/96 to 96/96. The method uses O(N) classical target coefficients, and a sparse classical solve with the same output delivery was faster on these small grids.

Given the matched end-to-end result and the test isolating the measurement mechanism, would you reconsider your novelty assessment and overall score?

AuthorsOpenReview ↗

A matched solve with the decomposition as the only change

Your question about total cost led us to hold the entire training procedure fixed and change only the operator circuit. We tested a new 256-cell directed grid with 64 distinct tile coefficients and one manufactured right-hand side. Five local factors represent it exactly at the smallest possible normalization. At that normalization any exact weighted-permutation expansion on the same register needs at least 65 terms.

All three implementations reached a 1% scale-aligned original-system residual from all 12 paired starts, following identical residual trajectories. Total CX per successful solve was 33.800 billion for the original workspace encoder, 2.988 billion for our joint compilation, and 2.980 billion when the workspace encoder also shared the grid operations. Our circuit uses two work qubits and the optimized comparator uses three.

We also ran immediate restarts, allowing three sweeps per attempt and six attempts per task. Each implementation made 30 attempts across eight tasks. Four tasks succeeded. Charging all 26 failed attempts, including every attempt spent on the four exhausted tasks, gave 11.117 versus 11.086 billion CX per success for ours and the optimized comparator. With one common calibrated CPU-simulator setting the corresponding times were 9.99 and 10.85 s. With the simulator default they were 23.06 and 18.62 s. The reproducible resource gain is one work qubit at nearly identical total CX and accuracy. This adds a heterogeneous operator and a restart-inclusive comparison to the evidence in our earlier reply.

Reviewer_4uvPOpenReview ↗
Rating
2
Confidence
4(+1)
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the measurement cost of variational quantum linear solvers (VQLS) for linear systems arising from PDE discretizations. StructVQLS completes local partial signed-permutation relations into Hermitian, self-inverse unitaries. Fixed Hermitian lifts preserve the original-system residual and its derivatives (Section 3.1, Theorems 1 and 3). The authors use this representation to construct complete residual-gradient estimators, coefficient-weighted measurement allocation, and a scheme for reusing past measurement counts. They also examine distributed residual coordination (Sections 3.2–3.3). Experiments compare StructVQLS with merged Pauli and direct-square representations under matched systems, ansätze, and optimization budgets. The clearest finite-shot improvements are over merged Pauli (Section 4).

Critical strengths

1. The comparison preserves the original optimization problem. Theorem 3 establishes that the fixed lifts preserve the original-system residual and its parameter derivatives. The different operator representations therefore yield the same exact objective and gradient; finite-shot differences are not confounded by a change of loss function. Section 3.3 and Appendix A.3 also account for the complete gradient, including the quadratic residual term, the linear right-hand-side term, and the learned scale.

2. The measurement mechanism is tested directly. The authors report both optimization outcomes and gradient-variance/RMSE measurements at fixed parameter points. They distinguish native GPU circuit-simulator sampling from measurement emulation. In the four paired native heat-system runs in Section 4.1, the mean final raw residual is 0.009030 for StructVQLS versus 0.02358 for merged Pauli. Appendix B (Table 3) also reports the small difference from direct-square. The paired design and fixed-point noise tests provide more informative evidence than endpoint comparisons alone.

Critical weaknesses

1. The incremental contribution beyond existing structured decompositions is not sufficiently established. Li et al. (2023) already obtained a 4d+14d+1-term self-inverse decomposition for Poisson operators, while Gnanasekaran and Surana (2024, 2026) studied compact quantum representations and access methods for structured sparse matrices (Section 2). Theorem 1 extends the construction to partial signed permutations and directed relations. These are concrete extensions, but a constant number of LCU terms for a fixed stencil is not, by itself, a sufficient novelty claim.

The experiments also leave the incremental benefit of this construction unclear. In Section 4.1 and Appendix B (Table 3), StructVQLS and direct-square achieve mean final raw residuals of 0.009030 and 0.009172, respectively. Their paired difference has a 95% confidence interval of [−0.003841, 0.003557][-0.003841,\,0.003557]. The multi-source experiments in Section 4.3 and Appendix D (Table 9) likewise show no consistent advantage over direct-square. The evidence strongly supports an improvement over merged Pauli, but does not clearly establish a corresponding advantage over another structure-aware representation.

2. Savings in LCU terms and logical shots do not establish lower end-to-end quantum execution cost. The 2K+12K+1 count in Theorem 1 is an LCU term count, not a circuit-depth or gate-count bound on restricted-connectivity hardware. The completed signed permutations still require index shifts, boundary-sign logic, and controlled implementations. In Appendix F.2 (Table 16), for eight data qubits, StructVQLS's expected CX count per sampled measurement increases from 943.86 with all-to-all connectivity to 2853.27 with linear connectivity. Under the separate normalized local objective in Appendix G.1 (Table 19), structured grouping uses approximately 46.80 million all-to-all CX gates per million shots, compared with 16.92 million for merged-equivalent grouping. Although this is not the main heat-system objective, it shows that fewer structured terms need not mean cheaper execution.

The main N=32768N=32768 results use GPU circuit-simulator sampling, without a unified compiled-resource comparison at that size that includes controlled operations, routing, and depth. Mesh refinement introduces another distinction. Equation (1) defines rk=κkΔt/hk2r_k=\kappa_k\Delta t/h_k^2, and Appendix A.4 notes that holding rkr_k fixed is not the same as holding the physical time step fixed. For time-dependent PDEs, the persistence of measurement savings must be assessed together with the discretization parameters and complete circuit costs.

Questions for authors
  1. What specific benefit do the directed completion in Theorem 1 and the associated measurement scheme provide beyond Li et al. (2023) and Gnanasekaran and Surana (2024, 2026)? Under the same objective and shot budget, what explains the similar performance of direct-square and StructVQLS in Sections 4.1 and 4.3?

  2. For the main N=32768N=32768 heat-system benchmark, can the authors provide a complete controlled-measurement circuit comparison of StructVQLS, direct-square, and merged Pauli, including CX counts, routing overhead, and depth under restricted connectivity, rather than only LCU term counts or logical shots?

  3. Under mesh refinement at fixed physical Δt\Delta t, rather than fixed rkr_k, how do the operator coefficients, gradient-estimation variance, and total measurement budget required to reach a specified physical time change?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 4uvP: Contributions, circuit costs and fixed-time accuracy

Thank you for asking us to clarify the contribution beyond existing decompositions, complete circuit costs, and refinement at a fixed physical time step. Section and table references are to the revised manuscript.

At n=15, StructVQLS (S) reduces expected CX versus merged Pauli (M) by 51.6%/48.9% on all-to-all/linear connectivity. D is structured direct square; BE is block encoding.

1. Complete n=15 circuit costs (Section 4.5, Table 1; Appendix K.4).

We compiled all 45/41/33,530 S/D/M observables at N=32768 on both topologies: 67,232 circuits. Including state/RHS preparation, controls, workspace and readout, coefficient-weighted u/cx results at rho=1 are:

MethodQubitsCX, all-to-all / linearDepth, all-to-all / linear
S183,681.55 / 15,645.695,453.43 / 13,306.35
D183,974.78 / 17,345.895,790.46 / 14,400.15
M16 or 177,606.62 / 30,630.6912,498.13 / 28,455.13

These per-measurement costs include routing; depth excludes readout. S also lowers CX versus D by 7.4%/9.8%. Linear routing multiplies CX by 4.250/4.364/4.027 for S/D/M, preserving the cost advantage. K.4 accounts for evolving training allocations.

Section 4.6 retains the normalized-local-objective comparison: S uses 46.80M versus 16.92M CX per 1M-shot update for merged-equivalent (ME) grouping.

Noisy precision (Section 4.5; Appendix K.7, Tables 43-44). Short relation circuits reduce whole-cost expected CX from BE's 7.098B to .540B at 1M attempts. Across eight N=64 states, S has 43-47%/59-60% lower normalized-cost MSE at CX depolarization epsilon_2=1e-5/1e-4, also winning at matched CX. GPU density-matrix simulation applies noise after each CX/u gate, epsilon_1=epsilon_2/10. All rejections are charged. MSE=(gate bias+sampling bias)^2+variance, conditional on defined estimates; failure tails are negligible. Both have large absolute bias at 1e-4. The comparison identifies a noise crossover: BE wins at 1e-6; S's lower gate bias yields better precision at the two higher levels.

2. Contribution and prior work (Sections 1-3).

For A=alpha_0 I+sum_s alpha_s R_s, K partial signed-permutation relations with distinct nonidentity unsigned supports and nonzero real coefficients give 2K+1 Hermitian involutions sharing K+1 permutation skeletons. This covers truncated stencils and directed interfaces with unequal forward/backward weights; coefficient/RHS changes reuse these circuits.

For D(A)=[[0,A],[A^T,0]], the fixed lift preserves the solve:

$ D(A)W_{\mathrm{in}}=W_{\mathrm{out}}A,\quad \|\rho Ax-b\|^2=\|\rho D(A)W_{\mathrm{in}}x-W_{\mathrm{out}}b\|^2 $

where W_in x=|1>x and W_out b=|0>b. Residuals and derivatives are preserved. The distributed row identity separates residual and nonnegative coordination penalty; complete gradients include quadratic, RHS, scale and coordination terms.

Li et al. establish the symmetric Poisson specialization and its 4d+1 count. Gnanasekaran and Surana provide general Sigma access and completion, including nonsymmetric A; Hogancamp et al. treat first-derivative operators. Our distributed formulation builds on Shen et al., making its residual/coordination decomposition explicit for these measurements.

S/D both have short coefficient masses: linear 3/3, quadratic 4.875/5.0. Eight paired GPU circuit-simulator starts give S/D/M raw residuals .008505/.008617/.025050; paired 95% CIs: S-D [-.002008,.001785], S-M [-.021805,-.011285]. Four paired nonsymmetric N=64 starts favor S over M under coefficient/pilot allocation (Section 4.1, K.1-K.3). Both structured estimators improve on M; S also reduces circuit cost versus D.

At fixed coefficients, S reuses relations and classically aggregates independent measurements as grids grow. BE coherently combines branches and selector preparation/uncomputation. We predict increasing noisy precision gains per CX as excess encoding work grows (Section 4.5).

3. Fixed physical time (Sections 3.3, 4.3; K.8, Tables 45-46).

At N=256, S lowers shared-state gradient variance (M/S=4.231) and reaches 5% continuum error in 3/4 starts versus M's 0/4 at equal 8.192B emulated shots/path. S/M errors are 4.968%/5.147% (SD .032%/.094%); exact-gradient mean 4.705%. Across N=16/64/256, M/S variance ratios are .990/1.851/4.231 and S coefficient masses 1.50/2.62/6.78.

Four paired starts use Delta t=1/400, T=1/100, four 512-update solves and each method's propagated field as classical RHS. 1M/4M shots/gradient cost 2.048B/8.192B shots/path. Tables 45-46 give all outcomes/discrete-reference errors.

With r_k=kappa_k Delta t/h_k^2, lambda_1=mu+4 sum_k r_k=O(h^-2). Bounded remaining scales and parameter count give a sufficient O(h^-8)/B variance envelope. Fixed physical time T requires T/Delta t solves; fixed r requires O(h^-2). These outcomes include propagated solver error.

Thank you for the additional experiments. However, I still find the novelty and experimental evidence limited. The improvements over other structure-aware baselines are not very convincing. I think the paper should focus more on the matrix decomposition itself, as the measurement allocation and subsequent optimization are fairly general techniques and do not need to be specifically designed for this problem. I therefore maintain my original rating.

AuthorsOpenReview ↗

What the matrix decomposition buys on a heterogeneous stencil

Thank you for asking us to isolate the contribution of the decomposition. Your direct-square comparison makes the question precise. On the original heat problem, both methods estimate the same residual objective, and direct-square already exploits the compact structure of the squared heat operator. Their paired final residuals are comparable. The benefit we can attribute to Theorem 1 there is that the completions of a directed relation share an index map. On the smooth 256-cell heat case, compiling that map once reduced a complete measurement circuit from 3,627 to 2,001 controlled-NOT (CX) gates with the same ideal measurement outcomes. Li et al. already establish the constant-term Poisson case, and Gnanasekaran and Surana provide general sparse access through Sigma factors. Li et al. Gnanasekaran and Surana

We followed your suggestion with a new decomposition result. Consider a periodic five-point grid with a different horizontal/vertical conductance ratio on each four-cell tile and directed circulation between tiles. On each tile, two conjugate unitary operations route a cell coherently to its horizontal and vertical neighbors. Their imaginary parts cancel, leaving exactly the required real weights. The same two operations serve every tile with its own angle. Adding the identity and the two circulation directions gives five local factors on the original register. Their total coefficient magnitude is 4, equal to the operator norm and therefore the smallest possible normalization. Local phase mixing has precedents, and Suresh gives constant-term encodings for two-phase periodic media. Here the number of distinct conductances grows with the grid. Local phase gates Suresh

The difference from weighted matching can be proved. After a checkerboard sign change, the matrix has nonnegative entries and every row sums to 4. At this normalization, each one-sparse factor must preserve the constant vector, forcing it to be a permutation. Every matrix entry must then be a subset sum of the same global weights. For N/4 tiles (a power of two), we give an explicit angle profile for which the matrix entries include N/4+1 rationally independent values. Thus every exact weighted-permutation expansion at this normalization needs at least N/4+1 terms. On the 256-cell example this gives five versus at least 65. Even allowing a matrix error of 0.004 in the maximum absolute row-sum norm and a normalization of 4.004 (both allowances are 0.1% of 4) still requires at least nine permutation terms. To isolate the effect of refinement, we fixed the same two materials on grids of side 8, 16 and 64. Five local factors and an explicit six-permutation construction both represented every matrix exactly at normalization 4. Weighted matching approach

We also tested direct-square on this same 256-cell matrix. We compiled 31 measurement settings for the directly expanded A⊤AA^\top A (7 to 14 CX per shot) and one for the source overlap (261 CX). The coherent loss uses one setting at 359 CX per shot. Both compiled implementations reproduced the same loss on all 24 test states to within 4×10−154\times10^{-15}. At equal total CX, even giving direct-square its variance-minimizing allocation across independent settings, the median predicted loss-variance ratio (direct-square / coherent) was 0.37 at the 12 initial states and 5,260 at the 12 states first reaching 1% residual in the coherent runs. Direct-square was more efficient at every start. Near a solution the coherent circuit counts a rare residual event, while the separate direct-square estimates retain noise as their means cancel. This fixed-state comparison identifies where the estimators differ. Training time is a separate endpoint.

We gave our workspace-based reference implementation the same coefficient access and coordinate-sharing optimization. On that same 256-cell matrix, our jointly compiled block uses 98 CX and two work qubits, and the optimized comparator uses 97 CX and three. We checked every column against the original operator. This gives a concrete reason to use the decomposition. It represents spatially varying coefficients with a fixed set of local factors and realizes that operator with one fewer work qubit at essentially the same gate cost. Would this result change your assessment of the decomposition's contribution?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.