Homomorphic encryption experiments on IBM’s cloud quantum computing platform

Abstract

Quantum computing has undergone rapid development in recent years. Owing to limitations on scalability, personal quantum computers still seem slightly unrealistic in the near future. The first practical quantum computer for ordinary users is likely to be on the cloud. However, the adoption of cloud computing is possible only if security is ensured. Homomorphic encryption is a cryptographic protocol that allows computation to be performed on encrypted data without decrypting them, so it is well suited to cloud computing. Here, we first applied homomorphic encryption on IBM’s cloud quantum computer platform. In our experiments, we successfully implemented a quantum algorithm for linear equations while protecting our privacy. This demonstration opens a feasible path to the next stage of development of cloud quantum information technology.

Graphical abstract

Keywords

quantum computing / homomorphic encryption / cloud computing / IBM quantum experience / linear equations

1 Introduction

In recent years, much progress has been made in developing quantum computing technologies [1-5]. Because of the quantum superposition principle, quantum computers can outperform their classical counterparts when performing certain tasks, for example, Shor’s algorithm [6-10], quantum simulation [11-14], solving linear systems of equations [15-17], and quantum machine learning [18, 19]. Therefore, the emergence of quantum computers will change the world. Owing to high construction and maintenance costs, the first quantum computers are likely to be owned only by a small number of organizations. Fortunately, however, with cloud service, ordinary users are also expected to be able to apply so as to use these quantum computers.

As expected, IBM recently made a five-qubit quantum computer publicly available over the cloud [20]. Based on a five-qubit superconducting chip in a star geometry and a full Clifford algebra, the system can be reprogrammed and allows for circuit design and simulation. Through the classical internet, users can easily test and execute quantum algorithms on an interactive platform called Quantum Experience. Several experiments have already been reported [21-23].

Future cloud quantum computing is likely to be available to users through an interface similar to IBM’s cloud quantum computing platform, where users interact with the platform through a website. In this case, the quantum circuit, input data, and output data of users are completely accessible to the server. While sharing cloud-based computational resources for quantum computing, we also need to consider privacy. Although a number of protocols and experiments have been proposed to develop secure cloud quantum computing [24-27], these encryption methods are not suited to the current level of technology, because input or output data cannot be accessible to the servers on the website in the previous protocol.

In classical cryptography, homomorphic encryption [28-30] is a scheme that allows certain operations to be performed on encrypted data without decryption. Thus, users can provide encrypted data to a remote server for processing without having to reveal the plaintext. Although the data are open to the server, the server cannot reveal the real data because the data are encrypted. After the server outputs the results to a user, the user can recover the actual output data through his privacy key. Therefore, homomorphic encryption has become a practical encryption technique for cloud computing.

In this study, we designed a homomorphic encryption protocol for cloud quantum computing, which is suitable for IBM’s cloud server. On the basis of the basic quantum gates provided by the server, we developed a series of construction methods for various operations. Finally, we successfully implemented a quantum algorithm for linear equations on IBM’s cloud server while protecting our privacy. This work will hopefully motivate more people to get involved in this field, because this study is the first to consider the security of users’ data on IBM’s cloud server and can provide guidance for future large-scale cloud quantum computing.

2 Methods

To solve linear equations on a quantum computer, we employ the quantum algorithm proposed by Harrow et al. [15], which can provide an exponential speedup over existing classical algorithms. Given a matrix A and a vector \mathit{b}, we aim to solve the equations A\mathit{x}=\mathit{b}. To convert the problem to a quantum version, we rescale \mathit{x} and \mathit{b} to \Vert \mathit{x}\Vert =\Vert \mathit{b}\Vert =1. Thus, we can encode the problem as

\begin{array}{}\text{(1)}& A|x⟩=|b⟩.\end{array}

Denote \{|u_i⟩\} and \{{\lambda }_i\} as the eigenbasis and eigenvalues of matrix A, respectively. The input state |b⟩ can be expanded in the eigenbasis of A as |b⟩={\sum }_{i=1}^N{\beta }_i|u_i⟩, where {\beta }_i=⟨u_i|b⟩. To seek the solution |x⟩=A^{-1}|b⟩/\Vert A^{-1}|b⟩\Vert, the algorithm can be decomposed into three main steps (see Fig. 1).

In the first step, phase estimation is applied to the transformation of |b⟩{|0⟩}^{\otimes n} into {\sum }_{i=1}^N{\beta }_i|u_i⟩|{\lambda }_i⟩, where {|0⟩}^{\otimes n} is the eigenvalue register of n qubits, and eigenvalues |{\lambda }_i⟩ are stored in the eigenvalue register after phase estimation.

In the second step, the map |{\lambda }_i⟩\to \lambda _i^{}{}_{}{}^{-1}|{\lambda }_i⟩ is implemented to extract the eigenvalues of A^{-1}. By implementing a controlled R({\lambda }^{-1}) rotation on an additional ancilla qubit initially in the state |0⟩, we can transform the system to

\begin{array}{}\text{(2)}& \sum _{i=1}^N{\beta }_i|u_i⟩|{\lambda }_i⟩\left(\sqrt{1-\frac{C^2}{{\lambda }_i^2}|0⟩+\frac{C}{{\lambda }_i}|1⟩}\right).\end{array}

The final step is to implement inverse phase estimation to disentangle the eigenvalue register to {|0⟩}^{\otimes n}. Then, we have

\begin{array}{}\text{(3)}& \sum _{i=1}^N{\beta }_i|u_i⟩\left(\sqrt{1-\frac{C^2}{{\lambda }_i^2}}|0⟩+\frac{C}{{\lambda }_i}|1⟩\right).\end{array}

After measuring and postselecting the ancillary qubit of |1⟩, we will obtain an output state {\sum }_{i=1}^{N}C({\beta }_i/{\lambda }_i)|u_i⟩, which is proportional to our expected result state |x⟩.

To delegate the task of solving linear equations to IBM’s cloud quantum computing platform, one can directly encode the quantum circuit on the servers without considering security. This is equivalent to sending the cloud server the matrix A and vector \mathit{b} directly. However, when security is required, this approach is no longer feasible. Inspired by homomorphic encryption (see Fig. 2), we can compile a homomorphically encrypted version of the algorithm.

To implement homomorphic encryption, we must ensure that the operations of the server and the encryption scheme of the user meet the following conditions:

\begin{array}{}\text{(4)}& f(E(x))=E(f(x)),\end{array}

where f denotes the operations of the server, and E(x) denotes the encryption of the message x. According to the conditions of homomorphic encryption, we can design the protocol as follows:

Step 1. For a linear equation Ax=b with n variants, the user randomly chooses a_i\in \{0,1\} as private keys, letting x_i=y_i+a_i, and then substitutes it into the linear equations

\begin{array}{}\text{(5)}& A(y_i+a_i)=b.\end{array}

The user rewrites the equations as A{y}_i=b^{\prime }, where b^{\prime }=b-A{a}_i, and then sends A and b^{\prime } to the cloud server.

Step 2. The server implements a quantum algorithm to solve the equations received from the user and feeds back the results \mathit{r} to the user.

Step 3. The user decrypts the results as

\begin{array}{}\text{(6)}& x_i=r_i+a_i.\end{array}

Here, we analyze the entire process of the protocol. Step 1 can be regarded as the encryption process. That is, for \forall x, E(x)=x^{\prime }, where x^{\prime } is the encryption of message x. Let g(x^{\prime }) and F be linear equations and the algorithm for solving linear equations, respectively. Then step 2 can be represented as F(g(x^{\prime }))\to x^{\prime }. Finally, step 3 is used to decrypt the results as D(x^{\prime })\to x, where D denotes the decryption operation; then the user can obtain the actual results. Note that the homomorphic encryption process perfectly hides the input and output of the user, and the server cannot obtain any of the private data, because it deals only with encrypted data.

3 Experimental realization

Here we present a proof-of-principle experiment of this protocol on IBM’s cloud quantum computing platform. Using one state qubit as the two-vector |b⟩, one eigenvalue qubit, and an ancilla qubit, we can use the protocol to solve systems of 2\times 2 linear equations. The quantum circuit of the algorithm for 2\times 2 linear equations can be compiled into the circuit shown in Fig. 3(a) [13]. A unitary R is introduced to diagonalize matrix A as A=R^{†}\left(\genfrac{}{}{0pt}{}{{\lambda }_{1}0}{\mathrm{\hspace{0.17em}\hspace{0.17em}0}{\lambda }_2}\right)R, where {\lambda }_i is the eigenvalue of A. R({\lambda }^{-1}) rotation can be realized by using a controlled R_y(\theta ), where R_y(\theta )=\exp (-\mathrm{i}\theta {\sigma }_y/2), {\sigma }_y is the usual Pauli matrix, and θ is controlled by the eigenvalue qubit with the function {\theta }_i=-2\arccos ({\lambda }_1/{\lambda }_2). The algorithm succeeds with probability when the ancilla qubit is measured in the state |1⟩. In our implementation, we choose the following two systems of linear equations:

\begin{array}{}\text{(7)}& \left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\cdot x=\left(\begin{array}{c}1/\sqrt{2}+0.7\\ 1/\sqrt{2}+0.3\end{array}\right),\end{array}

\begin{array}{}\text{(8)}& \left(\begin{array}{cc}1.75& 0.75\\ 0.75& 1.75\end{array}\right)\cdot x=\left(\begin{array}{c}1/\sqrt{2}+1.75\\ -1/\sqrt{2}+0.75\end{array}\right).\end{array}

Without loss of generality, we set the private key of the user to a_1=1,a_2=0. By substituting x_i=y_i+a_i into the linear equations, the user can perfectly hide his input data, and the equations can be rewritten as

\begin{array}{}\text{(9)}& \left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\cdot y=\left(\begin{array}{c}1\\ 1\end{array}\right)/\sqrt{2},\end{array}

\begin{array}{}\text{(10)}& \left(\begin{array}{cc}1.75& 0.75\\ 0.75& 1.75\end{array}\right)\cdot y=\left(\begin{array}{c}1\\ -1\end{array}\right)/\sqrt{2}.\end{array}

Then the user can encode the circuit on IBM’s cloud quantum computing platform. For both of these linear equations, the R gate in Fig. 3(a) can be compiled into a Hadamard gate [see Fig. 3(c)]. Note that IBM provides only the CNOT gate as a two-qubit gate. To realize the controlled R_y(\theta ) operation (\theta is equal to -{57.34}^{\circ } for both of the linear equations), we decomposed the controlled R_y(\theta ) gate into two CNOT gates, one R_y(\theta /2) gate and one R_y(-\theta /2) gate. In our implementation, we set the eigenvalue register as the central qubit of IBM’s superconductor quantum chip. As the chip allows operation of CNOT gates only with the central qubit as the target qubit in their star geometry, if we want to operate CNOT gates with the central qubit as a control qubit, we need to combine a CNOT gate and four Hadamard gates. Then the controlled R_y(\theta ) gate can be compiled to a combination of several Hadamard gates, CNOT gates, the R_y(\theta /2) gate, and the R_y(-\theta /2) gate [see Fig. 3(b)]. Now the question becomes how to construct an R gate, because only Clifford gates (X,Y,Z,H,S,S^{†} and CNOT) and two non-Clifford gates (T and T^{†}) are available on the platform. Adding almost any non-Clifford gate to the Clifford gates is universal [31]. Therefore, by adding the T gate to the Clifford gates, it is possible to reach all the points of the Bloch sphere. A Monte Carlo simulation indicates that the more T gates our circuit has, the more densely we can cover the Bloch sphere with states we can reach. Figure 4 depicts the states attainable by adding at most 1, 3, 5, and 7 T gates to the Clifford gates.

In Fig. 4, the red dot is the R_y(\theta /2) operation we desired. On the basis of the results of the numerical simulation, we can approximate the R_y(\theta /2) gate by the gate R_S, which is a combination of seven T gates and seven Hadamard gates [see Fig. 3(d)]. To characterize its accuracy, we compute the similarity F=1/2\cdot Tr(U_{ideal}{U}_{simu}) as 0.998, where U_{ideal} is the ideal unitary operation R_y(\theta /2), and U_{simu} is the simulated unitary operation R_S, indicating that our simulated unitary operation is very similar to the ideal operation R_y(\theta /2). Through the red dot (R_y(\theta /2) operation) and the purple dot (simulated operation R_S) in Fig. 4(d), it is more intuitive that these two dots are very close. At this point, we can compile the full circuit for solving the two equations on the IBM servers.

4 Results

Measuring the first qubit of the circuit in Fig. 3(a) in the Pauli Z,X,Y basis, we can obtain the solutions of the equations. Figures 5(a) and (b) show both the ideal (red bar) and experimentally obtained (blue bar) expectation values for each Pauli operator when the algorithm is implemented to solve Eqs. (9) and (10), respectively. We compute the fidelity of the output state as F=⟨x|{\rho }_{\exp }|x⟩, where |x⟩ is the ideal output state, and {\rho }_{\exp } is the experimentally output state from the measurement results of the Pauli Z,X,Y basis. The output states have fidelities of 0.992(1) and 0.920(7) for Eqs. (9) and (10), respectively, indicating that our experiments yielded highly reliable results.

By postprocessing the results using a classical computer, the user can easily decrypt the secret results to obtain the actual results as \{x_1=1.7173,x_2=0.6967\} and \{x_1=1.7227,x_2=0.6911\} for Eqs. (7) and (8), respectively. Theoretical analysis shows that the error is within 2% of the actual solution. Thus, the homomorphic encryption protocol is found to be successful.

5 Conclusion

In summary, we presented the first experimental demonstration of a homomorphic encryption protocol for solving linear equations on IBM’s cloud quantum computer platform. The protocol is very suitable for current technology, which enables users to delegate the task of computation by encoding the circuit on the website of quantum servers while protecting their data. Even though the current quantum computations on IBM’s server are proof-of-principle demonstrations, the process can be scaled to larger systems in the future. Ideally, this work will provide a workable solution for future cloud quantum computation.

References

[1] T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, and J. L. O’Brien, Quantum computers, Nature 464(7285), 45 (2010)

[2] X. L. Wang, X. D. Cai, Z. E. Su, M. C. Chen, D. Wu, L. Li, N. L. Liu, C. Y. Lu, and J. W. Pan, Quantum teleportation of multiple degrees of freedom of a single photon, Nature 518(7540), 516 (2015)

[3] J. Kelly, R. Barends, A. Fowler, A. Megrant, E. Jeffrey, T. White, D. Sank, J. Mutus, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, I. C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, A. N. Cleland, and J. M. Martinis, State preservation by repetitive error detection in a superconducting quantum circuit, Nature 519(7541), 66 (2015)

[4] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. White, J. Mutus, A. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O’Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and J. M. Martinis, Superconducting quantum circuits at the surface code threshold for fault tolerance, Nature 508(7497), 500 (2014)

[5] R. Barends, L. Lamata, J. Kelly, L. García-Álvarez, A. G. Fowler, A. Megrant, E. Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O’Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, E. Solano, and J. M. Martinis, Digital quantum simulation of fermionic models with a superconducting circuitm, Nature Communications 6, 7654 (2015)

[6] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev. 41(2), 303 (1999)

[7] L. M. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature 414(6866), 883 (2001)

[8] C. Y. Lu, D. E. Browne, T. Yang, and J. W. Pan, Demonstration of a compiled version of Shor’s quantum factoring algorithm using photonic qubits, Phys. Rev. Lett. 99(25), 250504 (2007)

[9] E. Lucero, R. Barends, Y. Chen, J. Kelly, M. Mariantoni, A. Megrant, P. O’Malley, D. Sank, A. Vainsencher, J. Wenner, T. White, Y. Yin, A. N. Cleland, and J. M. Martinis, Computing prime factors with a Josephson phase qubit quantum processor, Nat. Phys. 8(10), 719 (2012)

[10] T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, and R. Blatt, Realization of a scalable Shor algorithm, Science 351(6277), 1068 (2016)

[11] R. P. Feynman, Simulating physics with computers, Int. J. Theor. Phys. 21(6–7), 467 (1982)

[12] R. Blatt and C. Roos, Quantum simulations with trapped ions, Nat. Phys. 8(4), 277 (2012)

[13] A. A. Houck, H. E. Türeci, and J. Koch, On-chip quantum simulation with superconducting circuits, Nat. Phys. 8(4), 292 (2012)

[14] A. Aspuru-Guzik and P. Walther, Photonic quantum simulators, Nat. Phys. 8(4), 285 (2012)

[15] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103(15), 150502 (2009)

[16] S. Barz, I. Kassal, M. Ringbauer, Y. O. Lipp, B. Dakić A. Aspuru-Guzik, and P. Walther, A two-qubit photonic quantum processor and its application to solving systems of linear equations, Sci. Rep. 4, 6115 (2014)

[17] X. D. Cai, C. Weedbrook, Z. E. Su, M. C. Chen, M. Gu, M. J. Zhu, L. Li, N. L. Liu, C. Y. Lu, and J. W. Pan, Experimental quantum computing to solve systems of linear equations, Phys. Rev. Lett. 110(23), 230501 (2013)

[18] P. Rebentrost, M. Mohseni, and S. Lloyd, Quantum support vector machine for big data classification, Phys. Rev. Lett. 113(13), 130503 (2014)

[19] X. D. Cai, D. Wu, Z. E. Su, M. C. Chen, X. L. Wang, L. Li, N. L. Liu, C. Y. Lu, and J. W. Pan, Entanglement-based machine learning on a quantum computer, Phys. Rev. Lett. 114(11), 110504 (2015)

[20] IBM, The quantum experience, http://www.research.ibm.com/quantum/, 2016

[21] S. J. Devitt, Performing quantum computing experiments in the cloud, Phys. Rev. A 94, 032329 (2016)

[22] D. Alsina and J. I. Latorre, Experimental test of Mermin inequalities on a 5-qubit quantum computer, Phys. Rev. A 94, 012314 (2016)

[23] R. Rundle, T. Tilma, J. Samson, and M. Everitt, Quantum state reconstruction made easy: A direct method for tomography, arXiv: 1605.08922 (2016)

[24] A. Broadbent, J. Fitzsimons, and E. Kashefi, Universal blind quantum computation, in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), IEEE, 2009, pp 517-526

[25] J. F. Fitzsimons and E. Kashefi, Unconditionally verifiable blind computation, arXiv: 1203.5217 (2012)

[26] S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsimons, A. Zeilinger, and P. Walther, Demonstration of blind quantum computing, Science 335(6066), 303 (2012)

[27] S. Barz, J. F. Fitzsimons, E. Kashefi, and P. Walther, Experimental verification of quantum computation, Nat. Phys. 9(11), 727 (2013)

[28] R. L. Rivest, L. Adleman, and M. L. Dertouzos, On data banks and privacy homomorphisms, Foundations of Secure Computation 4, 169 (1978)

[29] C. Gentry, A fully homomorphic encryption scheme, Ph.D. thesis, Stanford University, 2009

[30] M. Van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, 2010, pp 24-43

[31] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, 2010

Rights & permissions

Higher Education Press and Springer-Verlag Berlin Heidelberg 2017