Quantum signal processing angles admit closed-form expressions via orthogonal polynomial theory, allowing O(log(1/ε)) gate block-encodings of smooth functions through Hermite expansions and full characterization of SU(1,1)-QSP polynomials by roots.
hub Canonical reference
The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
Canonical reference. 71% of citing Pith papers cite this work as background.
15
Pith papers citing it
77
external citations · Pith
Background
71% of classified citations
abstract
We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.
hub tools
citation-role summary
background 5
method 2
citation-polarity summary
representative citing papers
Two quantum linear system solvers are presented with query complexity independent of the condition number, scaling instead with an effective condition number or a solution-norm ratio.
A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
Quantum algorithm simulates RLC circuit dynamics in polylog(N) time and proves energy estimation is BQP-hard via reduction from harmonic oscillator networks.
Quantum algorithms achieve polylog(N) complexity for high-dimensional linear SDEs by amplitude-encoding the solution and noise via Dyson series or Euler-Maruyama approximations plus quantum linear systems solvers.
Constrained Uniform Polynomial (CUP) and Constrained Adaptive Polynomial (CAP) solvers achieve lower error than standard QSVT and Chebyshev methods in noise-limited regimes by optimizing accuracy versus block-encoding normalization under uniform or moment-based spectral models.
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
Constrained optimal polynomials (CUP and CAP) reduce quantum linear system solver errors under noise by jointly optimizing approximation accuracy and block-encoding normalization, outperforming standard QSVT and Chebyshev-iteration solvers in numerical benchmarks.
ROQAM formulates Green's function estimation via orthogonal polynomials to preserve Hessenberg structure under finite precision, enabling lower precision with depth and outperforming QSVD by orders of magnitude in resource estimates for a quantum impurity model.
Adding loop composition to branching quantum walk models produces a variable-time quantum search algorithm whose complexity matches the best known results.
D-VQLS with FWHT Pauli decomposition and 1% thresholding reduces circuit evaluations by 256x for 10-qubit tridiagonal systems while achieving over 99.99% fidelity and near-ideal scaling on up to 96 GPUs.
A new framework for block encoding sparse matrices that uses coherent permutations to reorder amplitudes while preserving superposition and combinatorial optimization to meet hardware connectivity limits.
Unitaria is a new open-source Python library that provides a high-level, composable interface for block encodings in quantum computing, enabling automatic circuit generation and classical simulation-based verification.
Encoding strategies for quantum fluid simulations trade off compactness against practicality in state preparation, measurement, boundary conditions, and nonlinear operations, with no single approach being universally optimal.
citing papers explorer
-
Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory
Quantum signal processing angles admit closed-form expressions via orthogonal polynomial theory, allowing O(log(1/ε)) gate block-encodings of smooth functions through Hermite expansions and full characterization of SU(1,1)-QSP polynomials by roots.
-
Faster quantum linear system solver beyond the condition number
Two quantum linear system solvers are presented with query complexity independent of the condition number, scaling instead with an effective condition number or a solution-norm ratio.
-
Tomography of quantum states with bounded extent
A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
-
Quantum Multi-Level Estimation of Functionals of Discrete Distributions
A quantum multi-level framework achieves near-optimal query complexity for q-Tsallis entropy estimation for q>1 and a speedup for q<1 over classical methods.
-
Simulating dynamics of RLC circuits with a quantum differential-algebraic equations solver
Quantum algorithm simulates RLC circuit dynamics in polylog(N) time and proves energy estimation is BQP-hard via reduction from harmonic oscillator networks.
-
Quantum algorithm for solving high-dimensional linear stochastic differential equations via amplitude encoding of the noise term
Quantum algorithms achieve polylog(N) complexity for high-dimensional linear SDEs by amplitude-encoding the solution and noise via Dyson series or Euler-Maruyama approximations plus quantum linear systems solvers.
-
Constrained Optimal Polynomials for Quantum Linear System Solvers
Constrained Uniform Polynomial (CUP) and Constrained Adaptive Polynomial (CAP) solvers achieve lower error than standard QSVT and Chebyshev methods in noise-limited regimes by optimizing accuracy versus block-encoding normalization under uniform or moment-based spectral models.
-
A shortcut to an optimal quantum linear system solver
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
-
Nonisothermal global-pressure exactness in fractured multiphase flow with aperture feedback
Constrained optimal polynomials (CUP and CAP) reduce quantum linear system solver errors under noise by jointly optimizing approximation accuracy and block-encoding normalization, outperforming standard QSVT and Chebyshev-iteration solvers in numerical benchmarks.
-
Estimating Green's functions with a robust quantum Arnoldi method
ROQAM formulates Green's function estimation via orthogonal polynomials to preserve Hessenberg structure under finite precision, enabling lower precision with depth and outperforming QSVD by orders of magnitude in resource estimates for a quantum impurity model.
-
Loop Composition in Quantum Algorithms
Adding loop composition to branching quantum walk models produces a variable-time quantum search algorithm whose complexity matches the best known results.
-
Distributed Variational Quantum Linear Solver
D-VQLS with FWHT Pauli decomposition and 1% thresholding reduces circuit evaluations by 256x for 10-qubit tridiagonal systems while achieving over 99.99% fidelity and near-ideal scaling on up to 96 GPUs.
-
Block Encoding of Sparse Matrices via Coherent Permutation
A new framework for block encoding sparse matrices that uses coherent permutations to reorder amplitudes while preserving superposition and combinatorial optimization to meet hardware connectivity limits.
-
Unitaria: Quantum Linear Algebra via Block Encodings
Unitaria is a new open-source Python library that provides a high-level, composable interface for block encodings in quantum computing, enabling automatic circuit generation and classical simulation-based verification.
-
Encoding strategies for quantum enhanced fluid simulations: opportunities and challenges
Encoding strategies for quantum fluid simulations trade off compactness against practicality in state preparation, measurement, boundary conditions, and nonlinear operations, with no single approach being universally optimal.