Quantum Locality?

Qi Han, Shuai Wang, Lijie Gou +1 more

Abstract In the era of rapid development of quantum mechanics, some issues in the field of quantum information have become increasingly important. Local quantum Bernoulli noises (LQBNs) is a localized Bernoulli functional, and it is the localization of quantum Bernoulli noises (QBNs). The distinctive feature of LQBNs lies in its localization properties, which make it highly valuable in the field of quantum information. In this paper, we study three new types of quantum conditional entropy with localization characteristics from three dimensions: local quantum conditional entropy, local quantum conditional entropy at the same position, and classical-quantum conditional entropy. Based on the locality of LQBNs, we prove that the local quantum conditional entropy is concave and unitary invariant. Surprisingly, we find that the local quantum mutual information (entropy) corresponding to the same position is 0. The local quantum conditional entropy defined based on the local quantum state at a specific position, proposed in this paper, provides new insights into understanding the impact of local quantum noise on the information transmission in quantum channels. This discovery not only deepens our understanding of the internal structure of local quantum entropy, but also reveals its influence on the performance of quantum communication.

Robert B. Griffiths

Stefano Pironio

Henrik Lievonen

In this thesis, I study how quantum computation and quantum communication can help large networks of computers to solve computational problems faster. I also connect the notion of locality between various models, including distributed quantum algorithms and online graph algorithms, and show that locality in online graph algorithms can be used to provide bounds for distributed quantum advantage. Towards proving distributed quantum advantage, I present the first family of LCL problems which shows a quantum advantage for distributed graph algorithms. Here LCLs, or Locally Checkable Labeling problems, are a family of graph problems described by a finite set of local constraints, and I mainly focus on them in this thesis. The models of distributed computing which this result separates are the classical LOCAL model and the quantum-LOCAL model. In both of these models, a network of computers exchanges messages in synchronous rounds, and the running time of the algorithm directly corresponds with locality, that is, how far the computers see in the network. In this thesis, I also introduce new models of computing that capture locality in stronger settings. Most notably, I introduce the online-LOCAL model which captures the locality of online graph algorithms, and show that it is, asymptotically, roughly as strong as the classical LOCAL model for solving LCL problems on rooted regular trees. I provide an online-LOCAL algorithm for finding a 3-coloring of a bipartite graph with lower locality than is possible in the classical LOCAL model, and show that the algorithm is tight. To draw things together, I show that quantum-LOCAL and online-LOCAL are indeed related to each other: any quantum-LOCAL algorithm can be simulated in the randomized online-LOCAL model. The converse does not hold in general, but an online-LOCAL algorithm solving an LCL problem in rooted, possibly non-regular, trees can be simulated in the classical LOCAL model—and thus in the quantum-LOCAL model—with an exponential cost in locality, putting indirectly a bound on the maximum possible attainable quantum advantage. Finally, I consider the sinkless orientation problem, which holds a central role in our understanding of the locality of LCL problems in the classical LOCAL model, and provide a simpler and more direct proof for its hardness using the supported LOCAL model. I also provide a simpler algorithm solving sinkless orientation in the SLOCAL model, which is a sequential version of the LOCAL model.

David A. Roberts, H. H. Wills

Qi Han, Lijie Gou, Shuai Wang +1 more

Abstract In this paper, we first introduce the local quantum information processing task by compressing the density operator based on local quantum Bernoulli noises. Then, the local quantum compression theorem is given, that is, the local quantum entropy is the minimum achievable rate of local compression. Finally, we prove the theorem with the proof of the direct coding theorem and the inverse theorem. The direct coding theorem shows that a scheme with such a local compression rate exists, and that this local compression rate converges to the local quantum entropy. The inverse theorem shows that the compression scheme with the rate below the local entropy is unachievable. With the continuous development of quantum technology, local quantum data compression technology will have broad application prospects and development space.