Prepare-and-Send Universal Blind Quantum Computation

Functionality Description

Delegated Computation is the task of assigning quantum computation to an untrusted device while maintaining privacy of the computation. It can be done via classical online/offline and quantum online/offline communication. Following description deals with a method which involves quantum offline and classical online communication, called Blind Quantum Computation. It comes with the properties of correctness i.e. if both parties follow the protocol the final outcome is correct, and blindness i.e. the Client to have Server carry out a quantum computation for her (Client) such that the Client’s inputs, outputs and circuit used for computation remain perfectly private from the Server.

Tag:	Two Party, Universal Task, Quantum Functionality, Quantum Delegated computation, Quantum Offline communication, Classical Online communication.

See also

Verifiable Delegated Quantum Computing, QKD.

Procedure/Outline

The following Universal Blind Quantum Computation (UBQC) protocol uses the unique feature of Measurement Based Quantum Computation (MBQC) that separates the classical and quantum parts of a computation. MBQC requires a set of initial entangled states, called graph states for computation. Here, we shall use a special family of graph states, Brickwork State which are universal (can implement any quantum operation) for X-Y measurements and do not leak any specific data about the computation during preparation. The protocol can be divided into two stages: preparation and computation.
Preparation stage includes a partially quantum Client preparing and sending quantum states to the Server who constructs the required brickwork state. Computation stage involves interaction. We shall discuss below three protocols with different attributes but same functionality. Protocol 1a deals with a partially quantum Client capable of preparing initial quantum states for the construction of brickwork state with classical input/output computation. Protocols 1b and 1c are extensions to accommodate quantum inputs and quantum outputs, respectively.

Protocol 1a:	Client is assumed to be able to prepare quantum states.

• Client’s preparation Client sends the initial qubits for construction of brickwork state to Server in this step. Client has in her mind a quantum computation as a measurement pattern on the brickwork state. She prepares m x n single qubit states with randomly chosen local phase in order to hide her classical inputs later.
• Server’s preparation Server prepares brickwork state of m rows and n columns. It entangles all the received qubits as per Client’s instructions. Thus, ends preparation stage.
• Interaction and Measurement Client and Server interact to perform operations needed for computation. For a given computation and graph state, MBQC provides a measurement angle and some extra Pauli X, Z corrections, for each qubit. The correction sets (also called Dependency sets), unique for every graph state are based on previous measurement outcomes and can be obtained from flow construction. Also, as Client’s input state has random local phase, the same should be added to the measurement angle for computation along with Pauli Corrections to get the correct outcome. Now, in order to hide the output, Client randomly chooses to add a π rotation or not. The final measurement angle includes all the above parameters and hence, is sent to the Server. When Server returns the classical outcome, Client gets the correct outcome by taking into account the random π rotation and then uses it to calculate measurement angle for for the next qubit. The step is repeated until every qubit has been measured. Server returns measurement outcomes for the last column to Client. Client deciphers this outcome to get the final result. This ends the computation stage.

Protocol 1b: Protocol 1a can be modified as follows if Client is provided with m quantum input states beforehand. Client is assumed to be able to prepare quantum states and apply single qubit gates (Pauli gates).

* Client’s input preparation This step encrypts the input state column using quantum one time pad. Client rotates her input qubits using single qubit gate Z(θ), in order to add random local phase. She randomly chooses to flip each qubit using single qubit gate X or do nothing. She then sends these qubits to Server. This is the only extra step as compared to Protocol 1a.

• Client’s auxilliary preparation This step is exactly same as Client’s preparation of m x n initial quantum states for brickwork state in Protocol 1a.
• Server’s preparation Server prepares brickwork state of m rows and n+1 columns in the order instructed by the Client. The ’m’ quantum inputs constitute the first column of brickwork state for this protocol. Thus ends the preparation stage
• Interaction and Measurement This step remains the same as Protocol 1a except that the bit flip used to hide Client’s input is taken care of while computing measurement angle to be sent for the first column.

Protocol 1c: This protocol is different from Protocol 1a such that the last column of the brickwork state is not measured but sent back to the Client. Client is assumed to be able to prepare quantum states and apply single qubit gates (Pauli gates). The following steps account for the modified protocol.

• Client’s auxilliary preparation This step is exactly same as Client’s preparation in Protocol 1a. The difference being, she prepares only m x n-1 initial states this time.
• Client’s output preparation The nth column of brickwork state contains quantum states with zero local phase.
• Server’s preparation Server prepares brickwork state of m rows and n columns in the order instructed by the Client.
• Interaction and Measurement This step remains exactly the same as Protocol 1a
• Output Correction In this step Client applies the Pauli Corrections X, Z on the last column of qubits sent to her by the server.

Notations

• φ, measurement angle for given MBQC pattern to implement the required computation
• φ0, measurement angle including Pauli X,Z corrections
• sX,sZ Dependency sets for Pauli X and Pauli Z corrections, respectively (obtained from flow construction).
• θ, randomly chosen angles by Client in order to hide classical input
• {math missing}, randomly chosen parameter for π rotation in order to hide classical output
• {math missing}, randomly chosen parameter for bit flip in order to hide quantum input
• δ, final measurement angle

Properties

Adversarial Assumption

• This protocol is secure against honest but curious adversary setting

Setup Assumptions

• Protocols 1a-1c need Client to be able to prepare given initial quantum states
• Protocols 1b and 1c need Client to be able to operate single qubit gates
• Protocols 1a-1c need a quantum channel from Client to Server to transfer initial quantum states
• Protocol 1c needs an additional quantum channel from Server to Client to transfer the quantum output

Parameters

• (m,n) define dimensions of the brickwork state

Security Claim/ Theorems

• Universality As brickwork states are universal for X-Y plane measurements, the protocol is universal. This protocol uses approximate universality although exact universality can be achieved if Client if allowed to communicate real numbers.
• Correctness If Client and Server follow protocols 1a-1c as described above, the outcome will be correct.
• Blindness Protocols 1a-1c are blind while leaking at most (m,n) to the Server
• At every step of Protocol 1a, Server’s quantum state is one-time padded as sX and sZ are hidden by the random key r for each qubit

Pseudo-Code: Universal Blind Quantum Computation- Protocols 1a, 1b, 1c

• Unless given specific mention in [.], following steps apply to all the three protocols 1a-1c

Preparation Stage

• Input: Client: Dimeonsions of Brickwork State (m,n), Input States (ψ0,y) [Protocol 1b only], Auxilliary Input States (ψx,y)
• Output: Server: Brickwork State Gmxn

Client [Protocol 1a]

1. Client’s preparation
   1. For each column x = 1,...,n
      1. For each row y = 1,...,m
         1. Client prepares and sends the qubits to Server.

Client [Protocol 1b]

1. Client’s input preparation
   1. For the input column (x = 0,y = 1,...,m) corresponding to Client’s input
      1. Client applies Z0,y(θ0,y) for θ0,y ∈R {0,π/4,2π/4,...,7π/4}.
      2. Client chooses i0,y ∈R {0,1} and applies . She sends the qubits to Server.
2. Client’s auxiliary preparation
   1. For each column x = 1,...,n
      1. For each row y = 1,...,m
         1. Client prepares |ψx,yi ∈R {|+θx,yi | θx,y = 0,π/4,2π/4,...,7π/4} and sends the qubits to Server.

Client [Protocol 1c]

1. Client’s auxiliary preparation
   1. For each column x = 1,...,n − 1
      1. For each row y = 1,...,m
         1. Client prepares |ψx,yi ∈R {|+θx,yi | θx,y = 0,π/4,2π/4,...,7π/4} and sends the qubits to Server.
2. Client’s output preparation
   1. 1. 1. Client prepares the last column of qubits |ψn,yi = |+i (y = 1,...,m) and sends the qubits

to Server.

Server’s preparation [Protocols 1a, 1b and 1c]

1. Server creates an entangled state from all received qubits, according to their indices, by applying ctrl-Z gates between the qubits in order to create a brickwork state Gn×m for Protocols 1a and 1c while Gn+1×m for Protocol 1b.

Computation Stage

• Input: Client: Measurement Angle: δx,y
• Output: Server: Measurement Outcome: sx,y

Interaction and measurement

1. For each column x = 1,...,n [Protocols 1a and 1b]; For each column x = 1,...,n−1 [Protocol 1c]
   1. For each row y = 1,...,m
      1. For Protocols 1a and 1c, Client computes φ0x,y where{equation missing}
         For Protocol 1b, Client computes with the special case .
      2. Client chooses rx,y ∈R {0,1} and computes .
      3. Client transmits δx,y to Server. Server measures in the basis {|+δx,yi,|−δx,yi}.
      4. Server transmits the result sx,y ∈ {0,1} to Client.
      5. If rx,y = 1 above, Client flips sx,y; otherwise she does nothing.

Output Correction [Protocol 1c only]

1. Server sends to Client all qubits in the last layer.
2. Client performs the final Pauli corrections .