On the power and limitations of quantum computing models : quantum walks and communication complexity

Ronald de Wolf

Angad Mohandas Kamat

Quantum computing resources have been known to provide speed-ups in computational complexity in many algorithms. The impact of these resources in communication, however, has not attracted much attention. We investigate the impact of \nquantum entanglement on communication complexity. We provide a positive result, \nby presenting a class of multi-party communication problems wherein the presence of \na suitable quantum entanglement lowers the classical communication complexity. We \nshow that, in evaluating certains function whose parameters are distributed among \nvarious parties, the presence of prior entanglement can help in reducing the required \ncommunication. We also present an outline of realizing the required entanglement \nthrough optical photon quantum computing. We also suggest the possible impact of \nour results on network information flow problems, by showing an instance of a lower \nbound which can be broken by adding limited power to the communication model.

Ran Raz, Amir Shpilka

We study the power of quantum proofs, or more precisely, the power of Quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the Linear Subspaces Distance problem. The problem is of geometrical nature: Each player gets a linear subspace of R m and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 · √ 2) and 0 if the distance is very large (say, larger than 0.9 · √ 2). We show that: 1. The QMA communication complexity of the problem is O(log m). 2. The (classical) MA communication complexity of the problem is Ω(m ɛ) (for some ɛ> 0). 3. The (standard) quantum communication complexity of the problem is Ω ( √ m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity.

孝志 三原

Lance Fortnow, John D. Rogers

V. S. Moskvin

Signal processing is important for modern technologies such as digital communication systems and sensor networks, and is used to enhance and optimize the quality of transmitted signals. However, traditional methods and design frameworks are insufficient for the demands of future communication networks, which are expected to be highly complex and constantly changing. Our research focuses on a mathematical model known as a Markov model, which represents a system as a series of states linked by transitions. This model can be applied to various signal processing challenges in telecommunications, such as the modeling of communication channels, sources of information, and the correction of distortion and noise in transmitted signals. We examine the random walk algorithm, a simple and efficient way to simulate the behavior of a Markov chain, as it can provide valuable insights into the performance of communication systems and help to optimize their design. However, it may not be able to accurately model systems with complex transitions or systems that exhibit long-term correlations. In order to address the challenges and limitations of classical random walk, we propose the use of quantum random walk, which is a quantum mechanical version of classical random walk. It describes the motion of particles in a probabilistic way, similar to classical random walk, but with the added complexity of quantum mechanics. We also provide quantum walk algorithm with Hadamard gate implementation for coin operator.