Flow Ambiguity: A Path Towards Classically Driven Blind Quantum Computation

Blind quantum computation protocols allow a user to delegate a computation to a remote quantum computer in such a way that the privacy of their computation is preserved, even from the device implementing the computation. To date, such protocols are only known for settings involving at least two quantum devices: either a user with some quantum capabilities and a remote quantum server or two or more entangled but noncommunicating servers. In this work, we take the first step towards the construction of a blind quantum computing protocol with a completely classical client and single quantum server. Specifically, we show how a classical client can exploit the ambiguity in the flow of information in measurement-based quantum computing to construct a protocol for hiding critical aspects of a computation delegated to a remote quantum computer. This ambiguity arises due to the fact that, for a fixed graph, there exist multiple choices of the input and output vertex sets that result in deterministic measurement patterns consistent with the same fixed total ordering of vertices. This allows a classical user, computing only measurement angles, to drive a measurement-based computation performed on a remote device while hiding critical aspects of the computation.

Popular Summary

As with the first conventional computers, the first quantum computers will likely be hosted only by major institutions. A client wishing to use one may have to rely on “cloud-based” quantum computing, where data are stored and manipulated at a remote site. In such a setting, privacy becomes an important concern. A protocol is needed for delegating quantum computation in a way that hides the work from the server performing it. All current protocols require the client to possess quantum capabilities, such as the ability to prepare or measure quantum states, or they require multiple noncommunicating servers. This limits the feasibility of secure cloud-based quantum computing to locations with extensive quantum networks. We show how an ordinary user without access to special quantum technology can hide critical aspects of a computation delegated to a remote quantum computer.

Our protocol exploits the ambiguity in the flow of information in a measurement-based quantum computer. The uncertainty arises because there are multiple ways to interpret a sequence of measurements on a cluster state as a quantum computation, if the logic for deciding dependencies between measurement settings is not known. During a run of this protocol, there are exponentially many choices of computation for the client, and the quantum server never receives enough information to unambiguously identify the client’s choice from her communication, even if the server actively deviates from the protocol.

Our intent is to demonstrate that it is possible for a client equipped only with a classical computer to obfuscate her choice of quantum computation from a malicious quantum server. While we do not offer a full solution, the results support the possibility of making secure cloud quantum computing accessible to a wider population using existing communications infrastructure.

Figure 1

Total order of the measurements for a generic $n\times m$ cluster state used as a resource state in Protocol 1.

Figure 2

(a) A cluster-state graph ${\mathcal{G}}_{n,m}$ with diagonal cuts imposed. The flow across each cut is independent, and the number of possible flows across each cut is indicated. (b) Several cuts with their neighboring vertices isolated.

Figure 3

$A_{\mu }^{\to }$ and $A_{\mu }^{\cancel{\to }}$ can be constructed recursively, as shown above. Here, arrows indicate information flow, while edges indicate the possibility of information flow.

Figure 4

A $2\times 2$ cluster state with measurement angles $\{\alpha ,\beta ,\gamma ,\delta \}$. In this example, we show how to encode two different computations using a fixed total order of measurements $\{1,2,3,4\}$. The difference follows from the choice of the $\mathcal{G}(I,O)$. In diagram (a), the input set is $\{1,3\}$, and the output set is $\{2,4\}$, with g-flow function $g(1)=\{2\}$ and $g(3)=\{4\}$. The equivalent circuit associated with the positive branch of this MBQC pattern is shown below. Note that any final round of corrections is pushed into the classical post-processing of the output. In diagram (b), the input set is $\{1,2\}$, the output set is $\{3,4\}$, $g(1)=\{3\}$, and $g(2)=\{4\}$. Similarly to (a), we show the circuit of the positive branch of the MBQC pattern, and the final round of corrections is classically post-processed.

Figure 5

List of the nine possible $\mathcal{G}(I,O{)}_{2,2}$ combinations (and associated patterns) with g-flow for the cluster state $|\mathrm{CS}{⟩}_{2,2}$. The arrows indicate the direction of the quantum information flow. Note that overlapping input and output sets are allowed. All the patterns implement unitary embeddings on the input state.

Figure 6

Illustration of an exemplary run of Protocol 1. At the start of the protocol, Alice’s computation is expressed as a measurement pattern on a graph, in this case, ${\mathcal{G}}_{2,2}$. This is communicated to Bob, who prepares the initial state. The computation then proceeds in rounds with Alice computing the relevant entries of ${\mathbf{s}}^x$ and ${\mathbf{s}}^z$ and, using these together with $r_i$, the measurement angle ${\alpha }_i^{\prime }$. The measurement angle ${\alpha }_i^{\prime }$ is communicated to Bob, who performs the measurement and returns the result to Alice as $b_i^{\prime }$. From this, Alice computes $b_i$ as $b_i^{\prime }\oplus r_i$. This process is repeated until all qubits have been measured. At the end of the protocol, for any fixed transcript of the communication (composed of ${\mathbf{\alpha }}^{\prime }$ and ${\mathbf{b}}^{\prime }$), it is always possible to find a choice for $\mathit{\alpha }$ consistent with the transcript for any choice of $\mathbf{f}$. In other words, for any of the possible g-flow configurations shown in Fig. 5, Bob can find an $\mathbf{\alpha }$ that would have led to the transcript he recorded, which means any of those g-flows is possible. This ambiguity is responsible for partially hiding Alice’s computation from Bob.