Nondeterministic Quantum Query and Communication Complexities

DOI10.1137/S0097539702407345zbMath1026.68055MaRDI QIDQ4706225

Ronald de Wolf

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

quantum computingnondeterminismcommunication complexityquery complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (22)

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Query Complexity in Expectation ⋮ Common information and unique disjointness ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ Quantum weakly nondeterministic communication complexity ⋮ Quantum attribute-based encryption: a comprehensive study ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ Unbounded-error quantum query complexity ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Unbounded-Error Classical and Quantum Communication Complexity ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Quantum certificate complexity ⋮ Extended formulations in combinatorial optimization ⋮ Information-theoretic approximations of the nonnegative rank ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Exponential separation of quantum and classical online space complexity ⋮ On the extension complexity of combinatorial polytopes ⋮ Quantum zero-error algorithms cannot be composed ⋮ The border support rank of two-by-two matrix multiplication is seven ⋮ Pitch, extension complexity, and covering problems ⋮ A short proof that the extension complexity of the correlation polytope grows exponentially ⋮ Unnamed Item

This page was built for publication: Nondeterministic Quantum Query and Communication Complexities