scientific article; zbMATH DE number 1775389
From MaRDI portal
Publication:4542521
zbMath1028.68056arXivquant-ph/9802040MaRDI QIDQ4542521
Harry Buhrman, Richard Cleve, Avi Wigderson
Publication date: 27 January 2004
Full work available at URL: https://arxiv.org/abs/quant-ph/9802040
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Network protocols (68M12)
Related Items
Experimental multipartner quantum communication complexity employing just one qubit ⋮ Quantum entanglement as a new information processing resource ⋮ An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Conic formulations of graph homomorphisms ⋮ Query Complexity in Expectation ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ The communication complexity of the Hamming distance problem ⋮ Turán numbers of sunflowers ⋮ Quantum separation of local search and fixed point computation ⋮ Approximate Degree in Classical and Quantum Computing ⋮ On a restricted cross-intersection problem ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Sabidussi versus Hedetniemi for three variations of the chromatic number ⋮ Deterministic quantum non-locality and graph colorings ⋮ Quantum weakly nondeterministic communication complexity ⋮ Towards characterizing the non-locality of entangled quantum states ⋮ From Quantum Query Complexity to State Complexity ⋮ A broader view on the limitations of information processing and communication by nature ⋮ Distinguishing orthogonality graphs ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ The communication complexity of functions with large outputs ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Bounds on oblivious multiparty quantum communication complexity ⋮ Unnamed Item ⋮ Communication and information complexity ⋮ Unbounded-error quantum query complexity ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ Intricacies of quantum computational paths ⋮ Quantum search with variable times ⋮ New degree bounds for polynomial threshold functions ⋮ Quantum lower bounds by quantum arguments ⋮ One-Sided Error Communication Complexity of Gap Hamming Distance. ⋮ Unavoidable hypergraphs ⋮ On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity ⋮ On decomposable correlation matrices ⋮ Optimal joint remote state preparation of arbitrary equatorial multi-qudit states ⋮ Property testing lower bounds via communication complexity ⋮ Noise and the Mermin-GHZ Game ⋮ Polynomial degree vs. quantum query complexity ⋮ On the power of Ambainis lower bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quantum pseudo-telepathy ⋮ Bell inequalities and the separability criterion ⋮ Exponential separation of quantum and classical online space complexity ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Streaming Algorithms with One-Sided Estimation ⋮ Unnamed Item ⋮ Noisy Interactive Quantum Communication ⋮ Frankl-Rödl-type theorems for codes and permutations ⋮ Communication Lower Bounds Using Directional Derivatives ⋮ Quantum communication and complexity. ⋮ Specified intersections ⋮ Quantum versus randomized communication complexity, with efficient players ⋮ Unnamed Item ⋮ Quantum homomorphisms ⋮ Upper bounds on communication in terms of approximate rank
