اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
77
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In communication complexity, a number of distant parties have the task of calculating a distributed function of their inputs, while minimizing the amount of communication between them. It is known that with quantum resources, such as entanglement and quantum channels, one can obtain significant reductions in the communication complexity of some tasks. In this work, we study the role of the quantum superposition of the direction of communication as a resource for communication complexity. We present a tripartite communication task for which such a superposition allows for an exponential saving in communication, compared to one-way quantum (or classical) communication; the advantage also holds when we allow for protocols with bounded error probability.
قيم البحث
اقرأ أيضاً
We give the first exponential separation between quantum and classical multi-party communication complexity in the (non-interactive) one-way and simultaneous message passing settings. For every k, we demonstrate a relational communication problem b
etween k parties that can be solved exactly by a quantum simultaneous message passing protocol of cost O(log n) and requires protocols of cost n^{c/k^2}, where c>0 is a constant, in the classical non-interactive one-way message passing model with shared randomness and bounded error. Thus our separation of corresponding communication classes is superpolynomial as long as k=o(sqrt{log n / loglog n}) and exponential for k=O(1).
In a variant of communication complexity tasks, two or more separated parties cooperate to compute a function of their local data, using a limited amount of communication. It is known that communication of quantum systems and shared entanglement can
increase the probability for the parties to arrive at the correct value of the function, compared to classical resources. Here we show that quantum superpositions of the direction of communication between parties can also serve as a resource to improve the probability of success. We present a tripartite task for which such a superposition provides an advantage compared to the case where the parties communicate in a fixed order. In a more general context, our result also provides the first semi-device-independent certification of the absence of a definite order of communication.
A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical protocols on _total_ Boolean functions in the two-party interactive model. The answer appears to be ``No. In 2002,
Razborov proved this conjecture for so far the most general class of functions F(x, y) = f(x_1 * y_1, x_2 * y_2, ..., x_n * y_n), where f is a_symmetric_ Boolean function on n Boolean inputs, and x_i, y_i are the ith bit of x and y, respectively. His elegant proof critically depends on the symmetry of f. We develop a lower-bound method that does not require symmetry and prove the conjecture for a broader class of functions. Each of those functions F(x, y) is obtained by what we call the ``block-composition of a ``building block g : {0, 1}^k by {0, 1}^k --> {0, 1}, with an f : {0, 1}^n -->{0, 1}, such that F(x, y) = f(g(x_1, y_1), g(x_2, y_2), ..., g(x_n, y_n)), where x_i and y_i are the ith k-bit block of x and y, respectively. We show that as long as g itself is ``hard enough, its block-composition with an_arbitrary_ f has polynomially related quantum and classical communication complexities. Our approach gives an alternative proof for Razborovs result (albeit with a slightly weaker parameter), and establishes new quantum lower bounds. For example, when g is the Inner Product function for k=Omega(log n), the_deterministic_ communication complexity of its block-composition with_any_ f is asymptotically at most the quantum complexity to the power of 7.
The quantum Zeno effect (QZE) is the phenomenon where the unitary evolution of a quantum state is suppressed e.g. due to frequent measurements. Here, we investigate the use of the QZE in a class of communication complexity problems (CCPs). Quantum en
tanglement is known to solve certain CCPs beyond classical constraints. However, recent developments have yielded CCPs where super-classical results can be obtained using only communication of a single d-level quantum state (qudit) as a resource. In the class of CCPs considered here, we show quantum reduction of complexity in three ways: using i) entanglement and the QZE, ii) single qudit and the QZE, iii) single qudit. The final protocol is motivated by experimental feasibility, and we have performed a proof of concept experimental demonstration.
Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks such as parallel computation and circuit optimisation. Crucially, the communication overhead introduced by the allotment process should be minimised -- a
key motivation behind the communication complexity problem (CCP). Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. Furthermore, the connection between quantum CCPs and nonlocality provides an information-theoretic insights into fundamental quantum mechanics. Here we connect quantum CCPs with a generalised nonlocality framework -- beyond the paradigmatic Bells theorem -- by incorporating the underlying causal structure, which governs the distributed task, into a so-called nonlocal hidden variable model. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities, whose violation is both necessary and sufficient for a quantum gain. We experimentally implement a multipartite CCP akin to the guess-your-neighbour-input scenario, and demonstrate a quantum advantage when multipartite Greenberger-Horne-Zeilinger (GHZ) states are shared among three users.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
