[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms

  • Conference paper
SOFSEM 2005: Theory and Practice of Computer Science (SOFSEM 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3381))

Abstract

The complexity of quantum query algorithms computing Boolean functions is strongly related to the degree of the algebraic polynomial representing this Boolean function. There are two related difficult open problems. First, Boolean functions are sought for which the complexity of exact quantum query algorithms is essentially less than the complexity of deterministic query algorithms for the same function. Second, Boolean functions are sought for which the degree of the representing polynomial is essentially less than the complexity of deterministic query algorithms. We present in this paper new techniques to solve the second problem.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum Lower Bounds by Polynomials. In: FOCS 1998, pp. 352–361 (1998)

    Google Scholar 

  2. Buhrman, H., de Wolf, R.: Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science 288(1), 21–43 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  3. Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society, London A400, 97–117 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  4. Gruska, J.: Quantum Computing. McGraw-Hill, New York (1999)

    Google Scholar 

  5. Midrijānis, G.: Exact quantum query complexity for total Boolean functions, http://arxiv.org/abs/quant-ph/0403168

  6. Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics and Computer Science, University of Latvia, Raina bulv. 29, Riga, Latvia

    Raitis Ozols, Rūsiņš Freivalds, Jevgeņijs Ivanovs, Elīna Kalniņa & Lelde Lāce

  2. Tsukuba College of Technology, 4-3-15 Amakubo, Tsukuba, Ibaraki, 305-0005, Japan

    Masahiro Miyakawa & Hisayuki Tatsumi

  3. Department of Mathematics, Cornell University, 511 Malott Hall, Ithaca, NY, 14853, U.S.A.

    Daina Taimiņa

Authors
  1. Raitis Ozols
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rūsiņš Freivalds
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jevgeņijs Ivanovs
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Elīna Kalniņa
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Lelde Lāce
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Masahiro Miyakawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Hisayuki Tatsumi
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Daina Taimiņa
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Charles University, Prague, Czech Republic

    Peter Vojtáš

  2. Institute of Informatics and Software Engineering Faculty of Informatics and Information technologies, Slovak University of Technology, Ilkovičova 3, 842 16, Bratislava,  

    Mária Bieliková

  3. STIX, École Polytechnique, 91128, Palaiseau Cedex, France

    Bernadette Charron-Bost

  4. Department of Computer Science, University of Loughborough, Loughborough, UK

    Ondrej Sýkora

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ozols, R. et al. (2005). Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms. In: Vojtáš, P., Bieliková, M., Charron-Bost, B., Sýkora, O. (eds) SOFSEM 2005: Theory and Practice of Computer Science. SOFSEM 2005. Lecture Notes in Computer Science, vol 3381. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30577-4_50

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-30577-4_50

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-24302-1

  • Online ISBN: 978-3-540-30577-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation