Prepare-and-Send Universal Blind Quantum Computation

The example protocol achieves the functionality of Secure Client- Server Delegated Quantum Computation by assigning quantum computation to an untrusted device while maintaining privacy of the input, output and computation of the client. The client requires to be able to prepare and send quantum states while the server requires to possess a device with quantum memory, measurement and entanglement generation technology. It has the properties of correctness, blindness and universality. Following description deals with a method which involves quantum offline and classical online communication, called Blind Quantum Computation.

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 Verifiable Universal Blind Quantum Computation (VUBQC).

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 states 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 three stages: preparation, computation and output correction.
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. Output Correction involves retrieval of correct output from the results sent by the Server. We shall discuss below three protocols with different attributes but same functionality. All UBQC protocols discussed below require Client to prepare the required quantum states for computation and send those to the Server, hence the name Prepare and Send UBQC. 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.

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

Requirements

• Network Stage: Quantum Memory
• Required Network Parameters:
  • $\epsilon _{j}$, which measures the error due to noisy operations.
  • Number of communication rounds
  • Circuit depth
  • Number of physical qubits used
• Client should have preparation devices
• Quantum offline channel
• Classical online channel
• Server should be able to generate large network of entangled quantum states.

Prepare-and-Send Universal Blind Quantum Computation

Properties

• (m,n) define dimensions of the brickwork state
• This protocol is secure/blind in every setting (universal)
• The Protocol needs Client to be able to prepare given initial quantum states
• The Protocols needs a quantum channel from Client to Server to transfer initial quantum states
• This protocol requires no quantum memory for the Client
• This protocol is universally composable (1)
• 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 the protocol as described above, the outcome will be correct.
• Blindness The protocol is blind while leaking at most (m,n) to the Server.

Notations

• • $\phi$, measurement angle for given MBQC pattern to implement the required computation
  • $\phi _{0}$, measurement angle including Pauli X,Z corrections
  • $s_{X},s_{Z}$ Dependency sets for Pauli X and Pauli Z corrections, respectively (obtained from flow construction).
  • $\theta$, randomly chosen angles by Client in order to hide classical input
  • r $\epsilon _{R}\{0,1\}$, randomly chosen parameter for $\pi$ rotation in order to hide classical output
  • $\delta _{x},y$, final measurement angle for the qubit at position (x,y) in the brickwork state

Pseudocode

click here for SimulaQron code

Stage 1: Preparation

• Input: Client: Dimensions of Brickwork State (m,n), Input States ($\psi _{0,y})$, Auxilliary Input States ($\psi _{x,y}$)
• Output: Server: Brickwork State $G_{\text{mxn}}$
  • Client’s preparation

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

• • Server’s preparation

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 $G_{\text{n x m}}$.

Stage 2: Computation Stage

• Input: Client: Measurement Angle: $\delta _{x,y}$
• Output: Server: Measurement Outcome: $s_{x,y}$
  • Interaction and measurement

1. For each column x = 1,...,n
   1. For each row y = 1,...,m
      1. Client computes $\phi '_{x,y}$ where $s_{0,y}^{X}=s_{0,y}^{Z}=0$
         
      2. Client chooses $r_{x,y}\epsilon _{R}{0,1}$ and computes $\delta _{x,y}=\phi '_{x,y}+\theta _{x,y}+\pi r_{x,y}$.
      3. Client transmits $\delta _{x,y}$ to Server. Server measures in the basis 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_{x,y}},|−_{\delta_{x,y}}\}} .
      4. Server transmits the result $s_{x,y}\epsilon {0,1}$ to Client.
      5. If $r_{x,y}=1,$ Client flips $s_{x,y}$; otherwise she does nothing.

• • Output Correction [only for quantum outputs]

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

References

1. Dunjko et al (2014)

*contributed by Shraddha Singh