Imagen de Portada

Sublinear Time Quantum Algorithm for Attention Approximation

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Song, Zhao, Xue, Jianfei, Zhang, Jiahao, Zhang, Lichen
Formato:	Preprint
Publicado:	2026
Materias:	Quantum Physics Data Structures and Algorithms Machine Learning
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Sublinear Time Quantum Sensitivity Sampling
por: Song, Zhao, et al.
Publicado: (2025)

Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming
por: Song, Zhao, et al.
Publicado: (2025)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
por: Hu, Hang, et al.
Publicado: (2022)

Quantum Speedup for Spectral Approximation of Kronecker Products
por: Gao, Yeqi, et al.
Publicado: (2024)

Training Overparametrized Neural Networks in Sublinear Time
por: Deng, Yichuan, et al.
Publicado: (2022)

A Quantum Approximation Scheme for k-Means
por: Jaiswal, Ragesh
Publicado: (2023)

Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm
por: Zhou, Leo, et al.
Publicado: (2024)

Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms
por: Gall, François Le
Publicado: (2023)

QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design
por: Yang, Rui, et al.
Publicado: (2024)

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
por: Kociumaka, Tomasz, et al.
Publicado: (2024)

Quantum Algorithms and Lower Bounds for Finite-Sum Optimization
por: Zhang, Yexin, et al.
Publicado: (2024)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
por: Danait, Ved, et al.
Publicado: (2025)

Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities
por: Su, Yuexin, et al.
Publicado: (2025)

Dynamic Correlation Clustering in Sublinear Update Time
por: Cohen-Addad, Vincent, et al.
Publicado: (2024)

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
por: Gu, Yuzhou, et al.
Publicado: (2023)

Fast-MWEM: Private Data Release in Sublinear Time
por: Haris, Themistoklis, et al.
Publicado: (2026)

Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit
por: Bellante, Armando, et al.
Publicado: (2025)

Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
por: Gu, Yuzhou, et al.
Publicado: (2024)

A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values
por: Chen, Tyler, et al.
Publicado: (2025)

Simple Quantum Algorithm for Approximate $k$-Mismatch Problem
por: Habib, Ruhan, et al.
Publicado: (2025)

Approximate Butterfly Counting in Sublinear Time
por: Luo, Chi, et al.
Publicado: (2026)

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
por: Grønlund, Allan, et al.
Publicado: (2024)

Quantum principal component analysis without eigenvector recovery
por: Yuan, Yewei, et al.
Publicado: (2026)

Instance-Optimal Quantum State Certification with Entangled Measurements
por: O'Donnell, Ryan, et al.
Publicado: (2025)

Learning the structure of any Hamiltonian from minimal assumptions
por: Zhao, Andrew
Publicado: (2024)

Terminal Embeddings in Sublinear Time
por: Cherapanamjeri, Yeshwanth, et al.
Publicado: (2021)

Learning fermionic linear optics with Heisenberg scaling and physical operations
por: Christensen, Aria, et al.
Publicado: (2026)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
por: Kannan, Ravindran, et al.
Publicado: (2024)

A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm
por: Kim, Junhyung Lyle, et al.
Publicado: (2024)

Optimal Scalarizations for Sublinear Hypervolume Regret
por: Zhang, Qiuyi
Publicado: (2023)

Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
por: Mishra, Nina, et al.
Publicado: (2025)

Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms
por: Caroppo, Susanna, et al.
Publicado: (2025)

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
por: Gall, François Le, et al.
Publicado: (2018)

Quantum Approximate Optimization Algorithms for Maximum Cut on Low-Girth Graphs
por: Li, Tongyang, et al.
Publicado: (2024)

Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications
por: Gong, Weiyuan, et al.
Publicado: (2025)

Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model
por: Feng, Weiming, et al.
Publicado: (2025)

SubGen: Token Generation in Sublinear Time and Memory
por: Zandieh, Amir, et al.
Publicado: (2024)

Tight Gap-Dependent Memory-Regret Trade-Off for Single-Pass Streaming Stochastic Multi-Armed Bandits
por: Ye, Zichun, et al.
Publicado: (2025)

Product-State Approximation Algorithms for the Transverse Field Ising Model
por: Lipardi, Vincenzo, et al.
Publicado: (2026)

Structure learning of Hamiltonians from real-time evolution
por: Bakshi, Ainesh, et al.
Publicado: (2024)