Home    People    Research    Publications    Presentations    Annual Report   

Publications by P. Høyer

Refereed Journal Publications

    2019

  1. A. Anshu, P. Høyer, M. Mhalla and S. Perdrix, Contextuality in multipartite pseudo-telepathy graph games, Journal of Computer and System Sciences 107: 156 - 165, 8 August 2019.

  2. G. Brassard, P. Høyer, K. Kalach, M. Kaplan, S. Laplante and L. Salvail, Key establishment à la Merkle in a quantum world, Journal of Cryptology 32(3): 601 - 634, 8 April 2019.

  3. 2016

  4. M. Adcock, P. Høyer and B. C. Sanders, Quantum computation with coherent spin states and the close Hadamard problem, Quantum Information Processing 15(4): 1361 - 1386, 1 April 2016.

  5. 2014

  6. T. Decker, P. Høyer, G. Ivanyos and M. Santha, Polynomial time quantum algorithms for certain bivariate hidden polynomial problems, Quantum Information and Computation 14(91): 796 - 806, 1 July 2014.

  7. 2013

  8. P. Høyer and J. Rashid, Quantum nonlocal boxes exhibit stronger distillability, Modern Physics Letters A 28(17): 1330012 (29 pp.), 29 May 2013, arXiv.org:quant-ph/1204.4622.

  9. M. Adcock, P. Høyer and B. C. Sanders, Gaussian quantum computation with oracle-decision problems, Quantum Information Processing 12(4): 1759 - 1779, 1 April 2013, arXiv.org:1206.1035.

  10. 2011

  11. N. Wiebe, D. W. Berry, P. Høyer and B. C. Sanders, Simulating quantum dynamics on a quantum computer, Journal of Physics A: Mathematical and General 44(44): 445308 (20 pp.), 18 October 2011, arXiv.org:1011.3489.

  12. 2010

  13. P. Høyer and J. Rashid, Optimal protocols for nonlocality distillation, Physical Review A 82(4): 042118 (6 pp.), 9 September 2010, arXiv.org:1009.1668.

  14. N. Wiebe, D. W. Berry, P. Høyer and B. C. Sanders, Higher order decompositions of ordered operator exponentials, Journal of Physics A: Mathematical and Theoretical 43(6): 065203 (20 pp.), 22 January 2010, arXiv.org:0812.0562.

  15. 2009

  16. M. Adcock, P. Høyer and B. C. Sanders, Limitations on continuous variable quantum algorithms with Fourier transforms, New Journal of Physics 11: 103035 (24 pp.), 21 October 2009, arXiv.org:arxiv:0812.3694.

  17. C. Dohotaru and P. Høyer, Exact quantum lower bound for Grover's problem, Quantum Information and Computation 9(5-6): 533 - 540, 1 May 2009, arXiv.org:0810.3647.

  18. 2008

  19. P. Høyer, J. Neerbek and Y. Shi, Quantum complexities of ordered searching,sorting, and element distinctness, Algorithmica 34(4): 429 - 448, 1 March 2008.

  20. 2006

  21. C. Dürr, M. Heiligman, P. Høyer and M. Mhalla, Quantum query complexity of some graph problems, SIAM Journal on Computing 35(6): 1310 - 1328, 1 May 2006, arXiv.org:quant-ph/0401091. (Best paper award for track A at ICALP '04).

  22. H. Buhrman, P. Høyer, S. Massar and H. Röhrig, Multipartite nonlocal quantum correlations resistant to imperfections, Physical Review A 73(1): 012321 (9 pp.), 18 January 2006.

  23. 2005

  24. P. Høyer, Quantum algorithms: When errors are intolerable, Nature Physics 1(3): 141 - 142, 1 December 2005.

  25. P. Høyer and R. Špalek, Lower bounds on quantum query complexity, Bulletin of the European Association for Theoretical Computer Science 87: 78 - 103, 1 October 2005, arXiv.org:quant-ph/0509153.

  26. H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha and R. de Wolf, Quantum algorithms for element distinctness, SIAM Journal on Computing 34(6): 1324 - 1330, 21 September 2005, arXiv.org:quant-ph/0007016.

  27. H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha and R. de Wolf, Quantum algorithms for element distinctness, SIAM Journal on Computing 34(6): 1324 - 1330, 1 September 2005, arXiv.org:quant-ph/0007016.

  28. P. Høyer and R. Špalek, Quantum Fan-out is Powerful, Theory of Computing 1: 81 - 103, 3 August 2005.

  29. P. Høyer and R. Špalek, Quantum circuits with unbounded fan-out, Theory of Computing 1(5): 81 - 103, 3 August 2005, arXiv.org:quant-ph/0208043.

  30. 2004

  31. M. Ettinger, P. Høyer and E. Knill, The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters 91(1): 43 - 48, 16 July 2004, arXiv.org:quant-ph/0401083.

  32. 2003

  33. H. Buhrman, P. Høyer, S. Massar and H. Röhrig, Combinatorics and Quantum Nonlocality, Physical Review Letters 91(4): 047903 (4 pp.), 25 July 2003, arXiv.org:quant-ph/0209052.

  34. 2002

  35. P. Høyer, J. Neerbek and Y. Shi, Quantum complexities of ordered searching, sorting, and element distinctness, Algorithmica 34(4): 429 - 448, 1 November 2002, arXiv.org:quant-ph/0102078. Special issue on Quantum Computation and Cryptography.

  36. G. Brassard, P. Høyer, M. Mosca and A. Tapp, Quantum amplitude amplification and estimation, Quantum Computation and Quantum Information 305, 1 October 2002, arXiv.org:quant-ph/0005055.

  37. 2000

  38. P. Høyer, Arbitrary phases in quantum amplitude amplification, Physical Review A 62(5): 052304 (5 pp.), 1 November 2000, arXiv.org:quant-ph/0006031.

  39. M. Ettinger and P. Høyer, On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics 25(3): 239 - 251, 1 October 2000, arXiv.org:quant-ph/9807029.

  40. P. Høyer, Simplified proof of the Fourier sampling theorem, Information Processing Letters 75(4): 139 - 143, 30 September 2000.

  41. 1999

  42. H. Buhrman, W. v. Dam, P. Høyer and A. Tapp, Multiparty quantum communication complexity, Physical Review A 60(4): 2737 - 2741, 1 October 1999, arXiv.org:quant-ph/9710054.

  43. P. Høyer, Conjugated operators in quantum algorithms, Physical Review A 59(5): 3280 - 3289, 1 May 1999.

  44. 1998

  45. P. Høyer and K. S. Larsen, Parametric permutation routing via matchings, Nordic Journal of Computing 5(2): 105 - 114, 1 July 1998.

  46. M. Boyer, G. Brassard, P. Høyer and A. Tapp, Tight bounds on quantum searching, Fortschritte Der Physik 46(4-5): 493 - 505, 1 June 1998.

E-prints on the arXiv

    2012

  1. J. Rashid and P. Høyer, Quantum nonlocal boxes exhibit stronger distillability, arXiv.org:1204.4622, 20 April 2012.


  2. 2005

  3. P. Høyer, T. Lee and R. Špalek, Tight adversary bounds for composite functions, arXiv.org:quant-ph/0509067, 9 September 2005.


  4. 2004

  5. H. Buhrman, P. Høyer, S. Massar and H. Röhrig, Multipartite Nonlocal Quantum Correlations Resistant to Imperfections, arXiv.org:quant-ph/0410139, 19 October 2004.


  6. 1997

  7. P. Høyer, Efficient quantum transforms, arXiv.org:quant-ph/9702028, 12 February 1997.


Conference Publications

    2017

  1. A. Anshu, P. Høyer, M. Mhalla and S. Perdrix, Contextuality in multipartite pseudo-telepathy graph games, 16 August 2017, Lecture Notes in Computer Science : 41 - 45, Proceedings of International Symposium on Fundamentals of Computation Theory (FCT 2017), Bordeaux, France, 11 Sep 2017 - 13 Sep 2017. LNCS, volume 10472.


  2. C. Dohotaru and P. Høyer, Controlled quantum amplification, 31 July 2017, Proceedings of 44th International Colloquium on Automata, Languages, and Programming (ICALP2017), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, Anca Muscholl, eds., Warsaw, Poland, 10 Jul 2017 - 14 Jul 2017 (ISBN 978-3-95977-041-5).


  3. A. Belovs, G. Brassard, P. Høyer, M. Kaplan, S. Laplante and L. Salvail, Provably secure key establishment against quantum adversaries, 30 June 2017, Proceedings of 12th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2017), M. M. Wilde, eds. 73: 3:1 - 3:17, 14 Jun 2017 - 16 Jun 2017, Published by ACM, New York (ISBN 978-3-95977-034-7).


  4. P. Høyer and M. Komeili, Efficient quantum walk on the grid with multiple marked elements, 15 May 2017, Proceedings of 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) 42: 1 - 14, Hannover, Germany, 8 Mar 2017 - 11 Mar 2017.


  5. 2011

  6. G. Brassard, P. Høyer, K. Kalach, M. Kaplan, S. Laplante and L. Salvail, Merkle puzzles in a quantum world (contributed, refereed), 14 August 2011, Lecture Notes in Computer Science 6841: 391 - 410, Proceedings of 31st Annual International Conference on Cryptology (CRYPTO 2011), Phillip Rogaway, eds., Santa Barbara, 14 Aug 2011 - 18 Aug 2011, arXiv.org:1108.2316.


  7. 2007

  8. P. Høyer, T. Lee and R. Špalek, Negative weights make adversaries stronger, Session 10B, 13 June 2007, Proceedings of The 39th ACM Symposium on Theory of Computing (STOC 2007): 526 - 535, San Diego, California, 11 Jun 2007 - 13 Jun 2007, Published by ACM, New York (ISBN 978-1-59593-631-8).


  9. 2006

  10. P. Høyer, M. Mhalla and S. Perdrix, Resources required for preparing graph states (contributed, refereed), 30 November 2006, Lecture Notes in Computer: Algorithms and Computation 4288: 638 - 649, Kolkata, India, 18 Dec 2006 - 20 Dec 2006, Published by Springer Berlin, Berlin, Germany (ISBN 978-3-540-49694-6).


  11. 2005

  12. P. Høyer, The phase matrix (contributed, refereed), 3 December 2005, Lecture Notes in Computer: Algorithms and Computation 3827: 308 - 317, Sanya, Hainan, China, 19 Dec 2005 - 21 Dec 2005, Published by Springer Berlin, Berlin, Germany (ISBN 978-3-540-30935-2).


  13. 2004

  14. R. Cleve, P. Høyer, B. Toner and J. Watrous, Consequences and limits of nonlocal strategies, 24 August 2004, Proceedings of 19th Annual Computational Complexity Conference (CCC 2004): 236 - 249, Amherst, MA, 21 Jun 2004 - 24 Jun 2004, Published by IEEE Comput. Soc., Los Alamitos, United States of America, arXiv.org:quant-ph/0404076.


  15. C. Dürr, M. Heiligman, P. Høyer and M. Mhalla, Quantum query complexity of some graph problems, 1 July 2004, Lecture Notes in Computer Science 3142: 481 - 493, Proceedings of 31st International Colloquium on Automata, Languages, and Programming (ICALP '04), J. Diaz, J. Karhumäki, A. Lepistö, D. Sannella, eds., Turku, Finland, 12 Jul 2004 - 16 Jul 2004 (ISBN 3 5402 2849 7). (Best paper award for track A).


  16. R. Cleve, P. Høyer, B. Toner and J. Watrous, Consequences and limits of nonlocal strategies, Computational Complexity, 21 June 2004, Proceedings of 19th IEEE Annual Conference on Computational Complexity (IEEE CCC 2004): 236 - 249, Amherst, 21 Jun 2004 - 24 Jun 2004, arXiv.org:quant-ph/0404076 (ISBN 0-7695-2120-7).


  17. 2003

  18. P. Høyer, M. Mosca and R. de Wolf, Quantum Search on Bounded-Error Inputs, 30 June 2003, Lecture Notes in Computer Science 2719: 291 - 299, Proceedings of 30th International Colloquium on Automata, Languages, and Programming (ICALP '03), Eindhoven, The Netherlands, 30 Jun 2003 - 4 Jul 2003, Published by Springer-Verlag, Berlin, Germany, arXiv.org:quant-ph/0304052.


  19. P. Høyer and R. Špalek, Quantum Circuits with Unbounded Fan-Out, 27 February 2003, Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS 2003) 2607: 234 - 246, Berlin, 27 Feb 2003 - 1 Mar 2003, Published by Springer-Verlag, Berlin, Germany (ISBN 3-540-00623-0). Proc. 20th International Symposium on Theoretical Aspects of Computer Science (STACS 03).


  20. 2002

  21. P. Høyer and R. de Wolf, Improved quantum communication complexity bounds for disjointness and equality, 14 March 2002, Lecture Notes in Computer Science 2285: 299 - 310, Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS 2002), Antibes - Juan les Pins, 14 Mar 2002 - 16 Mar 2002, Published by Springer-Verlag, Berlin, Germany, arXiv.org:quant-ph/0109068.


  22. 2001

  23. P. Høyer, Introduction to recent quantum algorithms, 27 August 2001, Proceedings of International Symposium on Mathematical Foundations of Computer Science (MFCS 2001) 2136: 62 - 73, Marianske Lazne, 27 Aug 2001 - 31 Aug 2001, Published by Springer-Verlag, Berlin, Germany.


  24. P. Høyer, J. Neerbek and Y. Shi, Quantum complexities of ordered searching, sorting, and element distinctness, 8 July 2001, Proceedings of 28th International Colloquium on Automata, Languages, and Programming (ICALP '01) 2076: 346 - 357, Heraklion, 8 Jul 2001 - 12 Jul 2001, Published by Springer-Verlag, Berlin, Germany, arXiv.org:quant-ph/0102078.


  25. H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha and R. de Wolf, Quantum algorithms for element distinctness, 30 June 2001, Proceedings of Sixteenth IEEE Conference on Computational Complexity (IEEE CCC 2001): 131-7, Chicago, 18 Jun 2001 - 21 Jun 2001 (ISBN 0 7695 1053 1).


  26. 1998

  27. G. Brassard, P. Høyer and A. Tapp, Quantum counting, 1 July 1998, Lecture Notes in Computer Science 1443: 820 - 831, Proceedings of 25th International Colloquium on Automata, Languages, and Programming (ICALP 1998), Aalborg, 13 Jul 1998 - 17 Jul 1998, arXiv.org:quant-ph/9805082.


  28. G. Brassard, P. Høyer and A. Tapp, Quantum cryptanalysis of hash and claw-free functions, 1 April 1998, Proceedings of Third Latin American Symposium on Theoretical Informatics (LATIN'98) (LATIN 1998) 1380: 163 - 169, Campinas, 20 Apr 1998 - 24 Apr 1998. Invited paper.


  29. 1997

  30. G. Brassard and P. Høyer, An exact quantum polynomial-time algorithm for Simon's problem, 1 June 1997, Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS 1997): 12 - 23, Ramat-Gan, 17 Jun 1997 - 19 Jun 1997, Published by IEEE Comput. Soc., Los Alamitos, United States of America, arXiv.org:quant-ph/9704027.


  31. 1995

  32. P. Høyer, A general technique for implementation of efficient priority queues, 4 January 1995, Proceedings of Third Israeli Symposium on Theory of Computing and Systems (ISTCS 1995): 57 - 66, Tel Aviv, 4 Jan 1995 - 6 Jan 1995, Published by Association for Computing Machinery.




For comments regarding this website, please contact
Last updated April 4, 2021