Nondeterministic Quantum Query and Quantum Communication Complexities

Simple item page
dc.creatorde Wolf, Ronald
dc.date2000-01-19
dc.date2004-01-15
dc.date.accessioned2026-07-07T03:15:50Z
dc.date.available2026-07-07T03:15:50Z
dc.descriptionWe 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.
dc.description19 pages, Latex
dc.identifierhttps://arxiv.org/abs/cs/0001014
dc.identifierhttp://arxiv.org/abs/cs/0001014
dc.identifierSIAM Journal on Computing, 32(3):681-699, 2003
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30134
dc.subjectComputational Complexity
dc.subjectQuantum Physics
dc.subjectE.4; F.1.1; F.1.2; F.1.3; F.2.0
dc.titleNondeterministic Quantum Query and Quantum Communication Complexities
dc.typetext

Files

Collections

arXiv