Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.
hub Canonical reference
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages =
Canonical reference. 71% of citing Pith papers cite this work as background.
44
Pith papers citing it
2
external citations · external index
Background
71% of classified citations
hub tools
citation-role summary
background 5
method 2
citation-polarity summary
representative citing papers
The work proves that approximating correlation clustering to additive εn² error requires Ω(n/ε²) adjacency-matrix queries, with stronger bounds under memory constraints in random and general query models.
Coherent quantum inference achieves O(1/ε) sample complexity for d-dimensional quantum purity amplification, exponentially better than the Ω(d/ε) required by any incoherent measurement-mediated protocol.
Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
The single-pass streaming space complexity of CSP(Γ) is characterized up to log factors by the non-redundancy NRD_n(Γ) of the constraint language.
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
Tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) whenever the basic LP admits a (γ,β)-integrality gap.
A cut-preserving sparsifier constructed from approximate max-flow enables faster all-pairs minimum-cut algorithms in unweighted graphs across cut-query, dynamic, and streaming models.
Algorithm computes smallest suffixient arrays in sublinear time O((n log σ)/√log n + min(r, r-bar) log^ε n) when alphabet is small and BWT has few runs.
Random dimension reduction replaces full dimension with max rank in sample complexity for symmetric quantum state properties and connects to but differs from random purification.
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.
Presents a quantum soft PCA framework with Fermi-Dirac filter for principal subspace scoring without eigenvector recovery, claiming dimension-independent sample complexity O(η^{-2}).
Quantum algorithm block-encodes Riccati solutions for m-particle m-hole RPA using Riesz projectors and QSVT, claiming linear system-size scaling under sparsity and polynomial cost in excitation rank m.
Symmetric Boolean CSP predicates of arity at most 5 have their non-redundancy NRD_n(R) classified as O(n^t) for small t, with all arity-4 cases and all but two arity-5 cases resolved via t-balancedness and OR-reductions.
A classical polynomial-time algorithm for optimized sampling of lottery tickets in neural networks removes the exponential dependence on data dimension from prior classical approaches.
A dynamic parallel constant-time LCE algorithm uses a string synchronizing sets hierarchy to handle updates with O(n^ε) work and enables constant-time maintenance for Dyck language membership and square detection.
QRSI spans degenerate quantum eigenspaces almost surely by conjugating the Hamiltonian with random unitaries on g parallel branches and using subspace estimation, while exactly preserving the spectral gap.
A two-pass sublinear-space streaming algorithm achieves (1/2-ε)-approximation for Max-DICUT on unbounded-degree graphs.
Quantum circuits for coherent multilayer neural network inference achieve quadratic to polylogarithmic speedups over classical methods depending on quantum data access models for inputs and weights.
The paper proposes an eigenstate filtering (EF) variant of quantum inverse power iteration (QIPI) that uses symmetric QSVT polynomials to robustly target excited states, showing better convergence than Chebyshev or Fourier approaches on H2, LiH, and BeH2.
k-local quantum Hamiltonians admit system-size-independent spectral gap for Gibbs samplers at high temperature, enabling FPT quantum approximation algorithms for partition functions.
Hermitian block embedding enables GQSP to implement the inverse of a non-Hermitian time-step matrix from 2D Black-Scholes finite-difference discretisation, with numerical results for two-asset calls matching classical backward-Euler polynomial approximation.
End-to-end QSP-based quantum circuits solve linear PDEs on IBM hardware with tunable error and handle non-homogeneous Dirichlet boundaries for a plasma Poisson problem.
citing papers explorer
-
Towards Minimax Estimation of High-Order Functionals by Quantum Arguments
Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.
-
Query Lower Bounds for Correlation Clustering under Memory Constraints
The work proves that approximating correlation clustering to additive εn² error requires Ω(n/ε²) adjacency-matrix queries, with stronger bounds under memory constraints in random and general query models.
-
An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
Coherent quantum inference achieves O(1/ε) sample complexity for d-dimensional quantum purity amplification, exponentially better than the Ω(d/ε) required by any incoherent measurement-mediated protocol.
-
Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems
Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
-
Streaming Complexity Separations for Dense and Sparse Graphs
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
-
Characterizing Streaming Decidability of CSPs via Non-Redundancy
The single-pass streaming space complexity of CSP(Γ) is characterized up to log factors by the non-redundancy NRD_n(Γ) of the constraint language.
-
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
-
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) whenever the basic LP admits a (γ,β)-integrality gap.
-
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
A cut-preserving sparsifier constructed from approximate max-flow enables faster all-pairs minimum-cut algorithms in unweighted graphs across cut-query, dynamic, and streaming models.
-
Computing Smallest Suffixient Arrays in Sublinear Time
Algorithm computes smallest suffixient arrays in sublinear time O((n log σ)/√log n + min(r, r-bar) log^ε n) when alphabet is small and BWT has few runs.
-
Random dimension reduction and learning symmetric properties of quantum states
Random dimension reduction replaces full dimension with max rank in sample complexity for symmetric quantum state properties and connects to but differs from random purification.
-
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 principal component analysis without eigenvector recovery
Presents a quantum soft PCA framework with Fermi-Dirac filter for principal subspace scoring without eigenvector recovery, claiming dimension-independent sample complexity O(η^{-2}).
-
Quantum Solvers for Nonlinear Matrix Equations in Quantum Chemistry
Quantum algorithm block-encodes Riccati solutions for m-particle m-hole RPA using Riesz projectors and QSVT, claiming linear system-size scaling under sparsity and polynomial cost in excitation rank m.
-
Non-Redundancy of Low-Arity Symmetric Boolean CSPs
Symmetric Boolean CSP predicates of arity at most 5 have their non-redundancy NRD_n(R) classified as O(n^t) for small t, with all arity-4 cases and all but two arity-5 cases resolved via t-balancedness and OR-reductions.
-
Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm
A classical polynomial-time algorithm for optimized sampling of lottery tickets in neural networks removes the exponential dependence on data dimension from prior classical approaches.
-
Longest Common Extension of a Dynamic String in Parallel Constant Time
A dynamic parallel constant-time LCE algorithm uses a string synchronizing sets hierarchy to handle updates with O(n^ε) work and enables constant-time maintenance for Dyck language membership and square detection.
-
Quantum Randomized Subspace Iteration
QRSI spans degenerate quantum eigenspaces almost surely by conjugating the Hamiltonian with random unitaries on g parallel branches and using subspace estimation, while exactly preserving the spectral gap.
-
Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
A two-pass sublinear-space streaming algorithm achieves (1/2-ε)-approximation for Max-DICUT on unbounded-degree graphs.
-
Accelerating Inference for Multilayer Neural Networks with Quantum Computers
Quantum circuits for coherent multilayer neural network inference achieve quadratic to polylogarithmic speedups over classical methods depending on quantum data access models for inputs and weights.
-
Efficient targeting of arbitrary excited states with quantum inverse power iteration through filtering polynomials
The paper proposes an eigenstate filtering (EF) variant of quantum inverse power iteration (QIPI) that uses symmetric QSVT polynomials to robustly target excited states, showing better convergence than Chebyshev or Fourier approaches on H2, LiH, and BeH2.
-
Fast mixing of all-to-all quantum systems at high temperatures
k-local quantum Hamiltonians admit system-size-independent spectral gap for Gibbs samplers at high temperature, enabling FPT quantum approximation algorithms for partition functions.
-
Solving 2D Black Scholes Equation via Hermitian Block Embedding and Generalised Quantum Signal Processing
Hermitian block embedding enables GQSP to implement the inverse of a non-Hermitian time-step matrix from 2D Black-Scholes finite-difference discretisation, with numerical results for two-asset calls matching classical backward-Euler polynomial approximation.
-
Quantum Signal Processing for Linear PDEs: Circuit Design and Experimental Validation
End-to-end QSP-based quantum circuits solve linear PDEs on IBM hardware with tunable error and handle non-homogeneous Dirichlet boundaries for a plasma Poisson problem.
-
How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures
Identifies conditions and explicit constructions allowing polynomial-size quantum circuits to implement geometry oracles for pseudorandom textured materials, in contrast to Grover-hard unstructured cases.
-
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.
-
Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface
The Eclipse Qrisp BlockEncoding interface provides high-level programming abstractions for block-encodings, enabling easier implementation of quantum algorithms such as QSVT, matrix inversion, and Hamiltonian simulation.
-
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.
-
TARE: Block Encoding Linear Combinations of Pauli Strings Without Ancilla State Preparation
TARE block-encodes sums of Pauli strings with reduced T-gate count and improved circuit depth versus standard LCU by leveraging mutually anti-commuting Pauli sets and transformations.
-
Hermitian Matrix Function Synthesis without Block-Encoding
GQSP enables polynomial synthesis of Hermitian matrices without block-encoding, yielding stable degree-independent success probability and closed-form symmetric expansions.
-
Efficient Simulation of Sparse, Non-Local Fermion Models
An auxiliary-fermion encoding removes Jordan-Wigner strings for sparse non-local fermion models, achieving asymptotically optimal Trotter circuit depth on qubits after one-time state preparation.
-
Quantum Simulation of Non-Hermitian Special Functions and Dynamics via Contour-based Matrix Decomposition
CBMD decomposes non-Hermitian evolution operators into Hermitian LCU terms via a matrix residue theorem, matching known optimal query bounds and offering a route to polynomial matrix functions.
-
Are controlled unitaries helpful?
Controlled unitaries can be decontrolled into standard unitaries with random phase, showing they do not help beyond global phase information for a large class of quantum problems.
-
Provable Quantum Advantage for Dynamical Phase Transition
Proves intractability of DQPT estimation on quantum computers but equivalence of subsystem DQPT decision to quantum circuit simulation, with quadratic speedup for critical time search.
-
From Meta Idea to Advanced Mathematical Discovery -- Human-AI Co-Discovery of Sign-Embedding Quantum Algorithms
Human-AI collaboration expanded a meta-idea on rational approximation into sign-embedding quantum algorithms for matrix problems, with humans retaining final judgment on routes and refinements.
-
Quantum element-wise transforms
Quantum algorithms for element-wise polynomial matrix transforms achieve exponential space reduction in polynomial degree with corrections to prior constructions.
-
A Demonstration of Quantum Circuit Implementation for Obstacle Flow Using Carleman-Linearized Lattice Boltzmann Method
Demonstration of quantum circuit implementation for 2D obstacle flow via Carleman-linearized LBM solved with QSVT, achieving logarithmic qubit and gate scaling with lattice points.
-
Quantum Flow algorithm: quantum simulations of chemical systems using reduced quantum resources and constant depth quantum circuits
QFlow-SD matches canonical UCCSD energies for tested molecules while using substantially fewer qubits via reduced active spaces and constant-depth circuits, with a composite classical-quantum downfolding strategy demonstrated for water.
-
Dissipative microcanonical ensemble preparation from KMS-detailed balance
Extends KMS-detailed balance constructions from open quantum systems to prepare microcanonical ensembles and other stationary states with criteria for efficient implementation.
-
Learning PDEs for Portfolio Optimization with Quantum Physics-Informed Neural Networks
Tensor-rank quantum and quantum-inspired PINNs solve the Merton HJB PDE with lower error and fewer parameters than classical fully connected PINNs.
-
Synthesizing Compound Pulse Gadgets for Hamiltonian Simulation on Trapped-Ion Platforms
The work introduces a GRAPE-based holistic pulse synthesis method to generate compound gadgets for QSVT Hamiltonian simulation of H2 on trapped ions, claiming reduced pulse duration and eliminated control latency compared to gate-based compilers.
-
Post-Moore Technologies for Plasma Simulation: A Community Roadmap
No single post-Moore technology replaces current HPC for plasma simulations, but FPGA-class accelerators offer near-term kernel offload, non-von Neumann architectures medium-term operator acceleration, and quantum computing long-term potential for warm dense matter microphysics.
-
Efficient Gaussian State Preparation in Quantum Circuits
A quantum circuit prepares approximate Gaussian states via single-qubit rotations followed by QFT, achieving high fidelity with optional angle pruning for O(n) gate cost.
-
Quantum Simulation of Ligand-like Molecules through Sample-based Quantum Diagonalization in Density Matrix Embedding Framework
Using DMET to fragment molecules and SQD to solve the fragments on IBM hardware, the authors report ground-state energies for eight ligand-like molecules that agree with DMET-FCI to within about 10⁻⁶ Hartree.