Computer Science – Computational Complexity
Scientific paper
2000-01-19
SIAM Journal on Computing, 32(3):681-699, 2003
Computer Science
Computational Complexity
19 pages, Latex
Scientific paper
We study nondeterministic quantum algorithms for Boolean functions f. Such algorithms have positive acceptance probability on input x iff f(x)=1. In the setting of query complexity, we show that the nondeterministic quantum complexity of a Boolean function is equal to its ``nondeterministic polynomial'' degree. We also prove a quantum-vs-classical gap of 1 vs n for nondeterministic query complexity for a total function. In the setting of communication complexity, we show that the nondeterministic quantum complexity of a two-party function is equal to the logarithm of the rank of a nondeterministic version of the communication matrix. This implies that the quantum communication complexities of the equality and disjointness functions are n+1 if we do not allow any error probability. We also exhibit a total function in which the nondeterministic quantum communication complexity is exponentially smaller than its classical counterpart.
No associations
LandOfFree
Nondeterministic Quantum Query and Quantum Communication Complexities does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Nondeterministic Quantum Query and Quantum Communication Complexities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nondeterministic Quantum Query and Quantum Communication Complexities will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-119390