PaperlayerView exact revision on arXiv

Source-linked AI summary

Private quantum computation: An introduction to blind quantum computing and related protocols

Joseph F. Fitzsimons

arXiv:1611.10107v1quant-phcs.CR

TL;DR

This review examines how quantum computation can be securely delegated to untrusted devices while preserving privacy and, in some protocols, integrity. It synthesizes blind and verifiable quantum-computation protocols across client and server capability settings, formalizing security through ideal resources and composable definitions. The field demonstrates blindness, verification mechanisms, and reduced client requirements, but completely classical single-server blind or verifiable computation remains an open question.

  • Problem

    Secure delegation must protect computation privacy and sometimes integrity against untrusted quantum servers, beyond what communication encryption and authentication provide.

  • Method

    The paper reviews blind and related delegated-quantum-computation protocols across client capabilities, server configurations, and formal security definitions.

  • Results

    Reviewed protocols establish blind computation with clients ranging from restricted quantum devices to single-qubit state preparation, while some also provide verification and composable security.

  • Takeaways & Limitations

    Blind quantum computation shows how delegated quantum processing can preserve privacy and, in some schemes, support verification while reducing client-side quantum requirements.

  • Takeaways & Limitations

    Whether blind or verifiable computation is possible with a completely classical client and a single server remains a prominent open question.

Abstract

from arXiv · show

Quantum technologies hold the promise of not only faster algorithmic processing of data, via quantum computation, but also of more secure communications, in the form of quantum cryptography. In recent years, a number of protocols have emerged which seek to marry these concepts for the purpose of securing computation rather than communication. These protocols address the task of securely delegating quantum computation to an untrusted device while maintaining the privacy, and in some instances the integrity, of the computation. We present a review of the progress to date in this emerging area.

I. INTRODUCTION

Delegated quantum computation offers practical access to remote quantum processors but creates privacy and integrity risks when servers are untrusted. Blind quantum computation addresses these risks, although fully classical single-server protocols remain difficult.

  • Motivation: Remote quantum computation is becoming more feasible because global communications networks and existing optical-fibre infrastructure support access to quantum processors.Early efforts have already provided Internet access to rudimentary quantum processors.
  • Security problem: Delegating computation to untrusted hardware can compromise the privacy or integrity of both the computation and its results.Encryption and authentication protect communications but do not address malicious-server behaviour.
  • Blind quantum computation: Blind quantum computation lets clients delegate quantum computations while hiding the computation’s structure from one or more remote quantum servers.Many BQC protocols also embed hidden tests to verify the computation.
  • Open challenge: The most desirable setting is verifiable blind computation for a completely classical client using a single quantum server, but progress toward it has been slow.A retained communication transcript can let the server rerun its part of the process many times.
  • Open challenge: A classical client and a single universal quantum server would connect blind computation to questions about BQP, NP, and polynomial-hierarchy collapse.Mechanisms supporting this functionality have only recently begun to emerge.
  • Research directions: Existing progress broadly relaxes either the client’s lack of quantum capabilities or the requirement for a single quantum server.The first category gives the client limited quantum capability insufficient for unaided quantum computation.

II. SECURITY

The review formalizes blind quantum computation through ideal resources and composable security, distinguishing correctness from blindness and relating blindness to verification. Verification uses traps or stabilizer checks, but its relationship with blindness remains unsettled.

  • Security definitions: Blindness can be defined by requiring that the server’s received information depend on the computation only through an allowed leakage function L(x).The leakage function commonly captures circuit dimensions.
  • Security definitions: The earlier blindness definition may fail to control information learned from the client’s resulting state after protocol completion.Stronger definitions therefore specify the protocol’s behaviour as part of a larger system.
  • Ideal resources: An ideal resource specifies blind-computation functionality independently of any particular protocol and exposes client and server interfaces.Quantum information passing through interfaces may belong to non-separable compound systems.
  • Composable security: Correctness requires an honest concrete protocol to match the ideal resource, while blindness requires indistinguishability from an ideal resource with a simulator.An ϵ-blind protocol is ϵ-close to the simulated ideal resource.
  • Verification: Verification can use hidden logical or physical trap qubits whose expected outcomes reveal server deviations, or stabilizer checks on received qubits.The stabilizer approach applies when the client performs adaptive measurements on a fixed resource state.
  • Verification: Several verification schemes do not immediately yield blind-computation protocols, leaving open whether blindness and verification are independent properties.Trap-based verification has already made several BQC protocols verifiable.

A. Restricted quantum computation

Childs’s protocol enables a client with restricted quantum capabilities to delegate universal quantum computation while hiding the computation. Quantum one-time-pad encryption protects transmitted qubits, while Clifford and non-Clifford gates require different correction strategies.

  • Client capabilities: Childs considered a client with quantum memory, qubit rearrangement, Pauli operations, and transmission ability, but without gates such as Toffoli or Hadamard.The server supplies the missing universal quantum-computation capability.
  • Encryption: Random Pauli operations form a quantum one-time pad that hides qubit states from server measurements while allowing the client to decode outcomes.The client encrypts selected qubits before transmitting them to the server.
  • Gate implementation: Clifford gates can act directly on encrypted states because the client updates the Pauli encryption key after conjugation.For non-Clifford gates such as T, additional corrections are required when the encryption does not commute with the gate.
  • Limitations: The protocol’s quantum-resource requirements depend on the computation, and it does not provide a general verification mechanism.Childs discussed limited verification possibilities, including witnesses for NP instances and tomography on selected gates.

B. State preparation

UBQC prepares a brickwork graph-state resource from client-generated randomized single-qubit states, then hides the computation through adaptive measurement angles. Measurement-based computation propagates logical qubits through this resource while the client decodes outcomes and blindness is maintained.

  • State preparation: MBQC expresses a quantum computation as sequential single-qubit measurements on a fixed graph-state resource.The brickwork state is used because the original UBQC construction hides measurements in the XY-plane.
  • State preparation: The brickwork graph maps rows to logical-qubit wires, vertices to single-qubit gates, and vertical edges to controlled-phase gates.Measurements in suitable unit-cell patterns implement arbitrary single-qubit rotations and CNOT gates.
  • State preparation: The client prepares NM randomized states |ψ_i⟩, sends them to the server, and the server entangles them according to the N × M brickwork graph.The random variables r_i and θ_i are selected uniformly from {0,1} and the allowed angle set, respectively.
  • State preparation: For each qubit, the client sends an adapted angle δ_i = φ′_i − θ_i, receives outcome b_i, and uses it to update later measurement angles.The adapted angle accounts for previous teleportation byproducts in the measurement-based computation.
  • State preparation: Random preparation angles make the server’s received state maximally mixed and independent of the client’s computation angles, establishing blindness.The protocol’s blindness was proved under the initial definition, while stronger composable security was proved subsequently.
  • State preparation: The protocol can use N + 1 qubits instead of the full NM-qubit resource by postponing controlled-phase operations.This reduction relies on commutation of operations involving non-neighbouring qubits.

C. Measurement

Measurement-based blind quantum computation shifts the client’s role from preparing states to adaptively measuring server-supplied resource qubits. This enables blind computation with composable security, while photon loss and detector requirements remain important practical constraints.

  • C. Measurement: Morimae and Fujii’s protocol has the client perform adaptive single-qubit measurements on a fixed graph state supplied one qubit at a time.The client can implement arbitrary computation while sending no information beyond the initial graph description.
  • C. Measurement: The measurement-based approach is trivially blind because communication proceeds only from the server to the client.It has also been shown to satisfy composable security definitions.
  • C. Measurement: Preparation and measurement approaches are dual under post-selection, making fault-tolerance constructions interchangeable between them.Trap-based verification techniques have been adapted to the measurement setting.
  • C. Measurement: Measurement may be easier than state preparation for photonic clients, but direct measurement protocols are highly susceptible to photon loss.They therefore require extremely efficient detectors and near-lossless communication links.
  • C. Measurement: Repeating remote state preparation until successful makes photon-detection failure impose overhead that scales inversely with the probability of one successful measurement attempt.This can permit BQC with a single low-quality detector and lossy links.

IV. BQC WITH MULTIPLE SERVERS

Multi-server protocols enable blind and verifiable quantum computation for clients without quantum capabilities by distributing the task across entangled servers that cannot communicate. Their benefits come with substantial overhead and a demanding non-communication assumption.

  • IV. BQC WITH MULTIPLE SERVERS: Multi-server protocols give an entirely classical client access to blind quantum computation by using multiple entangled servers prohibited from communicating.The client communicates classically with the servers.
  • IV. BQC WITH MULTIPLE SERVERS: Reichardt–Unger–Vazirani and McKague introduced delegation and verification schemes for classical clients using self-testing techniques based on CHSH games.Both protocols hide the computation from the servers, while RUV uses two servers and McKague uses more.
  • IV. BQC WITH MULTIPLE SERVERS: O(n^4 log n) overhead was achieved for verifiable blind computation with polynomially many servers through self-tested remote state preparation.This improved on earlier schemes with much steeper overhead scaling.
  • IV. BQC WITH MULTIPLE SERVERS: These protocols generally require communication rounds scaling polynomially with computation depth, although one-round non-blind verification protocols use very little communication.The one-round approaches are based on interactive proofs for the local Hamiltonian.
  • IV. BQC WITH MULTIPLE SERVERS: Eliminating client quantum capability requires accepting both higher overhead and the assumption that servers remain unable to communicate.Over arbitrary timescales, maintaining blindness may be impossible in practice because adversarial servers could eventually communicate.

V. COMPUTING ON ENCRYPTED DATA AND HOMOMORPHIC ENCRYPTION

Delegated quantum computation can be related to computing on encrypted data, where a fixed operation acts on an input encoding the circuit and associated states. Work in both blind computation and quantum homomorphic encryption seeks to reduce communication, but a counterpart to a key result remains absent.

  • V. COMPUTING ON ENCRYPTED DATA AND HOMOMORPHIC ENCRYPTION: A fixed unitary applied to an input encoding the full circuit and associated states provides a concrete link between blind computation and computing on encrypted data.In the encrypted-data setting, the operation being evaluated is public.
  • V. COMPUTING ON ENCRYPTED DATA AND HOMOMORPHIC ENCRYPTION: Communication overhead in blind quantum computation has been analyzed in terms of total communication and quantum communication, with protocols approaching corresponding lower bounds.These analyses cover multiple client settings.
  • V. COMPUTING ON ENCRYPTED DATA AND HOMOMORPHIC ENCRYPTION: Fully homomorphic encryption permits arbitrary processing of encrypted data without the encryption key or communication between client and server during processing.This development in classical cryptography motivates analogous reductions in delegated quantum computation round complexity.
  • V. COMPUTING ON ENCRYPTED DATA AND HOMOMORPHIC ENCRYPTION: The term “quantum homomorphic encryption” has also been used for interactive protocols more akin to computing on encrypted data than to a quantum analogue of classical homomorphic encryption.The terminology therefore covers related but distinct protocol classes.
  • V. COMPUTING ON ENCRYPTED DATA AND HOMOMORPHIC ENCRYPTION: No counterpart to the cited work on quantum homomorphic encryption has been found to date, even with a sufficiently large key.The passage states this as the current status of the field.

VI. PHYSICAL IMPLEMENTATIONS

Physical implementations have demonstrated delegated quantum computation in quantum optics, while scalable blind computation may require hybrid systems that use matter qubits for computation and photons for communication. Current photonic hardware remains constrained by loss, destructive measurement, and difficult entangling gates.

  • VI. PHYSICAL IMPLEMENTATIONS: Experimental work seeks to make blind and verifiable delegated-computation protocols physically realizable, building on proposals for fault-tolerant constructions.The effort addresses the gap between theoretical protocols and experiments.
  • VI. PHYSICAL IMPLEMENTATIONS: Hybrid architectures could use trapped ions or other matter qubits for computation while emitting entangled photons for communication.Client measurements could remotely establish correlations with server matter qubits sufficient for UBQC-like protocols.
  • VI. PHYSICAL IMPLEMENTATIONS: Matter–photonic entangled states have already been demonstrated in multiple systems, supporting hybrid architectures as a possible route beyond current experimental hurdles.The depicted example couples matter-qubit states to photon polarization, though other photonic degrees of freedom are possible.
  • VI. PHYSICAL IMPLEMENTATIONS: A four-qubit photonic resource state enabled a successful UBQC demonstration implementing blind Deutsch–Jozsa and Grover search algorithms.The experiments used resource states entangled according to several graph structures.
  • VI. PHYSICAL IMPLEMENTATIONS: Photons are well suited for communication but less suited to large-scale computation because current measurements are destructive and deterministic photonic entangling gates are difficult.Universal computation with linear optics is possible, but these hardware constraints remain significant.

VII. CONCLUSIONS AND OUTLOOK

Delegated quantum computation is timely, but the field remains young with major open questions about single-server security, blindness, verification, and fully homomorphic quantum encryption.

  • The field is still in its infancy, with frequent new results but many open questions remaining.
  • Secure blind or verifiable computation with a single server and a completely classical client remains an open question.This remains unresolved even when multiple non-entangled, non-communicating servers are allowed.
  • The precise relationship between blindness and verification is currently unresolved.
  • Fully homomorphic quantum encryption under plausible computational assumptions remains open despite promising progress by Dulek et al.
Loading 1611.10107v1…