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.

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$.

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.

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.

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.

$|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.

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.

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.

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.

## No comments:

## Post a Comment