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

Howard Barnum, Michael Saks

Research output: Contribution to journalArticle

27 Citations (Scopus)

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

Fingerprint

Query Complexity
Lower bound
Scalar, inner or dot product
Proof by induction
Quantum computers
Boolean functions
Decrease
Inner product space
Unit vector
Quantum Computation
Quantum State
Boolean Functions
Weighted Sums
Optimise
Upper bound

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

Cite this

@article{b71e7613f9c345fc827c9aa51b53fcb8,
title = "A lower bound on the quantum query complexity of read-once functions",
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.",
keywords = "Decision tree complexity, Lower bounds, Quantum computation, Quantum query complexity, Query complexity, Read-once functions",
author = "Howard Barnum and Michael Saks",
year = "2004",
month = "9",
day = "1",
doi = "10.1016/j.jcss.2004.02.002",
language = "English (US)",
volume = "69",
pages = "244--258",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Academic Press Inc.",
number = "2",

}

A lower bound on the quantum query complexity of read-once functions. / Barnum, Howard; Saks, Michael.

In: Journal of Computer and System Sciences, Vol. 69, No. 2, 01.09.2004, p. 244-258.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Barnum, Howard

AU - Saks, Michael

PY - 2004/9/1

Y1 - 2004/9/1

N2 - 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.

AB - 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.

KW - Decision tree complexity

KW - Lower bounds

KW - Quantum computation

KW - Quantum query complexity

KW - Query complexity

KW - Read-once functions

UR - http://www.scopus.com/inward/record.url?scp=3342887162&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3342887162&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2004.02.002

DO - 10.1016/j.jcss.2004.02.002

M3 - Article

AN - SCOPUS:3342887162

VL - 69

SP - 244

EP - 258

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 2

ER -