Quantum Computation

Negative weights make adversaries stronger

Peter Hoyer, Troy Lee, and Robert Spalek. STOC 2007

Resources required for preparing graph states

Peter Hoyer, Mehdi Mhalla, and Simon Perdrix. ISAAC 2006

Multipartite nonlocal quantum correlations resistant to imperfections   [ ps | pdf ]

Harry Buhrman, Peter Høyer, Serge Massar, and Hein Röhrig. Physical Review A, 73:012321, 2006.

Quantum query complexity of some graph problems   [ ps | pdf ]

Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. SIAM Journal on Computing, 35(6):1310--1328, 2006. (Best paper award for track A at ICALP'04.)

When errors are intolerable   [ Nature Physics ]

Peter Høyer. Nature Physics, 1(3):141--142, December 2005.

The phase matrix   [ ps | pdf ]

Peter Høyer. Proc. of 16th International Symposium on Algorithms and Computation (ISAAC'05), X. Deng and D. Du (Eds.), LNCS 3827, 308-317, December 2005.

Tight adversary bounds for composite functions [quantph/0509067]

Peter Høyer and Robert Špalek. September 2005.

Lower bounds on quantum query complexity   [ ps | pdf ]

Peter Høyer and Robert Špalek. Bulletin of the European Association for Theoretical Computer Science, 87:78-103, October 2005.

Quantum algorithms for element distinctness   [ ps | pdf ]

Harry Buhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frederic Magniez, Miklos Santha, and Ronald de Wolf. SIAM Journal on Computing, 34(6):1324-1330, 2005.

Quantum circuits with unbounded fan-out   [ ps | pdf ]

Peter Høyer and Robert Špalek. Theory of Computing, 1:81-103, 2005.

Consequences and limits of nonlocal strategies

Richard Cleve, Peter Høyer, Ben Toner, and John Watrous. Proc. of 19th IEEE Conference on Computational Complexity, June 2004.

The quantum query complexity of the hidden subgroup problem is polynomial   [ ps | pdf ]

Mark Ettinger, Peter Høyer, and Emanuel Knill. Information Processing Letters, 91(1):43-48, 16 July 2004.

Combinatorics and quantum nonlocality   [ ps | pdf ]

Harry Buhrman, Peter Høyer, Serge Massar, and Hein Röhrig. Physical Review Letters, 91:047903, 2003.

Quantum search on bounded-error inputs   [ ps | pdf ]

Peter Høyer, Michele Mosca, and Ronald de Wolf. Proc. of 30th International Colloquium on Automata, Languages, and Programming (ICALP'03), LNCS 2719, 291-299, 2003.

Improved quantum communication complexity bounds for disjointness and equality   [ ps | pdf ]

Peter Høyer and Ronald de Wolf. Proc. 19th International Symposium on Theoretical Aspects of Computer Science (STACS'02), LNCS 2285, 299-310, 2002.

Quantum amplitude amplification and estimation   [ ps | pdf ]

Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. In Quantum Computation and Quantum Information: A Millennium Volume, AMS Contemporary Mathematics Series, Volume 305, 2002.

Quantum complexities of ordered searching, sorting, and element distinctness   [ ps | pdf ]

Peter Høyer, Jan Neerbek, and Yaoyun Shi. Algorithmica, Springer-Verlag, 34(4):429--448, 2002. Special issue on Quantum Computation and Cryptography. Also in Proc. of 28th International Colloquium on Automata, Languages, and Programming (ICALP'01), LNCS 2076, 346-357, 2001.

Introduction to recent quantum algorithms   

Peter Høyer. Proc. of 26th International Symposium on Mathematical Foundations of Computer Science (MFCS'01), LNCS 2136, 62-73, 2001.

Simplified proof of the Fourier sampling theorem   [ ps | pdf ]

Peter Høyer. Information Processing Letters, 75(4):139-143, 2000.

Arbitrary phases in quantum amplitude amplification   [ ps | pdf ]

Peter Høyer. Physical Review A, 62:052304, 2000.

On quantum algorithms for noncommutative hidden subgroups   [ ps | pdf ]

Mark Ettinger and Peter Høyer. Advances in Applied Mathematics, 25(3):239-251, 2000.

Multiparty quantum communication complexity   [ ps | pdf ]

Harry Buhrman, Wim van Dam, Peter Høyer, and Alain Tapp. Physical Review A, 60(4):2737-2741, 1999.

Conjugated operators in quantum algorithms   [ ps | pdf ]

Peter Høyer. Physical Review A, 59(5):3280-3289, 1999.

Tight bounds on quantum searching   [ ps | pdf ]

Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Fortschritte Der Physik, 46(4-5):493-505, 1998.

Quantum counting   [ ps ]

Gilles Brassard, Peter Høyer, and Alain Tapp. Proc. of 25th International Colloquium on Automata, Languages, and Programming (ICALP'98), LNCS 1443, 820-831, 1998.

Quantum cryptanalysis of hash and claw-free functions   [ ps ]

Gilles Brassard, Peter Høyer, and Alain Tapp. Proc. of Third Latin American Symposium on Theoretical Informatics (LATIN'98), LNCS 1380, 163-169, 1998.

An exact quantum polynomial-time algorithm for Simon's problem   [ ps | pdf ]

Gilles Brassard and Peter Høyer. Proc. of Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS'97), 12-23, 1997.

Efficient quantum transforms   [ ps ]

Peter Høyer. February 1997.

Algorithmics

Parametric permutation routing via matchings   [ ps | pdf ]

Peter Høyer and Kim S. Larsen. Nordic Journal of Computing, 5(2):105-114, 1998.

A general technique for implementation of efficient priority queues   [ preprint.ps | istcs.ps ]

Peter Høyer. Proc. of Third Israeli Symposium on Theory of Computing and Systems (ISTCS'95), 57-66, 1995.