### 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 language | English (US) |
---|---|

Pages (from-to) | 244-258 |

Number of pages | 15 |

Journal | Journal of Computer and System Sciences |

Volume | 69 |

Issue number | 2 |

DOIs | |

State | Published - Sep 1 2004 |

### Fingerprint

### 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

}

*Journal of Computer and System Sciences*, vol. 69, no. 2, pp. 244-258. https://doi.org/10.1016/j.jcss.2004.02.002

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

Research output: Contribution to journal › Article

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 -