4 papers · 1 filter
Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
Frédéric Magniez, Sebastian Zur
How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function , the BHT algorithm finds a collision using $O(N^{1/3})…
The Compressed Oracle is a Worthy (Multiplicative) Adversary
Stacey Jeffery, Sebastian Zur
The compressed oracle technique, introduced in the context of quantum cryptanalysis, is the latest method for proving quantum query lower bounds, and has had an impressive number o…
Quantum Walks for Chemical Reaction Networks
Seenivasan Hariharan, Sebastian Zur, Sachin Kinge +3
Near a detailed-balance equilibrium, the perturbed mass-action dynamics of a chemical reaction network (CRN) map exactly onto an electrical-flow problem on the bipartite species-re…
Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
Jianqiang Li, Sebastian Zur
Recently, Apers and Piddock [TQC '23] strengthened the connection between quantum walks and electrical networks via Kirchhoff's Law and Ohm's Law. In this work, we develop a new mu…