A lower bound on the quantum query complexity of read-once functions

Howard Barnum, Michael Saks

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

We establish a lower bound of Ω(n) on the bounded-error quantum query complexity of read-once Boolean functions. The result is proved via an inductive argument, together with an extension of a lower bound method of Ambainis. Ambainis' method involves viewing a quantum computation as a mapping from inputs to quantum states (unit vectors in a complex inner-product space) which changes as the computation proceeds. Initially the mapping is constant (the state is independent of the input). If the computation evalutes the function f then at the end of the computation the two states associated with any f-distinguished pair of inputs (having different f values) are nearly orthogonal. Thus the inner product of their associated states must have changed from 1 to nearly 0. For any set of f-distinguished pairs of inputs, the sum of the inner products of the corresponding pairs of states must decrease significantly during the computation, By deriving an upper bound on the decrease in such a sum, during a single step, for a carefully selected set of input pairs, one can obtain a lower bound on the number of steps. We extend Ambainis' bound by considering general weighted sums of f-distinguished pairs. We then prove our result for read-once functions by induction on the number of variables, where the induction step involves a careful choice of weights depending on f to optimize the lower bound attained.

Original languageEnglish (US)
Pages (from-to)244-258
Number of pages15
JournalJournal of Computer and System Sciences
Volume69
Issue number2
DOIs
StatePublished - Sep 1 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Decision tree complexity
  • Lower bounds
  • Quantum computation
  • Quantum query complexity
  • Query complexity
  • Read-once functions

Fingerprint Dive into the research topics of 'A lower bound on the quantum query complexity of read-once functions'. Together they form a unique fingerprint.

  • Cite this