𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nondeterministic Quantum Query and Communication Complexities

✍ Scribed by de Wolf, Ronald

Book ID
118181184
Publisher
Society for Industrial and Applied Mathematics
Year
2003
Tongue
English
Weight
216 KB
Volume
32
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Relationships between nondeterministic a
Relationships between nondeterministic and deterministic tape complexities
✍ Walter J. Savitch πŸ“‚ Article πŸ“… 1970 πŸ› Elsevier Science 🌐 English βš– 816 KB

The amount of storage needed to simulate a nondeterministic tape bounded Turing machine on a deterministic Turing machine is investigated. Results include the following: Theorem. A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic [L(n)]2-tape bounded Turing machi

Quantum communication and complexity
Quantum communication and complexity
✍ Ronald de Wolf πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 182 KB

In the setting of communication complexity, two distributed parties want to compute a function depending on both their inputs, using as little communication as possible. The required communication can sometimes be signiΓΏcantly lowered if we allow the parties the use of quantum communication. We surv