The scheme UBQC (presented in [BFK08]) is a delegated quantum computation scheme based on the measurement-based framework. The paper presents several different settings, but the main scheme requires the client to prepare random single-qubit states. At the expense of an extra server, the client can be made purely classical (as long as the two servers do not communicate). Extensions are presented that offer authentication and fault-tolerance. The UBQC scheme is extended in Unconditionally Verifiable Blind Quantum Computation [FK12].
Another contribution of [BFK08] is the introduction of brickwork states for measurement-based quantum computation. These states are universal for quantum computation, and are used in constructions in TODO.
Key features: blindness, authentication, fault-tolerance, limited quantum power in client (realistic) in case of classical input.
The scheme is a distributed version of measurement-based quantum computation, where the client prepares the single-qubit states and computes the classical feedforward mechanism (new measurement angles etc), and the server creates the entanglement and performs the measurements.
| Preparation |
Client prepares sufficiently many \(|+\rangle\) states, and performs random Z-rotations on them (with angle \(0, \pi/4, ..., 7\pi/4\)). Server entangles them according to the structure of the brickwork state. (Note: the entangling operations commute with the random Z-rotations from the client). |
| Encryption |
Classical input: the measurement angles in the rest of the computation might depend on the input. (i.e. classical input determines the circuit) Client computes this herself. Quantum input: apply variation of the quantum one-time pad, but with eight possible Z-rotations (as above) instead of two. (Equivalently: apply quantum one-time pad, then apply a random Z-rotation as above.) |
| Decryption |
Classical output: server measures final layer of qubits, sends results to client (who possibly flips the result, depending on \(r\), see below) Quantum output: server sends final layer of qubits back to client, who undoes the altered quantum one-time pad. |
Note that for quantum input/output, the client needs to be able to perform a \(T\) gate...
The scheme is perfectly private, with no computational assumptions, except for unavoidable leakage of the size of the data. More formally, it is proven that:
These claims also hold if the execution of the protocol was malicious (on the side of the server).
Client needs to:
Server needs to:
Apart from the single-qubit states sent from client to server prior to the computation, they only need to communicate classically.
Delegated computation is possible as follows. The client has a measurement angle \(\varphi\) in mind. She knows the target qubit has a random Z-rotation \(\theta\) on it that needs to be accounted for. She sends the server the value \(\varphi + \theta + r \pi\), where \(r \in_R \{0,1\}\), and the server measures in that angle. The result is correct if \(r = 0\), and needs to be flipped otherwise. Hence, the client knows the measurement result and can use it to determine the next measurement angles in the `flow' of the brickwork state.
If the input was quantum, the client needs to adjust the first layer of measurement accordingly, so she can correct for any Pauli Xs.
If the output is also quantum, the client needs to keep track of the Pauli keys during the computation, accounting for them while picking the measurement angles.
The protocol necessarily leaks the size of the brickwork state, which provides an upper bound to the size of the circuit. Other than that, the protocol is blind.
The protocol can be extended to include authentication (client detects a non-cooperating server). The proof is not very rigorous, and in [FK12] (see Unconditionally Verifiable Blind Quantum Computation) it is claimed that the proof does not work for 'the most general adversary'.
For classical output: add as many trap wires (in state \(|0\rangle\) or \(|1\rangle\)) as there are input wires. The probability of detecting a cheating server is 1/2. Repeat the computation \(s\) times to amplify this probability to exponential \(1 - 2^{-s}\).
For quantum input and/or if used in combination with fault tolerance: add three times as many traps: in X, Y, and Z basis.
By using any error-correcting code, fault tolerance can be built into the scheme. Protocol 4 in [BFK08] promises fault tolerance combined with authentication: in this combination, the client should still accept if a small number of traps (below the fault-tolerance threshold) are corrupted.
TODO
Extended by Kashefi / Pappa
The protocol above can be interpreted as an interactive proof system with a BQP prover and an almost-classical verifier (with the ability to generate random single-qubit states). The preparation of these single-qubit states can be outsourced to a second server (that is not allowed to communicate with the computing server, but is allowed to be entangled with it)), resulting in a purely classical client.