Quantum Algorithms for Weighing Matrices and Quadratic Residues

Preprint English OPEN
van Dam, Wim;
  • Identifiers: doi: 10.1007/s00453-002-0975-4
  • Subject: Mathematics - Combinatorics | Computer Science - Computational Complexity | Quantum Physics
    arxiv: Computer Science::Databases

In this article we investigate how we can employ the structure of combinatorial objects like Hadamard matrices and weighing matrices to device new quantum algorithms. We show how the properties of a weighing matrix can be used to construct a problem for which the quantu... View more
  • References (30)
    30 references, page 1 of 3

    [1] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf, “Quantum lower bounds by polynomials”, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 352-361, IEEE Computer Society Press (1998); quant-ph report no. 9802049

    [2] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani, “Strengths and weaknesses of quantum computing”, SIAM Journal on Computing, Volume 26, No. 5, pages 1510-1523 (1997); quant-ph report no. 9701001

    [3] Bruce C. Berndt, Ronald J. Evans, and Kenneth S. Williams, Gauss and Jacobi Sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, Volume 21, John Wiley & Sons (1998)

    [4] Ethan Bernstein and Umesh Vazirani, “Quantum complexity theory”, SIAM Journal on Computing, Volume 26, No. 5, pages 1411-1473 (1997)

    [5] Andr´e Berthiaume, “Quantum computation”, in Complexity Theory Retrospective, In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, edited by Alan L. Selman, Volume 2, pages 23-51, SpringerVerlag (1997); URL http://andre.cs.depaul.edu/Andre/

    [6] Andr´e Berthiaume and Gilles Brassard, “Oracle quantum computing”, Journal of Modern Optics, Volume 41, No. 12, pages 2521-2535 (1994)

    [7] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp, “Tight bounds on quantum searching”, Fortschritte der Physik, Volume 46, No. 4-5, pages 493-505 (1998); quant-ph report no. 9605034

    [8] Harry Buhrman and Wim van Dam, “Bounded quantum query complexity”, Proceedings of the 14th Annual IEEE Conference on Computational Complexity, pages 149-156 (1999); quant-ph report no. 9903035

    [9] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca, “Quantum algorithms revisited”, Proceedings of the Royal Society of London A, Volume 454, pages 339-354 (1998); quant-ph report no. 9708016

    [10] Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics 138, Springer-Verlag (1993)

  • Related Organizations (2)
  • Metrics
Share - Bookmark