Universal Blind Quantum Computation
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The BQC protocol combines quantum cryptography and quantum computation to delegate a quantum computation from a client with no quantum computational power to an untrusted quantum server while keeping the client's data perfectly private.
“This new fundamental advantage of quantum computers is manifested in the blind quantum computing (BQC) protocol that combines notions of quantum cryptography and quantum computation to achieve the delegation of a quantum computation from a client with no quantum computational power to an untrusted quantum server, such that the client's data remains perfectly private.”
From Demonstration of Blind Quantum Computing (2012) · cites this paper as [29]
The protocol uses experimental resources in an optimised way compared to the original BQC proposal, independent of the physical system and without affecting blindness.
“Our protocol uses, compared to the original BQC proposal [29], the experimental resources in an optimised way, independent of the physical system and without affecting blindness.”
From Demonstration of Blind Quantum Computing (2012) · cites this paper as [29]
These photonic states can be combined via optical gates to create a universal resource state for BQC.
“As shown in Figure 1, these photonic states can be combined via optical gates to create a universal resource state for BQC [29].”
From Demonstration of Blind Quantum Computing (2012) · cites this paper as [29]
Quantum computers can provide unconditional security in data processing, a potential not known to be achievable classically.
“Remarkably, the recent theoretical work by Broadbent, Fitzsimons, and Kashefi [29] overcomes this limitation and shows that quantum computers can provide unconditional security in data processing - a hitherto unrecognized potential of quantum computers that is not known to be achievable classically.”
From Demonstration of Blind Quantum Computing (2012) · cites this paper as [29]
Self-testing is a verification process for the operations of a collection of untrusted quantum devices, and a key application of the blind computing protocol is towards such verification of quantum devices.
“Self-testing is a verification process for the operations of a collection of untrusted quantum devices [47, 48]; a key application of the blind computing protocol is also towards such verification of quantum devices [29, 30].”
From Demonstration of Blind Quantum Computing (2012) · cites this paper as [29]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472 · see citing works
Raussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477 · see citing works
Measurement-based quantum computation on cluster states
Raussendorf, R., Browne, D. E., & Briegel, H. J. (2003) · Physical Review A · doi:10.1103/physreva.68.022312 · Cited by 1,655 · see citing works
Theory of quantum error-correcting codes
Knill, E., & Laflamme, R. (1997) · Physical Review A · doi:10.1103/physreva.55.900 · Cited by 1,593 · see citing works
Quantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424 · see citing works
Quantum computational networks
Deutsch, D. E. (1989) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1989.0099 · Cited by 1,270 · see citing works
Multiparty entanglement in graph states
Hein, M., Eisert, J., & Briegel, H. J. (2004) · Physical Review A · doi:10.1103/physreva.69.062311 · Cited by 1,035 · see citing works
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374396 · Cited by 484 · see citing works
Graph states for quantum secret sharing
Markham, D., & Sanders, B. C. (2008) · Physical Review A · doi:10.1103/physreva.78.042309 · Cited by 445 · see citing works
Cluster-state quantum computation
Nielsen, M. A. (2006) · Reports on Mathematical Physics · doi:10.1016/s0034-4877(06)80014-5 · Cited by 408 · see citing works
A fault-tolerant one-way quantum computer
Raussendorf, R., Harrington, J., & Goyal, K. (2006) · Annals of Physics · doi:10.1016/j.aop.2006.01.012 · Cited by 397 · see citing works
Optimal encryption of quantum bits
Boykin, P. O., & Roychowdhury, V. (2003) · Physical Review A · doi:10.1103/physreva.67.042317 · Cited by 341 · see citing works
Authentication of quantum messages
Barnum, H., Crépeau, C., Gottesman, D., Smith, A., & Tapp, A. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181969 · Cited by 283 · see citing works
Ambainis, A., Mosca, M., Tapp, A., & de Wolf, R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892142 · Cited by 218 · see citing works
On hiding information from an oracle
Abadi, M., Feigenbaum, J., & Kilian, J. (1989) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(89)90018-4 · Cited by 202 · see citing works
Danos, V., Kashefi, E., & Panangaden, P. (2007) · Journal of the ACM · doi:10.1145/1219092.1219096 · Cited by 195 · see citing works
Self-citationComputational Power of Correlations
Anders, J., & Browne, D. E. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.050502 · Cited by 176 · see citing works
Interactive Proofs For Quantum ComputationsPreprint
Aharonov, D., Ben-Or, M., Eban, E., & Mahadev, U. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0810.5375 · Cited by 167 · see citing works
Fault-tolerant quantum computation with cluster states
Nielsen, M. A., & Dawson, C. M. (2005) · Physical Review A · doi:10.1103/physreva.71.042323 · Cited by 161 · see citing works
Arrighi, P., & Salvail, L. (2006) · International Journal of Quantum Information · doi:10.1142/s0219749906002171 · Cited by 141 · see citing works
Determinism in the one-way model
Danos, V., & Kashefi, E. (2006) · Physical Review A · doi:10.1103/physreva.74.052310 · Cited by 140 · see citing works
Self-citationUnified derivations of measurement-based schemes for quantum computation
Childs, A. M., Leung, D., & Nielsen, M. A. (2005) · Physical Review A · doi:10.1103/physreva.71.032318 · Cited by 135 · see citing works
A polynomial quantum algorithm for approximating the Jones polynomial
Aharonov, D., Jones, V. F. R., & Landau, Z. A. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132579 · Cited by 135 · see citing works
Secure assisted quantum computation
Childs, A. M. (2005) · Quantum Information and Computation · doi:10.26421/qic5.6-4 · Cited by 134 · see citing works
An introduction to measurement based quantum computationPreprint
Jozsa, R. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0508124 · Cited by 124 · see citing works
Critical components for diamond-based quantum coherent devices
Greentree, A. D., Olivero, P., Draganski, M., Trajkov, E., Rabeau, J. R., Reichart, P., Gibson, B. C., Rubanov, S., Huntington, S. T., Jamieson, D. N., et al. (2006) · Journal of Physics Condensed Matter · doi:10.1088/0953-8984/18/21/s09 · Cited by 78 · see citing works
Simple proof of fault tolerance in the graph-state model
Aliferis, P., & Leung, D. (2006) · Physical Review A · doi:10.1103/physreva.73.032308 · Cited by 56 · see citing works
Feigenbaum, J. (2007) · Springer eBooks · doi:10.1007/3-540-39799-x_38 · Cited by 35 · see citing works
Fault-tolerant quantum computation with local gates
Gottesman, D. (2000) · Journal of Modern Optics · doi:10.1080/095003400148240 · Cited by 31 · see citing works
Browne, D. E., & Briegel, H. J. (2006) · Wiley eBooks · doi:10.1002/9783527618637.ch20 · Cited by 23 · see citing works
Transversality versus Universality for Additive Quantum CodesPreprint
Zeng, B., Cross, A. W., & Chuang, I. L. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0706.1382 · Cited by 10 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- [9][9] C. Bennett and G. Brassard, 'Quantum cryptography: Public-key distribution and coin tossing,' in Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing , 1984, pp. 175-179. -
- [20][20] A. Greentree, P. Olivero, M. Draganski, E. Trajkov, J. Rabeau, P. Reichart, B. Gibson, S. Rubanov, S. Huntington, D. Jamieson, and S. Prawer, 'Critical components for diamondbased quantum coherent devices,' J. Phys.-Condes. Matter , vol. 18, pp. 825-842, 2006. -
Cited by
Sorted by citations
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646 · see citing works
Deterministic delivery of remote entanglement on a quantum network
Humphreys, P. C., Kalb, N., Morits, J. P. J., Schouten, R. N., Vermeulen, R. F. L., Twitchen, D. J., Markham, M., & Hanson, R. (2018) · Nature · doi:10.1038/s41586-018-0200-5 · Cited by 546 · see citing works
Demonstration of Blind Quantum Computing
Barz, S., Kashefi, E., Broadbent, A., Fitzsimons, J. F., Zeilinger, A., & Walther, P. (2012) · Science · doi:10.1126/science.1214707 · Cited by 475 · see citing works
Self-citationApplications of single photons to quantum communication and computing
Couteau, C., Barz, S., Durt, T., Gerrits, T., Huwer, J., Prevedel, R., Rarity, J., Shields, A., & Weihs, G. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00583-2 · Cited by 216 · see citing works
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145 · see citing works
Experimental verification of multipartite entanglement in quantum networks
McCutcheon, W., Pappa, A., Bell, B. A., McMillan, A., Chailloux, A., Lawson, T., Mafu, M., Markham, D., Diamanti, E., Kerenidis, I., et al. (2016) · Nature Communications · doi:10.1038/ncomms13251 · Cited by 137 · see citing works
- Authors
- Broadbent, A., Fitzsimons, J., & Kashefi, E.
- Affiliations
- University of Waterloo (CA)
- University of Edinburgh (GB)
- Venue
- 2009 50th Annual IEEE Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2009-10
- Pages
- 517-526
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2117593045
- Cited by
- 521
- References
- 32
- Citations by year
- 2026: 38 · 2025: 70 · 2024: 74 · 2023: 59 · 2022: 48 · 2021: 48 · 2020: 32 · 2019: 36 · 2018: 27 · 2017: 24 · 2016: 27 · 2015: 13 · 2014: 8 · 2013: 2 · 2012: 10
- FWCI
- 3.05
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- arXiv (Cornell University) (publishedVersion)
- Edinburgh Research Explorer (University of Edinburgh) (submittedVersion, other-oa)
- arXiv (Cornell University)
- Funders
- Engineering and Physical Sciences Research Council (EP/E059600/1)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Keywords
- blind quantum computation, measurement-based quantum computation, authentication protocols, BQP, fault tolerance
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
