Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Entropy lower bounds for quantum decision tree complexity
Autore:
Shi, YY;
Indirizzi:
Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA Princeton Univ Princeton NJ USA 08544 t Comp Sci, Princeton, NJ 08544 USA
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 1, volume: 81, anno: 2002,
pagine: 23 - 27
SICI:
0020-0190(20020116)81:1<23:ELBFQD>2.0.ZU;2-S
Fonte:
ISI
Lingua:
ENG
Soggetto:
POLYNOMIALS;
Keywords:
quantum computation; decision tree; lower bounds; computational complexity; entropy;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
8
Recensione:
Indirizzi per estratti:
Indirizzo: Shi, YY Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA Princeton Univ Princeton NJ USA 08544 ci, Princeton, NJ 08544 USA
Citazione:
Y.Y. Shi, "Entropy lower bounds for quantum decision tree complexity", INF PROCESS, 81(1), 2002, pp. 23-27

Abstract

We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard decision tree computation as a communication process in which the oracle and the computer exchange several rounds of messages, each round consisting of O(log n) bits. Let E(f) be the Shannon entropy of the random variable f (X), where X is taken uniformly random in f's domain. Our main result is that it takes n (E (f)) queries to computeany total function f. It is interesting to contrast this bound with the Omega (E (f)/log n) bound, which is tight for some partial functions. (C) 2002 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 19/01/20 alle ore 15:14:07