40 citations · 53 across the 2 of their papers we have counts for
9 papers
Tight adversary bounds for composite functions
Peter Hoyer, Troy Lee, Robert Spalek
The quantum adversary method is a versatile method for proving lower bounds on quantum algorithms. It yields tight bounds for many computational problems, is robust in having many…
Combinatorics and Quantum Nonlocality
Harry Buhrman, Peter Hoyer, Serge Massar +1
We use techniques for lower bounds on communication to derive necessary conditions (in terms of detector efficiency or amount of super-luminal communication) for being able to repr…
Bounds on quantum ordered searching
Peter Hoyer, Jan Neerbek
We prove that any exact quantum algorithm searching an ordered list of N elements requires more than \frac{1}π(\ln(N)-1) queries to the list. This improves upon the previously best…
Quantum State Detection Via Elimination
J. Mark Ettinger, Peter Hoyer
We present the view of quantum algorithms as a search-theoretic problem. We show that the Fourier transform, used to solve the Abelian hidden subgroup problem, is an example of an…
Hidden Subgroup States are Almost Orthogonal
Mark Ettinger, Peter Hoyer, Emanuel Knill
It is well known that quantum computers can efficiently find a hidden subgroup of a finite Abelian group . This implies that after only a polynomial (in ) number o…
A Quantum Observable for the Graph Isomorphism Problem
Mark Ettinger, Peter Hoyer
Suppose we are given two graphs on vertices. We define an observable in the Hilbert space $\Co[(S_n \wr S_2)^m]$ which returns the answer ``yes'' with certainty if the graphs a…