Full-text links:
Download:
- PostScript
- Other formats
Current browse context:
quant-ph
< prev | next >
new | recent | 0807
References & Citations
- INSPIRE HEP
(refers to | cited by) - NASA ADS
3 blog links
(what is this?)Bookmark
(what is this?)Quantum Physics
Title: Universal blind quantum computation
Authors:
Anne Broadbent,
Joseph Fitzsimons,
Elham Kashefi
(Submitted on 25 Jul 2008 (v1), last revised 12 Dec 2009 (this version, v3))
Abstract: 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.
Comments: | 20 pages, 7 figures. This version contains detailed proofs of authentication and fault tolerance. It also contains protocols for quantum inputs and outputs and appendices not available in the published version |
Subjects: | Quantum Physics (quant-ph) |
Journal reference: | Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 517-526 |
DOI: | 10.1109/FOCS.2009.36 |
Cite as: | arXiv:0807.4154 [quant-ph] |
(or arXiv:0807.4154v3 [quant-ph] for this version) |
Submission history
From: Joseph Fitzsimons [view email][v1] Fri, 25 Jul 2008 18:35:00 GMT (50kb)
[v2] Mon, 4 May 2009 00:36:03 GMT (324kb)
[v3] Sat, 12 Dec 2009 12:44:58 GMT (474kb)
Which authors of this paper are endorsers?