We give a basic overview of computational complexity, query complexity, and communication complexity, with quantum information incorporated into each of these scenarios. The aim is to provide simple but clear definitions, and to highlight the interplay between the three scenarios and currently-known quantum algorithms.
With the rapid advancement of quantum information technology, designing efficient distributed quantum algorithms to perform various information processing tasks remains challenging. In this paper, we consider a distributed scenario where two parties, Alice and Bob, given access to matrices A and B respectively, aim to estimate Tr(f(A)g(B)), where f and g are known functions. In this task, only local quantum operations, classical communication and single-qubit measurements are allowed due to the high cost of quantum communication and entangled measurements. We propose a distributed quantum algorithm framework to compute Tr(f(A)g(B)) within an additive error ε. The proposed algorithm framework requires O(d2/(δε2)) quantum queries and two-qubit gates, assuming that the minimum singular value of each matrix A,B∈Cd×d is at least δ. Additionally, our algorithm framework uses a simple Hadamard test architecture, enabling easier quantum hardware implementation. This algorithm framework allows for various applications including quantum divergence estimation, distributed solving of linear system, and distributed Hamiltonian simulation, while preserving the privacy of both parties. Furthermore, we establish a lower bound of Ω(max{1/ε2,dr/ε}) on the query complexity for the task, where r denotes the rank of the input matrices. We believe this framework holds broad applicability across a range of distributed quantum computing tasks.
Abstract: Query algorithms are used to compute Boolean functions. The definition of the function is known, but input is hidden in a black box. The aim is to com-pute the function value using as few queries to the black box as possible. As in other computational models, different kinds of query algorithms are possible: deterministic, probabilistic, as well as nondeterministic. In this paper, we present a new alternative definition of nondeterministic query algorithms and study algorithm complexity in this model. We demonstrate the power of our model with an example of computing the Fano plane Boolean function. We show that for this function the difference between deterministic and nondeterministic query complexity is 7N versus O(3N).