Prepare-and-Send Verifiable Universal Blind Quantum Computation

The example protocol achieves the functionality of Delegated Computation which is a take which enables a client with limited quantum technology to delegate a computation to an untrusted but powerful quantum server in such a manner, where the privacy of the computation is maintained. This protocol introduces verifiability as a property and allows the client to verify the correctness of Prepare-and-Send Universal Blind Quantum Computation. The client has an ability to verify whether the server has followed the instructions of the protocol and also can check if the server tried to deviate from the protocol which would have resulted in an incorrect output state.

Tags: Two Party,Universal Task, Quantum Functionality, Quantum Offline communication, Classical Online communication, Measurement Based Quantum Computation (MBQC), Measurement Only UBQC, Pseudo-Secret Random Qubit Generator (PSQRG), Prepare-and-Send Universal Blind Quantum Computation.

Assumptions

• The protocol assumes perfect state preparation, transmissions, and measurements.
• The client never deviates from the protocol.
• The position of the trap qubit always remains hidden from the server.

Outline

This protocol is a modified version of Prepare-and-Send Universal Blind Quantum Computation, which is based on MBQC. Here a powerful adversarial server is delegated with quantum computation while maintaining the privacy. Any computational deviations by this server are detected by high probability. This is achieved by insertion of randomly prepared and blindly isolated single qubits in the computation, which act as a trap (trap qubits), hence assisting the client in verification.

The brickwork states used in Prepare-and-Send Universal Blind Quantum Computation are modified to a cylinder brickwork states which enables the client to embed a trap qubit surrounded by multiple dummy qubits without disrupting the computation. This state is universal and maintains the privacy of the client's preparation.

The dummy qubits here do not take part in the actual computation as they are disentangled from the rest of the qubits of the graph state. Hence by adding them to the neighbouring nodes of the trap qubits, they are blindly isolated and thus do not interfere with the actual computation. The dummy qubits are added next to the trap qubit in a tape format.

This protocol is dived into four stages: Client's preparation, server's preparation, interaction and measurement, verification.

• Client's preparation: The partially quantum client prepares the quantum states with embedded traps qubits and sends them to the server for creation of the cylinder brickwork state.
  • For the server to create a cylinder brickwork state, the client prepares $m*n$ single qubit states. The Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} qubit input states are specially encoded and all the other non-input qubits except the trap qubit are prepared with randomly chosen local phase angles.
  • During this preparation, the client randomly selects one qubit as the trap qubit and corresponding to the graph of cylinder brickwork state, all the other qubits in the tape are set as the dummy qubits. The trap qubit is prepared with the local phase angle set to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} .
  • The client then sends all the prepared qubits in the respective order so the graph state can be constructed by the server.
    
    

• Server's Preparation: The server receives the qubits in the order of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} rows and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} columns and entangles them according to the cylinder brickwork state (using CZ gate).
  
  
• Interaction and Measurement: This step is exactly the same as for Prepare-and-Send Universal Blind Quantum Computation.
  • The client sends the measurement angle to the server for every single qubit. This measurement angle includes the parameters like correction sets obtained from flow construction, input state's random local phase and a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi} rotation to hide the output. Thus it reveals no information about the underlying computation.
  • The server sends the classical output of each non-input qubit's measurement to the client. The client considers the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi} rotation to get the corrected output. The client also uses this to calculate the measurement angle and thus repeats the process until the last output qubits are reached.
    
    
• Verification: The verification is carried on by the client by comparing the outcome of the trap qubit measurements with the expected outcome.

Quantum outputs:

• • The server sends all the output qubits to the client.
  • From these output qubits, the client performs a measurement on the trap qubit. If the output is equal to the expected outcome, the computation is verified. Otherwise, it is rejected.
  • If the computation is accepted, output correction is performed on the other output qubits (except the trap qubit).

Classical outputs:

• • The server continues performing measurements on the output qubits with the measurement angles sent by the server.
  • The client compares the output of the trap qubit with the expected output. If it is equal, computation is verified. Otherwise, it is rejected. If the computation is accepted, the client accepts the other output measurement results as the computation result.

Notation

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} : Total number of input qubits. Also total number of output qubits in quantum outputs.
• $m$: Total number of qubits in the graph state.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |I\rangle} : $n$ qubit input state.
• $|e\rangle$: Encoded $n$ qubit input state.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} : Set of random bits used in encoding Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |I\rangle} via quantum one time pad.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} : Trap qubit position vertex in the graph state.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} : Set of all position vertices in the tape of the cylinder brickwork state.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta_i} : Random local phase angles for qubit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |+\rangle_{\theta_i}} : Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{\sqrt{2}} (|0\rangle +e^{i\theta_i}|1\rangle)}
• $\phi _{i}$: True measurement angle for qubit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi^{'}_i} : Updated version of measurment angle for qubit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r \in \{ 0, 1\}} : randomly chosen parameter for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi} rotation in order to hide classical output.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta_i} : Final measurement angle for qubit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} .
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} : Measurement output by the server.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} : Sequence of length m describing the result of the nonoutput measurements. $s_{i}\in \{0,1\}$

Hardware Requirements

• Quantum computation resources for the server.
• A quantum channel from the client to the server to transfer initial quantum states.
• Classical channel from the client to the server to transfer measurement angles and outputs.
• Measurement devices for the server and the client in case of quantum outputs.

Properties

• The client is partially quantum and should be able to prepare the given initial quantum states.
• This protocol is secure against malicious adversary setting and also detects a cheating server.
• This protocol is universal in nature. The universality of the cylinder brickwork state guarantees that the server’s knowledge about the graph does not reveal anything about the underlying computation.
• This protocol requires no quantum memory for the client.
• This protocol is blind in nature, only revealing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} .
• This protocol is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-\frac{1}{2m}} verifiable in quantum output case.
• This protocol is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-\frac{1}{m}} verifiable in classical output case.
• The trap qubit in the tape format of the cylinder brickwork state remains disentangled from the rest of the graph.
• Every qubit of the underlying graph could potentially be an isolated trap qubit.

Pseudo-Code

Protocol for quantum output case:

Stage 1: Client's preparation:

Input: Input quantum states, prepared non-input qubits, a trap qubit, and dummy qubits.
Output: The server receives all the quantum states in order of the labeling of the vertices of the graph state.

• The client encodes and prepares the first Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -input state.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |e\rangle = X^{x1}_1 Z_1(\theta_1) \otimes ... \otimes X^{xn}_n Z_n(\theta_n)|I\rangle}

• Client randomly chooses the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} to be the trap qubit, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \in D} .
• For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = n+1, n+2, ....m} :
  • if $i\in D$:
    • if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} == dummy qubit:
      • State Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |0\rangle} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |1\rangle} is prepared
    • if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} == trap qubit:
      • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |+\rangle_{\theta_i}} is prepared
  • if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} == non-input qubit:
    • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |+\rangle_{\theta_i}} is prepared
• For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle l = 1, 2, ...n} :
  • The client sends the qubits to the server.

Stage 2: Server's preparation:
Output: Cylinder brickwork state which has a disentangled trap qubit.

• Server creates an entangled state from all received qubits using CZ operations according to their indices and creates the cylinder brickwork state.

Stage 3: Interaction and Measurement:
Input: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta_i}
Output: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i}

• For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = 1, 2, ... m-n} :
  • Client computes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_i} .
    • if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i == t} :
      • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_i = 0}
  • Client randomly selects Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_i} .
  • Client then computes the angle Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta_i} and sends this to the server.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta_i = \phi^{'}_i + \theta_i + r_i\pi}

• • Server measures Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i} and sends it to client.
  • Client sets the value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} to be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_i \oplus r_i} .

Stage 4: Verification:
Input: Output qubits Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m-n+1} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m}
Output: Verification result

• For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = m-n+1, ... m} :
  • Server sends output qubit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} to client.
• Client measures the output trap qubit Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} (which was disentangled) with angle Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta_t = \phi_t + r_t\pi} .
  • Client obtains the result Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_t} .
    • If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_t == r_t} :
      • Computation is accepted.
    • else:
      • Computation is rejected.

*contributed by Rhea Parekh