REVIEW 19 cited by
The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original 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.
Forward citations
Cited by 19 Pith papers
-
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.
-
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 Cheby...
-
Quantum Alternating Direction Method of Multipliers for Semidefinite Programming
QADMM is a quantum ADMM for SDPs with a polynomial proximal operator and QSVT-based updates; the stated convergence for the projected output is not established.
-
From Nonlinear Stochastic Differential Equations to Quantum Channels: The Kolmogorov--Lindblad Mapping
The Fokker-Planck density of a nonlinear SDE is the diagonal of a Lindblad-evolved quantum state, so classical expectations and two-time correlations become exact quantum channel observables.
-
A matching decomposition algorithm for simulating quantum walk Hamiltonians
Matching decomposition with edge compression builds quantum-walk circuits that need up to 43% fewer CX gates and 54% less depth than Pauli decomposition on tested sparse graphs.
-
Estimation of Nonlinear Physical Quantities By Measuring Ancillas
The paper presents QSVT-based algorithms that estimate Renyi and von Neumann entropies from copies of a quantum state by measuring ancillas, with improved sample complexity over prior copy-based methods.
-
A quantum dual logarithmic barrier method for linear optimization
A dual-only quantum interior point method for linear optimization with inexact Newton directions and O(√n) iteration complexity, using QLSA and tomography.
-
A preconditioned inexact infeasible quantum interior point method for linear optimization
A preconditioned inexact infeasible quantum interior point method improves the condition number of the normal equations from O(1/μ^2) to O(1/μ), yielding better QLSA query complexity.
-
An Implementation of the Finite Element Method in Hybrid Classical/Quantum Computers
A variational quantum linear solver is coupled to finite element discretizations by an element-wise unitary decomposition, verified on 1D heat problems up to 7 qubits but with strong scaling barriers.
-
Quantum Expectation-Maximization for Gaussian Mixture Models
A quantum EM algorithm fits Gaussian mixture models with per-iteration runtime polylogarithmic in the number of samples and polynomial in other parameters, under quantum access to the data.
-
Memory-, Circuit-, and Ansatz-Efficient VQLS for CFD on Hybrid Quantum-HPC Systems
The authors show that a Walsh-Hadamard transform cuts encoding memory by up to 1298x and an SVD-based two-term encoding gives a >10,000x per-iteration speedup for VQLS on CFD problems, while expressibility metrics fai...
-
Circuit-Efficient Randomized Quantum Simulation of Non-Unitary Dynamics with Observable-Driven and Symmetry-Aware Designs
A randomized compilation of LCHS for non-unitary dynamics, with an observable-driven variant and a symmetry-aware sampler, claims reduced ancilla and circuit depth at the cost of more repetitions.
-
Quantum Algorithm for Estimating Intrinsic Geometry
A quantum algorithm for local dimension and curvature estimation is proposed, but the claimed exponential speedup rests on unproven spectral-gap assumptions and an incorrect least-squares derivation.
-
Quantum Expectation-Maximization Algorithm
A quantum EM algorithm for Gaussian mixture models is proposed, with a claimed exponential speedup over classical EM, based on a noisy δ-EM variant that is only numerically validated.
-
Quantum algorithm for estimating Renyi entropies of quantum states
A DQC1-based algorithm estimates α-Rényi entropies of non-singular quantum states to additive or multiplicative precision using purified access, at expected cost O(1/(xε)^2) measurements.
-
Exploring the use of quantum computing for facilitating spatially and temporally resolved models of a biological cell
A perspective that maps potential quantum-algorithm speedups for whole-cell modeling and finds they depend on strong idealizations about data loading and fault tolerance.
-
Quantum Solution Framework for Finite-Horizon LQG Control via Block Encodings and QSVT
A proposal to solve finite-horizon LQG control with block-encoded quantum linear algebra, claiming O(T polylog(n)) runtime under strong assumptions about data access, conditioning, and ignoring output readout.
-
Quantum Algorithms for Portfolio Optimization
A quantum interior-point algorithm built on a quantum second-order cone program solver is proposed for constrained portfolio optimization, with a claimed near-linear speedup under favorable problem-dependent parameters.
-
Co-designed Quantum Discrete Adiabatic Linear System Solver Via Dynamic Circuits
A dynamic-circuit linear solver that measures and classically reconstructs the quantum state after every discrete adiabatic step claims to make circuit depth independent of the number of steps, with numerical fideliti...
Discussion (0). Continue with ORCID to comment.