A new quantum lower bound framework proves a tight bound for k-Distinctness.
Ambainis
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new $\Omega(\sqrt{N})$ lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via variety of different techniques.
citation-role summary
background 1
citation-polarity summary
years
2026 2verdicts
UNVERDICTED 2roles
background 1polarities
background 1representative citing papers
SYK disorder is shown to be an approximate unitary k-design for poly(N) k; under the planted-SYK hardness conjecture this yields gravitationally pseudorandom unitaries, implying cryptographic censorship in JT gravity with the regularized maximal geodesic length as distinguisher.
citing papers explorer
-
Tight Quantum Lower Bound for k-Distinctness
A new quantum lower bound framework proves a tight bound for k-Distinctness.
-
Pseudorandom Dynamics in the SYK Model and Cryptographic Censorship in JT Gravity
SYK disorder is shown to be an approximate unitary k-design for poly(N) k; under the planted-SYK hardness conjecture this yields gravitationally pseudorandom unitaries, implying cryptographic censorship in JT gravity with the regularized maximal geodesic length as distinguisher.