6 citations · 8 across the 5 of their papers we have counts for
7 papers
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
Francisco Escudero Gutiérrez, Junseo Lee, Sebastian Zur
We establish lower bounds for Hamiltonian property testing with access to the time-evolution operator but not its inverse. Each experiment may query the time-evolution operator mul…
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…
Multidimensional Quantum Walks, with Application to -Distinctness
Stacey Jeffery, Sebastian Zur
While the quantum query complexity of -distinctness is known to be for any constant , the best previous upper bound on the time comp…
Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability
Jan Czajkowski, Christian Majenz, Christian Schaffner +1
Game-playing proofs constitute a powerful framework for non-quantum cryptographic security arguments, most notably applied in the context of indifferentiability. An essential ingre…