A nonlocality distillation protocol for arbitrary high-dimensional systems is proposed. We study the nonlocality distillation in the 2-input d-output bi-partite case. Firstly, we give the one-parameter nonlocal boxes ...A nonlocality distillation protocol for arbitrary high-dimensional systems is proposed. We study the nonlocality distillation in the 2-input d-output bi-partite case. Firstly, we give the one-parameter nonlocal boxes and their correlated distilling protocol. Then, we generalize the one-parameter nonlocality distillation protocol to the twoparameter case. Furthermore, we introduce a contracting protocol testifying that the 2-input d-output nonlocal boxes make communication complexity trivial.展开更多
Security and privacy issues have attracted the attention of researchers in the field of IoT as the information processing scale grows in sensor networks.Quantum computing,theoretically known as an absolutely secure wa...Security and privacy issues have attracted the attention of researchers in the field of IoT as the information processing scale grows in sensor networks.Quantum computing,theoretically known as an absolutely secure way to store and transmit information as well as a speed-up way to accelerate local or distributed classical algorithms that are hard to solve with polynomial complexity in computation or communication.In this paper,we focus on the phase estimation method that is crucial to the realization of a general multi-party computing model,which is able to be accelerated by quantum algorithms.A novel multi-party phase estimation algorithm and the related quantum circuit are proposed by using a distributed Oracle operator with iterations.The proved theoretical communication complexity of this algorithm shows it can give the phase estimation before applying multi-party computing efficiently without increasing any additional complexity.Moreover,a practical problem of multi-party dating investigated shows it can make a successful estimation of the number of solution in advance with zero communication complexity by utilizing its special statistic feature.Sufficient simulations present the correctness,validity and efficiency of the proposed estimation method.展开更多
The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly....The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly.In this paper,we investigate how to quickly maintain the shortest distance of the dynamic graph in the distributed memory system.For a distributed system with p processors,the state-of-art algorithm to recompute the shortest distance of a graph with n vertices from scratch requires O(n^(2)/√p)bandwidth cost and O(√plog^(2)p)latency cost.For the insertion of k edges,we give an incremental algorithm with a bandwidth cost of O(nk√p+k^(2))and a latency cost of O(logp).For typical scenarios where k=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p)and O(√plogp),respectively.For the deletion of k edges,we give a decremental algorithm with a bandwidth cost of O(nk/√p+k^(2)+n^(2)/log^(3)p+|S|^(2)logp)and a latency cost of O(log^(3)p),where S is the separator size of a constructed graph and is related to the alteration degree of the shortest path of the dynamic graph.When k=O(n/√p)and S=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p∕log^(3)p)and O(√p∕logp),respectively.展开更多
基金Supported by the National Basic Research Program of China under Grant No 2012CB921900the National Natural Science Foundation of China under Grant Nos 11175089 and 11475089
文摘A nonlocality distillation protocol for arbitrary high-dimensional systems is proposed. We study the nonlocality distillation in the 2-input d-output bi-partite case. Firstly, we give the one-parameter nonlocal boxes and their correlated distilling protocol. Then, we generalize the one-parameter nonlocality distillation protocol to the twoparameter case. Furthermore, we introduce a contracting protocol testifying that the 2-input d-output nonlocal boxes make communication complexity trivial.
基金Supported by the National Natural Science Foundation of China under Grant Nos.61501247,61373131 and 61702277,the Six Talent Peaks Project of Jiangsu Province(Grant No.2015-XXRJ-013)Natural Science Foundation of Jiangsu Province(Grant No.BK20171458)+3 种基金the Natural Science Foundation of the Higher Education Institutions of Jiangsu Province(China under Grant No.16KJB520030)the NUIST Research Foundation for Talented Scholars under Grant Nos.2015r014,PAPD and CICAEET fundsfunded in part by the Science and Technology Development Fund,Macao SAR(File No.SKL-IOTSC-2018-2020,0018/2019/AKP,0008/2019/AGJ,and FDCT/194/2017/A3)in part by the University of Macao under Grant Nos.MYRG2018-00248-FST and MYRG2019-0137-FST.
文摘Security and privacy issues have attracted the attention of researchers in the field of IoT as the information processing scale grows in sensor networks.Quantum computing,theoretically known as an absolutely secure way to store and transmit information as well as a speed-up way to accelerate local or distributed classical algorithms that are hard to solve with polynomial complexity in computation or communication.In this paper,we focus on the phase estimation method that is crucial to the realization of a general multi-party computing model,which is able to be accelerated by quantum algorithms.A novel multi-party phase estimation algorithm and the related quantum circuit are proposed by using a distributed Oracle operator with iterations.The proved theoretical communication complexity of this algorithm shows it can give the phase estimation before applying multi-party computing efficiently without increasing any additional complexity.Moreover,a practical problem of multi-party dating investigated shows it can make a successful estimation of the number of solution in advance with zero communication complexity by utilizing its special statistic feature.Sufficient simulations present the correctness,validity and efficiency of the proposed estimation method.
基金supported in part by National Natural Science Foundation of China under Grants 61972447 and 61832006.
文摘The computation of the all-pairs shortest paths is an important graph algorithmic problem.When the graph changes,such as edge deletions/insertions,recalculating the shortest distance of a graph from scratch is costly.In this paper,we investigate how to quickly maintain the shortest distance of the dynamic graph in the distributed memory system.For a distributed system with p processors,the state-of-art algorithm to recompute the shortest distance of a graph with n vertices from scratch requires O(n^(2)/√p)bandwidth cost and O(√plog^(2)p)latency cost.For the insertion of k edges,we give an incremental algorithm with a bandwidth cost of O(nk√p+k^(2))and a latency cost of O(logp).For typical scenarios where k=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p)and O(√plogp),respectively.For the deletion of k edges,we give a decremental algorithm with a bandwidth cost of O(nk/√p+k^(2)+n^(2)/log^(3)p+|S|^(2)logp)and a latency cost of O(log^(3)p),where S is the separator size of a constructed graph and is related to the alteration degree of the shortest path of the dynamic graph.When k=O(n/√p)and S=O(n/√p),the bandwidth and latency costs are reduced by a factor of O(√p∕log^(3)p)and O(√p∕logp),respectively.
