PaperlayerView exact revision on arXiv

Source-linked AI summary

Universal blind quantum computation

Anne Broadbent, Joseph Fitzsimons, Elham Kashefi

arXiv:0807.4154v3quant-ph

TL;DR

The paper addresses how a client without quantum computational resources or memory can privately use a remote quantum computer. It presents a universal interactive protocol based on finite-set single-qubit preparation and measurement-based computation, with authentication, quantum inputs and outputs, and classical two-prover generalizations.

  • Problem

    The paper asks how a client lacking quantum computational resources or quantum memory can privately obtain the result of a computation performed by a remote quantum computer.

  • Method

    The protocol uses finite-set single-qubit preparations, interactive classical communication, adaptive single-qubit measurements, and measurement-based quantum computation; it also extends to quantum inputs and two entangled non-communicating servers.

  • Results

    The scheme supports universal blind quantum computation, detects interfering servers with overwhelming probability, and yields BQP interactive proofs with either a nearly classical verifier or a purely classical verifier using two entangled provers.

  • Takeaways & Limitations

    A client can delegate universal quantum computations while keeping inputs, outputs, and computations private, using only limited quantum state preparation and classical interaction.

  • Takeaways & Limitations

    The presented protocol considers approximate universality; exact universality requires Alice to communicate real numbers to Bob.

Abstract

from arXiv · show

We present a protocol which allows a client to have a server carry out a quantum computation for her such that the client's inputs, outputs and computation remain perfectly private, and where she does not require any quantum computational power or memory. The client only needs to be able to prepare single qubits randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. Our protocol is interactive: after the initial preparation of quantum states, the client and server use two-way classical communication which enables the client to drive the computation, giving single-qubit measurement instructions to the server, depending on previous measurement outcomes. Our protocol works for inputs and outputs that are either classical or quantum. We give an authentication protocol that allows the client to detect an interfering server; our scheme can also be made fault-tolerant. We also generalize our result to the setting of a purely classical client who communicates classically with two non-communicating entangled servers, in order to perform a blind quantum computation. By incorporating the authentication protocol, we show that any problem in BQP has an entangled two-prover interactive proof with a purely classical verifier. Our protocol is the first universal scheme which detects a cheating server, as well as the first protocol which does not require any quantum computation whatsoever on the client's side. The novelty of our approach is in using the unique features of measurement-based quantum computing which allows us to clearly distinguish between the quantum and classical aspects of a quantum computation.

1 Introduction

The paper presents universal blind quantum computation in which a client with no quantum memory delegates arbitrary computations while preserving privacy. Its measurement-based protocol also supports quantum inputs and outputs, authentication, fault tolerance, and classical-verifier proofs for BQP.

  • Core protocol: The protocol supports quantum inputs and outputs, including remote preparation, measurement, and processing of quantum information.For physical-qubit inputs, Alice applies local Pauli-X and Pauli-Z operators to implement a quantum one-time pad.
  • Complexity-theoretic applications: The protocol yields interactive proofs for BQP with a quantum prover and nearly classical verifier, or with two entangled non-communicating provers and a purely classical verifier.The two-prover construction uses shared entanglement and restricts communication between the provers.
  • Core protocol: Alice can delegate any quantum circuit to Bob without quantum computational resources or quantum memory, preparing only randomly chosen single qubits.The protocol separates Alice’s classical control from Bob’s quantum computation through measurement-based quantum computing.
  • Security and resources: Alice’s privacy is perfect except for unavoidable leakage of the computation’s size, while required quantum and classical communication is linear in circuit size.Bob learns the dimensions of the brickwork state, which upper-bound the computation size.
  • Security and resources: Authentication detects an interfering Bob with overwhelming probability, and the scheme can be made fault-tolerant.If interference is not corrected, Theorem 7 bounds undetected alteration by an exponentially small probability.
  • Technique: Measurement-based quantum computing enables the scheme by separating quantum operations performed by Bob from classical feedforward computed by Alice.The approach uses randomized preparation to obscure the computation from Bob.

2 Main Protocol

The main protocol represents a quantum computation as an adaptive measurement pattern on a brickwork state, with measurement angles adjusted using prior outcomes and hidden randomization.

  • Alice specifies a unitary U through measurement angles and dependency sets on the brickwork state.Each qubit is assigned a target angle together with X- and Z-dependencies derived from the flow construction.
  • The actual measurement angle is modified according to parity values computed from previous measurement outcomes.The protocol uses separate X- and Z-dependent outcome parities to adapt each measurement.
  • Protocol 1 implements blind computation of U when Alice’s classical input is incorporated into the unitary.In this setting, Alice computes U|0⟩, with the first layers of U allowed to depend on her input.
  • Alice prepares qubits with angles chosen from {0, π/4, 2π/4, . . . , 7π/4} and sends them to Bob.

2. Bob’s preparation

Bob prepares and measures the brickwork resource while Alice adaptively supplies randomized classical instructions. The protocol is correct and blind, while leaking only the resource dimensions.

  • Bob’s preparation: Bob creates the brickwork state by applying controlled-Z gates between the received qubits according to their indices.The brickwork state is defined from indexed |+⟩ qubits with controlled-Z edges within rows and specified inter-column connections.
  • Interaction and measurement: Alice sends randomized measurement angles δx,y, Bob returns outcomes sx,y, and Alice flips outcomes when rx,y = 1.The angle message incorporates a random bit, while the returned measurement outcomes drive the adaptive computation.
  • Bob’s preparation: The brickwork state is universal and supports layer-by-layer single-qubit measurements using angles {0, ±π/4, ±π/2}.The protocol uses approximate universality to restrict preparation and measurement angles to finite sets.
  • Correctness: The protocol is correct when Alice and Bob follow it, because randomized rotations and outcome flips reproduce Alice’s target measurements.Controlled-Z gates commute with Z-rotations, and the πrx,y term determines whether Alice flips Bob’s outcome.
  • Blindness: Protocol 1 is blind while leaking at most the dimensions (n, m) of the brickwork state.Bob’s classical and quantum views are independent of Alice’s input once the allowed leakage is fixed; the dimensions reveal bounds on computation size.
  • Blindness: Alice cannot reveal whether she accepts the result in the basic protocol because that bit could expose information about the computation.Protocol 4 is identified as the alternative when acceptance disclosure is needed.

3 Quantum Inputs and Outputs

The protocol extends to quantum inputs and outputs by adding local Pauli operations for input encryption and returning output qubits for final correction.

  • Quantum inputs: Quantum inputs require Alice to apply local Pauli-X and Pauli-Z operations, while the protocol remains correct and private.The first measurements undo the possible Pauli-X operation, and the quantum one-time pad protects the inputs.
  • Quantum inputs: Alice needs quantum memory when she already holds all input qubits, plus the ability to apply single-qubit gates.These requirements are only slightly beyond choosing among four single-qubit gates for quantum inputs.
  • Quantum outputs: For quantum outputs, Bob returns the final layer of qubits and Alice applies the final Pauli corrections.This supports blind quantum state preparation and requires a quantum channel from Bob to Alice.
  • Quantum outputs: At every step of Protocol 1, Bob’s quantum state is one-time padded.Random keys induce independent Pauli operators across the computation, encrypting the qubits manipulated by Bob.
  • Quantum outputs: The one-time-pad property, together with Theorems 2 and 3, establishes correctness and privacy for the quantum-output protocol.

1. Alice’s input preparation

For quantum inputs, Alice prepares the input column by applying randomized Z rotations and Pauli-X operations before sending the qubits to Bob.

  • Alice’s input preparation: Alice applies Z rotations with angles selected from {0, π/4, 2π/4, . . . , 7π/4} to the input qubits.
  • Alice’s input preparation: Alice randomly chooses a bit, applies the corresponding Pauli-X operation, and sends the input qubits to Bob.

2. Alice’s auxiliary preparation

Alice prepares randomly rotated single-qubit states and uses interactive classical messages to drive Bob’s measurement-based computation.

  • Alice sends Bob qubits prepared with angles θx,y chosen from eight equally spaced values.
  • Bob entangles the received qubits with controlled-Z gates to create a brickwork state G(n+1)×m.
  • Alice masks each measurement angle with a random bit, sends δx,y to Bob, receives sx,y, and conditionally flips the result.

1. Alice’s auxiliary preparation

The auxiliary preparation protocol uses Alice’s randomly chosen qubits and classical interaction to construct and measure a brickwork computation.

  • Alice prepares the last column as |+⟩ states and sends those qubits to Bob.
  • Bob applies controlled-Z gates according to the qubit indices to create the brickwork state Gn×m.
  • Alice randomizes each measurement angle with θx,y and πrx,y, transmits δx,y, receives sx,y, and corrects sx,y when rx,y=1.

5. Output Correction

The authenticated protocol returns encoded outputs with final Pauli corrections while using traps, fault-tolerant computation, and hidden wire permutations to detect interference and tolerate faults.

  • 5. Output Correction: Bob sends all qubits in the last layer to Alice, who applies the final Pauli corrections ZsZ n,yXsX.
  • Classical Output: For non-fault-tolerant classical outputs, repeated trap-wire checks bound the probability of accepting an incorrect output by 2^-s.Alice accepts only when repeated outputs are identical and no trap reveals cheating.
  • Authentication: The authenticated construction encodes logical qubits, inserts randomly interspersed trap wires, and keeps within-code wire permutations secret from Bob.For each logical qubit, the construction uses an error-correcting code and 3nT trap wires, with nT=nC.
  • Fault Tolerance: The protocol converts the fault-tolerant circuit to measurement-based computation and periodically measures ancillae and traps to estimate the error rate.Alice accepts when the estimated error rate is below the stated threshold and rejects otherwise.
  • Results: Protocol 4 is fault-tolerant and blind while leaking at most (n, m).
  • Authentication: If Bob interferes, he is detected except with exponentially small probability or his actions fail to alter the computation.The authentication guarantee is stated for the zero-error case of Protocol 4.

5 Entangled Servers

Protocol 5 enables a purely classical verifier to perform blind quantum computation with two non-communicating entangled provers.

  • One prover prepares the random qubits while the other performs universal blind quantum computation.
  • Authentication detects cheating by either server, while the computing server’s subsystem remains completely mixed and preserves blindness.

1. Alice’s preparation with Server 1

Alice chooses random measurement angles, sends them to Server 1, receives measurement outcomes, and uses those outcomes to adjust the authenticated blind computation with Server 2.

  • Server 1 measures his part and returns the outcome m_x,y to Alice.
  • Alice runs the authenticated blind quantum computing protocol with Server 2 using θ_x,y = ˜θ_x,y + m_x,yπ.

A Measurement-based quantum computing

Measurement-based quantum computing uses entanglement, single-qubit measurements, signals, and dependent corrections to execute universal measurement patterns in standard form.

  • MBQC applies entanglement operators and destructive single-qubit measurements to finite sets of input and output qubits.
  • Measurement outcomes are combined modulo 2 into signals that can control later corrections.
  • Dependent corrections can be absorbed into the measurement angle of the affected qubit.
  • Measurement patterns are universal and can be rewritten so preparation and entangling commands occur at the beginning.

B Universality of the Brickwork state

The brickwork state is universal: suitable single-qubit measurements implement a universal gate set, and tiled patterns realize arbitrary circuits layer by layer.

  • The brickwork state is universal using single-qubit measurement angles {0, ±π/4, ±π/2}, with measurements performed layer by layer.
  • Specific measurement angles implement the Hadamard, π/8, and identity gates.
  • A measurement pattern implements ctrl-X, and neighboring ctrl-X gates suffice to connect more distant qubits.
  • Patterns for the universal gates can be tiled to implement circuits whose gates act on at most two adjacent qubits.
Loading 0807.4154v3…