PHPeter Hoyer

Peter Hoyer

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Peter Hoyer has a total of 8 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Tight Bounds on Quantum Searching

    by Michel Boyer, Gilles Brassard, Peter Høyer, Alain Tappa


  • Open Access

    A Quantum Algorithm for Finding the Minimum

    by Christoph Durr, Peter Hoyer

    We give a quantum algorithm to find the index y in a table T of size N such that in time O(c sqrt N), T[y] is minimum with probability at least 1-1/2^c.


  • Open Access

    On Quantum Algorithms for Noncommutative Hidden Subgroups

    by Mark Ettinger, Peter Hoyer

    Quantum algorithms for factoring and discrete logarithm have previously been generalized to finding hidden subgroups of finite Abelian groups. This paper explores the possibility of extending this general viewpoint to finding hidden subgroups of noncommutative groups. We present a quantum algorithm for the special case of dihedral groups which determines the hidden subgroup in a linear number of calls to the input function. We also explore the difficulties of developing an algorithm to process the data to explicitly calculate a generating set for the subgroup. A general framework for the noncommutative hidden subgroup problem is discussed and we indicate future research directions.

  • Tight Bounds on Quantum Searching

    by Michel Boyer, Gilles Brassard, Peter Høyer, Alain Tapp


  • Open Access

    Quantum Counting

    by Gilles Brassard, Peter Hoyer, Alain Tapp

    We study some extensions of Grover's quantum searching algorithm. First, we generalize the Grover iteration in the light of a concept called amplitude amplification. Then, we show that the quadratic speedup obtained by the quantum searching algorithm over classical brute force can still be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform approximate counting, which can be seen as an amplitude estimation process.


  • Open Access

    Quantum Algorithm for the Collision Problem

    by Gilles Brassard, Peter Hoyer, Alain Tapp

    In this note, we give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O((N/r)^(1/3)) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.

  • Open Access

    An Exact Quantum Polynomial-Time Algorithm for Simon's Problem

    by Gilles Brassard, Peter Hoyer

    We investigate the power of quantum computers when they are required to return an answer that is guaranteed to be correct after a time that is upper-bounded by a polynomial in the worst case. We show that a natural generalization of Simon's problem can be solved in this way, whereas previous algorithms required quantum polynomial time in the expected sense only, without upper bounds on the worst-case running time. This is achieved by generalizing both Simon's and Grover's algorithms and combining them in a novel way. It follows that there is a decision problem that can be solved in exact quantum polynomial time, which would require expected exponential time on any classical bounded-error probabilistic computer if the data is supplied as a black box.

  • Open Access

    Efficient Quantum Transforms

    by Peter Hoyer

    Quantum mechanics requires the operation of quantum computers to be unitary, and thus makes it important to have general techniques for developing fast quantum algorithms for computing unitary transforms. A quantum routine for computing a generalized Kronecker product is given. Applications include re-development of the networks for computing the Walsh-Hadamard and the quantum Fourier transform. New networks for two wavelet transforms are given. Quantum computation of Fourier transforms for non-Abelian groups is defined. A slightly relaxed definition is shown to simplify the analysis and the networks that computes the transforms. Efficient networks for computing such transforms for a class of metacyclic groups are introduced. A novel network for computing a Fourier transform for a group used in quantum error-correction is also given.

  • Open Access

    On The Power of Exact Quantum Polynomial Time

    by Gilles Brassard, Peter Hoyer

    We investigate the power of quantum computers when they are required to return an answer that is guaranteed correct after a time that is upper-bounded by a polynomial in the worst case. In an oracle setting, it is shown that such machines can solve problems that would take exponential time on any classical bounded-error probabilistic computer.

  • Open Access

    Tight bounds on quantum searching

    by Michel Boyer, Gilles Brassard, Peter Hoeyer, Alain Tapp

    We provide a tight analysis of Grover's recent algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Using techniques from Shor's quantum factoring algorithm in addition to Grover's approach, we introduce a new technique for approximate quantum counting, which allows to estimate the number of solutions. Finally we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm nearly comes within a factor 2 of being optimal in terms of the number of probes required in the table.