Cover Image

Tight Quantum Lower Bound for k-Distinctness

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Belovs, Aleksandrs
Format:	Preprint
Published:	2026
Subjects:	Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight Quantum Lower Bound for Approximate Counting with Quantum States
by: Belovs, Aleksandrs, et al.
Published: (2020)

Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem
by: Belovs, Aleksandrs
Published: (2024)

Space-Efficient Quantum Error Reduction without log Factors
by: Belovs, Aleksandrs, et al.
Published: (2025)

Taming Quantum Time Complexity
by: Belovs, Aleksandrs, et al.
Published: (2023)

Quantum algorithms for Hopcroft's problem
by: Andrejevs, Vladimirs, et al.
Published: (2024)

On the quantum time complexity of divide and conquer
by: Allcock, Jonathan, et al.
Published: (2023)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
by: Wang, Qisheng, et al.
Published: (2024)

Tight Generalization Bound for Supervised Quantum Machine Learning
by: Wang, Xin, et al.
Published: (2025)

Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits
by: Letcher, Alistair, et al.
Published: (2023)

Multidimensional Quantum Walks, with Application to $k$-Distinctness
by: Jeffery, Stacey, et al.
Published: (2022)

Rényi exponent landscape of multipartite entanglement in free-fermion systems
by: Sokolovs, Aleksandrs
Published: (2026)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
by: He, Kun, et al.
Published: (2018)

The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction
by: Blanvillain, Agathe, et al.
Published: (2025)

Tighter Lower Bounds on Quantum Annealing Times
by: García-Pintos, Luis Pedro, et al.
Published: (2024)

Quantum State Learning Implies Circuit Lower Bounds
by: Chia, Nai-Hui, et al.
Published: (2024)

Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing
by: Braida, Arthur, et al.
Published: (2023)

Improved Lower Bounds for Learning Quantum Channels in Diamond Distance
by: Oufkir, Aadil, et al.
Published: (2026)

Bayesian Logarithmic Derivative Type Lower Bounds for Quantum Estimation
by: Zhang, Jianchao, et al.
Published: (2024)

National Quantum Strategies: A Data-Driven Approach to Understanding the Quantum Ecosystem
by: Goorney, Simon Richard, et al.
Published: (2026)

Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
by: Dufoulon, Fabien, et al.
Published: (2026)

Lower Bounds on Quantum Tunneling for Excited States
by: Fefferman, Charles L., et al.
Published: (2025)

Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers
by: Mori, Hitomi, et al.
Published: (2026)

Lower Bounds on Error Exponents via a New Quantum Decoder
by: Beigi, Salman, et al.
Published: (2023)

Lower Bounds for Quantum Secure Function Evaluation Reductions
by: Hänggi, Esther, et al.
Published: (2024)

Permutation Superposition Oracles for Quantum Query Lower Bounds
by: Majenz, Christian, et al.
Published: (2024)

Improved Circuit Lower Bounds and Quantum-Classical Separations
by: Grewal, Sabee, et al.
Published: (2024)

Continuous-Variable Quantum Key Distribution with Composable Security and Tight Error Correction Bound for Constrained Devices
by: Papanastasiou, Panagiotis, et al.
Published: (2025)

Lower Bounds for the Trotter Error
by: Hahn, Alexander, et al.
Published: (2024)

Subspace Variational Quantum Simulation: Fidelity Lower Bounds as Measures of Training Success
by: Park, Seung, et al.
Published: (2025)

A Recursive Lower Bound on the Energy Improvement of the Quantum Approximate Optimization Algorithm
by: Medina, Raimel A., et al.
Published: (2024)

Tripartite information of free fermions: a universal entanglement coefficient from the sine kernel
by: Sokolovs, Aleksandrs
Published: (2026)

Quantum Query-Space Lower Bounds Using Branching Programs
by: Bera, Debajyoti, et al.
Published: (2024)

Lower Bounds on Relative Error Quantum Compression and Classical Shadows
by: Sankar, Kaushik
Published: (2025)

Security of Key-Alternating Ciphers: Quantum Lower Bounds and Quantum Walk Attacks
by: Bai, Chen, et al.
Published: (2024)

Lower Bounds on Coherent State Rank
by: Cottier, Florian, et al.
Published: (2026)

A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More
by: Hhan, Minki
Published: (2024)

Structure-Fair Quantum Circuit Complexity: An Auditable Information-Theoretic Lower Bound
by: Liu, HongZheng, et al.
Published: (2025)

Lower Bounds of Entanglement Quantifiers Based On Entanglement Witnesses
by: Shi, Xian
Published: (2023)

Lower Bounds for Learning Hamiltonians from Time Evolution
by: Chen, Ziyun, et al.
Published: (2025)