Cover Image

No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kothari, Robin, O'Donnell, Ryan, Wu, Kewen
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity Cryptography and Security Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quartic quantum speedups for planted inference
by: Schmidhuber, Alexander, et al.
Published: (2024)

Uniformity testing when you have the source code
by: Canonne, Clément L., et al.
Published: (2024)

A Classical Quadratic Speedup for Planted $k$XOR
by: Gupta, Meghal, et al.
Published: (2025)

Average-Case Complexity of Quantum Stabilizer Decoding
by: Khesin, Andrey Boris, et al.
Published: (2025)

The NISQ Complexity of Collision Finding
by: Hamoudi, Yassine, et al.
Published: (2022)

Perfect Zero-Knowledge PCPs for #P
by: Gur, Tom, et al.
Published: (2024)

Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$
by: Ducas, Léo, et al.
Published: (2025)

Mind the Gap? Not for SVP Hardness under ETH!
by: Aggarwal, Divesh, et al.
Published: (2025)

Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
by: Dolev, Shlomi
Published: (2025)

The Planted Orthogonal Vectors Problem
by: Kühnemann, David, et al.
Published: (2025)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
by: Guruswami, Venkatesan, et al.
Published: (2025)

On the Maximum Distance Sublattice Problem and Closest Vector Problem
by: Kumar, Rajendra, et al.
Published: (2018)

Improved Hardness of BDD and SVP Under Gap-(S)ETH
by: Bennett, Huck, et al.
Published: (2021)

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
by: Epasto, Alessandro, et al.
Published: (2026)

On the instance optimality of detecting collisions and subgraphs
by: Ben-Eliezer, Omri, et al.
Published: (2023)

Query-optimal estimation of unitary channels in diamond distance
by: Haah, Jeongwan, et al.
Published: (2023)

Locality Bounds for Sampling Hamming Slices
by: Kane, Daniel M., et al.
Published: (2024)

Privately Estimating Black-Box Statistics
by: Steinke, Günter F., et al.
Published: (2025)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
by: Golowich, Noah, et al.
Published: (2024)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
by: Dvijotham, Krishnamurthy, et al.
Published: (2024)

InstaHide's Sample Complexity When Mixing Two Private Images
by: Huang, Baihe, et al.
Published: (2020)

SPAM Tolerance for Pauli Error Estimation
by: O'Donnell, Ryan, et al.
Published: (2025)

Quantum chi-squared tomography and mutual information testing
by: Flammia, Steven T., et al.
Published: (2023)

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
by: Sarkar, Rohit Sarma, et al.
Published: (2024)

Elfs, transducers and quantum walks
by: Apers, Simon, et al.
Published: (2026)

The state hidden subgroup problem and an efficient algorithm for locating unentanglement
by: Bouland, Adam, et al.
Published: (2024)

On estimating the quantum $\ell_α$ distance
by: Liu, Yupan, et al.
Published: (2025)

Certifying and learning quantum Ising Hamiltonians
by: Bluhm, Andreas, et al.
Published: (2025)

Certifying and learning local quantum Hamiltonians
by: Bluhm, Andreas, et al.
Published: (2026)

Testing and learning structured quantum Hamiltonians
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Fast quantum algorithm for differential equations
by: Bagherimehrab, Mohsen, et al.
Published: (2023)

On estimating the trace of quantum state powers
by: Liu, Yupan, et al.
Published: (2024)

Optimal lower bounds for quantum state tomography
by: Scharnhorst, Thilo, et al.
Published: (2025)

Optimal learning of quantum channels in diamond distance
by: Mele, Antonio Anna, et al.
Published: (2025)

Directed st-connectivity with few paths is in quantum logspace
by: Apers, Simon, et al.
Published: (2024)

Optimal Scheduling of Graph States via Path Decompositions
by: Elman, Samuel J., et al.
Published: (2024)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
by: Abbas, Amira, et al.
Published: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
by: Apers, Simon, et al.
Published: (2021)

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
by: Allcock, Jonathan, et al.
Published: (2024)

Sparsifying Suprema of Gaussian Processes
by: De, Anindya, et al.
Published: (2024)