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.

In recent years, security and privacy in edge computing have become a major challenge to the increased scale of information processing in sensor networks. Some people say that the data created by Internet of Things (IoT) sensors must be better protected. With more and more data protection regulations, new public awareness of tracking and the explosion of devices, simple device password solutions are no longer enough.

A new architecture using Security Agents should be constructed actively in local routers and networks to deal with Internet of Things security and computing, rather than offloading digital processing to data centers or clouds, or actually trying to execute it on IoT devices with limited resources. From the perspective of [

Different from the security framework based on edge computing proposed in [

This special quantum parallelism totally different from conventional information techniques also can be applied in communication complexity which is a standard that can determine how much communication cost spent in a distributed computing task [

One of the prerequisites for applying Grover’s iteration is to know the number of solutions in order to determine the optimal number of iterations [

We propose a distributed algorithm of phase estimation, which is used to estimate the number of solutions of MPC problem, and study how much quantum communication complexity is added to QD algorithm by using this method.

Additionally, considering the constraints of the statistical characteristics of the MPD (multi-party dating) problem, which can schedule appointments among different users and is seen as one of the practical applications of MPC, we develop the distributed estimation algorithm for estimating the number of solutions. This algorithm can be implemented without any multi-party communication through some simple local calculations. Finally, given many simulation results about this estimation algorithm prove the efficiency and correctness of the proposed method.

The quantum speed-up model of two-party computing is first discussed in paper [

For a reasonable extension of two-user model proposed in [

The kth user wants to compute the function

Without loss of generality, denote the domain of function

In summary, the goal of our research on the multi-party computing task is to find a solution x to equation

Any quantum distributed algorithm for MPC needs to know the number of solutions of a specific problem. When the number of solutions is unknown, the number of solutions must be estimated.

Grover’s database search problem is iterated by phase estimation algorithm, and the rotation angle of Grover problem is estimated by success rate and m bit accuracy [

For the MPC problem studied, we need to design a multi-party phase estimation algorithm to estimate the number of solutions of the MPC problem. The communication cost of the new phase estimation algorithm is deduced and evaluated.

According to the result of phase estimation algorithm of Grover’s search problem in paper [

Algorithm steps |
---|

Step 1: Quantum states are transformed into uniform superposition states via Hardmand gates. |

Assuming that the estimation error probability of the algorithm is 0, the probability of obtaining the rotation angle of M bit accuracy is obtained after measurement. The estimation error of rotation angle at this time. And the error of the number of solutions at this time

Since the accuracy and success rate of the estimates depend on the magnitude of M and e, the setting of both will ultimately affect the upper limit. Here, we note that if the accuracy is assumed, the substitution

The estimation algorithm needs to call Grover’s iteration

For MPC problems, Oracle operations are distributed, which means that estimation algorithms are also distributed. Each Grover’s iteration in

Firstly, in the DOO part, in the forward communication process from user 1 to user K, the communication cost is as follows:

The upper bound of

Similarly, the reverse communication process has the same communication overhead as the forward process. Therefore, the communication overhead of a complete DOO is:

According to the conclusion that the MPC phase estimation algorithm needs

By given

By replacing

It can be seen that the phase estimation algorithm has the same communication complexity as the MPC quantum distributed algorithm. This means that using phase estimation algorithm to estimate the number of solutions in advance will not increase the communication complexity of MPC quantum distributed algorithm.

An MPD problem is related to the appointment scheduling issue [

Suppose

And

Obviously, for any i, if

Assuming that K users want to make a successful appointment with a certain probability P, the length of the schedules prepared by users will be constrained. Obviously, the more users participate in the joint appointment, the longer the schedule of the appointment will be on the premise of guaranteeing a certain success rate. Therefore, given the expected probability P of successful appointment, under the premise of K users’ appointment, to meet P the probability of successful appointment, the relationship between the length of the schedule N and P is

For MPD problems, the probability distribution of M which denotes the number of solutions satisfies the following equation

Let

And the standard deviation of M is:

The above formula shows that if

Comparing with the phase estimation algorithm discussed in the previous section, we find that:

On the one hand, the estimation error obtained by using the phase estimation algorithm is

On the other hand, it can be inferred that the communication complexity

For the MPD problem, we choose the estimation method of using

According to paper [

Suppose we perform a specific MPD task, and its actual number of solutions is

The corresponding optimal number of iterations is

where CI (x) means that if the fractional part of X is greater than 0.5, it is rounded up; if the fractional part of X is less than or equal to 0.5, it is rounded down. In addition, the error probability of QD algorithm measurement results is

Therefore, when estimating

As depicted in

As a result, the correct probability of the measurement results using the estimated QD algorithm is

In this section, we simulate the MPD problem using the effect of evaluation. The number of experiments is C, and each experiment simulation produces a specific MPD task. The real value of the corresponding number of solutions is calculated by experiment, and the correct probability of measurement results is calculated.

For an MPD problem, we need to specify the probability of a successful appointment and the number of users in advance when we don’t know which time of the parties is free. And we generally set the success rate as a lower value of 50% and a higher value of 90%. Similarly, due to the exponential growth of resources consumed in MPD simulation, the number of users should be set to consider the value more suitable for the simulation environment. For the number of experiments, a smaller value and a larger value are selected to facilitate comparison. So the simulation involves the following settings: (1) the success rate of appointment P is set to be 50% or 90%; (2) the number of users K is set to 6 or 12; (3) the number of experiments C is set to 10 or 1000.

K = 6 P = 50% | K = 6 P = 90% | K = 12 P = 50% | K = 12 |
K = 20 P = 50% | K = 20 P = 90% | |
---|---|---|---|---|---|---|

Correct probability of measurement > 0.6 | 100% | 87.5% | 100% | 77.8% | 100% | 100% |

Correct probability of measurement > 0.8 | 100% | 62.5% | 80% | 44.4% | 100% | 30% |

K = 6 P = 50% | K = 6 P = 90% | K = 12 P = 50% | K = 12 P = 90% | K = 20 P = 50% | K = 20 P = 90% | |
---|---|---|---|---|---|---|

Correct probability of measurement > 0.6 | 70.3% | 92% | 95.9% | 88.9% | 90.9% | 92.3% |

Correct probability of measurement > 0.8 | 70.3% | 51.3% | 70.1% | 50.8% | 66.7% | 51.9% |

When the number of experiments is equal to 10, we can clearly see the distribution of the number of solutions from

As is shown in

Even if the quantum parallelism can speed many algorithms of multi-party computing up the realization of a quantum distributed algorithm still has been limited by solution’s amount estimation. It must be assured that the total communication complexity should not increase after apply solution’s amount estimation. Based on our study on the phase estimation algorithm for MPC problem the result shows it is possible to make a phase estimation without any complexity increasing. Theorem 1 presents that the communication complexity of phase estimation algorithm is

Thank for being partially supported by the China–USA Computer Science Research Center.