Pith

open record

sign in

arxiv: 2607.06533 · v1 · pith:SSM753RG · submitted 2026-07-07 · math.NA · cs.NA

Quantum-inspired methods for finite-element discretizations of the high-dimensional Poisson equation

Xue Wang , James H. Adler , Xiaozhe Hu This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 reserved 2026-07-08 02:29 UTCglm-5.2pith:SSM753RGrecord.jsonopen to challenge →

classification math.NA cs.NA
keywords algorithmshigh-dimensionalquantumquantum-inspiredclassicalmethodspdescomplexity
0
0 comments X

The pith

Quantum-inspired classical solvers hit a wall on high-dimensional PDEs

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

The paper asks whether quantum-inspired classical algorithms — methods that borrow ideas from quantum computing but run on ordinary hardware — can match the exponential-in-dimension speedup that true quantum algorithms achieve when solving the Poisson equation discretized by finite elements. The authors answer negatively in two stages. First, they analyze randomized coordinate descent (RCD), the best-known quantum-inspired solver for sparse symmetric positive-definite systems, and prove tight upper and lower bounds showing its complexity scales as ε^{-(d+2)} (unpreconditioned) or ε^{-2d} (with multigrid preconditioning via an expanded system), both exponential in the dimension d. Second, and more broadly, they use communication complexity — specifically a reduction from the k-player Set-Disjointness problem — to prove that ANY quantum-inspired classical algorithm working within the sampling-and-query access model must make at least Ω(ε^{-2d}/(d log ε^{-1})) oracle calls to solve a linear system arising from a finite-element discretization of the Laplacian with pure Neumann boundary conditions on a uniform mesh. Since this lower bound is exponential in d, no such classical method can replicate the polynomial-in-d scaling that quantum algorithms achieve. The central mechanism is a reduction that encodes Set-Disjointness inputs into a specially constructed right-hand side of the Poisson system, exploiting the independent-set structure of the sparsity graph of the stiffness matrix.

Core claim

The paper's core result is a general lower bound (Theorem 4.9): any quantum-inspired classical algorithm operating in the sampling-and-query model that solves the Laplace equation (pure Neumann conditions, linear finite elements, uniform mesh) must make at least Ω(ε^{-2d}/(d log ε^{-1})) calls to its sampling and query oracles. This is exponential in dimension d and matches the curse of dimensionality, establishing an asymptotic separation from quantum algorithms whose complexity is poly(d)·ε^{-3}·polylog(1/ε). The reduction works by constructing a specific right-hand side from k-player Set-Disjointness inputs, using an independent set of size k = Θ(N/d) in the sparsity graph of the discrete

What carries the argument

The reduction from k-player Set-Disjointness to solving a Poisson linear system. The construction picks an independent set of size k = Θ(N/d) in the sparsity graph of the stiffness matrix, encodes Set-Disjointness bit-strings into a specially chosen solution vector u*, and defines the right-hand side f = h^{d-2} G^T B^T b so that solving Au = f is equivalent to solving the Set-Disjointness problem. Communication complexity lower bounds (Proposition 4.5) then transfer to oracle-call lower bounds for any SQ-model algorithm. For the RCD-specific results, the key machinery is the scaled condition number κ_F(A) = ||A||_F^2/λ_min(A) and its analogues for the expanded (multigrid-preconditioned)系统.

If this is right

  • For high-dimensional elliptic PDEs discretized by finite elements, quantum-inspired classical algorithms cannot replace quantum algorithms if the goal is to overcome exponential scaling in dimension.
  • The separation between classical quantum-inspired methods (exponential in d) and quantum methods (polynomial in d) is now established for a concrete, widely-used PDE model, not just for abstract linear algebra problems.
  • Preconditioning via multigrid does not close the gap: the expanded-system analysis shows RCD still scales exponentially in d even with optimal conditioning.
  • The lower bound technique — reducing Set-Disjointness through the independent-set structure of FEM sparsity graphs — may be adaptable to other elliptic operators or discretization schemes to prove similar barriers.

Load-bearing premise

The general lower bound is proven for one specific instance: pure Neumann boundary conditions on a uniform mesh with linear elements, and the construction fixes the stiffness matrix A while varying only the right-hand side. The claim that the bound covers algorithms that exploit structure in A beyond the sampling-and-query model is asserted but not separately proven, and there is a gap between the RCD upper bound (ε^{-(d+2)}) and the general lower bound (ε^{-2d}) that leaves

What would settle it

A quantum-inspired classical algorithm, operating within the sampling-and-query access model, that solves the specified Poisson instance (Neumann, linear FEM, uniform mesh) in time polynomial in d and polynomial in 1/ε. Alternatively, a proof that the independent-set construction or the reduction from Set-Disjointness can be circumvented by exploiting additional structure of the stiffness matrix A that the current lower-bound argument does not account for.

read the original abstract

In recent years, quantum linear system algorithms have been applied to partial differential equations (PDEs), particularly in high-dimensional settings, demonstrating an exponential speedup in dimension. Concurrently, randomized and quantum-inspired classical linear solvers have emerged, showing computational complexity comparable to their quantum counterparts in many application areas. In this paper, we investigate the applicability of these quantum-inspired classical algorithms to PDEs. We provide both upper and lower bounds on their computational complexity, proving that these methods cannot achieve exponential speedup in dimension for discretizations of high-dimensional Poisson problems. Our theoretical findings definitively demonstrate that quantum-inspired classical algorithms are not competitive with quantum algorithms for solving PDEs, confirming that quantum methods retain a significant advantage for high-dimensional problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 5 minor

Summary. This paper studies whether quantum-inspired classical algorithms can achieve exponential speedup in dimension for finite-element discretizations of the high-dimensional Poisson equation. Two types of results are presented. First, the randomized coordinate descent (RCD) method is analyzed for both the original stiffness system and an expanded (multigrid-preconditioned) system, yielding upper and lower complexity bounds that are both exponential in the dimension $d$ (Theorems 3.3, 3.5, 3.8, 3.10). Second, a general lower bound is established via communication complexity (Theorem 4.9): any quantum-inspired classical algorithm solving the Laplace equation with pure Neumann conditions on a uniform mesh with linear elements requires at least $Ω(ε^{-2d}/(d log(ε^{-1})))$ oracle calls. The paper concludes that quantum-inspired classical algorithms cannot match the exponential-in-$d$ speedup of quantum algorithms for PDEs.

Significance. The paper addresses a timely and well-posed question at the interface of quantum and classical computing for PDEs. The RCD-specific bounds (Section 3) are derived cleanly from the Leventhal–Lewis convergence theory and standard FEM eigenvalue estimates, and the idea of using the expanded multigrid system to represent preconditioning within the RCD framework is a nice technical contribution. The general lower bound (Theorem 4.9) via a Set-Disjointness reduction is the most ambitious part of the paper and, if the access-model gap is resolved, would provide a meaningful separation result. The paper provides falsifiable, concrete complexity bounds rather than vague claims.

major comments (3)
  1. §4.1, Theorem 4.9 and the surrounding construction: The lower bound is established for algorithms with access to SQ(BG) and SQ(b), where B and b are constructed objects (Eqs. 4.2–4.3). However, the standard quantum-inspired linear system framework (cf. [28]) operates on SQ(A) and SQ(f), where A = h^{d-2} G^T G is the fixed stiffness matrix and f = h^{d-2} G^T B^T b is the right-hand side. The paper does not show that SQ(f) = SQ((BG)^T b) can be simulated from SQ(BG) and SQ(b) with bounded communication overhead per access. Without this simulation step, the lower bound for the least-squares formulation (4.4) does not directly transfer to algorithms that solve Au = f using the standard SQ(A)/SQ(f) oracle interface. This is a load-bearing gap for the central claim of Theorem 4.9 and should be addressed, either by providing the simulation argument or by clarifying the scope of the lowerbound
  2. §4.1, Theorem 4.9 vs. §3: The general lower bound is proven for pure Neumann boundary conditions (where A is singular), while the RCD upper and lower bounds in Section 3 are for mixed boundary conditions (where A is SPD). The paper does not analyze RCD for the pure Neumann case, so it is unclear whether the general lower bound (ε^{-2d}) is consistent with what RCD would achieve on the same problem instance. This mismatch should be discussed, at minimum to clarify whether the upper and lower bounds are being computed for comparable problems.
  3. Remark 4.10: The claim that Theorem 4.9 'covers any quantum-inspired classical algorithm that uses preconditioning' is asserted but not proven. The construction fixes the matrix A and varies only the right-hand side f. Algorithms that exploit structural properties of A beyond the SQ model (e.g., using the known sparsity pattern or multilevel hierarchy) might evade the bound. The remark should either be supported with a proof or softened to reflect that the lower bound applies to algorithms operating within the SQ(BG)/SQ(b) access model on the specific constructed instance.
minor comments (5)
  1. Abstract: The phrase 'definitively demonstrate' is stronger than what the results support, given the scope limitations of Theorem 4.9 (specific boundary conditions, specific access model). Consider softening.
  2. §2.2: The complexity comparison between classical FEM (O(ε^{-(d+1)})) and quantum FEM (O(ε^{-3})) is presented without discussing state preparation costs or the cost of reading out the solution, which are known caveats for quantum linear system algorithms applied to PDEs. A brief acknowledgment would improve balance.
  3. §3.2, Theorem 3.8: The cost analysis exploits the fact that u_0 = 0 implies u^i is at most i-sparse, giving O(k^2) total cost. This is a clever observation but should be more prominently flagged, as it is a special property of the zero initial guess that may not hold in practice.
  4. The gap between the RCD upper bound (ε^{-(d+2)} for the unpreconditioned case) and the general lower bound (ε^{-2d}) is noted but not discussed in terms of whether tighter analysis could close it. A sentence in the conclusions acknowledging this gap would be appropriate.
  5. Reference [17] (Jiang–Park–Xu) is cited as an arXiv preprint from 2025; verify whether a published version exists.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for a careful and constructive report. The referee raises three major comments, all focused on Section 4 and the scope of Theorem 4.9. We agree that the access-model gap identified in the first comment is a genuine issue that must be addressed in revision, and we will both add the missing simulation argument and clarify the scope of the lower bound where the simulation does not directly transfer. The boundary-condition mismatch (comment 2) is a legitimate observation that we will discuss explicitly. The overclaim in Remark 4.10 (comment 3) is correct; we will soften the remark. We provide detailed responses below.

read point-by-point responses

  1. Referee: §4.1, Theorem 4.9 and the surrounding construction: The lower bound is established for algorithms with access to SQ(BG) and SQ(b), where B and b are constructed objects (Eqs. 4.2–4.3). However, the standard quantum-inspired linear system framework (cf. [28]) operates on SQ(A) and SQ(f), where A = h^{d-2} G^T G is the fixed stiffness matrix and f = h^{d-2} G^T B^T b is the right-hand side. The paper does not show that SQ(f) = SQ((BG)^T b) can be simulated from SQ(BG) and SQ(b) with bounded communication overhead per access. Without this simulation step, the lower bound for the least-squares formulation (4.4) does not directly transfer to algorithms that solve Au = f using the standard SQ(A)/SQ(f) oracle interface.

    Authors: The referee correctly identifies a gap in the current presentation. The lower bound in Theorem 4.9 is established for algorithms operating with SQ(BG) and SQ(b) on the least-squares formulation (4.4), while the standard quantum-inspired framework of [28] operates on SQ(A) and SQ(f) for the normal equations Au = f. We will address this in two ways in the revision. First, we note that SQ(A) is straightforward: A = h^{d-2} G^T G is a fixed, public matrix determined by the mesh, so SQ(A) requires no communication. The substantive question is whether SQ(f) = SQ((BG)^T b) can be simulated from SQ(BG) and SQ(b) with bounded overhead. In the coordinator model, each entry f(j) = h^{d-2} (BG)^T(j,:) b = h^{d-2} sum_i (BG)(j,i) b(i) involves a sum over the nonzeros of the j-th column of BG. Since each column of BG has O(delta_max) = O(d) nonzeros (inherited from the sparsity of G), each entry query to f costs O(d) SQ(BG) queries and O(d) SQ(b) queries, giving O(d) communication overhead per entry. The norm ||f|| can be computed as ||f|| = h^{d-2} ||BG||_F ||b|| in the special case B^T B = I, where ||BG||_F is public (depending only on G and the public structure of B). For sampling from the distribution defined by f, the situation is more subtle: a direct simulation of SQ(f) from SQ(BG) and SQ(b) may incur overhead proportional to the column sparsity, which is O(d) and thus bounded. We will add this simulation argument as a lemma and clarify that the overhead is polynomial in d, which does not affect the exponential-in-d lower bound. Second, we will add an explicit remark clarifying that the lower bound applies to the least-squares formulation (4.4) with the SQ(BG)/SQ(b) interface, and that the transfer to the SQ(A)/SQ(f) interface holds with O(d) overhead per oracle call, which is revision: no

  2. Referee: §4.1, Theorem 4.9 vs. §3: The general lower bound is proven for pure Neumann boundary conditions (where A is singular), while the RCD upper and lower bounds in Section 3 are for mixed boundary conditions (where A is SPD). The paper does not analyze RCD for the pure Neumann case, so it is unclear whether the general lower bound (ε^{-2d}) is consistent with what RCD would achieve on the same problem instance. This mismatch should be discussed.

    Authors: The referee is correct that the boundary conditions differ between Section 3 (mixed, A SPD) and Section 4 (pure Neumann, A singular). We will add a discussion of this mismatch. The key points are: (1) For the pure Neumann case, A is symmetric positive semi-definite with a one-dimensional null space (constants). RCD can be applied to the restricted system on the orthogonal complement of the null space, and the convergence theory of Leventhal–Lewis applies with lambda_min replaced by the smallest nonzero eigenvalue. The eigenvalue estimates in Remark 3.2 carry over, since the smallest nonzero eigenvalue of the pure Neumann stiffness matrix is also Theta(poly(d) h^d) by the Poincaré inequality. Thus the RCD upper and lower bounds in Theorems 3.3 and 3.5 would hold with the same asymptotic scaling for the pure Neumann case. (2) The general lower bound of Theorem 4.9 gives Omega(epsilon^{-2d} / (d log(epsilon^{-1}))), while the RCD lower bound from Section 3 gives Omega(poly(d) epsilon^{-d} log(epsilon^{-1})). These are not directly comparable because they measure different things: the Section 3 lower bound is specific to RCD and counts iterations, while the Theorem 4.9 lower bound applies to any SQ-model algorithm and counts oracle calls. The gap between epsilon^{-d} and epsilon^{-2d} may reflect the difference between algorithm-specific and general lower bounds, or it may indicate that the general bound is not tight for RCD. We will state this explicitly rather than claim the bounds are tight against each other. revision: no

  3. Referee: Remark 4.10: The claim that Theorem 4.9 'covers any quantum-inspired classical algorithm that uses preconditioning' is asserted but not proven. The construction fixes the matrix A and varies only the right-hand side f. Algorithms that exploit structural properties of A beyond the SQ model (e.g., using the known sparsity pattern or multilevel hierarchy) might evade the bound. The remark should either be supported with a proof or softened.

    Authors: The referee is correct. The claim in Remark 4.10 is too strong as stated. The lower bound in Theorem 4.9 applies to algorithms operating within the SQ(BG)/SQ(b) access model on the specific constructed instance. Algorithms that exploit structural properties of A beyond what is captured by the SQ model—such as direct access to the sparsity pattern, the multilevel hierarchy, or other problem-specific structure—could potentially evade the bound. We do not have a proof that covers such algorithms. In the revision, we will soften Remark 4.10 to state that the lower bound applies to quantum-inspired classical algorithms operating within the SQ access model on the constructed instance, and that extending the lower bound to algorithms that exploit additional structure of A is an open problem. We will also note that the RCD analysis in Section 3, which does exploit the sparsity structure of A, still yields exponential-in-d complexity, providing evidence that structural exploitation alone does not suffice to overcome the curse of dimensionality—but this is not the same as a general lower bound for such algorithms. revision: no

Circularity Check

0 steps flagged

No significant circularity found. The derivation chain rests on independent external results, and the one self-citation is non-load-bearing.

full rationale

The paper's two-part derivation is self-contained against external benchmarks. Part 1 (RCD bounds, Section 3) substitutes FEM-specific eigenvalue and trace estimates (Eqs. 3.2–3.3, from Brenner–Scott [6] and Jiang–Park–Xu [17], both independent) into the RCD convergence rate of Leventhal–Lewis [19] (Lemma 3.1, independent). The upper and lower bounds (Theorems 3.3–3.10) follow by direct algebraic manipulation of these cited results—no parameter is fitted to data and then 'predicted.' Part 2 (general lower bound, Section 4) builds on the communication complexity framework of Phillips–Verbin–Zhang [24] (Prop. 4.5) and Mande–Shao [21] (Prop. 4.6), both independent. The reduction from Poisson to Set-Disjointness (§4.1) is an original construction: the paper constructs a specific right-hand side f = h^{d-2}G^T B^T b and matrix B (Eqs. 4.2–4.3) to encode the Set-Disjointness inputs, then invokes the known Θ(kn) communication lower bound (Prop. 4.5) to obtain Corollary 4.8 and Theorem 4.9. This is a genuine reduction, not a circular restatement. The one self-citation, [16] (Hu–Xu–Zikatanov), is used only for motivation of the probability choice p_i = 1/Ñ in the expanded-system RCD analysis (Section 3.2); the convergence proof (Theorem 3.6) is carried out in full within the paper and does not depend on [16] as a load-bearing theorem. The skeptic's concerns about the access-model gap (SQ(BG)/SQ(b) vs. SQ(A)/SQ(f)) and the preconditioning claim (Remark 4.10) are correctness/completeness issues, not circularity: they concern whether the lower bound applies as broadly as claimed, not whether the bound itself is tautological. No step in the chain reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

No free parameters are fitted or tuned. No new entities (particles, forces, dimensions) are postulated. The axioms are standard results from FEM theory, communication complexity, and graph theory, all sourced to external references. The main domain assumption is that the SQ-access model captures the relevant class of quantum-inspired algorithms, which is the standard assumption in this literature.

axioms (5)
  • domain assumption The SQ (sampling and query) access model of Chia et al. [7] correctly captures the class of quantum-inspired classical algorithms.
    Section 4 restricts to algorithms using SQ access; algorithms outside this model are not covered by the lower bound.
  • standard math Standard FEM eigenvalue estimates: λ_min(A) = Θ(poly(d)N^{-1}), tr(A) = Θ(dN^{2/d}), κ(A) = Θ(poly(d)N^{2/d}) for the d-dimensional Poisson stiffness matrix.
    Used in equations 3.2–3.3 and throughout Section 3; sourced from Brenner-Scott [6] and Jiang-Park-Xu [17].
  • domain assumption The condition number of the MG-preconditioned expanded system satisfies κ(D̃^{-1}Ã) = Θ(poly(d)) for the Laplacian.
    Used in Remark 3.7 and Theorem 3.8; sourced from Griebel-Hullmann [14] and Bramble-Pasciak-Xu [4].
  • standard math The k-player Set-Disjointness problem requires Θ(kn) communication for n ≥ 3200k.
    Proposition 4.5, sourced from Phillips-Verbin-Zhang [24].
  • domain assumption The greedy maximal independent set of the FEM sparsity graph has size k = Θ(N/d).
    Used in the proof of Theorem 4.9 to set k and derive the final lower bound; standard graph theory result applied to the specific graph structure.

pith-pipeline@v1.1.0-glm · 21211 in / 3569 out tokens · 585025 ms · 2026-07-08T02:29:59.882375+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 2 internal anchors

  1. [1]

    Research in the Mathematical Sciences , volume=

    Randomized and fault-tolerant method of subspace corrections , author=. Research in the Mathematical Sciences , volume=. 2019 , publisher=

    work page 2019

  2. [2]

    Mathematics of computation , volume=

    Parallel multilevel preconditioners , author=. Mathematics of computation , volume=

    work page

  3. [3]

    A polynomial dimension-dependence analysis of Bramble--Pasciak--Xu preconditioners

    A polynomial dimension-dependence analysis of Bramble--Pasciak--Xu preconditioners , author=. arXiv preprint arXiv:2512.06166 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  4. [4]

    Quantum preconditioning method for finite difference discretizations of the Poisson equation via Schr\"odingerization

    Quantum preconditioning method for linear systems problems via Schr " odingerization , author=. arXiv preprint arXiv:2505.06866 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    Quantum , volume=

    Variational quantum linear solver , author=. Quantum , volume=. 2023 , publisher=

    work page 2023

  6. [6]

    ACM Transactions on Quantum Computing , volume=

    Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm , author=. ACM Transactions on Quantum Computing , volume=. 2022 , publisher=

    work page 2022

  7. [7]

    Physical review letters , volume=

    Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing , author=. Physical review letters , volume=. 2019 , publisher=

    work page 2019

  8. [8]

    Singular Phenomena and Scaling in Mathematical Models , pages=

    On a multilevel preconditioner and its condition numbers for the discretized Laplacian on full and sparse grids in higher dimensions , author=. Singular Phenomena and Scaling in Mathematical Models , pages=. 2013 , publisher=

    work page 2013

  9. [9]

    SIAM Journal on Scientific Computing , volume=

    Multilevel algorithms considered as iterative methods on semidefinite systems , author=. SIAM Journal on Scientific Computing , volume=. 1994 , publisher=

    work page 1994

  10. [10]

    Quantum , volume=

    An improved quantum-inspired algorithm for linear regression , author=. Quantum , volume=. 2022 , publisher=

    work page 2022

  11. [11]

    Physical Review Letters , volume=

    Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions , author=. Physical Review Letters , volume=. 2021 , publisher=

    work page 2021

  12. [12]

    Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages=

    A quantum-inspired classical algorithm for recommendation systems , author=. Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages=

    work page

  13. [13]

    2008 , publisher=

    The mathematical theory of finite element methods , author=. 2008 , publisher=

    work page 2008

  14. [14]

    Mathematics of Operations Research , volume=

    Randomized methods for linear constraints: convergence rates and conditioning , author=. Mathematics of Operations Research , volume=. 2010 , publisher=

    work page 2010

  15. [15]

    Physical Review A , volume=

    Quantum algorithms and the finite element method , author=. Physical Review A , volume=. 2016 , publisher=

    work page 2016

  16. [16]

    ACM Transactions on Quantum Computing , volume=

    Faster quantum-inspired algorithms for solving linear systems , author=. ACM Transactions on Quantum Computing , volume=. 2022 , publisher=

    work page 2022

  17. [17]

    Error analysis for finite element operator learning methods for solving parametric second-order elliptic PDEs , author=

    work page

  18. [18]

    Proceedings of the 42nd International Conference on Machine Learning (ICML) , year=

    Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent , author=. Proceedings of the 42nd International Conference on Machine Learning (ICML) , year=

    work page

  19. [19]

    Quantum , volume=

    Lower bounds for quantum-inspired classical algorithms via communication complexity , author=. Quantum , volume=. 2025 , publisher=

    work page 2025

  20. [20]

    Proceedings of the eleventh annual ACM symposium on Theory of computing , pages=

    Some complexity questions related to distributive computing (preliminary report) , author=. Proceedings of the eleventh annual ACM symposium on Theory of computing , pages=

    work page

  21. [21]

    Theoretical computer science , volume=

    Quantum communication and complexity , author=. Theoretical computer science , volume=. 2002 , publisher=

    work page 2002

  22. [22]

    2020 , publisher=

    Communication complexity: and applications , author=. 2020 , publisher=

    work page 2020

  23. [23]

    Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=

    Lower bounds for number-in-hand multiparty communication complexity, made easy , author=. Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2012 , organization=

    work page 2012

  24. [24]

    Journal of the ACM , volume=

    Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning , author=. Journal of the ACM , volume=. 2022 , publisher=

    work page 2022

  25. [25]

    Physical review letters , volume=

    Quantum algorithm for linear systems of equations , author=. Physical review letters , volume=. 2009 , publisher=

    work page 2009

  26. [26]

    APS March Meeting Abstracts , volume=

    Quantum linear systems algorithm with exponentially improved dependence on precision , author=. APS March Meeting Abstracts , volume=

    work page

  27. [27]

    Physical review letters , volume=

    Preconditioned quantum linear system algorithm , author=. Physical review letters , volume=. 2013 , publisher=

    work page 2013

  28. [28]

    Physical Review A , volume=

    Variational quantum algorithms for nonlinear problems , author=. Physical Review A , volume=. 2020 , publisher=

    work page 2020

  29. [29]

    Journal of Physics A: Mathematical and Theoretical , volume=

    High-order quantum algorithm for solving linear differential equations , author=. Journal of Physics A: Mathematical and Theoretical , volume=. 2014 , publisher=

    work page 2014

  30. [30]

    SIAM Journal on Computing , volume=

    Quantum algorithm for systems of linear equations with exponentially improved dependence on precision , author=. SIAM Journal on Computing , volume=. 2017 , publisher=

    work page 2017

  31. [31]

    Werschulz, Arthur G , year=

    work page

  32. [32]

    1996 , publisher=

    Ritter, Klaus and Wasilkowski, Grzegorz W , journal=. 1996 , publisher=

    work page 1996

  33. [33]

    2003 , publisher=

    Iterative methods for sparse linear systems , author=. 2003 , publisher=

    work page 2003

  34. [34]

    SIAM Journal on Scientific Computing , volume=

    A sparse approximate inverse preconditioner for the conjugate gradient method , author=. SIAM Journal on Scientific Computing , volume=. 1996 , publisher=

    work page 1996

  35. [35]

    Science , volume=

    Materials challenges and opportunities for quantum computing hardware , author=. Science , volume=. 2021 , publisher=

    work page 2021

  36. [36]

    EPJ Quantum Technology , volume=

    Neutral atom quantum computing hardware: performance and end-user perspective , author=. EPJ Quantum Technology , volume=. 2023 , publisher=

    work page 2023

  37. [37]

    Quantum linear system solvers: A survey of algorithms and applications , author =. Rev. Mod. Phys. , volume =. 2026 , month =. doi:10.1103/x6gh-d8gh , url =

    work page doi:10.1103/x6gh-d8gh 2026