Quantum algorithms and communication protocols

Koji Nagata, Tadao Nakamura

We present quantum key distribution based on Deutsch's algorithm using an entangled state. The security of the protocol is based on it of Ekert 91 protocol. That is, the existence of eavesdroppers must destroy entanglement. Next, we study quantum communication based on two quantum algorithms, such as the Bernstein-Vazirani algorithm and Simon's algorithm. We discuss the fact that quantum communication overcomes classical communication by a factor of $N$ in the Bernstein-Vazirani algorithm case. Also we discuss the fact that quantum communication overcomes classical communication by a factor of $O(\sqrt{2^N}/N)$ in Simon's algorithm case.

David Peter Divincenzo

Lijie Chen, Ruosong Wang

In recent years, the polynomial method from circuit complexity has been applied to several fundamental problems and obtains the state-of-the-art running times (e.g., R. Williams's n^3 / 2^{Omega(sqrt{log n})} time algorithm for APSP). As observed in [Alman and Williams, STOC 2017], almost all applications of the polynomial method in algorithm design ultimately rely on certain (probabilistic) low-rank decompositions of the computation matrices corresponding to key subroutines. They suggest that making use of low-rank decompositions directly could lead to more powerful algorithms, as the polynomial method is just one way to derive such a decomposition. Inspired by their observation, in this paper, we study another way of systematically constructing low-rank decompositions of matrices which could be used by algorithms - communication protocols. Since their introduction, it is known that various types of communication protocols lead to certain low-rank decompositions (e.g., P protocols/rank, BQP protocols/approximate rank). These are usually interpreted as approaches for proving communication lower bounds, while in this work we explore the other direction. We have the following two generic algorithmic applications of communication protocols: - Quantum Communication Protocols and Deterministic Approximate Counting. Our first connection is that a fast BQP communication protocol for a function f implies a fast deterministic additive approximate counting algorithm for a related pair counting problem. Applying known BQP communication protocols, we get fast deterministic additive approximate counting algorithms for Count-OV (#OV), Sparse Count-OV and Formula of SYM circuits. In particular, our approximate counting algorithm for #OV runs in near-linear time for all dimensions d = o(log^2 n). Previously, even no truly-subquadratic time algorithm was known for d = omega(log n). - Arthur-Merlin Communication Protocols and Faster Satisfying-Pair Algorithms. Our second connection is that a fast AM^{cc} protocol for a function f implies a faster-than-bruteforce algorithm for f-Satisfying-Pair. Using the classical Goldwasser-Sisper AM protocols for approximating set size, we obtain a new algorithm for approximate Max-IP_{n,c log n} in time n^{2 - 1/O(log c)}, matching the state-of-the-art algorithms in [Chen, CCC 2018]. We also apply our second connection to shed some light on long-standing open problems in communication complexity. We show that if the Longest Common Subsequence (LCS) problem admits a fast (computationally efficient) AM^{cc} protocol (polylog(n) complexity), then polynomial-size Formula-SAT admits a 2^{n - n^{1-delta}} time algorithm for any constant delta > 0, which is conjectured to be unlikely by a recent work [Abboud and Bringmann, ICALP 2018]. The same holds even for a fast (computationally efficient) PH^{cc} protocol.

Krzysztof Bar

Mladen Pavičić

Chuan Xi Wang, Liang Hao, Si Yu Song +1 more

Quantum direct communications, including deterministic secure quantum communication and quantum secure direct communication protocol using two-qubit quantum search algorithm are proposed in this paper. Secret messages are encoded by two-qubit unitary operations and exchanged by the two communication parties directly. We discussed the security of the protocol under intercept-resend attack and individual attack. We found that the protocols are secure against eavesdropping attacks.