Delegated quantum computation

Suppose Alice wants to perform a quantum computation. She can implement some basic quantum gates on the state $|0\rangle$ but she does not own a fully-functional quantum computer. Bob runs a company that sells time on their quantum computer and thus offers his services to Alice. But Alice does not trust Bob. In particular, she does not want Bob to learn her quantum state at any point during the calculation. Is there a way for Bob to help Alice securely? Yes, this is a problem that can be solved by delegated computation.

In the task of delegated computation, Alice has an input $|q\rangle$ and a classical description $\mathsf{C}$ of the quantum circuit and she wants to obtain the output $\mathsf{C}(|q\rangle)$. Alice and Bob exchange a few messages, at the end of which Bob obtains a result $|r\rangle$, which he sends to Alice. Ideally, we want the protocol to be correct, verifiable, and blind.

The protocol is said to be correct if Alice accepts Bob's result and $|r\rangle = \mathsf{C}(|q\rangle)$ when both parties are honest. The protocol is said to be verifiable if for any cheating Bob, Alice either aborts or  finds $|r\rangle = \mathsf{C}(|q\rangle)$. The protocol is said to blind if for any cheating Bob, at the end of the protocol, Bob learns nothing about $|q\rangle$ or $\mathsf{C}$.

To fully describe the problem, we need to specify what resources Alice is allowed to have. For the protocol that we will describe here, Alice is allowed to (i) prepare qubits in $|0\rangle$,  (ii) store and exchange two qubits (quantum swap gate),  (iii) perform Pauli gates $X, Z$ where $X|0\rangle = |1\rangle, X|1\rangle = |0\rangle$ and $Z|0\rangle = |0\rangle, |Z1\rangle = (-1)|1\rangle$, (iv) generate random classical bits, and (v) measure qubits in the basis $|0\rangle, |1\rangle$.

She can talk to Bob through a quantum channel where she can send single qubits one at a time to Bob, as well as classical channel where she can tell Bob about the quantum operations Bob has to perform on the qubits.

Our approach here is based on the idea of computing on encrypted data. Suppose Alice has an input qubit in state $|q\rangle$. To encrypt this state using a quantum one-time pad (QOTP), we choose two random bits $j$ and $k$ and apply $Z^{k}X^{j}$ on $|q\rangle$ to get $|\tilde{q}\rangle = Z^{k}X^{j}|q\rangle$. If Alice keeps $j$ and $k$ to herself and sends only $|\tilde{q}\rangle$ to Bob, then she keeps her input private.

To see how the one-time pad works, suppose that Alice has $|q\rangle = a |0\rangle + b|1\rangle$. Then $\mathrm{Enc}_{j,k}|q\rangle = Z^k x^j |q\rangle = (-1)^{jk} (a |j\rangle + b|j \oplus 1\rangle)$, where $\oplus$ denotes addition mod 2.

The figure below shows how a qubit is encrypted using the quantum one-time pad. We also note that if the encrypted qubit is in the state $Z^{k}X^{j}|q\rangle$, this can be decrypted using the same classical bits $j$ and $k$, and by applying the $Z$ and $X$ in reverse.

Encrypting a qubit with a quantum one-time pad. Two random classical bits $(j,k)$ are chosen for the key. The operator $Z^k X^j$ is applied to generate an encrypted qubit. The encrypted qubit can be decoded by applying the operator in reverse order with the same key bits used. Note that the one-time pad can be used to encrypt many qubits just by performing this single-qubit procedure on each qubit.

Because the one-time pad encrypts and decypts using only $X$ and $Z$ gates, we do not change the resources available to Alice if she is provided an encryption and decryption QOTP device instead of the Pauli $X$ and $Z$ gates. If Alice has the red Enc box, she can perform $X$ by choosing the bits $j=1, k=0$ and she can perform $Z$ by choosing $j=0,k=1$.

Now in order for Alice to run a circuit $C$ on $|q\rangle$, she needs to find another circuit $\tilde{C}$ such that $\tilde{C}(\tilde{|q\rangle} = \tilde{C(|q\rangle)}$, that is, applying this new circuit to the encrypted input gives the encrypted version of the desired outcome $C(|q\rangle)$.

Any quantum circuit can be expressed in terms of a universal set of gates: a set of gates is universal if any circuit can be implemented efficiently using gates from that set. Here we shall consider the universal gate set $G = {H, \mathrm{CNOT}, T}$, where

$H$ is the Hadamard gate: $H|0\rangle = |+\rangle, H|1\rangle = |-\rangle$;

$\mathrm{CNOT}$ is the controlled-NOT gate on two qubits: $\mathrm{CNOT} |0,x\rangle = |0,x\rangle, \mathrm{CNOT}|1,x\rangle = |1,x \oplus 1\rangle$,  where $\oplus$ is addition mod 2;

and $T$ is often called the $\pi/8$-phase gate: $T|0\rangle = |0\rangle, T|1\rangle = \sqrt{i}|1\rangle$.

Our goal is to construct the equivalent circuits for implementing these quantum gates on an input encrypted using the quantum one-time pad. If we can show that Bob can help Alice implement gates from a universal set then we have effectively shown that he can help Alice perform any quantum computation.

Let us consider the Hadamard gate first. Note that if $|q\rangle = a |0\rangle + |1\rangle$, then we expect $H|q\rangle = a |+\rangle + b |-\rangle$. But Alice will be sending a qubit encrypted using the one-time pad so what Bob gets would be $|\tilde{q}\rangle = (-1)^{jk} (a |j\rangle + b|j \oplus 1\rangle)$.

It is easier to see what happens if we look at it case-by-case, and this is summarized in the table below. What the table tells us is after Alice applies $Z^k X^j$ on the qubit she sends to Bob, and Bob performs the Hadamard gate on the qubit and sends back the result, Alice can "undo" the encryption on the qubit by applying $X^k Z^j$.

The table above shows the effect of the Hadamard gate applied to the encrypted qubit, for different values of the key bits $j,k$. It shows that we can get  desired result, possibly up to an overall phase, if we apply $X^k Z^j$ on the qubit that Bob returns to Alice.

This means that if Alice encrypts using the bits $(j,k)$ and gives the encrypted qubit to Bob, after Bob performs the Hadamard gate and returns the result to Alice, she only has to decrypt with the bits exchanged, i.e. using the bits $(k,j)$. This circuit is shown below, where the blue box denotes an operation that honest Bob will perform. Later we will see what happens if Bob tries to cheat and does something different.

Delegated computation of the Hadamard gate. The red and green boxes are QOTP boxes that allow her to perform Pauli operations on qubits. Here we see that if Alice encrypts a qubit with key $(j,k)$ and Bob honestly performs $H$, then Alice can recover her desired output by interchanging the roles of the key bits during decryption. Note that the outcome might get an overall phase that might be relevant if this circuit is part of a larger one.

Next let us consider the CNOT gate.  In this case, Alice has two qubits in state $|q_1\rangle$ and $|q_2\rangle$. If we performed the CNOT gate directly on the two qubits, we expect that for

$|q_1\rangle = a |0\rangle + b |1\rangle$ and

$|q_2\rangle = c |0\rangle + d |1\rangle$, then

$\mathrm{CNOT} |q_1 q_2 \rangle = ac |00\rangle + ad |01\rangle + bd |10\rangle + bc |11\rangle$.

Alice will encrypt her input qubits using the QOTP with keys $(j,k)$ and $(l,m)$, respectively. She sends the qubits to Bob and asks him to perform $CNOT|q_1,q_2\rangle$. If he does this honestly and returns two qubits $|\tilde{q}_1\rangle,  |\tilde{q}_2\rangle$ to Alice. The state of these two qubits for an honest Bob is shown in the table below.

The effect of the CNOT gates on the encrypted pair of qubits. It is still possible to recover the desired output just by decrypting the qubits using the same keys as before, plus some Pauli gates for corrections.

Once more, we can carefully work out what Alice needs to do to recover the desired outcome by studying individual cases. This is straightforward but a bit tedious since we have 16 cases to consider. However, you may check that what Alice needs to do is apply $Z^k X^j Z^m$ to the first qubit $|\tilde{q}_1\rangle$ and $X^j Z^m X^l$ to the second qubit $|\tilde{q}_2\rangle$. This gives the desired outcome up to possibly an overall minus sign that can be corrected later if needed. 

Delegated computation of the CNOT gate. Here Alice encrypts her two qubits $|q_1\rangle$ and $|q_2\rangle$ using keys $(j,k)$ and $(l,m)$, resepctively for the QOTP. Once the result of Bob's computation is received, Alice can recover the correct result as follows: for the first qubit, she decrypts using the key $(j,k)$ but afterwards she applies a correction $Z^m$ (which can be implemented with the red box using key $(0,m)$). For the second qubit, she first applies the correction $X^j$ (which can be implemented with the red box using key $(j,0)$) before decrypting using the same key $(l,m)$. 

Finally let us consider the $T$ gate. This one gets a bit more complicated because Alice is limited to what she can recover using just Pauli gates. If we take as input a qubit in state $|q\rangle = a |0\rangle + b|1\rangle$, then applying $T$ gives us $T|q\rangle = a|0\rangle + b\sqrt{i}|1\rangle$.

Again, Alice will encrypt the qubit using a pair of key bits $(j,k)$ then send the encrypted qubit to Bob.  As we see in the table below, depending on the value of $j$, the state that an honest Bob returns will either be already be the one we want after decryption ($j=0$) or will require some correction by $T^2$.

The $T$ gate acting on an encrypted qubit. Upon decryption, we already have the desired output when $j=0$, but non-Pauli gate corrections are needed when $j = 1$.

The problem is that Alice can not perform $T^2$ since this can be implemented from $X$ and $Z$ only. The simplest solution is for Alice to ask Bob again. However, even if she does another encryption, Bob will notice that Alice asked for $T^2$ after $T$, which would reveal to him that $j =1$.

To keep $j$ secret from Bob, Alice should ask Bob to perform $T^2$ for both values of $j$. This can be achieved by preparing an extra qubit in state $|0\rangle$, and sending this qubit for the gate $T^2$ when $j = 0$. If we draw the quantum circuit, this corresponds to adding a controlled-swap gate after the qubit returned by Bob is decrypted. This is shown in the figure below.

Delegated computation of the $T$ gate. This calculation involves two stages because there is a slight complication when $j=1$ during the QOTP encryption. To get the correct result, we have to re-encrypt and resend the qubit to Bob and ask him to perform the $T^2$ gate. Aftewards, Alice can peform the final correction $Z^l$. Observe that when $j=0$, we already get the correct result just by decrypting the qubit received from an honest Bob. Thus, in order to keep the value of $j$ private, we send an different encrypted qubit to Bob, which does not affect the state of the other qubit.

The circuit shows that when $j=0$, we already have the desired out so when we ask Bob to perform $T^2$, we swap in the encrypted $|0\rangle$. Afterwards we swap back the two qubits  so we can later discard the extra qubit.

Resending the qubit to Bob for the $T^2$ correction. We see that after decrypting, we need an additional $Z$ correction when $l = 1$, which Alice can do herself.

The interesting case is when $j=1$. Here  after swapping, we will be encrypting the qubit $|q'\rangle = a\sqrt{i}|0\rangle + b|1\rangle$ using the key $(l,m)$ and sending it to Bob. The table above shows what happens next for various $(l,m)$. If he is honest, he performs $T^2$ and sends back the result. Alice decrypts normally and applies a $Z$ correction when $l = 1$. Note that the result here comes with an extra phase factors but since these only contribute to an overall phase, they do not yield any physically observable effects.

We have shown a protocol for delegated computation of a universal set of gates. Thus, we have  presented a way for Bob to assist Alice in her quantum computation, without revealing any of Alice's private data. The protocol works as intended when Bob is honest so it is correct.

Unfortunately, you may have noticed already that Alice has to tell Bob the operations he has to perform so the circuit is revealed to Bob. A simple way to make the computation blind is to make Alice run a fixed circuit that cycles through an $H, T$, and CNOT gate. If any of the gates is not needed, Alice sends a junk qubit to Bob. Then from Bob's point of view, he merely observes Alice asking him to perform a repeating sequence of $H, T$, and CNOT gates. Thus, we can make the protocol blind. (The drawback of doing it this way is that it becomes quite impractical if most of the gates are not needed.)

Finally we want to be able to verify if Bob indeed performed the operation Alice asked of him. In order for Alice to detect if Bob is cheating, she can perform some test runs on a random subset of her inputs. She can do two types of test runs. One is called the $X$-test and it uses as input a string of qubits all in state $0\rangle$. The other is called the $Z$-test  and it uses as input a string of qubits all in state $|+\rangle$.

The trick here is for Alice to run some computation on these test qubits such that net effect is equivalent to the identity operator on these inputs. This requires a bit of fiddling around to make sure the computation is complicated enough that Bob will not notice that he is doing an identity operation overall. The idea is that Alice knows which qubits are involved in the test runs so she just checks that she recovers the input states in those computations.

Thus, we have described a protocol for delegated computation based on the QOTP. The main drawback of the protocol is that, in order to make it blind and verifiable, Alice has to perform additional computations on junk qubits or test runs, which makes the protocol quite impractical when Alice's delegated circuit is large.

There are more efficient ways to do delegated computation if we used a different quantum computing model (one based on so-called cluster states) or if we can talk to two quantum servers instead of just one; the latter one even allows Alice to be entirely classical, i.e., she is unable to do any quantum operations.



Reference:

Andrew Childs, Secure Assisted Quantum Computation, Quantum Information and Computation 5 (2005) 456.