Nondeterministic Quantum Query and Quantum Communication Complexities

Abstract

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.

19 pages, Latex

References in corpus (9)

• Strengths and Weaknesses of Quantum Computing
• Quantum fingerprinting
• Substituting Quantum Entanglement for Communication
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• A Limit on the Speed of Quantum Computation in Determining Parity
• Complexity limitations on quantum computation
• Classical simulation of quantum entanglement without local hidden variables
• Improved Quantum Communication Complexity Bounds for Disjointness and Equality
• Sharp Quantum vs. Classical Query Complexity Separations

Cited by in corpus (6)

• Fooling One-Sided Quantum Protocols
• Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication
• Query complexity in expectation
• Properties and Application of Nondeterministic Quantum Query Algorithms
• Quantum Zero-Error Algorithms Cannot be Composed
• Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity