Are Randomized Quantum Linear Systems Solvers Practical?

• URL: http://arxiv.org/abs/2510.13766v1
• Date: Wed, 15 Oct 2025 17:12:55 GMT
• Title: Are Randomized Quantum Linear Systems Solvers Practical?
• Authors: Siddharth Hariprakash, Roel Van Beeumen, Katherine Klymko, Daan Camps,
• Abstract summary: randomized quantum algorithms have been proposed in the context of quantum simulation and quantum linear algebra.<n>We provide explicit bounds on all relevant parameters that control the total error for a randomized quantum linear systems solver.<n>Our work serves as a bridge between theoretical algorithmic proposals and efficient hardware implementations.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Randomized quantum algorithms have been proposed in the context of quantum simulation and quantum linear algebra with the goal of constructing shallower circuits than methods based on block encodings. While the algorithmic complexities of such randomized schemes have been shown to be suboptimal, it has been speculated that they may offer benefits in the early fault-tolerant era where circuit depth comes at a premium. In this work, we investigate the end-to-end resource requirements for a randomized quantum linear systems solver to estimate scalar properties of the matrix inverse by combining sampling from a Fourier series with Hamiltonian simulation. We derive explicit bounds on all relevant algorithmic parameters that control the total error. We analyze two algorithmic kernels for Hamiltonian simulation: a second order product formula approximation and a method called random Taylor expansion (RTE). Finally, we provide numerical demonstrations that confirm the validity of our analytical results and question the actual practicality of the randomized Fourier series-based approach for linear systems problems as we show that the sampling complexity can grow exponentially. By providing explicit bounds, our work serves as a bridge between theoretical algorithmic proposals and efficient hardware implementations while also enabling fair comparisons to alternative algorithms that exhibit optimal asymptotic complexities at the cost of large resource overheads.

Related papers

• Randomized Quantum Singular Value Transformation [18.660349597156266]
  We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT)<n>Standard implementations of QSVT rely on block encodings of the Hamiltonian, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms.<n>Our algorithms use only a single ancilla qubit and entirely avoid block encodings.
  arXiv  Detail & Related papers  (2025-10-08T10:14:15Z)
• An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations [0.0]
  We propose an efficient block-encoding technique for the implementation of the Linear Combination of Hamiltonian Simulations (LCHS)<n>This algorithm approximates a target nonunitary operator as a weighted sum of Hamiltonian evolutions.<n>We introduce an efficient encoding of the LCHS into a quantum circuit based on a simple coordinate transformation.
  arXiv  Detail & Related papers  (2025-01-19T19:03:29Z)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations.<n>The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.<n>The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• Harmonic Path Integral Diffusion [0.4527270266697462]
  We present a novel approach for sampling from a continuous multivariate probability distribution, which may either be explicitly known (up to a normalization factor) or represented via empirical samples. Our method constructs a time-dependent bridge from a delta function centered at the origin of the state space at $t=0$, transforming it into the target distribution at $t=1$. We contrast these algorithms with other sampling methods, particularly simulated and path integral sampling, highlighting their advantages in terms of analytical control, accuracy, and computational efficiency.
  arXiv  Detail & Related papers  (2024-09-23T16:20:21Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Approximating outcome probabilities of linear optical circuits [0.0]
  We propose classical algorithms for approximating outcome probabilities of a linear optical circuit. Our scheme renders an efficient estimation of outcome probabilities with precision depending on the classicality of the circuit. Our study sheds light on the power of linear optics, providing plenty of quantum-inspired algorithms for problems in computational complexity.
  arXiv  Detail & Related papers  (2022-11-14T08:21:51Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.